移除元素

27. 移除元素 - 力扣（LeetCode） (leetcode-cn.com)

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

• 不要使用额外的数组空间，$O(1) $额外空间
• 元素的顺序可以改变。
• 你不需要考虑数组中超出新长度后面的元素。

思路：快慢指针即可做

参考之前题目的移除元素写出解答：

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
            if (val != nums[fastIndex]) {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;
    }
};

细心的张同学发现这里还学到了python装饰器@classmethod的使用，

反转字符串

344. 反转字符串 - 力扣（LeetCode） (leetcode-cn.com)

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

老题目了

void reverseString(vector& s) {
        for(int i=0,j=s.size()-1;i


剑指Offer 05.替换空格
剑指 Offer 05. 替换空格 - 力扣（LeetCode） (leetcode-cn.com)
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
思路：统计空格个数。重新设置长度，从后往前原地修改字符串，复杂度$O(n)$

class Solution {
public:
    string replaceSpace(string s) {
        int count=0;
        int oldSize = s.size();
        for(int i=0;i){
            if(s[i]==' '){
                count++;
            }
        }
        //重新修改大小
        s.resize(s.size()+2*count);
        //从后向前修改-双指针
        int newSize = s.size();
        for(int i=oldSize-1,j=newSize-1;i){
            if(s[i]!=' '){
                s[j]=s[i];
            }else{
                s[j]='0';
                s[j-1]='2';
                s[j-2]='%';
                j-=2;
            }
        }
        return s;
    }
};

翻转字符串里的单词
151. 翻转字符串里的单词 - 力扣（LeetCode） (leetcode-cn.com)
这道题在字符串里做过，思路：去除多余空格，反转整个字符串，反转每个单词中的所有字符
去除多余空格函数里，只有遇到不是空格，才用

s[slowIndex]=s[fastIndex]


　　存下来。

class Solution {
public:
    void removeExtraSpaces(string& s) {
        int slowIndex = 0, fastIndex = 0; // 定义快指针，慢指针
        // 去掉字符串前面的空格
        while (s.size() > 0 && fastIndex < s.size() && s[fastIndex] == ' ') {
            fastIndex++;
        }
        for (; fastIndex < s.size(); fastIndex++) {
            // 去掉字符串中间部分的冗余空格
            if (fastIndex - 1 > 0
                    && s[fastIndex - 1] == s[fastIndex]
                    && s[fastIndex] == ' ') {
                continue;
            } else {
                s[slowIndex++] = s[fastIndex];
            }
        }
        if (slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') { // 去掉字符串末尾的空格
            s.resize(slowIndex - 1);
        } else {
            s.resize(slowIndex); // 重新设置字符串大小
        }
    }

    // 反转字符串s中左闭又闭的区间[start, end]
    void reverse(string& s, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }


    string reverseWords(string s) {
        removeExtraSpaces(s);
        //反转字符串
        reverse(s,0,s.size()-1);
        //反转每个单词，判断空格位置
        for(int i=0;i){
            int j=i;
            while(j' ') j++;
            reverse(s,i,j-1);
            //更新要反转的单词开始位置
            i = j;
        }
        return s;

    }

};

反转链表
206. 反转链表 - 力扣（LeetCode） (leetcode-cn.com)
题意：反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
思路，双指针or递归法，参考： and 
双指针解法：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        //节点的值不变，只是改变next的指向
        ListNode* pre = nullptr;
        ListNode* cur = head;
        ListNode* temp = new ListNode();
        while(cur){
            temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

删除链表的倒数第N个节点
19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode） (leetcode-cn.com)
给一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：使用一趟扫描实现 $O(n)$算法。
使用快慢指针，如果要删除的节点在中间，当快指针指向结尾的null时候，慢指针与快指针相隔n+1个节点，把慢指针slow->next删除即可
使用虚拟头节点+双指针方法：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* fast = dummyHead;
        ListNode* slow = dummyHead;
        while(n-- && fast != nullptr){
            fast = fast->next;
        }
        fast = fast->next;
        while(fast != nullptr){
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;
        return dummyHead->next;
    }
};

链表相交
面试题 02.07. 链表相交 - 力扣（LeetCode） (leetcode-cn.com)
思路：如果两个人在部分or全部相交的跑道，速度不一样，那么他们一定会在相交的跑道上相遇：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* A = headA, * B = headB;
        while (A != B) {//当没有相遇时候，会得到A->null == null<-B
            A = A != nullptr ? A->next : headB;
            B = B != nullptr ? B->next : headA;
        }
        return A;
    }
};

环形链表II
142. 环形链表 II - 力扣（LeetCode） (leetcode-cn.com)
给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
不允许修改 链表。
思路：快慢指针，快指针走两步，慢指针走一步，并且一定会在慢指针进入第一圈环内相遇：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow){
                //如果相遇了  从head到相遇点之间，查找那个严格意义上的入口节点
                ListNode* node1 = fast;
                ListNode* node2 = head;
                while(node1 != node2){
                    node1 = node1->next;
                    node2 = node2->next;
                }
                return node1;
            }
        }

        
        return NULL;
    }
};

为什么相遇之后，执行下面的代码就会走到环的入口？

//如果相遇了  从head到相遇点之间，查找那个严格意义上的入口节点
                ListNode* node1 = fast;
                ListNode* node2 = head;
                while(node1 != node2){
                    node1 = node1->next;
                    node2 = node2->next;
                }
                return node1;
    


　x+y = n(z+y)
如果快指针只是转了一圈，n=1，那么 x=z，相遇点就是入口节点
如果快指针转了不止一圈，n>1，那么 x=nz+(n-1)y = (n-1)(z+y) + z，设置nodel1和nodel2之后，可能??相遇节点就不是第一个入口节点了，但是他还是入口节点
三数之和 and 四数之和
15. 三数之和 - 力扣（LeetCode） (leetcode-cn.com)
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组
18. 四数之和 - 力扣（LeetCode） (leetcode-cn.com)
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）
思路：hash表不是很好去重，选择双指针方法去重，参考：