LeetCode.344.557.876.19(双指针)

344.反转字符串

class Solution {
  public:
    void reverseString(vector<char> &s) {
        for (int i = 0; i < s.size() / 2; i++) {
            char temp = s[i];
            s[i] = s[s.size() - 1 - i];
            s[s.size() - 1 - i] = temp;
        }
        // 477/477 cases passed (12 ms)
        // Your runtime beats 94.86 % of cpp submissions
        // Your memory usage beats 87.91 % of cpp submissions (22.5 MB)
        /*for (int i = 0, j = s.size() - 1; i < s.size() / 2; i++, j--) {
            s[i] ^= s[j];
            s[j] ^= s[i];
            s[i] ^= s[j];
        }*/
        // 477/477 cases passed (20 ms)
        // Your runtime beats 54.54 % of cpp submissions
        // Your memory usage beats 75.1 % of cpp submissions (22.5 MB)
        //*利用位运算实现swap，感觉效率也不是很高==
        //*^ 按位异或
        //*1 ^ 1 = 0 1 ^ 0 = 1 0 ^ 1 = 1 0 ^ 0 = 0
    }
};

557.反转字符串中的单词-iii

class Solution {
  public:
    string reverseWords(string s) {
        int i = 0, j = 0;
        for (; j < s.length(); j++) {
            if (s[j] == ' ') {
                for (int k = i; k < i + (j - i) / 2; k++) {
                    swap(s[k], s[j - 1 - k + i]);
                }
                i = j + 1;
            }
        }
        for (int k = i; k < i + (j - i) / 2; k++) {
            swap(s[k], s[j - 1 - k + i]);
        }
        return s;
        // 29/29 cases passed (8 ms)
        // Your runtime beats 92.23 % of cpp submissions
        // Your memory usage beats 98.21 % of cpp submissions (9.2 MB)
        //*调试了三次，成绩都很高感觉有点太简单了==
    }
};

876.链表的中间结点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
  public:
    ListNode *middleNode(ListNode *head) {
        /*ListNode *temp1 = head;
        ListNode *temp2 = head;
        int num = 0;
        while (temp1) {
            temp1 = temp1->next;
            num++;
            if (!(num % 2))
                temp2 = temp2->next;
        }
        return temp2;*/
        // 36/36 cases passed (0 ms)
        // Your runtime beats 100 % of cpp submissions
        // Your memory usage beats 85.58 % of cpp submissions (6.8 MB)
        //*参考快慢指针，链表的迭代也设置为快慢两个部分
        ListNode *temp1 = head;
        ListNode *temp2 = head;
        while (temp1 && temp1->next) {
            temp1 = temp1->next->next;
            temp2 = temp2->next;
        }
        return temp2;
        // 36/36 cases passed (0 ms)
        // Your runtime beats 100 % of cpp submissions
        // Your memory usage beats 86.9 % of cpp submissions (6.8 MB)
        //*连num都不用设置
    }
};

19.删除链表的倒数第-n-个结点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
  public:
    // int cur = 0;
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        if (head->next == nullptr)
            return nullptr;
        ListNode *temp = head;
        ListNode *ans = new ListNode(0, head);
        head = ans;
        while (temp) {
            temp = temp->next;
            if (!n)
                ans = ans->next;
            n = n > 0 ? n - 1 : 0;
        }
        ListNode *del = ans->next;
        ans->next = ans->next->next ? ans->next->next : nullptr;
        delete del;
        return head->next;
        // 208/208 cases passed (4 ms)
        // Your runtime beats 76.92 % of cpp submissions
        // Your memory usage beats 93.63 % of cpp submissions (10.3 MB)
        //*被特殊情况搞得心烦意乱，没想到最特殊的那个只要单独拎出来就好了==（双指针法）
        /*if (!head)
            return NULL;
        head->next = removeNthFromEnd(head->next, n);
        cur++;
        if (n == cur) {
            ListNode *next = head->next;//
            delete head;                //加上垃圾回收
            return next;
        }
        return head;*/
        // 208/208 cases passed (0 ms)
        // Your runtime beats 100 % of cpp submissions
        // Your memory usage beats 7.88 % of cpp submissions (10.5 MB)
        //我淦,递归法只要5行，缺点是没有垃圾回收，就算我加上了垃圾回收空间复杂度也没降下来，不知道为什么
    }
};