代码随想录前9日总结丨数组、链表、哈希表、字符串、双指针法

大纲

1. 回忆前9日做的题目，逐题给出思路，部分题目重写代码
2. 总结

回忆

数组

704. 二分查找 - 力扣（LeetCode）

思路：因为题给的数组已经有序，所以可以直接使用二分法查找，若target > nums[(left + right) \ 2]，则left = (left + right) \ 2 + 1，反之right = (left + right) \ 2 - 1，如果相等则返回答案

技巧：(left + right) \ 2可以表示为left + (right - left) \ 2，这样做可以防止溢出

27. 移除元素 - 力扣（LeetCode）

思路：使用快慢指针法，快指针用于探测，慢指针用于收集，如果快指针遇到的值是需要移除的target，直接忽略，否则将值赋给慢指针

代码实现

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int cnt = nums.size();
        int fast = 0;
        int slow = 0;
        while(fast < cnt) {
            if(nums[fast] != val) {
                nums[slow++] = nums[fast++];
            }
            else {
                fast++;
            }
        }
        return slow;
    }
};

977. 有序数组的平方 - 力扣（LeetCode）

思路：先遍历平方，然后用双指针法，从头尾开始比较，直到两指针相遇，哪个指针所指的值比较大，就将其加入至末尾，然后再移动指针，最后即可得到答案

209. 长度最小的子数组 - 力扣（LeetCode）

思路：使用滑动窗口，即两个快慢指针，快的指针控制窗口右端，负责使窗口内数据的总和大于target，慢的指针用于缩圈，负责使得窗口内数据的个数尽可能小，每次符合条件时都要记录此时窗口的长度，用一个变量来存储此时的最小长度，结束后返回即可

59. 螺旋矩阵 II - 力扣（LeetCode）

思路：一道模拟题，重点是把握区间，区间应该是左闭右开（如图所示）。重点是要把握圈数，圈数应该是n \ 2，同时中间位置也是n \ 2，或者也可以采用

int cnt = n * n;
while(cnt--) {
  // 功能代码
}

这样的方式来规定运行次数

但是要记住如果n为奇数，循环结束以后需要单独给最中间的值赋值

这里引用carl哥的图片

链表

203. 移除链表元素 - 力扣（LeetCode）

思路：定义一个虚拟头结点ListNode* dummyHead = head，然后遍历链表，每次遇到发现cur->next -> val == val，就执行移除操作cur->next = cur->next->next，最后返回dummyHead->next

707. 设计链表 - 力扣（LeetCode）

思路：按题目模拟即可，注意下列技巧，这种题目还是得自己写了才知道

技巧：使用头结点并且设置一个_size来记录链表的大小会方便很多，空指针建议使用nullptr而不`NULL，因为NULL具有二义性（既代表0又代表空指针），用nullptr比较准确

代码实现

class MyLinkedList {
public:
    struct Node {
        int val;
        Node* next;
        Node(): val(0), next(nullptr){}
        Node(int x): val(x), next(nullptr){}
        Node(int x, Node* next): val(x), next(next){}
    };
    MyLinkedList() {
        _size = 0;
        dummyHead =new Node(-1, nullptr);
    }

    int get(int index) {
        if(_size == 0 || index < 0 || index > _size -1) {
            return -1;
        }
        else {
            index;
            Node* cur = dummyHead->next;
            while(index--) {
                cur = cur->next;
            }
            return cur->val;
        }
    }

    void addAtHead(int val) {
        Node* new_Node = new Node(val,dummyHead->next);
        dummyHead->next = new_Node;
        _size++;
    }

    void addAtTail(int val) {
        Node* new_Node = new Node(val,nullptr);
        Node* cur = dummyHead;
        while(cur->next != nullptr) {
            cur = cur->next;
        }
        cur->next = new_Node;
        _size++;
    }

    void addAtIndex(int index, int val) {
        if(index == _size) {
            addAtTail(val);
        }
        else if(index > _size - 1) {
            return;
        }
        else if(index < 0){
            addAtHead(val);
        }
        else {
            Node* cur = dummyHead;
            while(index--) {
                cur = cur->next;
            }
            Node* new_Node = new Node(val, cur->next);
            cur -> next = new_Node;
            _size++;
        }
    }

    void deleteAtIndex(int index) {
        if(index > _size - 1 || index < 0) {
            return;
        }
        else {
            Node* cur = dummyHead;
            while(index--) {
                cur = cur->next;
            }
            cur->next = cur->next->next;
            _size--;
        }
    }
private: 
    int _size;
    Node* dummyHead;
};

206. 反转链表 - 力扣（LeetCode）

思路：设置三个指针,pre用来记录前一次的指针，cur用来表示现在的指针,tmp用来保存cur->next，因为如果不保存cur反转指向以后就会丢失cur->next，具体流程是tmp先保存cur->next，然后cur->next = pre，执行反转，接着再向下进行，把tmp赋值给cur，把cur赋值给pre

代码实现

//迭代方法
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr) {
            return nullptr;
        }
        else if(head->next == nullptr) {
            return head;
        }
        ListNode* cur = head;
        ListNode* pre = nullptr;
        ListNode* tmp = cur->next;
        while(cur) {
            tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};
//递归方法1，从前面往后逐渐反转
class Solution {
public:
    ListNode* reversel(ListNode* pre, ListNode*  cur) {
        if(cur == nullptr) {
            return pre;
        }
        ListNode* tmp = cur->next;
        cur->next = pre;
        return reversel(cur, tmp);
    }
    ListNode* reverseList(ListNode* head) {
        return reversel(nullptr, head);
    }
};
//递归方法2，从后向前逐渐反转
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 边缘条件判断
        if(head == NULL) return NULL;
        if (head->next == NULL) return head;

        // 递归调用，翻转第二个节点开始往后的链表
        ListNode *last = reverseList(head -> next);
        // 翻转头节点与第二个节点的指向
        head->next->next = head;
        // 此时的 head 节点为尾节点，next 需要指向 NULL
        head->next = NULL;
        return last;
    }
};

24. 两两交换链表中的节点 - 力扣（LeetCode）

思路：设置一个虚拟头结点，遍历链表，如果满足条件while(cur != nullptr && cur->next != nullptr && cur->next->next != nullptr)就进行两两交换即可

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

思路：使用双指针法，设置虚拟头结点，右边的指针先行n + 1步（为了让最后左边的指针停留在要删除的节点的前一个，这样好删除），然后左右两个指针同时行动，直到右边的指针走到末尾，此时即可进行删除操作left->next = left->next->next

面试题 02.07. 链表相交 - 力扣（LeetCode）

思路：先分别找出两个链表的长度，然后设置两个指针，快指针在长的链表上先行几步使得两个两个链表的剩余长度保持一致，然后两个指针同时遍历链表，如果指针所指的节点相同则返回结果

技巧：需要注意的是指针的值相同不同于指针相同，所以判断语句是slow == fast，而不是slow->val == fast->val

142. 环形链表 II - 力扣（LeetCode）

思路：这道题正规的做法是用数学方法证明，设置两个指针，快指针比慢指针每次多走一步，得出的结果是当这两个指针相遇，那么一定有环，此时再派遣一个指针从头出发，一个指针从相遇点出发，当新派出的两个指针相遇时，它们的相遇点就是环的入口。我当时没有想出怎么出环，直接走1e4(题目给的最大长度)步，如果还没结束就说明有环，我进入的那个点就是环入口，这样做速度就比较慢了，不过有时候想不出用数学方法证明就只能用这种方法。

这里引用carl哥的图片并且附上详细讲解的地址：代码随想录环形链表题解

哈希表

242. 有效的字母异位词 - 力扣（LeetCode）

思路：因为英文字母总共只有26个，所以可以直接用数组，先遍历t，每次遇到一个字母就将其在数组上的相应值加一，接着遍历s，每遇到一个字母就减一，最后遍历数组，如果全为0则返回true，否则返回false

349. 两个数组的交集 - 力扣（LeetCode）

思路：因为不能重复同时不需要排序，直接使用unordered_set来记录其中一个数组中所有的数值，接着遍历另外一个数组，如果这个数组中的值能在unordered_set中找到，那就加入结果集，最后返回结果集

202. 快乐数 - 力扣（LeetCode）

思路：每次都将处理后的结果存入unordered_set中，如果该结果已经其中出现过，说明陷入循环，执行return false，如果没有陷入循环最后肯定会变成1，执行return true

1. 两数之和 - 力扣（LeetCode）

思路：使用unordered_set，边循环边判断，如果在其中找到了target - 遍历到的值，那么就分别返回下标，否则将该值存入，然后返回答案

454. 四数相加 II - 力扣（LeetCode）

思路：取出其中两个数组，遍历这两个数组并且将其相加的结果和次数都存入unordered_map，接着遍历另外两个数组，如果target -这两个数组的和能在unordered_map中找到，那就添加次数到cnt(用来记录答案的)，最后返回cnt

383. 赎金信 - 力扣（LeetCode）

思路：和242. 有效的字母异位词 - 力扣（LeetCode）几乎一模一样，先遍历magazine，每次遇到一个字母就将其在数组上的相应值加一，接着遍历ransomNote，每遇到一个字母就减一，此时如果被减到小于0，则return false，如果循环成功结束，执行return true

15. 三数之和 - 力扣（LeetCode）

思路：使用双指针法，先给数组排序，然后遍历数组，每次遍历都先给第一个元素去重，去重条件是当该元素和前一位相等时continue，然后设置双指针，左指针从i + 1开始，右指针从nums.size() - 1开始，设置int sum = nums[left] + nums[right] + nums[i];，如果此时sum < 0，就执行right--，如果此时sum < 0，就执行left++，如果相等就记录下此时的坐标，这时候要进行一个去重，思路和去重第一个元素的时候类似，最后就可以得出答案。具体细节请看下面的代码

这题也可以使用哈希法，但是需要注意的点很多，而且哈希法运行速度比双指针慢很多，强烈建议使用双指针

代码实现

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int nsize = nums.size();
        vector<vector<int> > resultes;
        sort(nums.begin(), nums.begin() + nsize);
        if(nums[0] > 0 || nums[nsize - 1] < 0) {
            return resultes;
        }
        for(int i = 0;i < nsize - 2; ++i) {
            int left = i + 1;
            int right = nsize - 1;
            if(i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            while(left < right) {
                int sum = nums[left] + nums[right] + nums[i];
                if(sum < 0) {
                    left++;
                }
                else if(sum > 0) {
                    right--;
                }
                else {
                    resultes.push_back({nums[i], nums[left], nums[right]});
                    left++;
                    right--;
                    while(right < nsize - 1 && left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                    while(left > i + 1 && left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                }
            }
        }
        return resultes;
    }   
};

18. 四数之和 - 力扣（LeetCode）

思路：思路和三数之和几乎一致，只不过是用两层循环而已，外面直接套两层循环，里面用双指针，不过要注意的是这次题目给的target不再是固定值0，所以有些代码需要变动，还有题目给的数据可能会超过int的范围，所以求总和的时候应该用(long) or (long long)，具体直接看代码

//时间复杂度O(n3),空间复杂度O(1)
#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int nsize = nums.size();
        vector<vector<int>> results;
        for(int i = 0; i < nsize; ++i) {
            if(i > 0 && nums[i - 1] == nums[i]) {
                continue;
            }
            for(int j = i + 1; j < nsize; ++j) {
                if(j > i + 1 && nums[j - 1] == nums[j]) {
                    continue;
                }
                int left = j + 1;
                int right = nsize - 1;
                while(left < right) {
                    long long sum = (long long)nums[i] + (long long)nums[j] + (long long)nums[left] + (long long)nums[right];
                    if(sum < target) {
                        ++left;
                    }
                    else if(sum > target) {
                        --right;
                    }
                    else {
                        results.push_back(vector<int>{nums[i], nums[j], nums[left], nums[right]});
                        ++left;
                        --right;
                        while(left < right && left > j + 1 && nums[left] == nums[left - 1]) {
                            ++left;
                        }
                        while(left < right && right < nsize - 2 && nums[right] == nums[right + 1]) {
                            --right;
                        }
                    }
                }
            }
        }
        return results;
    }
};

字符串

344. 反转字符串 - 力扣（LeetCode）

思路：双指针法，头尾两个指针互相交换数据直至相遇

541. 反转字符串 II - 力扣（LeetCode）

思路：一道模拟题，按题目描述做就行了

技巧：循环步长可以设置为2 * k

剑指 Offer 05. 替换空格 - 力扣（LeetCode）

思路：双指针法，先遍历一遍数组，计下所有空格的数量，然后将数组扩容2 * 空格个数(因为要替换的字符串大小是3位)，然后再用双指针，一个慢指针在新数组的尾部，一个快指针在老数组尾部的位置，如果快指针遇到空格则给慢指针赋题目要求的%20，否则就正常赋值，走完一遍就全部替换完成了

151. 反转字符串中的单词 - 力扣（LeetCode）

思路：先用双指针法去掉字符串中多余的空格，具体方法是快指针遍历数组（或者直接for循环遍历，i当快指针）每次遇到单词都全部赋给慢指针，然后下一次遇到单词开头时给慢指针补一个空格，接着再继续遍历，结束遍历即去除完成。然后翻转整个字符串，接着再遍历一次字符串，如果遇到空格就翻转单词，还有在单词结尾的时候要记得把最后一个单词翻转，这样就完成了

剑指 Offer 58 - II. 左旋转字符串 - 力扣（LeetCode）

思路：先翻转要左旋部分的字符串，再翻转其他部分的字符串，最后翻转全部字符串即可

28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

思路：使用KMP，先构造next前缀表，然后遍历目标字符串，如果匹配上执行++j，j达到字符串长度 - 1则说明完全匹配，返回下标，如果匹配不上，则回退j，最后循环结束也没匹配上则返回-1，具体请看代码，详细解释可以看代码随想录详解KMP

class Solution {
public:
    void get_next(int* next, const string& s) {
            int j = -1;
            next[0] = j;
            int scnt = s.size();
            for(int i = 1; i < scnt; ++i) {
                while(j > -1 && s[j + 1] != s[i]) {
                    j = next[j];
                }
                if(s[j + 1] == s[i]) {
                    ++j;
                }
                next[i] = j;
            }
        }
    int strStr(string haystack, string needle) {
        int hcnt = haystack.size();
        int ncnt = needle.size();
        if(ncnt > hcnt) {
            return -1;
        }
        int next[ncnt];
        get_next(next, needle);
        int j = -1;
        for(int i = 0;i < haystack.size(); ++i) {
            while(j > -1 && needle[j + 1] != haystack[i]) {
                j = next[j];
            }
            if(needle[j + 1] == haystack[i]) {
                j++;
                if(j == ncnt - 1) {
                    return i - ncnt + 1;
                }
            }
        }
        return -1;
    }
};

459. 重复的子字符串 - 力扣（LeetCode）

思路：大体上两种思路，一种是找最小子串，一种是把两个重复的字符串s拼接起来，如果字符串s是重复的，那么在中间必定能拼成一个新的s，采用这种方法时为了避免干扰应该将新拼接成的字符串头尾抹去。找最小子串的话是用KMP,字符串长度 - 最大相同前后缀得出的就是最小子串，如果是重复的字符串那么必定由该子串构成且字符串长度除以该子串长度为0。详解请看代码随想录459.重复的子字符串解法

总结

​ 所有题目过下来，给我印象最深刻的就是双指针法，很多涉及到字符串或者找到某个最佳的值的时候都可以用双指针法，能够将复杂度降低还能使题目思路清晰。最典型的就是归类在哈希表里面的15. 三数之和 - 力扣（LeetCode）与18. 四数之和 - 力扣（LeetCode），用哈希表写反而相当复杂并且时间复杂度要比双指针法慢很多。在有序数组中找某一个数字的时候可以考虑采用二分法，或者用空间换时间，哈希法，木桶法都可以。在做链表题目的时候，最好设置一个虚拟头节点，这样操作会方便很多，而有些更复杂的题目例如设计链表这些涉及到很多链表操作的时候，可以设置一个值来记录链表的长度，这样可以提前判断很多非法的输入，也方便代码的书写，同时要注意链表中最好使用nullptr来代表空指针。哈希表主要在想要快速找到某一个值存不存在或者想要去重的时候可以使用到，用得好可以大大降低复杂度。字符串的问题要多往双指针的方向思考，还有做一些简单的字符串题目的时候不要贪恋库函数，能自己实现的尽量自己实现，除非与解题关系不大或者库函数本身的实现你已经非常熟络了。对于算法的学习，我才刚刚开始，但我会坚持每隔一段时间做一个总结，每次完成题目也会尽量从多种角度去思考，尽量采取多种解法，请诸君共勉!