代码随想录

参考资料

• 代码随想录 - 系统刷题, 总结的很棒 - 5

数组

力扣 no.704

二分查找

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right){
            int mid = (right - left) / 2 + left;
            int num = nums[mid];
            if (num == target) {
                return mid;
            } else if (num > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
};

• 前提为有序无重复
• 区间的定义 (循环不变量) 为两种, 左闭右闭或左闭右开
• 左闭右闭, while 使用 <=, if (nums [middle]>target) right 赋值为 middle-1
• 左闭右开, while 使用 <, if (nums [middle]>target) right 赋值为 middle

力扣 no.27

移除元素

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;
    }
};

• 双指针法
• 快指针寻找新数组的元素, 慢指针指向更新新数组下标的位置
• 首尾指针, 从数组两端向中间移动可以将 \(n+k\) 优化到 \(n\)

力扣 no.977

有序数组的平方

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int k = A.size() - 1;
        vector<int> result(A.size(), 0);
        for (int i = 0, j = A.size() - 1; i <= j;) { // 注意这里要 i <= j, 因为最后要处理两个元素
            if (A[i] * A[i] < A[j] * A[j])  {
                result[k--] = A[j] * A[j];
                j--;
            }
            else {
                result[k--] = A[i] * A[i];
                i++;
            }
        }
        return result;
    }
};

• 双指针法, 一开始我以为要合并相等项呢 (其实也差不多)

力扣 no.209

长度最小的子数组

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;
        int sum = 0; // 滑动窗口数值之和
        int i = 0; // 滑动窗口起始位置
        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            // 注意这里使用 while, 每次更新 i(起始位置), 并不断比较子序列是否符合条件
            while (sum >= s) {
                subLength = (j - i + 1); // 取子序列的长度
                result = result < subLength ? result : subLength;
                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处, 不断变更 i(子序列的起始位置)
            }
        }
        // 如果 result 没有被赋值的话, 就返回 0, 说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};

• 滑动窗口法

力扣 no.59

螺旋矩阵 II

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int t = 0;      // top
        int b = n-1;    // bottom
        int l = 0;      // left
        int r = n-1;    // right
        vector<vector<int>> ans(n,vector<int>(n));
        int k=1;
        while(k<=n*n){
            for(int i=l;i<=r;++i,++k) ans[t][i] = k;
            ++t;
            for(int i=t;i<=b;++i,++k) ans[i][r] = k;
            --r;
            for(int i=r;i>=l;--i,++k) ans[b][i] = k;
            --b;
            for(int i=b;i>=t;--i,++k) ans[i][l] = k;
            ++l;
        }
        return ans;
    }
};

• 模拟, 坚持循环不变量原则, 左闭右开

卡码网 no.58

区间和

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, a, b;
    cin >> n;
    vector<int> vec(n);
    for (int i = 0; i < n; i++) cin >> vec[i];
    while (cin >> a >> b) {
        int sum = 0;
        // 累加区间 a 到 b 的和
        for (int i = a; i <= b; i++) sum += vec[i];
        cout << sum << endl;
    }
} 

• 前缀和

卡码网 no.44

开发商购买土地\ n*m 个区块拥有权值, 所有区块分配给 A 和 B\ 只允许将区域按横向或纵向划分成两个子区域, 求 A 和 B 的最小权值之差\

#include <iostream>
#include <vector>
#include <climits>

using namespace std;
int main () {
    int n, m;
    cin >> n >> m;
    int sum = 0;
    vector<vector<int>> vec(n, vector<int>(m, 0)) ;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> vec[i][j];
            sum += vec[i][j];
        }
    }

    int result = INT_MAX;
    int count = 0; // 统计遍历过的行
    for (int i = 0; i < n; i++) {
        for (int j = 0 ; j < m; j++) {
            count += vec[i][j];
            // 遍历到行末尾时候开始统计
            if (j == m - 1) result = min (result, abs(sum - count - count));

        }
    }

    count = 0; // 统计遍历过的列
    for (int j = 0; j < m; j++) {
        for (int i = 0 ; i < n; i++) {
            count += vec[i][j];
            // 遍历到列末尾的时候开始统计
            if (i == n - 1) result = min (result, abs(sum - count - count));
        }
    }
    cout << result << endl;
}

• 求前缀和的过程中可解

链表

力扣 no.203

移除链表元素

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 删除头结点
        while (head != NULL && head->val == val) { // 注意这里不是 if
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
        }

        // 删除非头结点
        ListNode* cur = head;
        while (cur != NULL && cur->next!= NULL) {
            if (cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        return head;
    }
};

• 虚拟头节点/递归/朴素, 解法很多

力扣 no.707

设计链表

//get(index): 获取链表中第 index 个节点的值 如果索引无效, 则返回-1
//addAtHead(val): 在链表的第一个元素之前添加一个值为 val 的节点 插入后, 新节点将成为链表的第一个节点 
//addAtTail(val): 将值为 val 的节点追加到链表的最后一个元素
//addAtIndex(index, val): 在链表中的第 index 个节点之前添加值为 val 的节点 如果 index 等于链表的长度, 则该节点将附加到链表的末尾 如果 index 大于链表长度, 则不会插入节点 如果 index 小于 0, 则在头部插入节点
//deleteAtIndex(index): 如果索引 index 有效, 则删除链表中的第 index 个节点

• 略

力扣 no.206

翻转链表

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
};

• 迭代/递归

力扣 no.24

两两交换链表中的节点

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* temp = dummyHead;
        while (temp->next != nullptr && temp->next->next != nullptr) {
            ListNode* node1 = temp->next;
            ListNode* node2 = temp->next->next;
            temp->next = node2;
            node1->next = node2->next;
            node2->next = node1;
            temp = node1;
        }
        ListNode* ans = dummyHead->next;
        delete dummyHead;
        return ans;
    }
};

力扣 no.19

删除链表的倒数第 N 个节点

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        head=new ListNode(0, head);
        ListNode *s(head), *q(head);
        for(;n>-1;n--) q=q->next;
        while(q){
            q=q->next;
            s=s->next;
        }
        s->next=s->next->next;
        return head->next;
    }
};

• 双指针加哑节点

力扣 no.160

判断两个链表相交点

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}
// 双指针正解真的巧妙, 指针走完后交换到另一个链表的头节点
// 把三段距离设为 abc, 一个走完是 a+c, 另一个 b+c, 交换链表, 走同样距离刚好是 a+b+c, 刚好在交点处

• 用哈希 / 对齐太简单, 不说了

力扣 no.142

环形链表 II

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while (fast != nullptr) {
            slow = slow->next;
            if (fast->next == nullptr) {
                return nullptr;
            }
            fast = fast->next->next;
            if (fast == slow) {
                ListNode *ptr = head;
                while (ptr != slow) {
                    ptr = ptr->next;
                    slow = slow->next;
                }
                return ptr;
            }
        }
        return nullptr;
    }
};

• 快慢指针
• s 到达环入口时 (f - 环入口) 一定等于 s 与 f 相遇时 (环入口 - s) 设为距离 c
• 链表头到环入口距离一定为整数倍的环长 + c

哈希表

力扣 no.242

给定两个字符串 s 和 t, 编写一个函数来判断 t 是否是 s 的字母异位词

class Solution {
public:
    bool isAnagram(string s, string t) {
        int m[26]={0}, l(0);
        if(s.size()==t.size()) l=s.size();
        else return 0;
        for(int i(0);i<l;i++){
            m[s[i]-'a']++;m[t[i]-'a']--;
        }
        for(int i(0);i<26;i++){
            if(m[i]) return 0;
        }
        return 1;
    }
};

力扣 no.349

给定两个数组 nums1 和 nums2, 返回它们的交集

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> s(nums1.begin(), nums1.end());
        unordered_set<int> res;
        for(int i(0);i<nums2.size();i++){
            if(s.find(nums2[i])!=s.end()) res.insert(nums2[i]);
        }
        return vector<int>(res.begin(), res.end());
    }
};

• unordered_set 秒杀

力扣 no.202

快乐数

class Solution {
    int happy(int n){
        int sum;
        for(sum=0;n>0;n/=10) sum+=(n%10)*(n%10);
        return sum;
    }
public:
    bool isHappy(int n) {
        map<int, bool> m;
        while(n!=1){
            n=happy(n);
            if(m[n]) return 0;
            m[n]=1;
        }
        return 1;
    }
};

• 直接哈希非常简单
• 快慢指针判断环更好!!!
• 正解: 数学角度, 这道题其实只能存在一个环, 硬编码那个环, 然后只要到达环中某一个数字就返回 0

力扣 no.1

两数之和

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map <int, int> map;
        for(int i = 0; i < nums.size(); i++) {
            // 遍历当前元素, 并在 map 中寻找是否有匹配的 key
            auto iter = map.find(target - nums[i]); 
            if(iter != map.end()) {
                return {iter->second, i};
            }
            // 如果没找到匹配对, 就把访问过的元素和下标加入到 map 中
            map.insert(pair<int, int>(nums[i], i)); 
        }
        return {};
    }
};

• 无需多言

力扣 no.454

四数相加 II

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int, int> umap; //key:a+b 的数值, value:a+b 数值出现的次数
        // 遍历大 A 和大 B 数组, 统计两个数组元素之和, 和出现的次数, 放到 map 中
        for (int a : A) {
            for (int b : B) {
                umap[a + b]++;
            }
        }
        int count = 0; // 统计 a+b+c+d = 0 出现的次数
        // 再遍历大 C 和大 D 数组, 找到如果 0-(c+d) 在 map 中出现过的话, 就把 map 中 key 对应的 value 也就是出现次数统计出来
        for (int c : C) {
            for (int d : D) {
                if (umap.find(0 - (c + d)) != umap.end()) {
                    count += umap[0 - (c + d)];
                }
            }
        }
        return count;
    }
};

• \(O(n^2)\) 记录 \(a+b\) 的和, 然后 \(O(n^2)\) 遍历 \(c+d\) 看是否有相反数

力扣 no.383

赎金信

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        int[] cnt = new int[26];
        for (char c : magazine.toCharArray()) {
            cnt[c - 'a']++;
        }
        for (char c : ransomNote.toCharArray()) {
            cnt[c - 'a']--;
            if(cnt[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}

• 简单

力扣 no.15

三数之和

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        // 找出 a + b + c = 0
        // a = nums[i], b = nums[left], c = nums[right]
        for (int i = 0; i < nums.size(); i++) {
            // 排序之后如果第一个元素已经大于零, 那么无论如何组合都不可能凑成三元组, 直接返回结果就可以了
            if (nums[i] > 0) {
                return result;
            }
            // 错误去重 a 方法, 将会漏掉-1, -1, 2 这种情况
            /*
            if (nums[i] == nums[i + 1]) {
                continue;
            }
            */
            // 正确去重 a 方法
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = nums.size() - 1;
            while (right > left) {
                // 去重复逻辑如果放在这里, 0, 0, 0 的情况, 可能直接导致 right<=left 了, 从而漏掉了 0, 0, 0 这种三元组
                /*
                while (right > left && nums[right] == nums[right - 1]) right--;
                while (right > left && nums[left] == nums[left + 1]) left++;
                */
                if (nums[i] + nums[left] + nums[right] > 0) right--;
                else if (nums[i] + nums[left] + nums[right] < 0) left++;
                else {
                    result.push_back(vector<int>{nums[i], nums[left], nums[right]});
                    // 去重逻辑应该放在找到一个三元组之后, 对 b 和 c 去重
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;

                    // 找到答案时, 双指针同时收缩
                    right--;
                    left++;
                }
            }

        }
        return result;
    }
};

• 排序加双指针
• 这题的去重比较复杂, 要注意

力扣 no.18

四数之和

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for (int k = 0; k < nums.size(); k++) {
            // 剪枝处理
            if (nums[k] > target && nums[k] >= 0) {
                // 一级剪枝
                break;
            }
            // 对 nums[k]去重
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for (int i = k + 1; i < nums.size(); i++) {
                // 2 级剪枝处理
                if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
                    break;
                }

                // 对 nums[i]去重
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int left = i + 1;
                int right = nums.size() - 1;
                while (right > left) {
                    // nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
                    if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) {
                        right--;
                    // nums[k] + nums[i] + nums[left] + nums[right] < target 会溢出
                    } else if ((long) nums[k] + nums[i] + nums[left] + nums[right]  < target) {
                        left++;
                    } else {
                        result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
                        // 对 nums[left]和 nums[right]去重
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;

                        // 找到答案时, 双指针同时收缩
                        right--;
                        left++;
                    }
                }

            }
        }
        return result;
    }
};

• 类似三数之和, 只是多了一层循环, 注意复杂的去重

字符串

力扣 no.344

反转字符串

class Solution {
public:
    void reverseString(vector<char>& s) {
        int n = s.size();
        for (int left = 0, right = n - 1; left < right; ++left, --right) {
            swap(s[left], s[right]);
        }
    }
};

力扣 no.541

反转字符串 II

class Solution {
public:
    string reverseStr(string s, int k) {
        int n = s.length();
        for (int i = 0; i < n; i += 2 * k) {
            reverse(s.begin() + i, s.begin() + min(i + k, n));
        }
        return s;
    }
};

卡码网 no.54

替换数字

#include <iostream>
using namespace std;
int main() {
    string s;
    while (cin >> s) {
        int sOldIndex = s.size() - 1;
        int count = 0; // 统计数字的个数
        for (int i = 0; i < s.size(); i++) {
            if (s[i] >= '0' && s[i] <= '9') {
                count++;
            }
        }
        // 扩充字符串s的大小, 也就是将每个数字替换成"number"之后的大小
        s.resize(s.size() + count * 5);
        int sNewIndex = s.size() - 1;
        // 从后往前将数字替换为"number"
        while (sOldIndex >= 0) {
            if (s[sOldIndex] >= '0' && s[sOldIndex] <= '9') {
                s[sNewIndex--] = 'r';
                s[sNewIndex--] = 'e';
                s[sNewIndex--] = 'b';
                s[sNewIndex--] = 'm';
                s[sNewIndex--] = 'u';
                s[sNewIndex--] = 'n';
            } else {
                s[sNewIndex--] = s[sOldIndex];
            }
            sOldIndex--;
        }
        cout << s << endl;       
    }
}

力扣 no.151

反转字符串中的单词

class Solution {
public:
    string reverseWords(string s) {
        string ans;
        int i(s.size()-1);
        for(;i>=0;i--) if(s[i]!=' ') break; // 找到第一个非空格字符
        for(;i>=0;i--){
            if(s[i]==' '&&s[i+1]!=' '){ // 找到一个单词的结束位置
                for(int k=i+1;k<s.size()&&s[k]!=' ';k++) ans+=s[k]; // 反转单词
                ans+=' '; // 单词之间添加空格
            }
        }
        if(s[0]!=' ') // 处理第一个单词
            for(int k=0;k<s.size()&&s[k]!=' ';k++) ans+=s[k];
            else ans.erase(ans.size()-1); // 第一个单词后面没有空格, 所以需要删除最后一个空格
        return ans;
    }
};

• 这是刚学的时候写的代码, 实际上有\(O(1)\)空间的解法

class Solution {
public:
    void reverse(string& s, int start, int end){ //翻转, 区间写法: 左闭右闭 []
        for (int i = start, j = end; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }

    void removeExtraSpaces(string& s) {//去除所有空格并在相邻单词之间添加空格, 快慢指针
        int slow = 0;   //整体思想参考https://programmercarl.com/0027.移除元素.html
        for (int i = 0; i < s.size(); ++i) { //
            if (s[i] != ' ') { //遇到非空格就处理, 即删除所有空格
                if (slow != 0) s[slow++] = ' '; //手动控制空格, 给单词之间添加空格slow != 0 说明不是第一个单词, 需要在单词前添加空格
                while (i < s.size() && s[i] != ' ') { //补上该单词, 遇到空格说明单词结束
                    s[slow++] = s[i++];
                }
            }
        }
        s.resize(slow); //slow的大小即为去除多余空格后的大小
    }

    string reverseWords(string s) {
        removeExtraSpaces(s); //去除多余空格, 保证单词之间之只有一个空格, 且字符串首尾没空格
        reverse(s, 0, s.size() - 1);
        int start = 0; //removeExtraSpaces后保证第一个单词的开始下标一定是 0
        for (int i = 0; i <= s.size(); ++i) {
            if (i == s.size() || s[i] == ' ') { //到达空格或者串尾, 说明一个单词结束进行翻转
                reverse(s, start, i - 1); //翻转, 注意是左闭右闭 []的翻转
                start = i + 1; //更新下一个单词的开始下标start
            }
        }
        return s;
    }
};

• 先反转整个字符串, 然后再反转每个单词

卡码网 no.55

右旋字符串

#include <iostream>
using namespace std;
int main() {
    int n;
    string s;
    cin >> n >> s;
    reverse(s.begin(), s.begin() + s.size() - n);
    reverse(s.begin() + s.size() - n, s.end());
    reverse(s.begin(), s.end());
    cout << s << endl;
}

• 显然跟右旋数组一样

力扣 no.28

实现 strStr()

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        if (m == 0) {
            return 0;
        }
        vector<int> pi(m);
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle[i] != needle[j]) {
                j = pi[j - 1];
            }
            if (needle[i] == needle[j]) {
                j++;
            }
            pi[i] = j;
        }
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack[i] != needle[j]) {
                j = pi[j - 1];
            }
            if (haystack[i] == needle[j]) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }
};

• KMP 板子

力扣 no.459

重复的子字符串

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        return (s + s).find(s, 1) != s.size();
    }
};

• 想法易于理解, 证明困难
• 使用语言的子串查找函数 (部分是 BM 算法)

// 模式串自前向后匹配, 匹配时自后向前, 因此匹配失败时, 会同时出现坏字符和好后缀

// 坏字符规则的实现
// 维护字符到模式串中最后一次出现的位置的映射
int BadChar(int j, char temp, string str) {
   int index = -1;
   for (int i = j - 1; i >= 0; --i) {
       if (str[i] == temp) {
           index = i;
           break;
       }
   }
   return j - index;
}
// 好后缀规则的实现
// 维护好后缀到模式串中最后一次出现的位置的映射, 有点像 KMP 算法的 next 数组
int GoodSuffix(int j, string& pat) {
   int terminal = pat.length() - 1;
   int index = -1;
   j--;
   while (j >= 0) {
       if (pat[j] == pat[terminal]) {
           index = j;
           break;
       } else j--;
   }
   return terminal - index;
}
// Boyer-Moore搜索算法的主体
// 每次匹配失败时, 坏字符和好后缀的移动距离取较大的那个
int BM(string source, string target) {
   int i = 0, j = 0, soulen = source.length(), tarlen = target.length();
   int badvalue = 0, distance = 0;
   if (soulen < tarlen) {
       printf("字符串的长度小于搜索词的长度\n");
       return -1;
   }
   i = tarlen - 1; j = tarlen - 1;
   while (i < soulen) {
       if (source[i] == target[j]) {
           if (j == 0) {
               printf("匹配成功\n");
               return i;
           }
           i--; j--;
       } else {
           if (j == tarlen - 1) {
               badvalue = BadChar(j, source[i], target);
               cout << "坏字符移动: " << badvalue << endl;
               i = i + tarlen - 1 - j + badvalue;
               j = tarlen - 1;
           } else {
               badvalue = BadChar(j, source[i], target);
               if (badvalue == -1) badvalue = target.length();
               distance = badvalue > GoodSuffix(j, target) ? badvalue : GoodSuffix(j, target);
               cout << "好后缀为: " << GoodSuffix(j, target) << " 坏字符为: " << badvalue << " 比较之后移动" << distance << endl;
               i = i + tarlen - 1 - j + distance;
               j = tarlen - 1;
           }
       }
   }
   return -1;
}

• 优化的 BM 算法的平均时间复杂度普遍优于 KMP 算法
• 这题可以使用 KMP 算法, 原因是 next[n-1] == n-1-i 与题目等效, 即 next 指示的最后一个字符的回退长度为 i

栈与队列

力扣 no.232

用栈实现队列

class MyQueue {
public:
    stack<int> stIn;
    stack<int> stOut;
    /** Initialize your data structure here. */
    MyQueue() {

    }
    /** Push element x to the back of queue. */
    void push(int x) {
        stIn.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        // 只有当stOut为空的时候, 再从stIn里导入数据（导入stIn全部数据）
        if (stOut.empty()) {
            // 从stIn导入数据直到stIn为空
            while(!stIn.empty()) {
                stOut.push(stIn.top());
                stIn.pop();
            }
        }
        int result = stOut.top();
        stOut.pop();
        return result;
    }

    /** Get the front element. */
    int peek() {
        int res = this->pop(); // 直接使用已有的pop函数
        stOut.push(res); // 因为pop函数弹出了元素res, 所以再添加回去
        return res;
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return stIn.empty() && stOut.empty();
    }
};

• 两个栈来回倒数据

力扣no.225

用队列实现栈

class MyStack {
public:
    queue<int> que;

    MyStack() {

    }

    void push(int x) {
        que.push(x);
    }

    int pop() {
        int size = que.size();
        size--;
        while (size--) { // 将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部
            que.push(que.front());
            que.pop();
        }
        int result = que.front(); // 此时弹出的元素顺序就是栈的顺序了
        que.pop();
        return result;
    }

    int top(){
        int size = que.size();
        size--;
        while (size--){
            // 将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部
            que.push(que.front());
            que.pop();
        }
        int result = que.front(); // 此时获得的元素就是栈顶的元素了
        que.push(que.front());    // 将获取完的元素也重新添加到队列尾部, 保证数据结构没有变化
        que.pop();
        return result;
    }

    bool empty() {
        return que.empty();
    }
};

• 每次 pop 操作都需要将队列头部的元素 (除了最后一个元素外) 重新添加到队列尾部

力扣 no.20

有效的括号

class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 != 0) return false; // 如果s的长度为奇数, 一定不符合要求
        stack<char> st;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') st.push(')');
            else if (s[i] == '{') st.push('}');
            else if (s[i] == '[') st.push(']');
            // 第三种情况: 遍历字符串匹配的过程中, 栈已经为空了, 没有匹配的字符了, 说明右括号没有找到对应的左括号 return false
            // 第二种情况: 遍历字符串匹配的过程中, 发现栈里没有我们要匹配的字符所以return false
            else if (st.empty() || st.top() != s[i]) return false;
            else st.pop(); // st.top() 与 s[i]相等, 栈弹出元素
        }
        // 第一种情况: 此时我们已经遍历完了字符串, 但是栈不为空, 说明有相应的左括号没有右括号来匹配, 所以return false, 否则就return true
        return st.empty();
    }
};

力扣 no.1047

删除字符串中的所有相邻重复项

class Solution {
public:
    string removeDuplicates(string S) {
        string result;
        for(char s : S) {
            if(result.empty() || result.back() != s) {
                result.push_back(s);
            }
            else {
                result.pop_back();
            }
        }
        return result;
    }
};

力扣 no.150

逆波兰表达式求值

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        // 力扣修改了后台测试数据, 需要用longlong
        stack<long long> st; 
        for (int i = 0; i < tokens.size(); i++) {
            if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
                long long num1 = st.top();
                st.pop();
                long long num2 = st.top();
                st.pop();
                if (tokens[i] == "+") st.push(num2 + num1);
                if (tokens[i] == "-") st.push(num2 - num1);
                if (tokens[i] == "*") st.push(num2 * num1);
                if (tokens[i] == "/") st.push(num2 / num1);
            } else {
                st.push(stoll(tokens[i]));
            }
        }

        long long result = st.top();
        st.pop(); // 把栈里最后一个元素弹出（其实不弹出也没事）
        return result;
    }
};

力扣 no.239

滑动窗口最大值

class Solution {
private:
    class MyQueue { //单调队列（从大到小）
    public:
        deque<int> que; // 使用deque来实现单调队列
        // 每次弹出的时候, 比较当前要弹出的数值是否等于队列出口元素的数值, 如果相等则弹出
        // 同时pop之前判断队列当前是否为空
        void pop(int value) {
            if (!que.empty() && value == que.front()) {
                que.pop_front();
            }
        }
        // 如果push的数值大于入口元素的数值, 那么就将队列后端的数值弹出, 直到push的数值小于等于队列入口元素的数值为止
        // 这样就保持了队列里的数值是单调从大到小的了
        void push(int value) {
            while (!que.empty() && value > que.back()) {
                que.pop_back();
            }
            que.push_back(value);

        }
        // 查询当前队列里的最大值 直接返回队列前端也就是front就可以了
        int front() {
            return que.front();
        }
    };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue que;
        vector<int> result;
        for (int i = 0; i < k; i++) { // 先将前k的元素放进队列
            que.push(nums[i]);
        }
        result.push_back(que.front()); // result 记录前k的元素的最大值
        for (int i = k; i < nums.size(); i++) {
            que.pop(nums[i - k]); // 滑动窗口移除最前面元素
            que.push(nums[i]); // 滑动窗口前加入最后面的元素
            result.push_back(que.front()); // 记录对应的最大值
        }
        return result;
    }
};

• 单调队列板子
• 很容易想到新值进入的逻辑, 对于当前最大值出队列只需要知道队列此时接下来的最大值, 因此只保留单调递减的元素即可
• 不需要考虑元素的位次只需要维护队列的最大大小即可

力扣 no.347

前 K 个高频元素

class Solution {
public:
    // 小顶堆
    class mycomparison {
    public:
        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
            return lhs.second > rhs.second;
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // 要统计元素出现频率
        unordered_map<int, int> map; // map<nums[i],对应出现的次数>
        for (int i = 0; i < nums.size(); i++) {
            map[nums[i]]++;
        }

        // 对频率排序
        // 定义一个小顶堆, 大小为k
        priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;

        // 用固定大小为k的小顶堆, 扫面所有频率的数值
        for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
            pri_que.push(*it);
            if (pri_que.size() > k) { // 如果堆的大小大于了K, 则队列弹出, 保证堆的大小一直为k
                pri_que.pop();
            }
        }

        // 找出前K个高频元素, 因为小顶堆先弹出的是最小的, 所以倒序来输出到数组
        vector<int> result(k);
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;

    }
};

// 桶排序
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> counts;
        int max_count = 0;
        for (const int & num : nums) {
            max_count = max(max_count, ++counts[num]);
        }
        vector<vector<int>> buckets(max_count + 1);
        for (const auto & p : counts) {
            buckets[p.second].push_back(p.first);
        }
        vector<int> ans;
        for (int i = max_count; i >= 0 && ans.size() < k; --i) {
            for (const int & num : buckets[i]) {
                ans.push_back(num);
                if (ans.size() == k) {
                    break;
                }
            }
        }
        return ans;
    }
};

• 堆板子
• 桶排序!!!

二叉树

二叉树遍历

• 前序遍历, 中序遍历, 后序遍历, 层序遍历
• 递归遍历, 迭代遍历
• 略

力扣 no.654

最大二叉树

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        int n = nums.size();
        vector<int> stk;
        vector<TreeNode*> tree(n);
        for (int i = 0; i < n; ++i) {
            tree[i] = new TreeNode(nums[i]);
            while (!stk.empty() && nums[i] > nums[stk.back()]) {
                tree[i]->left = tree[stk.back()];
                stk.pop_back();
            }
            if (!stk.empty()) {
                tree[stk.back()]->right = tree[i];
            }
            stk.push_back(i);
        }
        return tree[stk[0]];
    }
};

• 在构建单调栈时, 如果不单调往外出顺手挂上左, 依然单调就挂右

力扣 no.226

翻转二叉树

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()) {
            TreeNode* node = st.top();              // 中
            st.pop();
            swap(node->left, node->right);
            if(node->right) st.push(node->right);   // 右
            if(node->left) st.push(node->left);     // 左
        }
        return root;
    }
};

• 遍历时交换左右子树即可

力扣 no.101

对称二叉树

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right) {
        if (left == NULL && right != NULL) return false;
        else if (left != NULL && right == NULL) return false;
        else if (left == NULL && right == NULL) return true;
        else if (left->val != right->val) return false;
        else return compare(left->left, right->right) && compare(left->right, right->left);

    }
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return compare(root->left, root->right);
    }
};

• 可以迭代
• 本质就是通过相反的遍历顺序, 来 "翻转" 左子树与右子树, 然后比较是否相等

力扣 no.104

二叉树的最大深度

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == NULL) return 0;
        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);
        return 1 + max(leftDepth, rightDepth);
    }
};

• 递归遍历, 取左右子树的最大深度 + 1 即可

力扣 no.111

二叉树的最小深度

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        int leftDepth = minDepth(root->left);
        int rightDepth = minDepth(root->right);
        if (root->left == NULL && root->right != NULL) return 1 + rightDepth;
        else if (root->left != NULL && root->right == NULL) return 1 + leftDepth;
        else return 1 + min(leftDepth, rightDepth);
    }
};

• 递归遍历, 取左右子树的最小深度 + 1 即可
• 注意, 当左子树或右子树为空时, 最小深度为右子树或左子树的深度 + 1

力扣 no.222

完全二叉树的节点个数

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        TreeNode* left = root->left;
        TreeNode* right = root->right;
        int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的, 为了下面求指数方便
        while (left) {  // 求左子树深度
            left = left->left;
            leftDepth++;
        }
        while (right) { // 求右子树深度
            right = right->right;
            rightDepth++;
        }
        if (leftDepth == rightDepth) {
            return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2, 所以leftDepth初始为0
        }
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};

• 利用完全二叉树特性, 将树分为若干满二叉树与其他节点
• 力扣官方题解为二分

力扣 no.110

平衡二叉树

class Solution {
public:
    // 返回以该节点为根节点的二叉树的高度, 如果不是平衡二叉树了则返回-1
    int getHeight(TreeNode* node) {
        if (node == NULL) {
            return 0;
        }
        int leftHeight = getHeight(node->left);
        if (leftHeight == -1) return -1;
        int rightHeight = getHeight(node->right);
        if (rightHeight == -1) return -1;
        return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);
    }
    bool isBalanced(TreeNode* root) {
        return getHeight(root) == -1 ? false : true;
    }
};

• 用 -1 表示已经不是平衡二叉树

力扣 no.257

二叉树的所有路径

class Solution {
private:

    void traversal(TreeNode* cur, string path, vector<string>& result) {
        path += to_string(cur->val); // 中
        if (cur->left == NULL && cur->right == NULL) {
            result.push_back(path);
            return;
        }
        if (cur->left) traversal(cur->left, path + "->", result); // 左
        if (cur->right) traversal(cur->right, path + "->", result); // 右
    }

public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        string path;
        if (root == NULL) return result;
        traversal(root, path, result);
        return result;

    }
};

力扣 no.404

左叶子之和

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == NULL) return 0;
        int leftValue = sumOfLeftLeaves(root->left);    // 左
        int rightValue = sumOfLeftLeaves(root->right);  // 右
        int midValue = 0;
        if (root->left && !root->left->left && !root->left->right) {
            midValue = root->left->val;
        }
        int sum = midValue + leftValue + rightValue;
        return sum;
    }
};

力扣 no.513

找树左下角的值

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        int result = 0;
        if (root == NULL) return result;
        queue<TreeNode*> que;
        que.push(root);
        while (!que.empty()) {
            int size = que.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = que.front();
                que.pop();
                if (i == 0) result = node->val; // 记录最后一行第一个元素
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
        }
        return result;
    }
};

• 层序遍历秒杀

力扣 no.112

路径总和

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == NULL) return false;
        if (root->left == NULL && root->right == NULL) return targetSum == root->val;
        return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
    }
};

力扣 no.113

路径总和 II

class solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    // 递归函数不需要返回值, 因为我们要遍历整个树
    void traversal(TreeNode* cur, int count) {
        if (!cur->left && !cur->right && count == 0) { // 遇到了叶子节点且找到了和为sum的路径
            result.push_back(path);
            return;
        }

        if (!cur->left && !cur->right) return ; // 遇到叶子节点而没有找到合适的边, 直接返回

        if (cur->left) { // 左 （空节点不遍历）
            path.push_back(cur->left->val);
            count -= cur->left->val;
            traversal(cur->left, count);    // 递归
            count += cur->left->val;        // 回溯
            path.pop_back();                // 回溯
        }
        if (cur->right) { // 右 （空节点不遍历）
            path.push_back(cur->right->val);
            count -= cur->right->val;
            traversal(cur->right, count);   // 递归
            count += cur->right->val;       // 回溯
            path.pop_back();                // 回溯
        }
        return ;
    }

public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        result.clear();
        path.clear();
        if (root == NULL) return result;
        path.push_back(root->val); // 把根节点放进路径
        traversal(root, sum - root->val);
        return result;
    }
};

力扣 no.106

从中序与后序遍历序列构造二叉树

class Solution {
private:
    TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {
        if (postorder.size() == 0) return NULL;

        // 后序遍历数组最后一个元素, 就是当前的中间节点
        int rootValue = postorder[postorder.size() - 1];
        TreeNode* root = new TreeNode(rootValue);

        // 叶子节点
        if (postorder.size() == 1) return root;

        // 找到中序遍历的切割点
        int delimiterIndex;
        for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
            if (inorder[delimiterIndex] == rootValue) break;
        }

        // 切割中序数组
        // 左闭右开区间: [0, delimiterIndex)
        vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
        // [delimiterIndex + 1, end)
        vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );

        // postorder 舍弃末尾元素
        postorder.resize(postorder.size() - 1);

        // 切割后序数组
        // 依然左闭右开, 注意这里使用了左中序数组大小作为切割点
        // [0, leftInorder.size)
        vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
        // [leftInorder.size(), end)
        vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());

        root->left = traversal(leftInorder, leftPostorder);
        root->right = traversal(rightInorder, rightPostorder);

        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.size() == 0 || postorder.size() == 0) return NULL;
        return traversal(inorder, postorder);
    }
};

• 以后序数组的最后一个元素为切割点, 先切中序数组, 根据中序数组, 反过来再切后序数组

力扣 no.105

从前序与中序遍历序列构造二叉树

class Solution {
private:
        TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& preorder, int preorderBegin, int preorderEnd) {
        if (preorderBegin == preorderEnd) return NULL;

        int rootValue = preorder[preorderBegin]; // 注意用preorderBegin 不要用0
        TreeNode* root = new TreeNode(rootValue);

        if (preorderEnd - preorderBegin == 1) return root;

        int delimiterIndex;
        for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
            if (inorder[delimiterIndex] == rootValue) break;
        }
        // 切割中序数组
        // 中序左区间, 左闭右开[leftInorderBegin, leftInorderEnd)
        int leftInorderBegin = inorderBegin;
        int leftInorderEnd = delimiterIndex;
        // 中序右区间, 左闭右开[rightInorderBegin, rightInorderEnd)
        int rightInorderBegin = delimiterIndex + 1;
        int rightInorderEnd = inorderEnd;

        // 切割前序数组
        // 前序左区间, 左闭右开[leftPreorderBegin, leftPreorderEnd)
        int leftPreorderBegin =  preorderBegin + 1;
        int leftPreorderEnd = preorderBegin + 1 + delimiterIndex - inorderBegin; // 终止位置是起始位置加上中序左区间的大小size
        // 前序右区间, 左闭右开[rightPreorderBegin, rightPreorderEnd)
        int rightPreorderBegin = preorderBegin + 1 + (delimiterIndex - inorderBegin);
        int rightPreorderEnd = preorderEnd;

        root->left = traversal(inorder, leftInorderBegin, leftInorderEnd,  preorder, leftPreorderBegin, leftPreorderEnd);
        root->right = traversal(inorder, rightInorderBegin, rightInorderEnd, preorder, rightPreorderBegin, rightPreorderEnd);

        return root;
    }

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (inorder.size() == 0 || preorder.size() == 0) return NULL;

        // 参数坚持左闭右开的原则
        return traversal(inorder, 0, inorder.size(), preorder, 0, preorder.size());
    }
};

• 以前序数组的第一个元素为切割点, 先切中序数组, 根据中序数组, 反过来再切前序数组

力扣 no.617

合并二叉树

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if (t1 == NULL) return t2;
        if (t2 == NULL) return t1;
        queue<TreeNode*> que;
        que.push(t1);
        que.push(t2);
        while(!que.empty()) {
            TreeNode* node1 = que.front(); que.pop();
            TreeNode* node2 = que.front(); que.pop();
            // 此时两个节点一定不为空, val相加
            node1->val += node2->val;

            // 如果两棵树左节点都不为空, 加入队列
            if (node1->left != NULL && node2->left != NULL) {
                que.push(node1->left);
                que.push(node2->left);
            }
            // 如果两棵树右节点都不为空, 加入队列
            if (node1->right != NULL && node2->right != NULL) {
                que.push(node1->right);
                que.push(node2->right);
            }

            // 当t1的左节点 为空 t2左节点不为空, 就赋值过去
            if (node1->left == NULL && node2->left != NULL) {
                node1->left = node2->left;
            }
            // 当t1的右节点 为空 t2右节点不为空, 就赋值过去
            if (node1->right == NULL && node2->right != NULL) {
                node1->right = node2->right;
            }
        }
        return t1;
    }
};

• 其实用指针迭代遍历就行

力扣 no.700

二叉搜索树中的搜索

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == NULL || root->val == val) return root;
        TreeNode* result = NULL;
        if (root->val > val) result = searchBST(root->left, val);
        if (root->val < val) result = searchBST(root->right, val);
        return result;
    }
};

力扣 no.98

验证二叉搜索树

class Solution {
public:
    TreeNode* pre = NULL; // 用来记录前一个节点
    bool isValidBST(TreeNode* root) {
        if (root == NULL) return true;
        bool left = isValidBST(root->left);

        if (pre != NULL && pre->val >= root->val) return false;
        pre = root; // 记录前一个节点

        bool right = isValidBST(root->right);
        return left && right;
    }
};

• 就是中序遍历有序性

力扣 no.530

二叉搜索树的最小绝对差

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        TreeNode* pre = NULL;
        int result = INT_MAX;
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) { // 指针来访问节点, 访问到最底层
                st.push(cur); // 将访问的节点放进栈
                cur = cur->left;                // 左
            } else {
                cur = st.top();
                st.pop();
                if (pre != NULL) {              // 中
                    result = min(result, cur->val - pre->val);
                }
                pre = cur;
                cur = cur->right;               // 右
            }
        }
        return result;
    }
};

• 同上

力扣 no.501

二叉搜索树中的众数

//略

• 同上

力扣 no.236

二叉树的最近公共祖先

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == q || root == p || root == NULL) return root; // 遇到空返回
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (left != NULL && right != NULL) return root; // 左右都不为空, 说明根节点就是最近公共祖先
        else if (left == NULL && right != NULL) return right; // 左空右有, 返回右
        else if (left != NULL && right == NULL) return left; // 左有右空, 返回左
        else  { // (left == NULL && right == NULL)
            return NULL;
        }
    }
};

• 后序遍历
• 左右各有一个节点, 说明根节点就是最近公共祖先

力扣 no.235

二叉搜索树的最近公共祖先

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        int l = min(p->val, q->val),r = max(p->val, q->val);
        while(root){
            if (root->val > r) root = root -> left;
            else if (root->val < l) root = root -> right;
            else return root;
        }
        return root;
    }
};

力扣 no.701

二叉搜索树中的插入操作

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == nullptr) {
            return new TreeNode(val);
        }
        TreeNode* pos = root;
        while (pos != nullptr) {
            if (val < pos->val) {
                if (pos->left == nullptr) {
                    pos->left = new TreeNode(val);
                    break;
                } else {
                    pos = pos->left;
                }
            } else {
                if (pos->right == nullptr) {
                    pos->right = new TreeNode(val);
                    break;
                } else {
                    pos = pos->right;
                }
            }
        }
        return root;
    }
};

• 找不到就插

力扣 no.450

删除二叉搜索树中的节点

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) {
            return nullptr;
        }
        if (root->val > key) {
            root->left = deleteNode(root->left, key);
            return root;
        }
        if (root->val < key) {
            root->right = deleteNode(root->right, key);
            return root;
        }
        if (root->val == key) {
            if (!root->left && !root->right) {
                return nullptr;
            }
            if (!root->right) {
                return root->left;
            }
            if (!root->left) {
                return root->right;
            }
            TreeNode *successor = root->right;
            while (successor->left) {
                successor = successor->left;
            }
            root->right = deleteNode(root->right, successor->val);
            successor->right = root->right;
            successor->left = root->left;
            return successor;
        }
        return root;
    }
};

• 先找到目标节点, 然后看左右子树, 如果都有, 把后继给填上就可以

力扣 no.669

修剪二叉搜索树

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (root == nullptr) {
            return nullptr;
        }
        if (root->val < low) {
            return trimBST(root->right, low, high);
        } else if (root->val > high) {
            return trimBST(root->left, low, high);
        } else {
            root->left = trimBST(root->left, low, high);
            root->right = trimBST(root->right, low, high);
            return root;
        }
    }
};

• 对于每个节点只需要管自己在不在就行

力扣 no.108

将有序数组转换为二叉搜索树

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return helper(nums, 0, nums.size() - 1);
    }

    TreeNode* helper(vector<int>& nums, int left, int right) {
        if (left > right) {
            return nullptr;
        }

        // 选择任意一个中间位置数字作为根节点
        int mid = (left + right + rand() % 2) / 2;

        TreeNode* root = new TreeNode(nums[mid]);
        root->left = helper(nums, left, mid - 1);
        root->right = helper(nums, mid + 1, right);
        return root;
    }
};

• 每次取中间点, 递归构建左右子树

力扣 no.538

把二叉搜索树转换为累加树

class Solution {
public:
    int sum = 0;
    TreeNode* convertBST(TreeNode* root) {
        if (!root) return 0; 
        convertBST(root->right);
        sum+=root ->val;
        root ->val =sum;
        convertBST(root->left);
        return root;
    }
};

• 从右到左中序遍历, 累加即可

回溯

力扣 no.77

组合

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(int n, int k, int startIndex) {
        if (path.size() == k) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) { // 优化的地方
            path.push_back(i); // 处理节点
            backtracking(n, k, i + 1);
            path.pop_back(); // 回溯, 撤销处理的节点
        }
    }
public:

    vector<vector<int>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }
};

• 回溯板子
• 回溯有选和不选, 枚举选两种写法
• 可以状态压缩, 降低空间

力扣 no.216

组合总和 III

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    int sum;
    void backtracking(int n, int k, int startIndex) {
        if (path.size() == k&&sum == n) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i <=9; i++) {
            path.push_back(i); // 处理节点
            sum+=i;
            backtracking(n, k, i + 1);
            path.pop_back(); // 回溯, 撤销处理的节点
            sum -=i;
        }
    }
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        backtracking(n, k, 1);
        return result;
    }
};

• 回溯板子
• 也可以状态压缩

力扣 no.17

电话号码的字母组合

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> combinations;
        if (digits.empty()) {
            return combinations;
        }
        unordered_map<char, string> phoneMap{
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
        };
        string combination;
        backtrack(combinations, phoneMap, digits, 0, combination);
        return combinations;
    }

    void backtrack(vector<string>& combinations, const unordered_map<char, string>& phoneMap, const string& digits, int index, string& combination) {
        if (index == digits.length()) {
            combinations.push_back(combination);
        } else {
            char digit = digits[index];
            const string& letters = phoneMap.at(digit);
            for (const char& letter: letters) {
                combination.push_back(letter);
                backtrack(combinations, phoneMap, digits, index + 1, combination);
                combination.pop_back();
            }
        }
    }
};

• 回溯板子

力扣 no.39

组合总和

class Solution {
public:
    void dfs(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& combine, int idx) {
        if (idx == candidates.size()) {
            return;
        }
        if (target == 0) {
            ans.emplace_back(combine);
            return;
        }
        // 直接跳过
        dfs(candidates, target, ans, combine, idx + 1);
        // 选择当前数
        if (target - candidates[idx] >= 0) {
            combine.emplace_back(candidates[idx]);
            dfs(candidates, target - candidates[idx], ans, combine, idx);
            combine.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        vector<int> combine;
        dfs(candidates, target, ans, combine, 0);
        return ans;
    }
};

• 可重复选, 依旧回溯

力扣 no.40

组合总和 II

class Solution {
private:
    vector<pair<int, int>> freq;
    vector<vector<int>> ans;
    vector<int> sequence;

public:
    void dfs(int pos, int rest) {
        if (rest == 0) {
            ans.push_back(sequence); // 找到一个组合
            return;
        }
        if (pos == freq.size() || rest < freq[pos].first) {
            return; // 超过边界, 或者剩余值小于当前数
        }

        dfs(pos + 1, rest); // 不选当前数

        int most = min(rest / freq[pos].first, freq[pos].second); // 最多选当前数的次数
        for (int i = 1; i <= most; ++i) { 
            sequence.push_back(freq[pos].first); // 选当前数
            dfs(pos + 1, rest - i * freq[pos].first); // 递归到下一层
        }
        for (int i = 1; i <= most; ++i) {
            sequence.pop_back(); // 回溯, 撤销选当前数
        }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        for (int num: candidates) {
            if (freq.empty() || num != freq.back().first) {
                freq.emplace_back(num, 1); // 统计每个数出现的次数
            } else {
                ++freq.back().second;
            }
        }
        dfs(0, target);
        return ans;
    }
};

• 预处理出所有数出现的次数
• 回溯, 选项是当前数的选择数量

力扣 no.131

分割回文串

class Solution {
private:
    vector<vector<int>> f;
    vector<vector<string>> ret;
    vector<string> ans;
    int n;

public:
    void dfs(const string& s, int i) {
        if (i == n) {
            ret.push_back(ans);
            return;
        }
        for (int j = i; j < n; ++j) {
            if (f[i][j]) {
                ans.push_back(s.substr(i, j - i + 1));
                dfs(s, j + 1);
                ans.pop_back();
            }
        }
    }

    vector<vector<string>> partition(string s) {
        n = s.size();
        f.assign(n, vector<int>(n, true));

        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                f[i][j] = (s[i] == s[j]) && f[i + 1][j - 1];
            }
        }

        dfs(s, 0);
        return ret;
    }
};

• DP 预处理出所有回文串
• 回溯, 选项变成当前数开始所有回文串

力扣 no.93

复原 IP 地址

class Solution {
private:
    static constexpr int SEG_COUNT = 4;

private:
    vector<string> ans;
    vector<int> segments;

public:
    void dfs(const string& s, int segId, int segStart) {
        // 如果找到了 4 段 IP 地址并且遍历完了字符串, 那么就是一种答案
        if (segId == SEG_COUNT) {
            if (segStart == s.size()) {
                string ipAddr;
                for (int i = 0; i < SEG_COUNT; ++i) {
                    ipAddr += to_string(segments[i]);
                    if (i != SEG_COUNT - 1) {
                        ipAddr += ".";
                    }
                }
                ans.push_back(move(ipAddr));
            }
            return;
        }

        // 如果还没有找到 4 段 IP 地址就已经遍历完了字符串, 那么提前回溯
        if (segStart == s.size()) {
            return;
        }

        // 由于不能有前导零, 如果当前数字为 0, 那么这一段 IP 地址只能为 0
        if (s[segStart] == '0') {
            segments[segId] = 0;
            dfs(s, segId + 1, segStart + 1);
            return;
        }

        // 一般情况, 枚举每一种可能性并递归
        int addr = 0;
        for (int segEnd = segStart; segEnd < s.size(); ++segEnd) {
            addr = addr * 10 + (s[segEnd] - '0');
            if (addr > 0 && addr <= 0xFF) {
                segments[segId] = addr;
                dfs(s, segId + 1, segEnd + 1);
            } else {
                break;
            }
        }
    }

    vector<string> restoreIpAddresses(string s) {
        segments.resize(SEG_COUNT);
        dfs(s, 0, 0);
        return ans;
    }
};

• 回溯

力扣 no.78

子集

class Solution {
private:
    vector<vector<int>> ans;
    vector<int> path;

public:
    void dfs(vector<int>& nums, int start) {
        ans.push_back(path); // 找到一个子集
        if (start == nums.size()) {
            return; // 超过边界
        }
        for (int i = start; i < nums.size(); ++i) {
            path.push_back(nums[i]); // 选当前数
            dfs(nums, i + 1); // 递归到下一层
            path.pop_back(); // 回溯, 撤销选当前数
        }
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return ans;
    }
};

• 板子

力扣 no.90

子集 II

class Solution {
private:
    vector<vector<int>> ans;
    vector<int> path;

public:
    void dfs(vector<int>& nums, int start) {
        ans.push_back(path); // 找到一个子集
        if (start == nums.size()) {
            return; // 超过边界
        }
        for (int i = start; i < nums.size(); ++i) {
            if (i > start && nums[i] == nums[i - 1]) { // 去重但不考虑 start 与 start 前一个
                continue;                             // 所以不会忽略重复元素多次出现的解
            }
            path.push_back(nums[i]); // 选当前数 // 第一个无脑选, 不会错过
            dfs(nums, i + 1); // 递归到下一层
            path.pop_back(); // 回溯, 撤销选当前数
        }
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end()); // 排序, 方便去重
        dfs(nums, 0);
        return ans;
    }
};

• 看注释

力扣 no.491

非递减子序列

class Solution {
public:
    vector<int> temp; 
    vector<vector<int>> ans;

    void dfs(int cur, int last, vector<int>& nums) {
        if (cur == nums.size()) { // 遍历完所有数
            if (temp.size() >= 2) { // 找到一个非递减子序列
                ans.push_back(temp);
            }
            return;
        }
        if (nums[cur] >= last) { // 大选, 等选
            temp.push_back(nums[cur]);
            dfs(cur + 1, nums[cur], nums);
            temp.pop_back(); // 回溯
        }
        if (nums[cur] != last) { // 小不选, 大不选
            // 没有等于的情况, 这使得避免 [4,7,7,8] 中 [4,7] [4,7] 这样的重复
            dfs(cur + 1, last, nums); // 但第二个 7 会被选到, 不会错过 [4,7,8]
        }
    }

    vector<vector<int>> findSubsequences(vector<int>& nums) {
        dfs(0, INT_MIN, nums);
        return ans;
    }
};

力扣 no.46

全排列

class Solution {
public:
    void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){
        // 所有数都填完了
        if (first == len) {
            res.emplace_back(output);
            return;
        }
        for (int i = first; i < len; ++i) {
            // 动态维护数组
            swap(output[i], output[first]); // 选择
            // 继续递归填下一个数
            backtrack(res, output, first + 1, len);
            // 撤销操作
            swap(output[i], output[first]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > res;
        backtrack(res, nums, 0, (int)nums.size());
        return res;
    }
};

• 通过选择不同的数, 来构造不同的排列
• 类似选择排序, \(O(1)\) 空间

力扣 no.47

全排列 II

class Solution {
    vector<int> vis;

public:
    void backtrack(vector<int>& nums, vector<vector<int>>& ans, int idx, vector<int>& perm) {
        if (idx == nums.size()) {
            ans.emplace_back(perm);
            return;
        }
        for (int i = 0; i < (int)nums.size(); ++i) {
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                continue;
            }
            perm.emplace_back(nums[i]);
            vis[i] = 1;
            backtrack(nums, ans, idx + 1, perm);
            vis[i] = 0;
            perm.pop_back();
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> perm;
        vis.resize(nums.size());
        sort(nums.begin(), nums.end()); // 排序, 方便去重
        backtrack(nums, ans, 0, perm);
        return ans;
    }
};

• 不能原地, 否则会改变原数组的顺序

力扣 no.332

重新安排行程

class Solution {
public:
    unordered_map<string, priority_queue<string, vector<string>, std::greater<string>>> vec;

    vector<string> stk;

    void dfs(const string& curr) {
        while (vec.count(curr) && vec[curr].size() > 0) {
            string tmp = vec[curr].top();
            vec[curr].pop();
            dfs(move(tmp));
        }
        stk.emplace_back(curr);
    }

    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for (auto& it : tickets) {
            vec[it[0]].emplace(it[1]);
        }
        dfs("JFK");

        reverse(stk.begin(), stk.end());
        return stk;
    }
};

• 欧拉图 / 半欧拉图
• 整个图最多存在一个死胡同 (出度和入度相差1), 且这个死胡同一定是最后一个访问到的, 否则无法完成一笔画
• DFS的调用其实是一个拆边的过程 (既每次递归调用删除一条边, 所有子递归都返回后, 再将当前节点加入结果集保证了结果集的逆序输出), 一定是递归到这个死胡同 (没有子递归可以调用), 后递归函数开始返回, 所以死胡同是第一个加入结果集的元素

力扣 no.51

N 皇后

class Solution {
public:
    vector<vector<string>> res;
    vector<string> t;

    // 一行只能存在一个皇后,  故按行递归
    void backtrack(int n, int cur){
        if(cur == n){
            res.push_back(t);
            return;
        }

        for(int j = 0;j < n;j++){
            if(is_valid(n, cur, j)){
                t[cur][j] = 'Q';
                backtrack(n, cur + 1);
                t[cur][j] = '.';
            }
        }
    }

    bool is_valid(int n, int row, int col){
        int nrow = row;
        int ncol = col;
        // 是否同列
        for(int i = 0;i < nrow;i++){
            if(t[i][ncol] == 'Q') return false;
        }
        // 是否正对角
        for(int i = nrow, j = ncol;i >=0 && j >= 0;--i,--j){
            if(t[i][j] == 'Q') return false;
        }
        // 是否反对角
        for(int i = nrow, j = ncol;i >=0 && j <= n;--i,++j){
            if(t[i][j] == 'Q') return false;
        }

        return true;
    }

    vector<vector<string>> solveNQueens(int n) {
        // 初始化棋盘矩阵
        t.resize(n, string(n, '.'));

        backtrack(n, 0);
        return res;
    }
};

• 回溯简单, 判断是否合法是重点
• 可以标记行列斜线, 可以用位运算压缩状态

力扣 no.37

解数独

class Solution {
private:
    int line[9];          // 行掩码: line[i] 的第 d 位为 1 表示第 i 行已存在数字 d+1
    int column[9];        // 列掩码: column[j] 的第 d 位为 1 表示第 j 列已存在数字 d+1
    int block[3][3];      // 3*3 宫掩码: block[bx][by] 的第 d 位为 1 表示对应宫已存在数字 d+1
    bool valid;           // 标记是否已找到合法解
    vector<pair<int, int>> spaces; // 待填空格坐标列表

    // 翻转数字 d 在 (i,j) 处的存在状态（异或 1<<d）
    void flip(int i, int j, int digit) {
        line[i] ^= (1 << digit);
        column[j] ^= (1 << digit);
        block[i / 3][j / 3] ^= (1 << digit);
    }

    // 回溯填空格
    void dfs(vector<vector<char>>& board, int pos) {
        if (pos == spaces.size()) { // 所有空格处理完毕
            valid = true;
            return;
        }

        auto [i, j] = spaces[pos];
        // 计算可用数字掩码: 9 位二进制, 0 表示可用
        int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff;
        // 枚举所有可用数字（lowbit 技巧）
        for (; mask && !valid; mask &= (mask - 1)) {
            int digitMask = mask & (-mask);
            int digit = __builtin_ctz(digitMask); // 数字 0~8 对应实际 1~9
            flip(i, j, digit);                    // 占位
            board[i][j] = digit + '0' + 1;        // 填入字符
            dfs(board, pos + 1);                  // 递归下一个空格
            flip(i, j, digit);                    // 回溯
        }
    }

public:
    void solveSudoku(vector<vector<char>>& board) {
        memset(line, 0, sizeof(line));
        memset(column, 0, sizeof(column));
        memset(block, 0, sizeof(block));
        valid = false;

        // 1. 读取初始盘面, 记录已存在数字
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] != '.') {
                    int digit = board[i][j] - '0' - 1;
                    flip(i, j, digit);
                }
            }
        }

        // 2. 唯一候选法: 不断填入唯一可填数字, 直到无法继续
        while (true) {
            int modified = false;
            for (int i = 0; i < 9; ++i) {
                for (int j = 0; j < 9; ++j) {
                    if (board[i][j] == '.') {
                        int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff;
                        if (!(mask & (mask - 1))) { // 仅 1 个候选
                            int digit = __builtin_ctz(mask);
                            flip(i, j, digit);
                            board[i][j] = digit + '0' + 1;
                            modified = true;
                        }
                    }
                }
            }
            if (!modified) break;
        }

        // 3. 收集剩余空格
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    spaces.emplace_back(i, j);
                }
            }
        }

        // 4. 回溯求解
        dfs(board, 0);
    }
};

• 同上

贪心

力扣 no.455

分发饼干

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int m = g.size(), n = s.size();
        int count = 0;
        for (int i = 0, j = 0; i < m && j < n; i++, j++) {
            while (j < n && g[i] > s[j]) {
                j++;
            }
            if (j < n) {
                count++;
            }
        }
        return count;
    }
};

力扣 no.376

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) {
            return n;
        }
        int prevdiff = nums[1] - nums[0];
        int ret = prevdiff != 0 ? 2 : 1;
        for (int i = 2; i < n; i++) {
            int diff = nums[i] - nums[i - 1];
            if ((diff > 0 && prevdiff <= 0) || (diff < 0 && prevdiff >= 0)) {
                ret++;
                prevdiff = diff;
            }
        }
        return ret;
    }
};

• 贪心

力扣 no.53

最大子数组和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre = 0, maxAns = nums[0];
        for (const auto &x: nums) {
            pre = max(pre + x, x);
            maxAns = max(maxAns, pre);
        }
        return maxAns;
    }
};

• 贪心 + DP

力扣 no.122

买卖股票的最佳时机 II

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        int n = prices.size();
        for (int i = 1; i < n; ++i) {
            ans += max(0, prices[i] - prices[i - 1]);
        }
        return ans;
    }
};

力扣 no.55

跳跃游戏

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int rightmost = 0;
        for (int i = 0; i < n; ++i) {
            if (i <= rightmost) {
                rightmost = max(rightmost, i + nums[i]);
                if (rightmost >= n - 1) {
                    return true;
                }
            }
        }
        return false;
    }
};

• 贪心

力扣 no.45

跳跃游戏 II

class Solution {
public:
    int jump(vector<int>& nums) {
        int maxPos = 0, n = nums.size(), end = 0, step = 0;
        for (int i = 0; i < n - 1; ++i) {
            if (maxPos >= i) {
                maxPos = max(maxPos, i + nums[i]);
                if (i == end) {
                    end = maxPos;
                    ++step;
                }
            }
        }
        return step;
    }
};

• 贪心

力扣 no.1005

K 次取反后最大化的数组和

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int i = 0;
        while (i < n && k > 0) {
            if (nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
                i++;
            } else {
                break;
            }
        }
        if (k > 0 && k % 2 == 1) {
            sort(nums.begin(), nums.end());
            nums[0] = -nums[0];
        }
        int ans = 0;
        for (int num : nums) {
            ans += num;
        }
        return ans;
    }
};

• 排序 + 贪心

力扣 no.134

加油站

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int i = 0;
        while (i < n) {
            int sumOfGas = 0, sumOfCost = 0;
            int cnt = 0;
            while (cnt < n) {
                int j = (i + cnt) % n;
                sumOfGas += gas[j];
                sumOfCost += cost[j];
                if (sumOfCost > sumOfGas) {
                    break;
                }
                cnt++;
            }
            if (cnt == n) {
                return i;
            } else {
                i = i + cnt + 1;
            }
        }
        return -1;
    }
};

• 贪心

力扣 no.135

分发糖果

class Solution {
   public int candy(int[] ratings) {
       int n = ratings.length;
       int ret = 1;    //用于记录答案
       //pre用于记录前一个同学分得的糖果数量
       int inc = 1, dec = 0, pre = 1;
       for (int i = 1; i < n; i++) {
           if(ratings[i] >= ratings[i-1]){
               //处于递增序列中
               dec = 0;    //递减序列长度在递增序列中始终为0
               pre = ratings[i] == ratings[i- 1] ? 1 : pre+1;  //当前同学和上一个同学分数相等时, 直接分配1个就行, 这样满足最小
               ret += pre;
               inc = pre;      //inc用于记录上一个递增序列的长度

           }else {
               //处于递减序列中
               dec++;
               if(dec == inc){
                   //当递减序列长度和递增序列长度相等时, 把递增序列的最后一个同学分配到递减序列中
                   dec++;
               }
               ret += dec; //这里加的dec相当于把递减序列翻转后加的每个同学的糖果数量
               pre = 1;    //pre在递减序列中没有意义, 因为我肯定比前一个同学少；

           }
       }
       return ret;

   }
}

• 贪心

力扣 no.860

柠檬水找零

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        int five = 0, ten = 0;
        for (int bill : bills) {
            if (bill == 5) {
                five++;
            } else if (bill == 10) {
                if (five == 0) {
                    return false;
                }
                five--;
                ten++;
            } else {
                if (five > 0 && ten > 0) {
                    five--;
                    ten--;
                } else if (five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
};

• 贪心

力扣 no.406

根据身高重建队列

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), [](const vector<int>& u, const vector<int>& v) {
            return u[0] < v[0] || (u[0] == v[0] && u[1] > v[1]);
        });
        int n = people.size();
        vector<vector<int>> ans(n);
        for (const vector<int>& person: people) {
            int spaces = person[1] + 1;
            for (int i = 0; i < n; ++i) {
                if (ans[i].empty()) {
                    --spaces;
                    if (!spaces) {
                        ans[i] = person;
                        break;
                    }
                }
            }
        }
        return ans;
    }
};

• 一眼正解, 在想数据结构快速确定前空位数量
• 结果答案 \(O(n^2)\)

力扣 no.452

用最少数量的箭引爆气球

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if (points.empty()) {
            return 0;
        }
        sort(points.begin(), points.end(), [](const vector<int>& u, const vector<int>& v) {
            return u[1] < v[1];
        });
        int pos = points[0][1];
        int ans = 1;
        for (const vector<int>& balloon: points) {
            if (balloon[0] > pos) {
                pos = balloon[1];
                ++ans;
            }
        }
        return ans;
    }
};

• 排序 + 贪心

力扣 no.435

无重叠区间

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) {
            return 0;
        }
        sort(intervals.begin(), intervals.end(), [](const vector<int>& u, const vector<int>& v) {
            return u[1] < v[1];
        });
        int n = intervals.size();
        int right = intervals[0][1];
        int ans = 1;
        for (int i = 1; i < n; ++i) {
            if (intervals[i][0] >= right) {
                ++ans;
                right = intervals[i][1];
            }
        }
        return n - ans;
    }
};

• 右端点排序 + 贪心选择靠前的
• 好好悟一下, 发现等效最长上升子序列

力扣 no.763

划分字母区间

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) {
            return 0;
        }
        sort(intervals.begin(), intervals.end(), [](const vector<int>& u, const vector<int>& v) {
            return u[1] < v[1];
        });
        int n = intervals.size();
        int right = intervals[0][1];
        int ans = 1;
        for (int i = 1; i < n; ++i) {
            if (intervals[i][0] >= right) {
                ++ans;
                right = intervals[i][1];
            }
        }
        return n - ans;
    }
};

• 记录每个字母的最后一次出现, 然后左指针开始遍历
• 右指针去调整最小的范围, 就是当前区间内所有字母当中的最大最后一次出现, 直到追逐上结束

力扣 no.56

合并区间

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.empty()) {
            return {};
        }
        sort(intervals.begin(), intervals.end(), [](const vector<int>& u, const vector<int>& v) {
            return u[0] < v[0];
        });
        vector<vector<int>> ans;
        int left = intervals[0][0], right = intervals[0][1];
        for (const vector<int>& interval: intervals) {
            if (interval[0] > right) {
                ans.push_back({left, right});
                left = interval[0];
                right = interval[1];
            } else {
                right = max(right, interval[1]);
            }
        }
        ans.push_back({left, right});
        return ans;
    }
};

• 排序 + 贪心
• 一看前几题, easy

力扣 no.738

单调递增的数字

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string strN = to_string(n);
        int i = 1;
        while (i < strN.length() && strN[i - 1] <= strN[i]) {
            i += 1;
        }
        if (i < strN.length()) {
            while (i > 0 && strN[i - 1] > strN[i]) {
                strN[i - 1] -= 1;
                i -= 1;
            }
            for (i += 1; i < strN.length(); ++i) {
                strN[i] = '9';
            }
        }
        return stoi(strN);
    }
};

• 找到第一个不满足递增的位置, 然后减一, 后面全变成 \(9\)
• 注意是第一个与不满足递增的位置的前一个数相等的位置 (防止减一破坏已有序列)

力扣 no.968

监控二叉树

// 版本二
class Solution {
private:
    int result;
    int traversal(TreeNode* cur) {
        if (cur == NULL) return 2;
        int left = traversal(cur->left);    // 左
        int right = traversal(cur->right);  // 右
        if (left == 2 && right == 2) return 0;
        else if (left == 0 || right == 0) {
            result++;
            return 1;
        } else return 2;
    }
public:
    int minCameraCover(TreeNode* root) {
        result = 0;
        if (traversal(root) == 0) { // root 无覆盖
            result++;
        }
        return result;
    }
};

• 后序遍历获取全部信息
• 自下向上贪心

动态规划

力扣 no.509

class Solution {
public:
    int fib(int n) {
        if (n < 2) {
            return n;
        }
        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
};

• 正解矩阵快速幂 / 通项公式

力扣 no.70

爬楼梯

class Solution {
public:
    int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
};

• 同上

力扣 no.746

使用最小花费爬楼梯

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        int prev = 0, curr = 0;
        for (int i = 2; i <= n; i++) {
            int next = min(curr + cost[i - 1], prev + cost[i - 2]);
            prev = curr;
            curr = next;
        }
        return curr;
    }
};

力扣 no.62

不同路径

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> f(m, vector<int>(n));
        for (int i = 0; i < m; ++i) {
            f[i][0] = 1;
        }
        for (int j = 0; j < n; ++j) {
            f[0][j] = 1;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }
        return f[m - 1][n - 1];
    }
};

• 正解组合数学 \(C_{m+n-2}^{m-1}\)

力扣 no.63

不同路径 II

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int n = obstacleGrid.size(), m = obstacleGrid.at(0).size();
        vector <int> f(m);

        f[0] = (obstacleGrid[0][0] == 0);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (obstacleGrid[i][j] == 1) {
                    f[j] = 0;
                    continue;
                }
                if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
                    f[j] += f[j - 1];
                }
            }
        }

        return f.back();
    }
};

力扣 no.343

整数拆分

class Solution {
public:
    int integerBreak(int n) {
        vector <int> dp(n + 1);
        for (int i = 2; i <= n; i++) {
            int curMax = 0;
            for (int j = 1; j < i; j++) {
                curMax = max(curMax, max(j * (i - j), j * dp[i - j]));
            }
            dp[i] = curMax;
        }
        return dp[n];
    }
};

// 正解
class Solution {
public:
    int integerBreak(int n) {
        if (n <= 3) {
            return n - 1;
        }
        int quotient = n / 3;
        int remainder = n % 3;
        if (remainder == 0) {
            return (int)pow(3, quotient);
        } else if (remainder == 1) {
            return (int)pow(3, quotient - 1) * 4;
        } else {
            return (int)pow(3, quotient) * 2;
        }
    }
};

• dp[i] 表示将整数 i 拆分成至少两个正整数的和之后, 这些正整数的最大乘积
• 状态转移方程: dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j])), j 在 \([1, i)\) 之间
• 对于大于 4 的正整数, 总是存在一种拆分的方案, 使得拆分成的两个正整数的乘积大于拆分前的正整数
  • 简化为: dp[i] = max(max(2 * (i - 2), 2 * dp[i - 2]), max(3 * (i - 3), 3 * dp[i - 3]))
• 将 \(4\) 拆分为 \(2^2\) 是等效的, \(3^2\) 优于 \(2^3\), 故正解为尽可能拆分为 \(3\), \(2\) 不多于两个 (\(2^2\) 优于 \(3^1\))

力扣 no.96

不同的二叉搜索树

class Solution {
public:
    int numTrees(int n) {
        vector<int> G(n + 1, 0);
        G[0] = 1;
        G[1] = 1;

        for (int i = 2; i <= n; ++i) { // 遍历所有根节点数为 i 的情况
            for (int j = 1; j <= i; ++j) { // 遍历所有左子树节点数为 j 的情况
                G[i] += G[j - 1] * G[i - j]; // 左子树节点数为 j - 1, 右子树节点数为 i - j
            }
        }
        return G[n];
    }
};

• 本质上就是卡塔兰数

\[ C_0=1, C_{n+1} = \frac{2(2n+1)}{n+2} C_n \]

0-1 背包

• dp[i][j] 表示前 i 个物品, 背包容量为 j 时的最大价值
• 状态转移方程: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]), \(w[i]\) 为第 i 个物品的重量, \(v[i]\) 为第 i 个物品的价值
• 初始化: dp[i][0] = 0, \(i \in [0, N]\)
• 答案: dp[N][W], \(N\) 为物品数量, \(W\) 为背包容量
• 由于 dp[i][j] 只与 dp[i - 1][j] 和 dp[i - 1][j - w[i]] 相关, 可以将空间复杂度优化为 \(O(W)\) (滚动数组)

力扣 no.416

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) {
            return false;
        }
        int sum = 0, maxNum = 0;
        for (auto& num : nums) {
            sum += num;
            maxNum = max(maxNum, num);
        }
        if (sum & 1) {
            return false;
        }
        int target = sum / 2;
        if (maxNum > target) {
            return false;
        }
        vector<int> dp(target + 1, 0);
        dp[0] = true;
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            for (int j = target; j >= num; --j) {
                dp[j] |= dp[j - num];
            }
        }
        return dp[target];
    }
};

• dp[i][j] 表示前 i 个数, 能否凑出和为 j
• 显然上一层能, 下一层就能, 否则看上一层能否凑出来 dp[i-1][j - nums[i]]
• 贪心是错的!!! 这是一个 NP 完全问题

力扣 no.1049

最后一块石头的重量 II

class Solution {
public:
    int lastStoneWeightII(vector<int> &stones) {
        int sum = accumulate(stones.begin(), stones.end(), 0);
        int n = stones.size(), m = sum / 2;
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        dp[0][0] = true;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= m; ++j) {
                if (j < stones[i]) {
                    dp[i + 1][j] = dp[i][j];
                } else {
                    dp[i + 1][j] = dp[i][j] || dp[i][j - stones[i]];
                }
            }
        }
        for (int j = m;; --j) {
            if (dp[n][j]) {
                return sum - 2 * j;
            }
        }
    }
};

• 答案为 sum - 2 * j, \(j\) 为尽可能接近 sum / 2 的和

力扣 no.494

目标和

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (int& num : nums) {
            sum += num;
        }
        int diff = sum - target;
        if (diff < 0 || diff % 2 != 0) {
            return 0;
        }
        int neg = diff / 2;
        vector<int> dp(neg + 1);
        dp[0] = 1;
        for (int& num : nums) {
            for (int j = neg; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        return dp[neg];
    }
};

力扣 no.474

一和零

class Solution {
public:
    vector<int> getZerosOnes(string& str) { // 统计字符串中 0 和 1 的数量
        vector<int> zerosOnes(2);
        int length = str.length();
        for (int i = 0; i < length; i++) {
            zerosOnes[str[i] - '0']++;
        }
        return zerosOnes;
    }

    int findMaxForm(vector<string>& strs, int m, int n) {
        int length = strs.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 0; i < length; i++) { // 遍历所有字符串
            vector<int>&& zerosOnes = getZerosOnes(strs[i]);
            int zeros = zerosOnes[0], ones = zerosOnes[1];
            for (int j = m; j >= zeros; j--) { // 遍历所有 0 的最多数量为 j 的情况
                for (int k = n; k >= ones; k--) { // 遍历所有 1 的最多数量为 k 的情况
                    dp[j][k] = max(dp[j][k], dp[j - zeros][k - ones] + 1);
                }
            }
        }
        return dp[m][n];
    }
};

• 0-1 背包的三维变种

完全背包

• dp[i][j] 表示前 i 个物品, 背包容量为 j 时的最大价值
• 状态转移方程: dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i]), \(w[i]\) 为第 i 个物品的重量, \(v[i]\) 为第 i 个物品的价值
• 初始化: dp[i][0] = 0, \(i \in [0, N]\)
• 答案: dp[N][W], \(N\) 为物品数量, \(W\) 为背包容量
• 遍历顺序
  • 求最大值 -> 都可以
  • 求组合数 -> 先遍历物品, 再遍历背包
  • 求排列数 -> 先遍历背包, 再遍历物品

力扣 no.518

零钱兑换 II

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1, 0);
        dp[0] = 1;

        for (int i = 0; i < coins.size(); i++) {
            for (int j = coins[i]; j < amount+1; j++) {
                // 用例中有相加超过INT最大值的例子，因此加一个判断。由于最终结果一定还可以用INT表示，因此筛掉这种情况在最终的运行结果上不会有区别
                // 并且做出这个判断时，要避免进行加和操作，而要用减法来代替
                if (dp[j] < INT_MAX - dp[j - coins[i]]) { 
                    dp[j] += dp[j - coins[i]];
                }
            }
        }
        return dp[amount];
    }
};

力扣 no.377

组合总和 Ⅳ

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<unsigned long long> dp(target+1, 0);
        dp[0] = 1;

        for (int j = 1; j <= target; j++) {
            for (int i :nums) {
                if (j-i>=0) { 
                    dp[j] += dp[j - i];
                }
            }
        }
        return dp[target];
    }
};

卡码网 no.57

爬楼梯

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, m;
    while (cin >> n >> m) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) { // 遍历背包
            for (int j = 1; j <= m; j++) { // 遍历物品
                if (i - j >= 0) dp[i] += dp[i - j];
            }
        }
        cout << dp[n] << endl;
    }
}

力扣 no.322

零钱兑换

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1, INT_MAX);
        dp[0]=0;
        for (int j = 1; j <= amount; j++) {
            for (int i :coins) {
                if (j-i>=0&&dp[j-i]!=INT_MAX) { 
                    dp[j] = min(dp[j],dp[j - i]+1);
                }
            }
        }
        return dp[amount]==INT_MAX?-1:dp[amount];
    }
};

力扣 no.279

完全平方数

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1, INT_MAX);
        vector<int> nums;
        dp[0]=0;
        for(int i(0);i*i<=n;i++){
            nums.push_back(i*i);
        }
        for (int j = 1; j <= n; j++) {
            for (int i :nums) {
                if (j-i>=0&&dp[j-i]!=INT_MAX) { 
                    dp[j] = min(dp[j],dp[j - i]+1);
                }
            }
        }
        return dp[n]==INT_MAX?-1:dp[n];
    }
};

• 同上

力扣 no.139

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        auto wordDictSet = unordered_set <string> ();
        for (auto word: wordDict) {
            wordDictSet.insert(word); // 哈希一下
        }

        auto dp = vector <bool> (s.size() + 1);
        dp[0] = true;
        for (int i = 1; i <= s.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (dp[j] && wordDictSet.find(s.substr(j, i - j)) != wordDictSet.end()) { // 前 j 个字符可以被拆分, 且 j 到 i 之间的字符在字典中
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[s.size()];
    }
};

多重背包

• 每个物品有多个, 展开成 0-1 背包即可

力扣 no.198

打家劫舍

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }
        int size = nums.size();
        if (size == 1) {
            return nums[0];
        }
        int first = nums[0], second = max(nums[0], nums[1]);
        for (int i = 2; i < size; i++) {
            int temp = second;
            second = max(first + nums[i], second);
            first = temp;
        }
        return second;
    }
};

力扣 mo.213

打家劫舍 II

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        int result1 = robRange(nums, 0, nums.size() - 2); // 情况二
        int result2 = robRange(nums, 1, nums.size() - 1); // 情况三
        return max(result1, result2);
    }
    // 198.打家劫舍的逻辑
    int robRange(vector<int>& nums, int start, int end) {
        if (end == start) return nums[start];
        vector<int> dp(nums.size());
        dp[start] = nums[start];
        dp[start + 1] = max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[end];
    }
};

• 手动抉择一下哪个不选

力扣 no.337

打家劫舍 III

class Solution {
public:
    int rob(TreeNode* root) {
        vector<int> result = robTree(root);
        return max(result[0], result[1]);
    }
    // 长度为2的数组，0：不偷，1：偷
    vector<int> robTree(TreeNode* cur) {
        if (cur == NULL) return vector<int>{0, 0};
        vector<int> left = robTree(cur->left);
        vector<int> right = robTree(cur->right);
        // 偷cur，那么就不能偷左右节点。
        int val1 = cur->val + left[0] + right[0];
        // 不偷cur，那么可以偷也可以不偷左右节点，则取较大的情况
        int val2 = max(left[0], left[1]) + max(right[0], right[1]);
        return {val2, val1};
    }
};

力扣 no.121

买卖股票的最佳时机

class Solution {
public:
   int maxProfit(vector<int>& prices) {
       int pre = prices[0], ans = 0;
       for (int i = 0; i < prices.size(); i++) {
           ans = max(ans, prices[i] - pre);
           pre = min(pre, prices[i]);
       }
       return ans;
   }
};

力扣 no.123

买卖股票的最佳时机 III

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;
        for (int i = 1; i < n; ++i) {
            buy1 = max(buy1, -prices[i]);
            sell1 = max(sell1, buy1 + prices[i]);
            buy2 = max(buy2, sell1 - prices[i]);
            sell2 = max(sell2, buy2 + prices[i]);
        }
        return sell2;
    }
};

• 状态机 DP

力扣 no.188

买卖股票的最佳时机 IV

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        vector<int> dp(2*k);
        for (int i = 0; i < k; ++i) {
            dp[2*i] = -prices[0];
        }
        for (int i = 1; i < n; ++i) {
            dp[0] = max(dp[0], -prices[i]);
            dp[1] = max(dp[1], dp[0] + prices[i]);
            for(int j(1);j<k;++j){
                dp[2*j] = max(dp[2*j], dp[2*j-1]-prices[i]);
                dp[2*j+1] = max(dp[2*j+1], dp[2*j] + prices[i]);
            }
        }
        return dp[2*k-1]; 
    }
};

力扣 no.309

买卖股票的最佳时机含冷冻期

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) {
            return 0;
        }

        int n = prices.size();
        int f0 = -prices[0];
        int f1 = 0;
        int f2 = 0;
        for (int i = 1; i < n; ++i) {
            int newf0 = max(f0, f2 - prices[i]); // 之前持有 / 今天买入
            int newf1 = f0 + prices[i]; // 今天卖出
            int newf2 = max(f1, f2); // 今天卖出 / 之前卖出
            f0 = newf0;
            f1 = newf1;
            f2 = newf2;
        }

        return max(f1, f2);
    }
};

力扣 no.714

买卖股票的最佳时机含冷冻期

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        if(prices.size()==1)return 0;
        int n=prices.size();
        int dp1=-prices[0],dp2=0;
        for(int i=1;i<n;i++){
            dp1=max(dp1,dp2-prices[i]);
            dp2=max(dp2,dp1+prices[i]-fee);
        }
        return dp2;
    }
};

// 贪心
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        int buy = prices[0] + fee; // 买的时候算手续费
        int profit = 0;
        for (int i = 1; i < n; ++i) {
            if (prices[i] + fee < buy) {
                buy = prices[i] + fee; // 买便宜的
            }
            else if (prices[i] > buy) {
                profit += prices[i] - buy; // 赚就直接卖
                buy = prices[i]; // 关键点, 为了计算连续卖的累计, 卖了以后当成无手续费的买入    
            }
        }
        return profit;
    }
};

力扣 no.300

最长递增子序列

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = (int)nums.size();
        if (n == 0) {
            return 0;
        }
        vector<int> dp(n, 0);
        for (int i = 0; i < n; ++i) {
            dp[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};

// 二分查找 + 贪心
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len = 1, n = (int)nums.size();
        if (n == 0) {
            return 0;
        }
        vector<int> d(n + 1, 0);
        d[len] = nums[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i] > d[len]) {
                d[++len] = nums[i];
            } else {
                int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (d[mid] < nums[i]) {
                        pos = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                d[pos + 1] = nums[i];
            }
        }
        return len;
    }
};

• 贪心, 遍历数组一遍, 维护一个当前最长的递增子序列, 每次遇到一个新的非递增数, 就二分查找它应该替换的位置 (因为是替换, 不影响正确计数)

力扣 no.674

最长连续递增子序列

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int ans = 0;
        int n = nums.size();
        int start = 0;
        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] <= nums[i - 1]) {
                start = i;
            }
            ans = max(ans, i - start + 1);
        }
        return ans;
    }
};

力扣 no.718

最长重复子数组

// DP
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp (nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
        int result = 0;
        for (int i = 1; i <= nums1.size(); i++) {
            for (int j = 1; j <= nums2.size(); j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                if (dp[i][j] > result) result = dp[i][j];
            }
        }
        return result;
    }
};

// 省点空间
class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        vector<int> dp(vector<int>(B.size() + 1, 0));
        int result = 0;
        for (int i = 1; i <= A.size(); i++) {
            for (int j = B.size(); j > 0; j--) { // 反着遍历, 因为要用到上一行的结果
                if (A[i - 1] == B[j - 1]) {
                    dp[j] = dp[j - 1] + 1;
                } else dp[j] = 0; // 注意这里不相等的时候要有赋0的操作
                if (dp[j] > result) result = dp[j];
            }
        }
        return result;
    }
};

// 滑动窗口
class Solution {
public:
    int maxLength(vector<int>& A, vector<int>& B, int addA, int addB, int len) { // 计算最长公共子数组长度
        int ret = 0, k = 0;
        for (int i = 0; i < len; i++) {
            if (A[addA + i] == B[addB + i]) {
                k++;
            } else {
                k = 0;
            }
            ret = max(ret, k);
        }
        return ret;
    }
    int findLength(vector<int>& A, vector<int>& B) {
        int n = A.size(), m = B.size();
        int ret = 0;
        for (int i = 0; i < n; i++) { // 遍历 A 对齐 B 的开始
            int len = min(m, n - i);
            int maxlen = maxLength(A, B, i, 0, len);
            ret = max(ret, maxlen);
        }
        for (int i = 0; i < m; i++) { // 遍历 B 对齐 A 的开始
            int len = min(n, m - i);
            int maxlen = maxLength(A, B, 0, i, len);
            ret = max(ret, maxlen);
        }
        return ret;
    }
};

• 动态规划, dp[i][j] 表示 nums1[i - 1]为结尾 和 nums2[j - 1] 为结尾的最长公共子数组的长度
• 正解二分查找 + 序列哈希, 二分查找 \(k\), 枚举 \(k\) 长度的子数组并进行序列哈希, 检查是否存在一个公共子数组

力扣 no.1143

最长公共子序列

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.length(), n = text2.length();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; i++) {
            char c1 = text1.at(i - 1);
            for (int j = 1; j <= n; j++) {
                char c2 = text2.at(j - 1);
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
};

• 动态规划, dp[i][j] 表示 text1[i - 1]为结尾 和 text2[j - 1] 为结尾的最长公共子序列的长度

力扣 no.1035

同上

力扣 no.392

判断子序列

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int n = s.size(), m = t.size();

        vector<vector<int> > f(m + 1, vector<int>(26, 0));
        for (int i = 0; i < 26; i++) {
            f[m][i] = m;
        }

        for (int i = m - 1; i >= 0; i--) {
            for (int j = 0; j < 26; j++) {
                if (t[i] == j + 'a')
                    f[i][j] = i;
                else
                    f[i][j] = f[i + 1][j];
            }
        }
        int add = 0;
        for (int i = 0; i < n; i++) {
            if (f[add][s[i] - 'a'] == m) {
                return false;
            }
            add = f[add][s[i] - 'a'] + 1;
        }
        return true;
    }
};

• 动态规划, f[i][j] 表示对于 s[i] 来说, 下一个字符 j 出现的位置

力扣 no.115

不同的子序列

class Solution {
public:
    int numDistinct(string s, string t) {
        int m=s.size();
        int n=t.size();
        vector<vector<unsigned long long>> dp(m+1,vector<unsigned long long>(n+1));
        for(int i=0;i<=m;i++)
            dp[i][0]=1;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(s[i-1]==t[j-1])
                    dp[i][j]=dp[i-1][j-1] + dp[i-1][j]; // 不仅继承 (跳过这个的方案数), 而且加上 dp[i-1][j-1]
                else
                    dp[i][j]=dp[i-1][j]; // 继承上一个状态
            }
        }
        return dp[m][n];
    }
};

力扣 no.583

两个字符串的删除操作

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.length(), n = word2.length();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; i++) {
            char c1 = word1.at(i - 1);
            for (int j = 1; j <= n; j++) {
                char c2 = word2.at(j - 1);
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return (m-dp[m][n])+(n-dp[m][n]);
    }
};

• 同最长公共子序列

力扣 no.72

编辑距离

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
        for (int i = 0; i <= word1.size(); i++) dp[i][0] = i; // 初始化 word1 为空串时的编辑距离
        for (int j = 0; j <= word2.size(); j++) dp[0][j] = j; // 初始化 word2 为空串时的编辑距离
        for (int i = 1; i <= word1.size(); i++) {
            for (int j = 1; j <= word2.size(); j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1]; // 字符相同, 则继承上一个状态 (不需要操作)
                }
                else {
                    dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
                    // 字符不同, 则取三种操作的最小值 + 1
                    // 针对 word1[i - 1] 来说, 有三种操作
                    // dp[i - 1][j - 1] 表示替换操作
                    // dp[i - 1][j] 表示删除操作
                    // dp[i][j - 1] 表示插入操作
                }
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

力扣 no.647

回文子串

// 动态规划, dp[i][j] 表示 s[i:j] 是否为回文子串
class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        int result = 0;
        for (int i = s.size() - 1; i >= 0; i--) {
            for (int j = i; j < s.size(); j++) {
                if (s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1])) {
                    // 当 s[i] == s[j] 时, 有两种情况
                    // 1. j - i <= 1, 即 i == j 或 i + 1 == j, 则 dp[i][j] = true
                    // 2. dp[i + 1][j - 1] == true, 则 dp[i][j] = true
                    result++;
                    dp[i][j] = true;
                }
            }
        }
        return result;
    }
};

// Manacher 算法
class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        string t = "$#";
        for (const char &c: s) {
            t += c;
            t += '#';
        }
        n = t.size();
        t += '!';
        // abc -> $#a#b#c#!, 防止越界, 天然不同而终止

        auto f = vector <int> (n); // f[i] 表示以 i 为中心的最长回文半径
        int iMax = 0, rMax = 0, ans = 0;
        for (int i = 1; i < n; ++i) {
            // 初始化 f[i], 关键操作, 利用对称性质, 避免重复计算
            f[i] = (i <= rMax) ? min(rMax - i + 1, f[2 * iMax - i]) : 1;
            // 中心拓展
            while (t[i + f[i]] == t[i - f[i]]) ++f[i];
            // 动态维护 iMax 和 rMax
            if (i + f[i] - 1 > rMax) {
                iMax = i; // 更新 iMax, 表示当前最长回文半径的中心为 iMax
                rMax = i + f[i] - 1;
            }
            // 统计答案, 当前贡献为 (f[i] - 1) / 2 上取整
            ans += (f[i] / 2);
        }

        return ans;
    }
};

力扣 no.516

最长回文子序列

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.length();
        vector<vector<int>> dp(n, vector<int>(n));
        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1;
            char c1 = s[i];
            for (int j = i + 1; j < n; j++) {
                char c2 = s[j];
                if (c1 == c2) {
                    dp[i][j] = dp[i + 1][j - 1] + 2; // 中间夹着的最长 + 2
                } else {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                    // 理论上是三种的最大值, 但是由于 dp[i + 1][j - 1] 是包含在 dp[i + 1][j] 和 dp[i][j - 1] 中的, 所以可以省略
                }
            }
        }
        return dp[0][n - 1];
    }
};

单调栈

力扣 no.739

每日温度

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> ans(n);
        stack<int> s;
        for (int i = 0; i < n; ++i) {
            while (!s.empty() && temperatures[i] > temperatures[s.top()]) {
                int previousIndex = s.top();
                ans[previousIndex] = i - previousIndex;
                s.pop();
            }
            s.push(i);
        }
        return ans;
    }
};

• 单调栈板子

力扣 no.496

下一个更大元素 I

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int,int> hashmap;
        stack<int> st;
        for (int i = nums2.size() - 1; i >= 0; --i) {
            int num = nums2[i];
            while (!st.empty() && num >= st.top()) {
                st.pop();
            }
            hashmap[num] = st.empty() ? -1 : st.top();
            st.push(num);
        }
        vector<int> res(nums1.size());
        for (int i = 0; i < nums1.size(); ++i) {
            res[i] = hashmap[nums1[i]];
        }
        return res;
    }
};

• 单调栈 + 哈希表

力扣 no.503

下一个更大元素 II

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> ret(n, -1);
        stack<int> stk;
        for (int i = 0; i < n * 2 - 1; i++) {
            while (!stk.empty() && nums[stk.top()] < nums[i % n]) {
                ret[stk.top()] = nums[i % n];
                stk.pop();
            }
            stk.push(i % n);
        }
        return ret;
    }
};

• 单调栈 + 循环数组

力扣 no.42

接雨水

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        int left = 0, right = height.size() - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = max(leftMax, height[left]);
            rightMax = max(rightMax, height[right]);
            if (height[left] < height[right]) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }
};

• 求两侧最高 -> DP
• 单调栈出栈时, 计算面积
• 双指针, 能升高时尽量高, 降低时, 计算面积

力扣 no.84

柱状图中最大的矩形

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> left(n), right(n, n);

        stack<int> mono_stack;
        for (int i = 0; i < n; ++i) {
            while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
                right[mono_stack.top()] = i;
                mono_stack.pop();
            }
            left[i] = (mono_stack.empty() ? -1 : mono_stack.top());
            mono_stack.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }
};

• 通过单调栈, 求每个柱子的左侧和右侧第一个比它低的柱子的下标
• 计算面积

图论

图理论

略

力扣 no.797

所有可能的路径

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> stk;

    void dfs(vector<vector<int>>& graph, int x, int n) {
        if (x == n) {
            ans.push_back(stk);
            return;
        }
        for (auto& y : graph[x]) {
            stk.push_back(y);
            dfs(graph, y, n);
            stk.pop_back();
        }
    }

    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        stk.push_back(0);
        dfs(graph, 0, graph.size() - 1);
        return ans;
    }
};

岛屿问题

花式遍历

• 深度优先搜索
• 广度优先搜索
• 求孤岛 -> 临边界的岛屿变海洋
• 水流问题 -> 从边界开始, 向内部扩散, 获取水流
• 将矩阵中的一格水变为一块陆地 -> 先找岛屿, 遍历海洋变陆地, \(O(1)\) 求面积
• 海岸线 -> 陆地的非陆地邻接数

字符串接龙

略

有向图的完全联通

有向图搜索

并查集

int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0);

// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}
// 并查集里寻根的过程
int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}

// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

// 将v->u 这条边加入并查集
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根
    if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}

寻找存在的路径

并查集板子

冗余连接

遍历边, 两端在同一个集合的话, 就是冗余连接

冗余连接II

找入度为 2 的节点, 删除构成环的边

Prim 算法

略

Kruskal 算法

略

拓扑排序

略

dijkstra 算法

• 堆优化

Bellman ford 算法

略

Floyd 算法

略

A star 算法

• A* 算法 = Dijkstra 算法 + 启发式函数
• 核心公式: \(f(n) = g(n) + h(n)\)
  • \(f(n)\) 代替 Dijkstra 中优先队列的排序依据
  • \(g(n)\) 从起点到当前节点 \(n\) 的实际代价 (Dijkstra 中的 \(d[n]\))
  • \(h(n)\) 从当前节点 \(n\) 到终点的预估代价
  • 当然你可以改权重
• \(h(n)\) 必须满足可采纳性
  • 换言之, 预估必须是乐观的
  • 否则可能找不到最优解
  • \(h(n) \le\) 实际从 \(n\) 到终点的代价
• 常见的 \(h(n)\) 计算方式
  • 曼哈顿距离, 用于只能上下左右走的情况, \(h = |x_1 - x_2| + |y_1 - y_2|\)
  • 欧几里得距离, 用于可以任意角度移动的情况, \(h = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}\)
  • 切比雪夫距离, 用于只能在八个方向移动的情况, \(h = \max(|x_1 - x_2|, |y_1 - y_2|)\)