[toc]

tags：【双指针】，【前缀和】，【原地哈希】

【好题】，【不会】，【重要】，【继续看】

方法

双指针

前后定长双指针

前后快慢双指针

左右双向双指针

  • 611.有效三角形的个数
    • 方法一：二重循环a、b，对c进行二分查找（查找最后一个满足a+b<c的c）
    • 方法二：遍历c，左右双指针表示a(nums[i])和b(nums[j])，参考
      • if(nums[i] + nums[j] > c) ，此时有j-i个三角形，j向左走（i向右走无用）
      • if(nums[i] + nums[j] <= c) ，此时有0个三角形，i向右走（j向左走无用）
  • 11.盛最多水的容器：盛水体积只取决于左右两隔板的高度（木桶理论）
    • 区别于接雨水，雨水可能分布在不连续的凹陷处

两分支双指针

滑动窗口

  • 904. 水果成篮

    • 基于双指针的滑动窗口
    • 必须使用滑动窗口保证水果是连续的，如果只使用哈希表，则可能出现中间有中断的情况

  • 76. 最小覆盖子串：代码

    • 对t统计词频，得到相同的两个ump：tump和tmp_ump
    • 只移动右指针，找到s中第一个包含t的区间
      • 移动右指针的过程中，逐步递减并erasetmp_ump中的元素，直到tmp_ump为空，此时就找到了s中第一个包含t的区间，同时维护区间的词频win_ump
    • 窗口进行移动：将c=s[left++]从win_ump中减一，同时左指针向右移动了一位，
      • 如果此时win_ump[c] >= tump[c]，说明c不在t中，或者c是t中是多余重复的，因此continue
      • 如果此时win_ump[c] < tump[c]，说明c是t中的，需要右指针向右移动，再次找到c字符，因此得到了新的窗口
      • 技巧：可以s+=' '，避免最后跳出循环还要移动左指针，

  • 3.无重复字符的最长子串 【重要】

    • 同最长无重复子数组，都是用左右双指针作为滑动窗口，同时数组做哈希用于判断是否用过该元素

  • 1004.最大连续1的个数Ⅲ

    • 两种思路
      • 复杂的代码：维护窗口内0的数量，但同时也分情况讨论左右断点的情况
      • 简洁的代码：找出一个最长的子数组，该子数组中最多有k个0，因此只需要维护窗口内0的数量即可

数组【二刷】

模拟题

  • 498.对角线遍历：i+j==level

  • 48.旋转图像

    • 最重要的是找到原来(i,j)位置的元素，旋转之后在什么位置（(j,n-i-1)）
    • 矩阵变换的方法也是从上面的对应关系来的
      • 先转置(j,i)，再水平翻转(j,n-i-1)
      • 或者先垂直翻转(n-i-1,j)，再转置(j,n-i-1)

  • 54.螺旋矩阵 和 59. 螺旋矩阵 II

    • 按圈遍历，设定四个逐步减小的边界
    • 每圈遍历中，判断新到达的位置是否超出边界，若是则改变方向

(二分)查找

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

// 假设v非递减
int find_first_ge(vector<int>& v, int target) { // 返回第一个>=target的元素的索引（lower_bound）
    int left = 0, right = v.size(), mid = -1;
    while(left < right){
        mid = left + (right - left) / 2;
        if(v[mid] > target) right = mid; // target is in left part
        else if(v[mid] < target) left = mid + 1; // target is in right part
        else right = mid; // v[mid] == target, 
    }
    return left; // now left == right
}
int find_first_gt(vector<int>& v, int target) { // 返回第一个>target的元素的索引（upper_bound）
    int left = 0, right = v.size(), mid = -1;
    while(left < right){
        mid = left + (right - left) / 2;
        if(v[mid] > target) right = mid;
        else if(v[mid] < target) left = mid + 1;
        else left = mid + 1; // difference
    }
    return left;
}
int find_last_le(vector<int>& v, int target) { // 返回最后一个<=target的元素的索引
    return find_first_gt(v, target) - 1; // 即第一个>target的元素的前一个位置
}
int find_last_lt(vector<int>& v, int target) { // 返回最后一个<target的元素的索引
    return find_first_ge(v, target) - 1; // 即第一个>=target的元素的前一个位置
}
  • 240.搜索二维矩阵Ⅱ
    • 方法一：从右上开始，按照搜索二叉树的逻辑查找
    • 方法二：每行进行一次二分查找
  • 162.寻找峰值 【继续看】
    • 方法一：分治，类似归并排序，递归找最大值
    • 方法二：类似二分查找，判断nums[mid]与nums[mid+1]的大小关系（即判断中点是上坡还是下坡），从而修改左右索引
      • 原理是因为开始时left和right都是最小值，此后mid部分永远是高点
      • 细节：在函数体中，left与right不相等，因此mid永远不会等于right，同时left与right是左闭右闭，代码
  • 搜索旋转排序数组系列：是否有重复数字，如果有重复数组，首先移动左右端点，保证left和right指向的元素不同。多使用原语表示（比如find_first_gt、find_first_ge）

排序

  • 快排：在partition时，如果选left作为pivot，则需要先移动右边的指针，原理

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

    void qSort(vector<int>& nums, int left, int right){ // [left, right]
    if(left >= right) return ;
    if(left+1 == right){
        if(nums[left] <= nums[right]) return ;
        else {swap(nums[left], nums[right]); return ;}
    }

    // 左中右，取中间大小的值，放在最左边
    int begin = left, end = right, mid = (left + right) / 2;
    int pivot = max(min(nums[left], nums[right]), nums[mid]);
    if(nums[right] == pivot) swap(nums[left], nums[right]);
    else if(nums[mid] == pivot) swap(nums[left], nums[mid]);

    // 注意元素是覆盖的
    while(left < right){
        while(left < right && nums[right] >= pivot) --right;
        nums[left] = nums[right];
        while(left < right && nums[left] <= pivot) ++left;
        nums[right] = nums[left];
    } // now: left == right
    nums[left] = pivot;

    // 缩小中轴范围，尤其针对重复元素多的数组
    while(left > begin && nums[left] == nums[left-1]) --left;
    while(right < end && nums[right] == nums[right+1]) ++right;

    qSort(nums, begin, left-1);
    qSort(nums, right+1, end);
}

  • 归并排序

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

    // 归并排序需要辅助数组，因为前后两个有序数组是连着的，
void mergeSort(vector<int>& out, int begin, int end, vector<int>& in){ // [begin, end)
    if(begin >= end || begin+1 == end) return ;
    int mid = (begin + end) / 2;
    mergeSort(out, begin, mid, in); // [begin, mid)
    mergeSort(out, mid, end, in); // [mid, end)

    // now left part and right part are all sorted, merge them into out
    int i = begin, j = mid, k = begin;
    while(i < mid && j < end){
        if(in[i] <= in[j]) out[k++] = in[i++]; // stable
        else out[k++] = in[j++];
    }
    while(i < mid) out[k++] = in[i++];
    while(j < end) out[k++] = in[j++];

    // copy out back to in
    for(int s = begin; s < end; ++s) in[s] = out[s];
}
    • BM20 数组中的逆序对： 归并方式，前后两段数据都是有序数组，比如前面一段数组中nums[a]大于后面一段数组中nums[b]，则前面数组中[a:mid)这一段元素都大于nums[b]，这些都是逆序对，只需在归并时统计这样的长度即可。代码

  • 堆排序

    • 第一种方法：数组原地构建最大堆，数组原地进行排序

       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

      void heapSort(vector<int>& nums){
    buildMaxHeap(nums);
    int len = nums.size();
    for(int i = len-1; i >0; --i){
        swap(nums[0], nums[i]); // 将最大堆的首元素（最大元素）放在数组后面位置
        adjust(nums, 0, --len); // 首元素变了，因此需要调整，同时堆的长度减一
    }
}

void buildMaxHeap(vector<int>& nums){
    int n = nums.size();
    for(int i = n/2-1; i >= 0; --i){ // n/2-1是最后一个非叶节点，依次向上检测和调整每个非叶节点
        adjust(nums, i, n);
    }
}    

void adjust(vector<int>& nums, int idx, int len) { // 当前节点的索引为idx，在[0, len)范围内是最大堆
    while(idx * 2 + 1 < len){
        int leftSon = idx * 2 + 1;
        int rightSon = idx * 2 + 2;
        int largeIdx = idx; // largeIdx指向{根节点，左孩子，右孩子}中较大的值
        if(leftSon < len && nums[leftSon] > nums[idx]) largeIdx = leftSon;
        if(rightSon < len && nums[rightSon] > nums[largeIdx]) largeIdx = rightSon;
        if(largeIdx != idx){
            swap(nums[idx], nums[largeIdx]);
            idx = largeIdx;
        }else break;
    }
}

    • 第二种方法：数组构建最小堆，依次弹出

       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

      // 手写堆
class minHeap{
private:
    vector<int> heap;
    int len = -1;
public:
    minHeap(vector<int>& nums): heap(nums) { 
        len = heap.size();
        // build minHeap
        for(int i = n/2-1; i >= 0; --i) adjust(i); 
    }
    void adjust(int idx){
        while(idx * 2 + 1 < len){
            int leftSon = idx * 2 + 1;
            int rightSon = idx * 2 + 2;
            int largeIdx = idx; // largeIdx指向{根节点，左孩子，右孩子}中较大的值
            if(leftSon < len && heap[leftSon] > heap[idx]) largeIdx = leftSon;
            if(rightSon < len && heap[rightSon] > heap[largeIdx]) largeIdx = rightSon;
            if(largeIdx != idx){
                swap(heap[idx], heap[largeIdx]);
                idx = largeIdx;
            }else break;
        }        
    }
    int top() { return heap[0];} // return min value
    void pop() {
        swap(heap[0], heap[--len]);
        adjust(0);
    }
};

// 或者调用优先队列
vector<int> heapSort(vector<int>& nums){
    priority_queue<int, vector<int>, greater<int>> pq;
    for(int n: nums) pq.push(n);
    vector<int> ans;
    while(!pq.empty()) {ans.push_back(pq.top()); pq.pop();}
    return ans;
}

  • 179.最大数

    • 巧妙的自定义排序规则：a+b<b+a

  • 215.数组中的第k个最大元素 【重要】

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

    int findKthLargest(vector<int>& nums, int begin, int end, int k){ // [begin, end), 快排逻辑
    if(begin+1 == end) return nums[begin];
    if(begin+2 == end){
        if(k == begin) return max(nums[begin], nums[begin+1]);
        if(k == begin+1) return min(nums[begin], nums[begin+1]);
    }

    int left = begin, right = end-1; // [left, right]
    int pivot = nums[left];

    while(left < right){
        while(left < right && nums[right] <= pivot) --right;
        nums[left] = nums[right];
        while(left < right && nums[left] >= pivot) ++left;
        nums[right] = nums[left];
    }
    int mid = left; // now left == right        
    nums[mid] = pivot;

    if(k-1 == mid) return pivot;
    else if(k-1 < mid){
        while(mid > k-1 && nums[mid] == nums[mid-1]) --mid;
        return findKthLargest(nums, begin, mid+1, k); // 注意这里还是传入[begin, mid+1)而非[begin, mid)，因为经过while优化，此时mid可以退到和begin位置相同
    }
    else{ // k-1 > mid
        while(mid < k-1 && nums[mid] == nums[mid+1]) ++mid;
        return findKthLargest(nums, mid, end, k); // 注意这里还是传入[mid, end)而非[mid+1, end)
    }
}

  • 剑指40.最小k个数：快排逻辑

套路题

  • 14.最长公共前缀
    • 按行比，按列比，都行
  • 209.长度最小的子数组
    • 方法一：贪心+双指针
    • 方法二：前缀和+二分
      • 细节较多：前缀和是inclusive的还是exculsive的（这里用的是exculsive的），二分找的是第一个大于val的位置
  • 剑指21.调整数组顺序使奇数位于偶数前面
    • 如果不需要保持奇数/偶数内部的相对顺序，左右双指针向内走
  • 169.多数元素
    • 投票法：维护一个元素值value和计数值cnt，数组元素等于value时累加cnt，不等于value时递减cnt，当cnt==0时更新value
    • 可以保证最后众数的cnt至少为1
  • 128.最长连续序列
    • 哈希表unordered_map<int, bool>（bool表示是否使用过该数字），元素往前往后分别试探
  • 31.下一个排列 ： 题解 与556.下一个更大元素Ⅲ相同
    • 从后往前遍历，找到一个最长的后缀，这个后缀是逆序的（即该后缀从前往后看递减，从后往前看递增）
    • 该最长后缀前面一个元素nums[idx]，是小于最长后缀的第一个元素的
    • 在该最长后缀中，找到最后一个>nums[idx]的元素nums[pos]，然后交换（因此最长后缀又变长了一位）
    • 最后reverse[idx+1, end)，因此数组前面部分不动，后面部分得到了下一个排列

综合

  • 560.和为K的子数组：【前缀和】+【哈希表】
    • 通过前缀和可以将区间和转换为两个点的查询
    • 通过哈希表记录遍历过的位置的前缀和（value是特定前缀和的计数）
    • 现在已知一个点和中间差值，通过哈希找到另一个点
    • 区别209.长度最小的子数组

字符串

模拟

套路

链表【二刷】

  • 206. 反转链表

    • 注意递归写法

      1
2
3
4
5
6
7

      ListNode* reverseList(ListNode* head) { // 递归，返回反转链表的头
    if(head==nullptr || head->next==nullptr) return head; // 当前是空节点，或者是最后一个节点    
    ListNode* newHead = reverseList(head->next); // 已经将head->next部分的链表处理完毕
    head->next->next  = head; 
    head->next = nullptr;
    return newHead;
}

    • 迭代写法1：遍历，修改相邻节点的指针指向

    • 迭代写法2：创建虚拟头节点，进行头插法（遍历链表，插入到虚拟头节点之后）

  • 142. 环形链表 II 【好题】

  • 148.排序链表

    • 递归方法：（自顶向下的）归并排序，时间复杂度O(n logn)，空间复杂度O(logn)
    • 迭代方法：自底向上的归并排序，时间复杂度O(n logn)，空间复杂度O(1)

  • 143.重排链表 【好题】

    • 先快慢指针寻找中点，然后后半段链表原地反转，最后两个链表合并

  • 23.合并K个升序链表

    • 最小堆：priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq;

    • 归并：

       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

      ListNode* mergeKLists(vector<ListNode*>& lists){
    return merge(lists, 0, lists.size()-1);
}

ListNode* merge(vector<listNode*> & lists, int l, int r){ //[left, right]
    if(l == r) return lists[l];
    if(l > r) return nullptr;
    int mid = (l + r) / 2;
    return mergetTwoLists(merge(lists, l, mid), merge(lists, mid+1, r));
}

ListNode* mergeTwoLists(ListNode* a, ListNode* b) {/*两个链表合并*/}

  • 445.两数相加Ⅱ

    • 一种方法是反转链表，另一种是使用栈进行计算

  • LRU缓存 【好题】代码

    • 数据结构：双向链表维护最近更新的节点，unordered_map<int,Node*>实现从key到链表中节点的映射

    • 设置dummyHead与dummyTail，可以避免专门判断head与tail是否为空（因为是双向链表，所以要设置头尾两个dummyNode）

    • 在Node中需要同时包含key和value，因为当删除某个node时，需要知道其对应的key，从而删除哈希表中对应的表项

    • 在向链表插入节点或是从链表中删除节点时，不要忘记更新map

  • LFU缓存 【好题】

    • 方法一：map记录key到Node的映射，使用平衡二叉树保存Node的结构
    • 方法二：双哈希表

递归

递归写法代码量一般比较少，也比较优雅，尤其在没有头节点的情况下避免对头节点另外判断

单链表的排序：归并排序

哈希表【二刷】

  • 有时可以直接使用数组进行哈希，有时需要使用map（unordered_map）或set（unordered_set）进行哈希，注意如果键无法进行哈希，则无法使用unordered_map或unordered_set（比如vector容器就没有hash方法，不能作为unordered_map或unordered_set的键）

  • 202.快乐数：使用哈希表空间复杂度为O(n)，将其视为快慢指针此时空间复杂度为O(1)

  • n数之和系列：给定n数之和

    • 给定一个数组，要求返回其中一个元组下标：哈希

    • 给定一个数组，要求返回所有元组下标：先排序，外层遍历，内层左右指针向中移动，根据当前三数之和确定左指针还是右指针移动，同时注意跳过相同的数字

    • 给定多个数组，要求返回元组的个数：哈希

  • 【原地哈希】

    • 例题：LCR 120.寻找文件副本：可能有多个重复数字，返回任意其一

      • 调整数组为nums[i]==i，如果将i写入到nums[i]时发现原来已经nums[i]==i，说明i就是重复数字
      • 方法：通过交换实现调整

    • 442.数组中重复的数据：数字出现1或2次，返回所有出现两次的数字

    • 287.寻找重复数：只有一个重复数，返回之；但是不能修改原数组

      • Floyd判圈

    • 268.丢失的数字：只有一个缺失的数字，返回之

    • 41.缺失的第一个正数 ：首先要判断数字是否在[0,n]的范围内

      • 方法一：标记

         1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

        int minNumberDisappeared(vector<int>& nums) {
    // write code here
    if(nums.size() == 0) return 1;

    nums.push_back(0);
    for(int& n: nums){
        if(n < 0) n = INT_MAX-1; // 将数组中的元素都转换为正数
    }

    for(int i = 0; i < nums.size(); ++i){
        int j = abs(nums[i]);
        if(j < nums.size()){ // 如果位置j在数组内
            nums[j] = -abs(nums[j]); // 将位置j的数值标记为负
        }
    }

    for(int i = 1; i < nums.size(); ++i){ 
        if(nums[i] > 0) return i; // 找一个没有标记过的位置
    }
    return nums.size();
}

      • 方法二：交换

         1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

        int minNumberDisappeared(vector<int>& nums) {
    // write code here
    if(nums.size() == 0) return 1;

    nums.push_back(0);
    for(int i = 0; i < nums.size(); ++i){
        while(nums[i] >= 0 && nums[i] < nums.size() && nums[i] != nums[nums[i]])
            swap(nums[i], nums[nums[i]]);
    }

    for(int i = 1; i < nums.size(); ++i){
        if(nums[i] != i) return i;
    }
    return nums.size();
}

    • 总结：虽然原地哈希的核心部分都是判断当前位置j的元素j=nums[i]为索引时，是否已经写入j?=nums[j]，但是中间很多细节略微不同

  • 974.和可被K整除的子数组：前缀和+哈希表

    • 前缀和实际上是前缀和的取模，使用哈希表记录模和其计数

  • 12.整数转罗马数字

    • 哈希表记录数字到字符串的映射，注意使用map<int, string, greater<int>>将key从大到小排列

栈与队列【二刷】

  • 用栈模拟队列：一个输入栈，一个输出栈
  • 用队列模拟栈：只需要一个队列，将元素进行循环弹入弹出
  • 优先队列
    • 注意优先队列如何自定义比较顺序

栈

  • 基本计算器Ⅱ：遇到加减法入栈（即栈内都进行加法运算），有两种不太相同的写法：比如a+b*c

    • 方法一：暂存数字。比如解析+时，暂存的是数字a，此时可以入栈；比如解析*时，暂存的是数字b（运算符前面的数字），此时先不能入栈，需要继续向后解析完c之后，更新暂存的数字

    • 方法二：暂存数字前的运算符，更简洁。比如解析b时，当前暂存的运算符是+（数字前面的运算符），因此遇到新的运算符*时，根据需要出栈入栈

      • 技巧：将a+b*c处理成a+b*c+0，且开始时暂存的运算符是+

    • 但是当表达式中含有括号时，可以递归，但是此时不太好在递归函数传入的表达式参数后面+0，具体代码如下：

       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

          int solve(string s) {
        return func(s, 0).first;
    }

    pair<int, int> func(string& s, int idx){
        // s += "+0"; // 本来想在表达式末尾加上0，但是因为使用的使用，所以无法使用
        stack<int> numSt;
        int num = 0; // 相当于在表达式前面加上 0+
        char preSymbol = '+';

        for(; idx < s.size(); ++idx){
            // cout << idx << " " << num << endl;
            if(s[idx] >= '0' && s[idx] <= '9') num = num * 10 + (s[idx] - '0');
            else if(s[idx] == '('){
                pair<int, int> p = func(s, idx+1);
                num = p.first;
                idx = p.second;
            }
            else if(s[idx] == ')') break;
            else{
                // 此时这几个变量的顺序: numSt.top() preSymbol num s[idx]
                if(preSymbol == '+') numSt.push(num);
                else if(preSymbol == '-') numSt.push(-num);
                else if(preSymbol == '*') {
                    int tmp = numSt.top(); numSt.pop();
                    numSt.push(tmp * num);
                }
                preSymbol = s[idx];
                num = 0;
            }
        }

        if(preSymbol == '+') numSt.push(num);
        else if(preSymbol == '-') numSt.push(-num);
        else if(preSymbol == '*') {
            int tmp = numSt.top(); numSt.pop();
            numSt.push(tmp * num);
        }

        int ans = 0;
        while(!numSt.empty()){
            ans += numSt.top();
            numSt.pop();
        }
        return make_pair(ans, idx);
    }
};

  • 394.字符串解码：【重要】

    • 方法一：【双栈】写法，数字栈与string栈
      • 字符串出栈时，每个元素需要先reverse，连起来字符串之后要再次reverse（因为出栈是逆序的，每个元素内部有时顺序的）
      • 数字栈使用stack<int>，string栈使用deque<string>进行模拟，方便最后进行出栈
    • 方法二：递归写法
      • 全局的索引idx，函数传参string和重复数量cnt
      • 如果遇到[，则进入递归；如果遇到]，则退出递归
      • 递归就是顺着累加字符串，不需要reverse

  • 678.有效的括号字符串：

    • 方法一：【双栈】
      • 括号一个栈st，星号一个栈star_st，栈内存放下标
      • 括号按照传统方法出入栈，星号直接入星号栈
      • 在遍历完成之后，括号栈依次出栈，
        • 如果当前是(，需要保证star_st.top()大于(的下标
        • 如果当前是)，需要保证star_st.top()小于)的下标（极其注意需要当前star_st.top()可能大于)的下标，需要while依次出栈，与上面逻辑不同）
    • 方法二：贪心
      • 维护未匹配的(的数量可能的最大值和最小值，遇到星号时，最小值减一，最大值加一
        • 如果最大值<0，则字符串无效
      • 遍历完成后，只有最小值=0时，字符串才可能有效

  • 最小栈 参考

    • 方法一：【双栈】
      • 一个普通栈，一个最小栈（用来记录最小值）
      • 如果当前元素==minStack.top()，也要push/pop最小栈
    • 方法二：使用一个栈，并维护当前最小值minVal
      • 入栈：如果当前元素<=minVal，则先将minVal入栈，然后再将当前元素入栈，同时更新minVal的值；否则直接入栈
      • 技巧：minVal初始值设定为最大值
    • 方法三：使用一个栈
      • 每次入栈元素为当前元素-minVal -> st.top()，如果结果是负数，说明minVal需要更新minVal=当前元素
      • 每次出栈或top，如果栈顶元素是正数，则原来的元素=minVal+st.top()；如果栈顶元素是负数，则说明当前minVal经过更新变得更小，原来的元素=minVal，复原原来的minVal=原来的元素(即旧的minVal)-st.top()

单调队列

  • 239. 滑动窗口最大值

    • 方法一：大根堆，维护一个大根堆，里面存放数组索引，但是比较方法是按照对应元素大小进行比较，出队列时肯定是当前最大元素，而且可以判断该元素是否在窗口范围内

      • 最坏情况如果是一个递增序列，每次push都是log(i)的复杂度，总的复杂度为sum(log(i))=O(n log(n))

    • 方法二：单调队列，维护一个递减的deque，里面存放数组索引，从后面pop_back可以比较当前元素与队尾元素，保持队列递增；从前面pop_front可以保持元素位于窗口范围内

      • 最坏情况是O(n)
       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

      vector<int> maxInWindows(vector<int>& num, int size) {
    // write code here
    int len = num.size();
    vector<int> v; 
    if(size > len || size == 0) return v;
    if(size == 1) return num;

    deque<int> dq; // 滑动窗口，里面存放数组下标，对应的数组元素递减（队首元素对应数组元素最大）
    for(int idx = 0; idx < size - 1; ++idx){ // 注意遍历到滑动窗口大小-1的位置
        while(!dq.empty() && num[dq.back()] <= num[idx]) dq.pop_back();
        dq.push_back(idx);
    }

    // 每次遍历idx，对应的都是滑动窗口的末尾
    for(int left = 0, idx = size-1; idx < len; ++idx, ++left){ 
        while(!dq.empty() && dq.front() < left) dq.pop_front(); // dq前面元素不在滑窗内了
        while(!dq.empty() && num[dq.back()] <= num[idx]) dq.pop_back(); // dq后面新加的元素更大
        dq.push_back(idx);
        v.push_back(num[dq.front()]);
    }
    return v;
}

单调栈

  • 739. 每日温度：从左往右，找到第一个比当前元素大的元素

  • 单调递增栈（从栈顶到栈底递增，栈顶元素为已经遍历过部分的最小值），如果当前元素nums[i]大于栈顶元素nums[top]，则从左往右nums[top]第一个比它大的元素是nums[i]

  • 496. 下一个更大元素 I：单调栈+哈希表

  • 503. 下一个更大元素 II：朴素想法是将循环数组展开，但是可以相同的单调栈代码跑两遍（第二遍继续使用第一遍剩下的单调栈）

  • 42. 接雨水 【重要】

  • 方法一：单调栈，从栈顶到栈底递增（反映到柱子上就是往下的台阶）

    • 横着接水：如果当前元素height[i]高于栈顶的柱子H=height[st.top()]，则栈顶的柱子H为最低高度，pop之后的栈顶为左边比H更高的位置，当前位置i为右边比H更高的位置，横着按层累加

    • 时间复杂度O(n)，空间复杂度O(n)

       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

      int trap(vector<int>& height) {
    if(height.size() <= 2) return 0;
    stack<int> st;
    int ans = 0;

    for(int i = 0; i < height.size(); ++i){
        while(!st.empty() && height[st.top()] < height[i]) {
            int mid = height[st.top()]; st.pop();
            if(!st.empty()){
                ans += ( min(height[st.top()], height[i]) - mid) * (i - st.top() - 1);
            }
        }
        st.push(i);
    }
    return ans;
}

  • 方法二：双指针

    • 竖着接水：维护左右边历史最高柱子，往中间移动的过程中：

      • 如果右边低，当前水位最高只能按照低的来，ans += rightHeight - height[right--]
      • 左边同理

    • 时间复杂度O(n)，空间复杂度O(1)

       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

      int trap(vector<int>& height) {
    if(height.size() <= 2) return 0;

    int left = 0, right = height.size() - 1, ans = 0;
    int leftHeight = height[left], rightHeight = height[right];
    while(left < right){
        leftHeight = max(leftHeight, height[left]);
        rightHeight = max(rightHeight, height[right]);
        if(leftHeight <= rightHeight) { // 左边低
            ans += leftHeight - height[left++];
        }
        else{
            ans += rightHeight - height[right--];
        }
    }
    return ans;
}

  • 方法三：两个数组，分别从左向右和从右向左记录当前最高水位，也是竖着接水

  • 类似题目：盛水最多的容器

    • 这个题目使用双指针的方式

  • 84. 柱状图中最大的矩形 【重要】

  • 单调栈，从栈顶到栈底递减（反应到柱子上就是往上的台阶）

    • 找每个柱子左右两边第一个低于该柱子的位置：如果当前元素height[i]低于栈顶的柱子H=height[st.top()]，有：
      • i-1位置的柱子一定不低于H
      • pop之后的栈顶位置+1一定不低于H（注意与接雨水的细微区别）
      • 因此可以算面积

  • 时间复杂度O(n)，空间复杂度O(n)

  • 技巧：在原来height数组开头height.insert(heights.begin(), 0)，在结尾height.push_back(0)，可以保证最后栈中无元素

  • 85.最大矩形

  • 402. 移掉 K 位数字

    • 单调栈：从栈底到栈顶递增，同时维护栈的顺序和k>0

优先队列

  • 347.前K个高频元素：小根堆，遍历过程中逐步弹出堆顶，剩下的就是高频元素

    • 注意优先队列的写法：

      1
2

      auto cmp = [](pair<int, int>& p1, pair<int, int>& p2){return p1.second > p2.second;};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);

  • 手写堆

  • 最小的k个元素/最小的第k个元素：维护一个最大堆，堆顶是当前最大元素（k个最小的元素中最大的一个）；如果新来的数比堆顶元素小，则弹出堆顶，新元素入堆

  • 数据流中的中位数：两个优先队列，前一半数组用最大堆，后一半数组用最小堆

    • 但是注意，为了保证后一半数组都大于前一半数组，新来的数需要先push到前面的最大堆中，然后再取top，放到后面的最小堆中
    • 同时需要保证前面最大堆的大小>=后面最小堆的大小

二叉树【二刷】

遍历

DFS

  • 递归写法：

    • 确定递归函数的参数和返回值
    • 确定终止条件
    • 确定单层递归的逻辑

  • 迭代写法：

    • 道理：当前arrive（或access）的节点，未必就是要add进数组的节点

      • 前序：第一次arrive的节点，就是add进数组的节点
      • 中序：第二次arrive的节点，就是add进数组的节点

    • 前序：空节点不入栈

       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

      vector<int> preorderTraversal(TreeNode* root) {
    vector<int> v;
    stack<TreeNode*> st;
    if(root == nullptr) return v;

    st.push(root);
    while(!st.empty()){
        TreeNode* now = st.top(); st.pop();
        v.push_back(now->val);
        if(now->right) st.push(now->right);
        if(now->left) st.push(now->left);
    }
    return v;
}

    • 中序：使用now指向当前arrive的节点，now指向可以为空，此时出栈一个元素，now指向其右节点

       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

      vector<int> inorderTraversal(TreeNode* root) {
    vector<int> v;
    stack<TreeNode*> st;
    TreeNode* now = root;
    while(now != nullptr || !st.empty()){
        // 比如中间->可能now指向空指针，此时stack不能为空
        //         ->可能stack为空，但是now指向右节点
        // 最后now指向某个节点的右空树，且stack都出栈已经为空，此时就是结束
        if(now == nullptr){ 
            now = st.top(); st.pop(); // st.top()是第二次访问，可以add进数组
            v.push_back(now->val);
            now = now->right;
        }
        else{ // now != nullptr
            st.push(now);
            now = now->left;
        }
    }
    return v;
}

    • 后序：可以按照【根右左】的顺序遍历，然后reverse（即左右根）

BFS

迭代写法：注意是否要分层；如果不用分层，则不用计算每层的size，更简单一些

递归写法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> vv;
    bfs(root, vv, 0);
    return vv;
}

void bfs(TreeNode* root, vector<vector<int>>& vv, int depth){
    if(root == nullptr) return ;
    if(vv.size() == depth) vv.push_back(vector<int>());

    vv[depth].push_back(root->val);

    if(root->left) bfs(root->left, vv, depth+1);
    if(root->right) bfs(root->right, vv, depth+1);
}

二叉树

  • 222.完全二叉树的节点个数 【好题】

    • 如何判断满二叉树？向左递归深度==向右递归深度
    • 完全二叉树中，某个节点左子树和右子树中，至少有一个是满二叉树，参考
    • 复杂度分析：
      • 每次递归需要计算当前节点的高度，O(log n)
      • 最多需要调用“树的高度”次，O(log n)
      • 相乘，O(log n) * O(log n)

  • 110.平衡二叉树

    • 注意二叉树节点【深度】和【高度】的差异
      • 高度：该节点到叶子节点的最长，求高度适合用前序遍历
      • 深度：根节点到该节点的路径，求深度适合用后序遍历

  • 112.路径总和

    • 注意分辨递归什么时候有返回值
      • 不用完整搜索整棵二叉树，找到其中一条路径即可，需要返回值（比如本题），比如if判断当前节点后直接返回。或者说遍历的思维
      • 需要完整搜索整棵二叉树，或者说二叉树与回溯的结合
        • 需要返回值（比如递归求深度）
        • 不需要返回值

  • 124.二叉树中的最大路径和 【好题】

  • 236.二叉树的最近公共祖先 【好题】

    • 递归方法：
      • 后序遍历：分别在左右子树中找p和q的最近公共祖先，然后根据找到的情况进行处理
        • 如果子树递归返回nullptr，说明子树不包含p或者q
        • 如果子树递归返回非nullptr，说明子树包含p、或q、或pq
      • 理解返回值：返回值是以root为根的子树中，p或q的最近公共祖先，如果该子树不包含p或者q，则返回nullptr
        • 如果root==p || root==q，则当前root至少为一个节点祖先，另一个节点可能在这个子树上，也可能不在这个子树上，但至少返回root
        • 如果当前root为根的子树，没有p或者q（左右子树都是nullptr），只能返回nullptr
        • 如果当前root为根的子树，左右子树分别有p和q，则root为最近公共祖先，返回root
        • 如果当前root为根的左子树或右子树其中一个，同时有p和q，则只能将其最近公共祖先向上返回
    • 迭代方法：使用map记录子节点到父节点的映射，再使用一个map记录p到root的路径，最后q向上回到root过程中找到最近同时访问的节点

  • 543.二叉树的直径

    • 维护一个计算每个节点最大深度的递归函数deepest
    • 在计算节点左右子树的过程中，更新树的直径

  • 662.二叉树最大宽度：中间nullptr也算

    • pair<TreeNode*, unsigned long long>保存节点和其id，×2得到其左节点id，×2+1得到其右节点id，最后id相减

  • 116.填充每个节点的下一个右侧节点指针

    • 常规方法：使用队列进行迭代
    • 递归方法：递归函数中传入两个节点指针

  • 671.二叉树中第二小的节点：root是最小的，遍历一遍，比root大的其中最小的

  • 区分572.另一棵树的子树 和 LCR 143.子结构判断(这个题目关于空节点本身没有说清楚)

  • 863.二叉树中所有距离为K的结点

    • 遍历一遍得到子节点到父节点的map，从而变树为图，然后dfs

  • 297.二叉树的序列化与反序列化 【好题】

    • 第一种方法：使用括号表示编码（BNF编码）进行序列化，使用递归函数进行反序列化，代码
      • BNF编码：比如postOrder BNF编码(左)(右)(根)
      • 反序列化时，递归函数中需要使用栈，从而确定左右子树在字符串中的范围
    • 第二种方法：使用逗号表示编码按照层序遍历进行序列化，使用迭代方法进行反序列化，代码
      • 序列化方式与leetcode样例给出方式相同，不需要特殊表示换层
      • 反序列化同样使用队列，字符串遍历的过程中入栈出栈
    • 第三种方法：使用逗号表示编码进行序列化，使用递归函数进行反序列化，代码
      • 序列化表示形式与第二种方法相同，但是好像只能使用前序遍历
        • 如果使用中序/后序，字符串中第一个元素解码后是nullptr，在反序列化的递归函数中第一个元素就直接返回，不会处理后面的字符串了
        • 如果使用前序，字符串中第一个元素肯定不为nullptr，可以递归下去
      • 反序列化过程需要维护一个全局的索引，从而在不同的递归函数之间确定当前处理的元素的位置

  • 652.寻找重复的子树

    • 使用基于后序遍历的二叉树序列化，模板类似297.二叉树的序列化与反序列化中第一种方法，但是序列化格式可以简化
    • 在后序遍历进行序列化的过程中，同时维护unordered_map<string, pair<TreeNode*, int>>的映射

二叉搜索树

综合

  • 437.路径总和Ⅲ 【好题】，【二叉树】+【前缀和】+【回溯】

    • 递归方法：以每个节点为root（O(n)），再计算包含root时的路径数量（O(n)），复杂度O(n^2)

    • 前缀和：在前序遍历的过程中，记录当前节点的前缀和，并遍历过的节点的前缀和保存到map中（value是特定前缀和的个数）

      • 根据当前前缀和和root->val，可以得到当前分支上符合要求的路径的个数
      • 当当前root返回时，当前的前缀和也需要从map中复原

回溯

  • 回溯

    • 思路：二叉树/多叉树的递归遍历

      • 视为二叉树的话，每个元素选择或不选，每个dfs中有两条路径
      • 视为多叉树的话，在每个for循环中进行选择，注意选择之后的回溯复原就表示没有选择当前元素，然后可以选择后面的元素

    • 写法：数组直接作为全局变量，进行多叉树的遍历时使用一个startIdx来表示当前搜索数组的位置

    • 细节问题：

      • 使用startIdx还是从0开始
      • 能否对数组排序？
        • 能，如果需要去重，维护一个全局的used数组
          • used数组的索引，表示nums的下标（一般是这个，比如有重复元素时，使用str[i]==str[i-1 && isVisit[i-1]来判断），还是nums元素的值
        • 不能，如果需要去重，则每一层应该维护一个局部的set

  • 组合问题：从N个数中选k个数，有几种选法

    • 77.组合：模板题
    • 216.组合总数Ⅲ：直接在for循环中进行剪枝
    • 17.电话号码的字母组合：使用字符串数组（或者二维数组）来进行数字到字符串的对应
    • 39.组合总和：
    • 40.组合总和Ⅱ：使用used数组进行去重，初始化used=false：
      • 当数组中相邻两个元素相等且used=true时，表示这两个元素在同一个树枝上（在一个分支上），此时不用去重（即组合内部使用了相同的元素）
      • 当数组中相邻两个元素相等且user=false时，表示这两个元素在递归的同一层（同一树层上），此时表示后面会有相同的组合出现，因此需要去重（continue）

  • 切割问题：一个字符串不同切割方式，有几种方式

    • 131.分割回文串：逐个分割每个元素进行判断，同样是递归的树形结构
    • 93.复原IP地址：感觉写成三叉树的递归方式，而非是for循环的递归方式更直观和易于理解
      • 三叉树方式：从当前位置开始的子串，分别作为一个字符、两个字符、三个字符进行匹配

  • 子集问题：N个数中相关子集的个数

    • 78.子集：递归的树形结构的所有节点
    • 90.子集Ⅱ：理解“树枝去重”与“树层去重”的逻辑，对于相同的数字，前面的可以选或不选，后面的必须不能选
    • 491.递增子序列：同样需要去重，但不能使用全局的used数组来去重
      • 90.子集Ⅱ中数组是有序的，可以保证相同的数字都是挨着的，
      • 491.递增子序列中数组无序，如果按上面的方式，只能保证相同的连着的数字是去重的，相同的不挨着的数字会重复，因此只能每一层维护一个局部的used数组，动态判断该数字之前是否出现过

  • 排列问题：N个数的不同排列方式

    • 46.全排列：

      • 方法一：使用used数组记录该数字是否使用过，仔细考虑for循环和回溯（回退）的过程
      • 方法二：使用swap和startIdx，每次减小排列的规模

    • 47.全排列Ⅱ：对比491.递增子序列

    • 332.重新安排行程：

      • 错误理解和写法：每个机场只到一次（因此使用一个数组记录该节点是否到过）
      • 正确理解：所有路径都走且只走一次（可能比如北京到上海有好几张票，都要使用，因此使用unordered_map<string, map<string, int>>来进行建图，然后dfs,回溯更新int的值）

  • 棋盘问题：

    • 51.N皇后：画出搜索的树形结构，dfs中逐层放置皇后
    • 37.解数独：
      • 二维的递归，注意最外层for循环的是数组/棋盘，而不是各种可能性或组合（即选或不选）
      • 判断合法性时，只是判断当前元素是否行、列、方格重复

贪心

区间贪心

  • 55. 跳跃游戏：维护一个当前可以跳跃到的最右边界
  • 45.跳跃游戏Ⅱ
  • 435.无重叠区域
    • 当有重叠区域时，更新右端点right = min(right, v[1]);的含义：如果重叠，使得右端点最小
      • 如果旧的right更小，则移除掉新来的区间
      • 如果新来的区间v[1]更小，则移除原来的区间
  • 452.用最少数量的箭引爆气球 对比435.无重叠区域
    • 按照每个点的start进行排序，当前重叠范围为[start, right]，start递增，维护逐渐缩小的重叠区间right = min(right, points[i][1])
  • 主持人调度（二）：排序+最小堆
    • 按开始时间、结束时间先排序区间
    • 使用最小堆保存当前正在进行的所有活动的结束时间，堆顶是最早的结束时间
      • 因此，如果新来的某次活动，开始时间小于堆顶的最早结束时间，则这个活动可以连起来

两个维度贪心

上下坡

动态规划

总结

动规五部曲：

  • 确定dp数组的含义和下标的含义
  • 确定递推公式
  • 确定dp数组的初始化
  • 确定遍历顺序
  • 举个例子

单纯动规

直接寻找/使用最优子结构

01背包

  • 494.目标和：要装满背包，有几种方法
    • 注意，0可以特殊处理，也可以不用特殊处理
  • 416.分割等和子集： 给定背包容量，能不能装满这个背包
    • 方法一：dp[j]就表示背包容量为j时，能否将背包装满
    • 方法二：视为标准01背包，物品价值和重量相等，最后看容量为j的背包里最大价值
  • 1049.最后一块石头的重量Ⅱ：
    • 首先转换成标准01背包：分成两堆石头，一堆小，一堆大，让小的那堆尽量接近一半
  • 474.一和零：给定背包容量，装满背包最多有多少个物品
    • 注意背包是二维的（长对应0的数量，宽对应1的数量）

排列数与组合数

打家劫舍系列

  • 198.打家劫舍：
    • 不要硬套01背包，01背包只是动规中很套路的一个模板；除了直接题目可以直接套模板，剩下的还是要具体分析出来递推公式
  • 213.打家劫舍Ⅱ
    • 拆环为链，拆分成两种情况，各跑一遍
  • 337.打家劫舍Ⅲ：树形DP
    • 每个节点有一个状态数组
    • 在后序遍历中，得到左右子树的状态，更新当前节点的状态

买卖股票的最佳时机系列

  • 121.买卖股票的最佳时机

    • dp数组表示持有/不持有股票，第0天持有即买入
    • 划分状态
      • 首先为什么标准01背包不需要针对每个背包的容量分成两种状态的数组？
        • 动规原理是最优子结构，标准01背包中物品之间是相互独立的，不存在某件放入a物品后必须放入b物品这样的关联
      • 其次为什么打家劫舍问题也不需要针对每一间房屋分成两种状态的数组？
        • 首先可以分，而且公式写出来也很清晰，在比如树形DP中还必须要分
        • 但是打家劫舍中，只是相邻两个房屋之间有关联，公式中可以直接将关联表示出来
      • 买卖股票中为什么必须要分成两种状态的数组？
        • 因为买卖股票的两天之间的关联不是固定的
        • 买卖股票中还需要注意两种状态的定义：是持有/不持有，而非买入/卖出
      • 什么是状态？
        • 第i天进行第j笔交易，是持有还是不持有
    • 注意如何保证只买入一次？区别122.买卖股票的最佳时机Ⅱ
    • 加上手续费相同714.买卖股票的最佳时机含手续费

  • 122.买卖股票的最佳时机Ⅱ

  • 123.买卖股票的最佳时机Ⅲ

  • 309.最佳买卖股票时机含冷冻期

    • 细化状态（比如不持有股票可以细分为今天卖出还是维持原来不持有的状态）
    • 画出状态转移图

序列问题

递增序列/数组

  • 300.最长递增子序列 LIS

    • 674.最长连续递增序列是连续的递增序列（或称为递增数组），是否连续决定是否内部要使用一个for循环找到比当前元素小的位置

    • 可以使用贪心+二分实现更低的复杂度

      • 贪心：d[len]表示：长度为len的LIS的最后一个元素值，该元素值越小越好

      • 二分：d[]数组单调递增，

         1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

        int d[N]; // 长度为len的LIS中的最后一个元素的值
int lengthOfLIS(vector<int>& nums) {
    if(nums.size() == 1) return 1;

    d[0] = -1000000;
    d[1] = nums[0];
    int len = 1; // 当前最长LIS的长度
    for(int i = 1; i < nums.size(); ++i){
        if(nums[i] > d[len]) // 如果当前最长LIS后面可以继续添加一个元素
            d[++len] = nums[i];
        else{ // nums[i] <= d[len]
            // // 固定nums[i]为结尾，找前面尽可能长的一个LIS，同时该LIS的最大值<nums[i]
            // // 即：长度j尽可能大，同时d[j] < nums[i]
            // int j = find_last_lt(d, 0, len+1, nums[i]);
            // d[j+1] = min(d[j+1], nums[i]);
            // 另一种等价的写法：找到d中第一个>nums[i]的位置j
            // 说明j-1长度的LIS的最大元素小于nums[i]，j长度的LIS最大元素又>nums[i]
            // 说明为j长度的LIS找到了更小的一个末尾元素
            int j = find_first_ge(d, 0, len+1, nums[i]);
            d[j] = nums[i];
        }
    } 
    return len;
}

        参考

  • 673.最长递增子序列的个数

    • 使用贪心+树状数组实现O(nlogn)的复杂度，参考

  • 354.俄罗斯套娃信封问题

    • 先排序，w正排，h倒排（保证相同w时，大h不能包含小h）
    • 通过排序将二维LIS转换为一维的LIS

  • 368.最大整除子集

    • 与LIS方法差不多
重复数组、公共序列、子数组/序列问题

  • 718.最长重复子数组

    • 使用滚动数组进行优化：代码
      • 内层逆序：之所以逆序，一是因为不将物品重复放入，二是因为可能依赖是斜向上的，逆序可以直接访问未更新之前的数值
      • 也可以使用顺序，不过要将原来未更新之间的数值记录下来
    • 其实是这个题目对遍历顺序没有要求，因为if中dp依赖左上旧值，else中dp直接是0
      • 其他题目中，else中可能需要用到刚才更新过的值，因此只能从前向后遍历

  • 1143.最长公共子序列 和 1035.不相交的线

    • 使用滚动数组进行优化：使用两个数组来回调替，或者直接记录依赖的旧值
    • 极其注意如果使用一维数组优化，同时使用pre来记录斜上角的值时，此时tmp=dp[j]还是tmp=dp[j+1]，tmp保存的是当前dp要被覆盖的值

  • 53.最大子数组和

    • 遇到数组和第一直觉总是前缀和，但是这个题目使用动规很简单

  • 392.判断子序列

    • 可以使用双指针
    • 使用动规：状态转移方程很类似
      • dp可以表示相同序列的长度
      • dp也可以是bool数组，表示s[0, i]是否为t[0, j]的子序列
        • 使用滚动数组优化二维数组时，注意将初始化方式从原来的二维情况下转换到一维情况下，比如当i=0时容易记起初始化，但是i=1,2,3…之后，dp[0]或者dp数组开头几个数字就容易忘记初始化，代码

  • 115.不同的子序列

字符串操作
回文相关

其他

  • 152.乘积最大子数组：【好题】，也是分状态，但是其中另一个状态隐含在题目中，需要分析，很巧

第一次几乎完全不会

动规+单调队列

图论

DFS与BFS

  • 797.所有可能的路径：DFS+回溯

  • 200.岛屿数量：DFS，BFS模板题

  • 1020.飞地的数量：第一阶段原地修改原来的二维数组标记，第二阶段再次遍历

  • 130.被围绕的区域：原地修改二维数组标记

  • 827.最大人工岛：保存中间计算结果（岛屿面积），避免重复计算

    • 首先遍历，每个岛屿进行编号，同时使用map记录id到岛屿面积的映射
    • 对于水块，上下左右累加岛屿面积

  • 127.单词接龙：

    单词个数n，单词长度m

    • 方法一：BFS内部，对单词进行遍历，找到相邻的单词，最坏情况复杂度O(nnm)
    • 方法二：BSF内部，对当前单词逐字母进行替换，判断替换后的单词是否在词表中，复杂度O(26*n)

  • BM61 矩阵最长递增路径 DFS+动规

    • DFS的模板，动规的公式：

      1
2
3
4
5

      // 从(x,y)到(xx,yy)递增
if(inBound(xx,yy) && mat[x][y] < mat[xx][yy]){
    dfs(mat, xx, yy); // DFS计算dp[xx][yy]的值
    dp[x][y] = max(dp[x][y], dp[xx][yy]+1);
}

并查集

数学

模拟

  • 9.回文数：
    • 空间复杂度O(1)的方法：原来数字取模除十的过程中，与反转后的数组比较大小
  • 172.阶乘后的零：实际上就是找因子5的个数

位运算

  • 常用技巧：对于int n

    • 获取n的最低位的1：n & (-n)
    • 将n的最低位1变为0：n & (n-1)

  • 191.位1的个数：

    • 循环检查二进制位：if(n & (1 << i)) ++cnt
    • lsb翻转：n & (n-1)结果为将n的二进制lsb变为0，因此：while(n) {n &= (n-1); ++cnt;}

  • 136.只出现一次的数字：数组异或，原理是异或具有交换律

  • 137.只出现一次的数字Ⅱ：

    • 对于32位int，统计每一个bit中1的个数cnt，如果cnt无法整除3，则只出现一次的数字在当前bit为1，ans |= (1 << i)

  • 260.只出现一次的数字Ⅲ：分组异或

    • xorsum一定不为0，否则所有数字都出现两次，假设两个出现一次的数字为a和b

    • xorsum的最低有效位lsb，则一定是a的lsb=1，b的lsb=0（或反过来）

      • 为什么要取最低有效位？为了实现分组，a和b在最低有效位不同，

    • 出现两次的数字，其lsb一定相同；因此根据这个lsb可以将所有数字分成两类，分别进行异或

       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

      vector<int> FindNumsAppearOnce(vector<int>& nums) {
    // write code here
    int xorsum = 0;
    for(int n: nums) xorsum ^= n;

    int lsb = xorsum == INT_MIN ? xorsum : xorsum & (-xorsum);
    int a = 0, b = 0;
    for(int n: nums){
        if(n & lsb) a ^= n;
        else b ^= n;
    }
    return vector<int>{min(a,b), max(a,b)};
}

其他

  • 快速幂
  • 470.用Rand7()实现Rand10()：拒绝采样
    • 注意不能直接使用rand7() * rand7()，因为其中元素概率不完全相同，比如14的概率是2/49，1的概率是1/49，6的概率是4/49
    • 视为行列索引：row=rand7(); col=rand7(); c = (row-1)*7 + col;，这样每个元素等概率

设计

  • 705.设计哈希集合：基于vector<list<int>>的链地址法
  • 706.设计哈希映射：基于vector<list<pair<int,int>>>的链地址法
  • 380.O(1)时间插入、删除和获取随机元素：
    • 一个vector用来获取随机元素
    • 一个unordered_map<int, int>用来记录val到idx的映射
  • 208.实现Trie（前缀树）
    • 类似二叉树，Trie本身就是一个node，里面有vector<Trie*> children(26, nullptr)表示26叉树
    • Trie节点中包含一个属性isEnd，如果当前节点表示字符串的最后一个字符，则当前节点的下一个节点的isEnd=true
    • 包含一个辅助函数Trie* searchPrefix(string prefix)，返回prefix字符串结尾的下一个节点

继续刷

437.路径总和Ⅲ

4.寻找两个正序数组的中位数

85.最大矩形

28.找出字符串中第一个匹配项的下标：KMP模板

附录一：ACM输入输出模板

  • A+B问题

    1
2
3
4
5
6
7
8

    int main(){
    int a, b;
    while(scanf("%d %d", &a, &b) != EOF) {

    }
    // while(cin >> a >> b) {} // 或者cin输入
    return 0;
}

    注意scanf输入中的换行，对于输入int不影响，但是对于输入char会影响，比如可能会将换行吃掉

  • 平均绩点

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

    #include <cstdio>
#include <string>
#include <iostream>
using namespace std;

int main(){
    string s;
    while (getline(cin, s)) { // 接受一整行字符串

    }
    return 0;
}

附录二：刷题列表

牛客面试笔刷TOP101