LeetCode 刷题笔记：hot100

本人的一些 LeetCode 刷题笔记，欢迎参考。

哈希

哈希表的作用是记录之前出现过的内容，C++ 中对应的数据结构有三种：数组、unordered_set、unordered_map。理想情况下，哈希表的插入/删除/查询的时间复杂度为 $O(1)$。

1. 两数之和

https://leetcode.cn/problems/two-sum/description

力扣第一题，非常经典。基本思路是，扫描一遍数组，记录之前扫过的数以及对应的下标，对每个数 nums[i]，查询是否出现过 target - nums[i]，如果有，则返回两个 对应的下标。

要记录之前扫过的数及其下标，就要使用哈希表来存储，查询效率高。同时，由于要存储对应的下标，因此在 C++ 中采用 unordered_map 数据结构。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> seen;
        for (int i = 0; i < nums.size(); i++) {
            if (seen.find(target - nums[i]) != seen.end()) {
                return {i, seen[target - nums[i]]};
            } else {
                seen[nums[i]] = i;
            }
        }
        return {-1, -1};
    }
};

扫描一遍数组，每次操作 $O(1)$，时间复杂度 $O(n)$。空间复杂度 $O(n)$。

2. 字母异位词分组

https://leetcode.cn/problems/group-anagrams/description/

这题需要将字符串进行分组，分组的标准是：字符串中 26 个字母的出现频次均相同。在扫描所有字符串的过程中，使用一个哈希表存储每一类的字符串。当扫描到一个新的字符串时，检查是否已经有对应的类，如果有则直接加入。

本题的关键在于哈希表的键的设计，这个键需要表征每一组字符串。两个常见的想法是：将排序后的字符串作为键，因为每一类字符串包含的字母相同，排序后形成的字符串一定相同；将出现26个字母的次数作为键。我们这里选择第一种。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> ht;
        for (string &str: strs) {
            string key = str;
            sort(key.begin(), key.end());
            ht[key].emplace_back(str);
        }
        // collect result
        vector<vector<string>> result;
        for (auto &it: ht) {
            result.emplace_back(it.second);
        }
        return result;
    }
};

对于每个字符串，需要对字符串进行排序，设字符串最大长度为 $k$，则时间复杂度为 $O(nk\log k)$。空间复杂度 $O(nk)$。

3. 最长连续序列

https://leetcode.cn/problems/longest-consecutive-sequence/description

这题同样需要记住数组里出现的元素，方便查找，我们使用哈希表。由于不需要记住其他数值，只需要知道一个数是否出现过，我们使用 unordered_set。对于每个数 x，我们依次往后访问 x+1、x+2、…，查询下一个数是否出现，得到序列长度。

但这样时间复杂度为 $O(n^2)$，因为对序列中每一个数，都统计了序列长度。事实上，我们只需要对第一个数开始的序列统计长度就可以。因此，在访问每个数 x 时，都判断 x-1 是否在数组中，如果确实存在，则不统计从 x 开始的序列长度。这样，确保了时间复杂度为 $O(n)$，即整个数组只被访问常数次。空间复杂度 $O(n)$。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> ht(nums.begin(), nums.end());
        int maxlen = 0;
        for (const int &num: ht) {
            if (ht.find(num - 1) != ht.end()) continue;
            int curlen = 0;
            while (ht.find(num + curlen) != ht.end()) curlen++;
            maxlen = max(maxlen, curlen);
        }
        return maxlen;
    }
};

注意一个点，遍历数组的时候，应该遍历哈希表，而不是遍历初始数组。初始数组可能包含很多重复元素，遍历可能超时。

双指针

4. 移动零

https://leetcode.cn/problems/move-zeroes/description/

本题的关键是原地操作，原地操作的核心是避免覆盖有用数据。

本题使用双指针法。定义一个读指针 read 和一个写指针 write，从左到右移动。当读指针读到非 0 数值时，写到写指针的位置。由于写指针所写的位置都已经被读指针读过，不会存在数据覆盖的问题。时间复杂度 $O(n)$，空间复杂度 $O(1)$。

还有一种方法，就是在读到非 0 数值时，也将两个指针对应的数交换，效果是一样的。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int read = 0, write = 0;
        while (read < nums.size()) {
            if (nums[read] != 0) {
                nums[write++] = nums[read++];
            } else {
                read++;
            }
        }
        while (write < nums.size()) {
            nums[write++] = 0;
        }
    }
};

5. 盛最多水的容器

https://leetcode.cn/problems/container-with-most-water/description/

给定两个边界 i 和 j，储存的水量是 min(height[i], height[j]) * (j - i)。我们想要找到一组 (i, j)，使得这个水量最大。这道题有点类似滑动窗口，它存在一个单调性条件。注意到，当给定 (i, j) 时，如果将高度较高的一边向中间移动，水量一定减小。也就是说，我们对于高度较低一边的当前位置，已经不需要再对另一端遍历中间的所有位置了，因为其水量一定全部小于当前水量，这就避免了 $O(n^2)$ 的暴力搜索。

综上所述，我们的思路是，将指针初始化在头尾，逐渐向中间移动，记录整个过程中的最大水量。每次的移动方法是，移动高度较低的那一边。时间复杂度 $O(n)$，空间复杂度 $O(1)$。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int i = 0, j = height.size() - 1;
        int maxWater = 0, curWater;
        while (i < j) {
            curWater = min(height[i], height[j]) * (j - i);
            maxWater = max(maxWater, curWater);
            if (height[i] < height[j]) i++;
            else j--;
        }
        return maxWater;
    }
};

6. 三数之和

https://leetcode.cn/problems/3sum/description/

本题的关键是去重。由于返回值不需要包含下标，我们可以首先对数组进行排序，这样更方便去重。

基本思路是：固定三元组中最小的数 nums[i]，将问题转化为在一个数组中找到所有和为 -nums[i] 的二元组，这一步通过双指针实现即可。具体来说，两个指针分别指向 i 右侧数组的首尾，逐渐向中间移动，在过程中收集所有和为 -nums[i] 的去重二元组。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int i = 0, j, k, target, curSum;
        vector<vector<int>> result;
        while (i < nums.size()) {
            target = -nums[i];
            j = i + 1; k = nums.size() - 1;
            while (j < k) {
                curSum = nums[j] + nums[k];
                if (curSum < target) j++;
                else if (curSum > target) k--;
                else {
                    result.push_back({nums[i], nums[j], nums[k]});
                    while (j < k && nums[j + 1] == nums[j]) j++;
                    while (j < k && nums[k - 1] == nums[k]) k--;
                    j++; k--;
                }
            }
            while (i < nums.size() - 1 && nums[i + 1] == nums[i]) i++;
            i++;
        }
        return result;
    }
};

时间复杂度 $O(n^2)$，空间复杂度 $O(\log n)$（排序）。

7. 接雨水

https://leetcode.cn/problems/trapping-rain-water/description

这道题的思路没有那么直接，我们需要考虑这个雨水的体积究竟如何计算。观察可以发现，从左到右遍历柱子，当出现一个高度为 x 的柱子时，它能决定和左侧每一根“它们之间没有高度超过 x 的柱子”的柱子之间的水量，而这个水量由左侧柱子以及它们之间柱子的最大高度决定。

我们需要维护一个单调栈，存储数组下标，从栈底到栈口，对应的柱子高度单调减小。当扫描到一个新的柱子 k 时，如果栈顶的柱子 j 高度不超过 height[k]，将其弹出并将该高度作为水池的底，假设此时栈顶为 i，那么此时形成水池的高度是 min(height[i], height[k]) - height[j]，宽度是 k - i - 1，如此依次弹出所有高度不超过 height[k] 的柱子，接着将这个新的柱子 j 压入栈中。被弹出的这些柱子已经无法和 k 右侧的柱子一起接住雨水，因为它们被 k 阻挡。

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> st;
        int result = 0, i, j;
        for (int k = 0; k < height.size(); k++) {
            while (!st.empty() && height[k] >= height[st.top()]) {
                j = st.top(); st.pop();
                if (!st.empty()) {
                    i = st.top();
                    result += (min(height[i], height[k]) - height[j]) * (k - i - 1);
                }
            }
            st.push(k);
        }
        return result;
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(n)$。这道题也有动态规划和双指针的做法。

滑动窗口

8. 无重复字符的最长子串

https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/

这道题采用滑动窗口的思路，依次向右扩展窗口，如果发现读入的数已经在字符串中出现过，则缩小左侧窗口，直到该字符不重复，记录过程中窗口的最大值，即为答案。可以使用 unordered_set 哈希表来记录当前字符串中有哪些元素。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> seen;
        int result = 0, i = 0;
        for (int j = 0; j < s.length(); j++) {
            if (seen.find(s[j]) != seen.end()) {
                while (s[i] != s[j]) seen.erase(s[i++]);
                i++;
            } else {
                seen.insert(s[j]);
            }
            result = max(result, j - i + 1);
        }
        return result;
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(|\Sigma|)$，其中 $|\Sigma|$ 表示字符集的大小。

9. 找到字符串中所有字母异位词

https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/

这道题思路比较直接，因为窗口的大小是固定的，就是 p 的长度。我们只要一格格移动这个窗口，维护好这个窗口中有哪些字母出现（即每个字母出现多少次），是否和 p 中出现的字母完全一致就可以了。可以采取存储差值的方法，当所有差值全为 0 的时候，表明窗口中包含的字符和 p 完全一致。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        if (s.length() < p.length()) return {};
        int diff[26];
        vector<int> result;
        int non_zero = 0, tmp, j;
        for (int i = 0; i < p.length(); i++) {
            tmp = ++diff[p[i] - 'a'];
            if (tmp == 1) non_zero++;
            else if (tmp == 0) non_zero--;
            tmp = --diff[s[i] - 'a'];
            if (tmp == -1) non_zero++;
            else if (tmp == 0) non_zero--;
        }
        for (int i = 0; i + p.length() <= s.length(); i++) {
            j = i + p.length() - 1;
            if (i != 0) {
                tmp = --diff[s[j] - 'a'];
                if (tmp == -1) non_zero++;
                else if (tmp == 0) non_zero--;
                tmp = ++diff[s[i - 1] - 'a'];
                if (tmp == 1) non_zero++;
                else if (tmp == 0) non_zero--;
            }
            if (non_zero == 0) result.push_back(i);
        }
        return result;
    }
};

时间复杂度 $O(n + m)$，空间复杂度 $O(|\Sigma|)$。

子串

10. 和为 K 的子数组

https://leetcode.cn/problems/subarray-sum-equals-k/description/

本题可以做一些转化：找和为 k 的子数组，即找起始位置 i 和终止位置 j 使得 nums[i...j] 的和为 k，可以转化为 pre[j] - pre[i - 1] == k，其中 pre[i] 表示 nums[0...i] 中所有数的和。

因此，我们按字串结尾位置遍历数组，假设遍历到 j 位置时，前缀和为 prefix_sum，那么我们就要找到之前是否存在等于 k - prefix_sum 的前缀和，其个数就等于以 j 结尾的和为 k 子数组的个数。而查找之前出现过的前缀和，当然要用哈希表，并且应该记录出现了几次。这样，我们只要遍历一次数组，就可以累加得到和为 k 的子数组的数量。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> ht;
        ht[0] = 1;
        int prefix_sum = 0, result = 0;
        for (int i = 0; i < nums.size(); i++) {
            prefix_sum += nums[i];
            if (ht.count(prefix_sum - k)) result += ht[prefix_sum - k];
            ht[prefix_sum]++;
        }
        return result;
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

11. 滑动窗口最大值

https://leetcode.cn/problems/sliding-window-maximum/description/

使用一个双端队列维护可能作为最大值的下标，从左端弹出过期元素（落到窗口外的元素），右端插入刚进入窗口的元素。这个队列是一个单调栈，假如 i 在 j 左侧，即 i < j，则一定有 nums[i] > nums[j]，否则 nums[i] 不可能作为窗口中的最大值。因此，每次插入新元素时，都要弹出右侧比它小的所有元素。队列的最左侧即为当前窗口最大值的位置。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        vector<int> result;
        for (int i = 0; i < nums.size(); i++) {
            while (!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back();
            dq.push_back(i);
            if (i < k - 1) continue;
            while(!dq.empty() && dq.front() <= i - k) dq.pop_front();
            result.push_back(nums[dq.front()]);
        }
        return result;
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(k)$。

12. 最小覆盖子串

https://leetcode.cn/problems/minimum-window-substring/description/

本题采用滑动窗口的思路：当窗口满足覆盖要求时，将窗口左边界右移（收缩左边界），缩小窗口；否则，将窗口右边界右移（扩展右边界），扩大窗口。在此过程中，记录满足覆盖要求的最大窗口。

判断窗口是否满足覆盖要求，使用哈希表。diff 记录了 t 中每个字符的出现情况，具体来说，t[x] 表示字符 x 在 t 中出现的次数减去在当前窗口中出现的次数。pst 表示 diff 中正数的个数，当 pst == 0 时，表示所有 t 中字符在当前窗口中的出现次数都达到 t 中次数，故当前窗口满足覆盖要求。

class Solution {
public:
    string minWindow(string s, string t) {
        if (s.length() < t.length()) return "";
        unordered_map<char, int> diff;
        for (int i = 0; i < t.length(); i++) {
            diff[t[i]]++;
        }
        int pst = diff.size(), min_len = INT_MAX, result = 0;
        if (diff.find(s[0]) != diff.end())
            if (--diff[s[0]] == 0) pst--;
        for (int i = 0, j = 0; j < s.length(); ) {
            if (pst == 0) {
                int cur_len = j - i + 1;
                if (cur_len < min_len) {
                    min_len = cur_len;
                    result = i;
                }
                if (diff.find(s[i]) != diff.end())
                    if (++diff[s[i]] == 1) pst++;
                i++;
            } else {
                if (++j < s.length() && diff.find(s[j]) != diff.end())
                    if (--diff[s[j]] == 0) pst--;
            }
        }
        return min_len == INT_MAX ? "" : s.substr(result, min_len);
    }
};

时间复杂度 $O(n + m)$，空间复杂度 $O(|\Sigma|)$。

普通数组

13. 最大子数组和

https://leetcode.cn/problems/maximum-subarray/description/

这道题可以采用贪心的思路：从左到右扫描数组，计算累计和，如果当前累计和为负，就将累计和清零，重新开始计算数组和。这一思路是很直接的。

这一思路也可以理解为动态规划。dp[i] 表示以 i 位置结尾的子数组的最大和，递推公式为 dp[i] = max(nums[i], dp[i - 1] + nums[i])，初始化 dp[0] = nums[0]，最终结果是 dp[i] 的最大值。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum = 0, result = INT_MIN;
        for (int i = 0; i < nums.size(); i++) {
            if (sum < 0) sum = 0;
            sum += nums[i];
            result = max(result, sum);
        }
        return result;
    }
};

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

14. 合并区间

https://leetcode.cn/problems/merge-intervals/description/

本题的思路比较直接，直接从左向右模拟合并区间的过程。先按照左边界递增将所有区间排序，维护一个当前的左边界 left 和右边界 right。设下一个区间是 [l, r]，如果 l <= right，则将 right 更新为 max(right, r)，完成对下一个区间的合并；如果 l > right，则将当前区间加入最终结果，并重新设定 left 和 right 分别为 l 和 r。

class Solution {
public:
    static bool cmp(const vector<int> &a, const vector<int> &b) {
        return a[0] < b[0];
    }

    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp);
        vector<vector<int>> result;
        int left = intervals[0][0], right = intervals[0][1];
        for (int i = 1; i < intervals.size(); i++) {
            int l = intervals[i][0], r = intervals[i][1];
            if (l > right) {
                result.push_back({left, right});
                left = l, right = r;
            } else {
                right = max(r, right);
            }
        }
        result.push_back({left, right});
        return result;
    }
};

时间复杂度 $O(n \log n)$，空间复杂度 $O(\log n)$，均来自排序。

15. 轮转数组

https://leetcode.cn/problems/rotate-array/description/

不妨假设 k < n。有一种可以原地轮转 k 步的方法：先将 [0, n-k-1] 和 [n-k, n-1] 分别反转，再将整个数组反转，即可实现数组的轮转。其中，反转使用前后交换的方法可以原地解决。

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n;
        revert(nums, 0, n - k - 1);
        revert(nums, n - k, n - 1);
        revert(nums, 0, n - 1);
    }

    void revert(vector<int> &nums, int begin, int end) {
        for (int left = begin, right = end; left < right; left++, right--) {
            swap(nums[left], nums[right]);
        }
    }
};

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

16. 除了自身以外数组的乘积

https://leetcode.cn/problems/product-of-array-except-self/description/

观察可知，每个位置 k 的乘积可以用 [0, k-1] 的前缀积和 [k+1, n-1] 的后缀积相乘得到。而整个数组的前缀积和后缀积都可以在 $O(n)$ 时间内，通过一次遍历计算得出。

因此，本题的思路是：先从左到右遍历数组，记录每个位置的前缀积；再从右到左遍历数组，记录每个位置的后缀积，并将其乘到对应的前缀积上，得到最终数组。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> product(n, 1);
        int cur_prod = 1;
        for (int i = 0; i < n; i++) {
            product[i] *= cur_prod;
            cur_prod *= nums[i]; 
        }
        cur_prod = 1;
        for (int i = n - 1; i >= 0; i--) {
            product[i] *= cur_prod;
            cur_prod *= nums[i];
        }
        return product;
    }
};

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

17. 缺失的第一个正数

https://leetcode.cn/problems/first-missing-positive/description/

本题的难点在于要求空间复杂度为 $O(1)$，这意味着我们不能额外使用哈希表。我们可以尝试将原数组当作哈希表使用。

首先观察到，最终结果的范围是 [1, n+1]，其中 n 是数组长度。我们使用 nums[i-1] 的正负记录正整数 i 是否出现，如果出现，将 nums[i-1] 改为负数，即取相反数。整个流程是：在开始之前，先将 nums 中所有非正数修改为 n+1；扫描一次数组，对于每个数 i（负数则取相反数），将 nums[i-1] 变为对应的负数；最后再从左向右扫描数组，找到第一个不为负数的位置。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0) nums[i] = n + 1;
        }
        for (int i = 0; i < n; i++) {
            int num = abs(nums[i]);
            if (num <= n) nums[num - 1] = - abs(nums[num - 1]);
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) return i + 1;
        }
        return n + 1;
    }
};

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

矩阵

18. 矩阵置零

https://leetcode.cn/problems/set-matrix-zeroes/description/

为了只使用 $O(1)$ 的空间，我们必须利用原有的矩阵记录信息。考虑使用第一行和第一列作为每一行或每一列是否存在 0 的标记，即如果 matrix[i][j] == 0，那么令 matrix[i][0] = matrix[0][j] = 0。这样第二遍只需要扫描第一行和第一列，就可以把包含 0 的行和列全部置零。

但这样有一个问题，第一行和第一列是否包含 0 的信息会丢失。因此，我们还需要两个变量 rflag 和 cflag 来分别记录第一行和第一列是否包含 0。

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        bool rflag = false, cflag = false;
        int m = matrix.size(), n = matrix[0].size();
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                cflag = true;
                break;
            }
        }
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                rflag = true;
                break;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    break;
                }
            }
        }
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < m; i++) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    break;
                }
            }
        }
        for (int i = 1; i < m; i++) {
            if (matrix[i][0] != 0) continue;
            for (int j = 1; j < n; j++) matrix[i][j] = 0;
        }
        for (int j = 1; j < n; j++) {
            if (matrix[0][j] != 0) continue;
            for (int i = 1; i < m; i++) matrix[i][j] = 0;
        }
        if (cflag) {
            for (int i = 0; i < m; i++) matrix[i][0] = 0;
        }
        if (rflag) {
            for (int j = 0; j < n; j++) matrix[0][j] = 0;
        }
    }
};

时间复杂度 $O(mn)$，空间复杂度 $O(1)$。

19. 螺旋矩阵

https://leetcode.cn/problems/spiral-matrix/description/

本题模拟出过程即可，每一轮向中心收紧一圈。设当前圈数为 start，也就是这一圈开始的列数，初始值为 0。设 endx = m - 1 - start，endy = n - 1 - start，那么这一圈要收集的位置就是依次四条边：matrix[start][start:endy]、matrix[start+1:endx-1][endy]、matrix[endx][endy:start:-1]、matrix[endx-1:start+1:-1][start]（均为闭区间），直到收集到 m * n 个数停止。

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<int> result;
        int start = 0;
        while (result.size() < m * n) {
            int endx = m - 1 - start, endy = n - 1 - start;
            for (int y = start; y <= endy && result.size() < m * n; y++) result.push_back(matrix[start][y]);
            for (int x = start + 1; x < endx && result.size() < m * n; x++) result.push_back(matrix[x][endy]);
            for (int y = endy; y >= start && result.size() < m * n; y--) result.push_back(matrix[endx][y]);
            for (int x = endx - 1; x > start && result.size() < m * n; x--) result.push_back(matrix[x][start]);
            start++;
        }
        return result;
    }
};

时间复杂度 $O(mn)$，空间复杂度 $O(1)$。

20. 旋转图像

https://leetcode.cn/problems/rotate-image/description/

本题要求原地旋转一个矩阵，观察到可以每四个数一组进行旋转，即 matrix[i][j]、matrix[j][n-1-i]、matrix[n-1-i][n-1-j]、matrix[n-1-j][i]，注意其中 i 和 j 的取值。

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < (n + 1) / 2; i++) {
            for (int j = 0; j < n / 2; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - j][i];
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
                matrix[j][n - 1 - i] = tmp;
            }
        }
    }
};

时间复杂度 $O(n^2)$，空间复杂度 $O(1)$。

21. 搜索二维矩阵 II

https://leetcode.cn/problems/search-a-2d-matrix-ii/description/

观察到一个性质，对于每个元素，其下边和右边所有元素比它大，左边和上边所有元素比它小。利用这性质，我们从矩阵的右上角 matrix[0][n-1] 开始搜索。设当前位置值是 x = matrix[r][c]，只考虑当前位置左侧和下方的所有元素，即只考虑 matrix[r:n-1][0:c]（闭区间），其他元素已经被排除。如果 x < target，表明这一行的元素都小于 target，因此 r += 1；如果 x > target，表明这一列的元素都大于 target，因此 c -= 1；如果 x == target，返回结果。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int r = 0, c = n - 1;
        while (r < m && c >= 0) {
            int x = matrix[r][c];
            if (x == target) return true;
            else if (x < target) r++;
            else c--;
        }
        return false;
    }
};

时间复杂度 $O(m + n)$，空间复杂度 $O(1)$。

链表

22. 相交链表

https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

我们可以先求出两个链表的长度，设长度差为 gap。在两个链表的头部设置两个指针，让更长链表的指针先走 gap 步，然后两个指针同时向后移动，每一步检查是否相等即可。

class Solution {
public:
    int getSize(ListNode *head) {
        int size = 0;
        ListNode *cur = head;
        while (cur) {
            cur = cur->next;
            size++;
        }  
        return size;
    }

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int sizeA = getSize(headA), sizeB = getSize(headB);
        ListNode *curA = headA, *curB = headB;
        int gap = sizeA - sizeB;
        if (gap > 0) {
            while (gap-- && curA) curA = curA->next;
        } else if (gap < 0) {
            while (gap++ && curB) curB = curB->next;
        }
        while (curA && curB) {
            if (curA == curB) return curA;
            curA = curA->next;
            curB = curB->next;
        }
        return nullptr;
    }
};

时间复杂度 $O(m + n)$，空间复杂度 $O(1)$。

23. 反转链表

https://leetcode.cn/problems/reverse-linked-list/description/

反转链表是链表的经典题目，采用双指针法，pre 和 cur 指针分别指向前一个和后一个节点，基本过程如下。

tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;

完整代码如下。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur) {
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};

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

24. 回文链表

https://leetcode.cn/problems/palindrome-linked-list/description/

本题的难点在于要求 $O(1)$ 的空间复杂度。一个方法是，把后半段链表原地反转，再用两个指针分别从头节点和中间同时移动，检查每个节点值是否一致。最后需要将链表恢复。

class Solution {
public:
    int getSize(ListNode *head) {
        ListNode *cur = head;
        int size = 0;
        while (cur) {
            cur = cur->next;
            size++;
        }
        return size;
    }

    ListNode* reverse(ListNode *head) {
        ListNode *pre = nullptr, *cur = head;
        while (cur) {
            ListNode *tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }

    bool isPalindrome(ListNode* head) {
        int size = getSize(head);
        ListNode *ftail = head;
        for (int i = 1; i < (size + 1) / 2; i++) ftail = ftail->next;
        ListNode *bhead = ftail->next;
        bhead = reverse(bhead);
        ListNode *cur1 = head, *cur2 = bhead;
        while (cur2) {
            if (cur1->val != cur2->val) {
                reverse(bhead);
                return false;
            };
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        reverse(bhead);
        return true;
    }
};

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

25. 环形链表

https://leetcode.cn/problems/linked-list-cycle/description/

判断链表是否有环，可以采用快慢指针法。定义快指针 fast 和慢指针 slow，两指针均从 head 出发，fast 指针每次走两格，slow 指针每次走一格，如果两指针相遇，表明存在环。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *fast = head, *slow = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) return true;
        }
        return false;
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(1)$。注意，快指针可以在慢指针进入环的一圈内追到慢指针，因为它们之间的距离每次减小 1 格。

26. 环形链表 II

https://leetcode.cn/problems/linked-list-cycle-ii/description/

这题在上一题的基础上增加了一个要求：找到链表开始入环的第一个节点。如果用哈希表的方法，这是容易的。但是如果采用快慢指针的方法，需要一些思考。

假设快慢指针相遇在了某个位置，这时将慢指针移动到 head 的位置，然后两个指针同时每次一格向后移动，其相遇处就是环的入口处。

这可以用数学证明。设链表从头到环入口处距离为 $x$，环入口到相遇位置距离为 $y$，相遇位置到环入口距离为 $z$。那么相遇时，慢指针走过的路程为 $x + y$（注意，慢指针不可能走超过一圈，因为我们已经说过，快指针可以在慢指针进入环的一圈内追到慢指针），快指针走过的路程为 $x + y + k(y + z)$，其中正整数 $k$ 是快指针转过的圈数。由相遇前两者的速度可知，$x + y + k(y + z) = 2(x + y)$，整理可得 $x = (k-1)(y+z)+z$，也就是说 $x$ 和 $z$ 只差整数个环的长度。因此，只要两个指针分别从链表头和相遇处开始，每次同时移动一格，就一定能同时到达环入口处。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast = head, *slow = head;
        bool existCycle = false;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                existCycle = true;
                break;
            }
        }
        if (!existCycle) return nullptr;
        fast = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }
};

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

27. 合并两个有序链表

https://leetcode.cn/problems/merge-two-sorted-lists/description/

本题和合并两个有序数组的过程类似，每次从两个链表头部选择更小的元素加入新链表尾部即可。可以先添加一个哑节点指向头节点，以便统一链表为空的情形。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *dummyHead = new ListNode();
        ListNode *cur1 = list1, *cur2 = list2, *cur = dummyHead;
        while (cur1 && cur2) {
            if (cur1->val <= cur2->val) {
                cur->next = cur1;
                cur1 = cur1->next;
            } else {
                cur->next = cur2;
                cur2 = cur2->next;
            }
            cur = cur->next;
        }
        if (cur1) cur->next = cur1;
        if (cur2) cur->next = cur2;
        ListNode *head = dummyHead->next;
        delete dummyHead;
        return head;
    }
};

时间复杂度 $O(m+n)$，空间复杂度 $O(1)$。

28. 两数相加

https://leetcode.cn/problems/add-two-numbers/description/

本题从低位到高位，依次模拟每一位的相加情况即可。用指针 cur1 和 cur2 分别遍历两个链表，将其逐位相加，直到 cur1、cur2 均为空指针且进位 carry 等于 0。

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *dummyHead = new ListNode();
        ListNode *cur1 = l1, *cur2 = l2, *cur = dummyHead;
        int carry = 0;
        while (cur1 || cur2 || carry) {
            int op1 = cur1 ? cur1->val : 0;
            int op2 = cur2 ? cur2->val : 0;
            int sum = op1 + op2 + carry;
            carry = sum / 10;
            cur->next = new ListNode(sum % 10);
            cur = cur->next;
            cur1 = cur1 ? cur1->next : cur1;
            cur2 = cur2 ? cur2->next : cur2;
        }
        ListNode *head = dummyHead->next;
        delete dummyHead;
        return head;
    }
};

时间复杂度 $O(\max(m, n))$，空间复杂度 $O(1)$。

29. 删除链表的倒数第 N 个结点

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/

删除链表的倒数第 $n$ 个节点，就是要找到其前一个节点。有一种进行一趟扫描的方法，先添加一个哑节点指向头节点（为了将头节点的删除统一），定义两个指针 fast 和 slow 均指向哑节点，让 fast 指针先向前走 $n + 1$ 步，然后两个指针同时一格格向前移动，当 fast 指针为空时，slow 指针就指向倒数第 $n$ 个节点的前一个节点，这时删除倒数第 $n$ 个节点即可。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummyHead = new ListNode(0, head);
        ListNode *fast = dummyHead, *slow = dummyHead;
        for (int i = 0; i <= n; i++) fast = fast->next;
        while (fast) {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        ListNode *newHead = dummyHead->next;
        delete dummyHead;
        return newHead;
    }
};

时间复杂度 $O(L)$，空间复杂度 $O(1)$。

30. 两两交换链表中的节点

https://leetcode.cn/problems/swap-nodes-in-pairs/description/

本题主要是模拟过程。先添加一个哑节点指向头节点，然后遍历链表，后面有不少于两个节点时，交换两个节点即可。注意循环结束的边界条件，避免操作空指针。

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode *dummyHead = new ListNode(0, head);
        ListNode *cur = dummyHead;
        while (cur->next && cur->next->next) {
            ListNode *tmp = cur->next;
            cur->next = cur->next->next;
            tmp->next = cur->next->next;
            cur->next->next = tmp;
            cur = tmp;
        }
        ListNode *newHead = dummyHead->next;
        delete dummyHead;
        return newHead;
    }
};

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

31. K 个一组翻转链表

https://leetcode.cn/problems/reverse-nodes-in-k-group/description/

这道题是反转链表的进阶版，主体还是反转链表，不涉及额外的算法，但是加上了链表之间的连接操作，即每一组反转结束后，要将上一组的尾节点 pre_tail 的 next 指针指向这次的头节点。又由于每组的尾节点是反转前的头节点，所以每一组反转前的头节点用 pre_cur 进行保存。

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode *pre = nullptr, *cur = head, *pnr = head;
        ListNode *pre_tail = nullptr, *pre_cur = nullptr, *result = nullptr;
        while (pnr) {
            for (int i = 0; i < k; i++) {
                if (pnr) pnr = pnr->next;
                else {
                    pre_tail->next = cur;
                    return result;
                }
            }
            pre_cur = cur;
            pre = nullptr;
            while (cur != pnr) {
                ListNode *tmp = cur->next;
                cur->next = pre;
                pre = cur;
                cur = tmp;
            }
            if (pre_tail) pre_tail->next = pre;
            else result = pre;
            pre_tail = pre_cur;
        }
        return result;
    }
};

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

32. 随机链表的复制

https://leetcode.cn/problems/copy-list-with-random-pointer/description/

本题的难点在于，如果按顺序复制节点，其 random 指针指向的节点可能还不存在。我们可以考虑，在复制某个节点的时候，递归地复制所有相关的节点。但这要求我们有一个哈希表 ht，能用于判断某个节点是否已经被复制，该表记录了原节点地址到新节点地址的映射。

class Solution {
private:
    unordered_map<Node*, Node*> ht;
public:
    Node* copyRandomList(Node* head) {
        if (!head) return nullptr;
        if (!ht.count(head)) {
            Node *newHead = new Node(head->val);
            ht[head] = newHead;
            newHead->next = copyRandomList(head->next);
            newHead->random = copyRandomList(head->random);
        }
        return ht[head];
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

33. 排序链表

https://leetcode.cn/problems/sort-list/description/

考虑到要求时间复杂度 $O(n \log n)$ 且空间复杂度 $O(1)$，采用自底向上的归并排序。从单个节点开始，每次合并相邻的两段（参考“合并两个有序链表”那题），从 1 个节点有序，到 2 个节点、4 个节点有序，最终整个序列有序。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *dummyHead = new ListNode();
        ListNode *cur1 = list1, *cur2 = list2, *cur = dummyHead;
        while (cur1 && cur2) {
            if (cur1->val <= cur2->val) {
                cur->next = cur1;
                cur1 = cur1->next;
            } else {
                cur->next = cur2;
                cur2 = cur2->next;
            }
            cur = cur->next;
        }
        if (cur1) cur->next = cur1;
        if (cur2) cur->next = cur2;
        ListNode *head = dummyHead->next;
        delete dummyHead;
        return head;
    }

    int getSize(ListNode *head) {
        int size = 0;
        ListNode *cur = head;
        while (cur) {
            cur = cur->next;
            size++;
        }
        return size;
    }
    
    ListNode* sortList(ListNode* head) {
        int size = getSize(head);
        ListNode *dummyHead = new ListNode(0, head);
        for (int len = 1; len < size; len *= 2) {
            ListNode *pre = dummyHead, *cur = dummyHead->next;
            while (cur) {
                ListNode *head1 = cur;
                for (int i = 1; i < len && cur->next; i++) cur = cur->next;
                ListNode *head2 = cur->next;
                cur->next = nullptr;
                cur = head2;
                for (int i = 1; i < len && cur && cur->next; i++) cur = cur->next;
                ListNode *next = nullptr;
                if (cur) {
                    next = cur->next;
                    cur->next = nullptr;
                }
                pre->next = mergeTwoLists(head1, head2);
                while (pre->next) pre = pre->next;
                cur = next;
            }
        }
        ListNode *newHead = dummyHead->next;
        delete dummyHead;
        return newHead;
    }
};

时间复杂度 $O(n \log n)$，空间复杂度 $O(1)$。

34. 合并 K 个升序链表

https://leetcode.cn/problems/merge-k-sorted-lists/description/

本题需要合并 $K$ 个升序链表，关键是每次选出 $K$ 个链表头中最小的，摘下来挂到合并的新链表上。要维护和更新 $K$ 个数中的最小数，考虑使用小顶堆。每次弹出堆顶节点（即 $K$ 个链头节点中值最小的），然后将该节点的下一个节点加入堆中即可。

注意 C++ 中优先级队列的使用方法，特别是自定义的相关语法。

class Solution {
public:
    struct Node {
        int val;
        ListNode *ptr;
    };

    struct cmp {
        bool operator()(Node& a, Node& b) {
            return a.val > b.val;
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *dummyHead = new ListNode();
        ListNode *cur = dummyHead;
        for (ListNode *node : lists) {
            if (node) pq.push({node->val, node});
        }
        while (!pq.empty()) {
            Node curr = pq.top(); pq.pop();
            cur->next = curr.ptr;
            cur = cur->next;
            ListNode *next = curr.ptr->next;
            if (next) pq.push({next->val, next});
        }
        ListNode *head = dummyHead->next;
        delete dummyHead;
        return head;
    }
private:
    priority_queue<Node, vector<Node>, cmp> pq;
};

每次插入和删除时间为 $O(\log k)$，最多 $kn$ 个点，总时间复杂度 $O(kn \log k)$，空间复杂度 $O(k)$。

35. LRU 缓存

https://leetcode.cn/problems/lru-cache/description/

为了实现根据 key 的 $O(1)$ 查找，我们需要使用哈希表。为了实现 LRU 的排队策略，在 $O(1)$ 时间内从队列中选一个元素排到队尾，我们需要使用链表。但是注意三件事情：

• 为了快速找到节点来完成队列调整，我们在哈希表中应当存放的值是节点指针，而不是 value；
• 单向链表的节点删除需要 $O(n)$ 时间，因为我们需要找到前一个节点，因此我们需要使用双向链表；
• 为了在逐出节点时同时删去哈希表中的项，在每个节点中我们还需要存放 key 值。

我们将队尾设在双向链表的头部，队头设在双向链表的尾部。

struct DLinkedNode {
    int key, value;
    DLinkedNode* pre;
    DLinkedNode* next;

    DLinkedNode() : key(0), value(0), pre(nullptr), next(nullptr) {}
    DLinkedNode(int _key, int _value) : key(_key), value(_value), pre(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    unordered_map<int, DLinkedNode*> cache;
    DLinkedNode* head;
    DLinkedNode* tail;
    int size;
    int cap;

public:
    LRUCache(int capacity) {
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->pre = head;
        cap = capacity;
        size = 0;
    }
    
    int get(int key) {
        auto find_res = cache.find(key);
        if (find_res == cache.end()) return -1;
        DLinkedNode* cur = find_res->second;
        // remove node
        cur->pre->next = cur->next;
        cur->next->pre = cur->pre;
        // add to head
        cur->pre = head; cur->next = head->next;
        head->next->pre = cur;
        head->next = cur;
        return cur->value;
    }
    
    void put(int key, int value) {
        auto find_res = cache.find(key);
        if (find_res != cache.end()) {
            DLinkedNode* cur = find_res->second;
            // remove node
            cur->pre->next = cur->next;
            cur->next->pre = cur->pre;
            // add to head
            cur->pre = head; cur->next = head->next;
            head->next->pre = cur;
            head->next = cur;
            cur->value = value;
            return;
        }
        if (size == cap) {
            DLinkedNode* out = tail->pre;
            // remove from tail
            out->pre->next = tail;
            tail->pre = out->pre;
            cache.erase(out->key);
            delete out;
            size--;
        }
        size++;
        DLinkedNode* cur = new DLinkedNode(key, value);
        cache.emplace(key, cur);
        // add to head
        cur->pre = head; cur->next = head->next;
        head->next->pre = cur;
        head->next = cur;
    }
};

时间复杂度对于 put 和 get 都是 $O(1)$，空间复杂度 $O(\text{capacity})$。

二叉树

36. 二叉树的中序遍历

https://leetcode.cn/problems/binary-tree-inorder-traversal/description/

本题考查基本算法——二叉树的中序遍历，可以采用递归法或迭代法完成。递归法比较简单，这里采用迭代法。

使用一个栈，模拟递归函数的调用过程。flag 是标记位，标记了该节点是第一次还是第二次加入栈中，中序遍历只有当左子树访问完之后，才会访问根结点。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        if (!root) return result;
        stack<pair<TreeNode*, int>> st;
        st.push({root, 0});
        while (!st.empty()) {
            auto [cur, flag] = st.top(); st.pop();
            if (flag == 0) {
                st.push({cur, 1});
                if (cur->left) st.push({cur->left, 0}); 
            } else {
                result.push_back(cur->val);
                if (cur->right) st.push({cur->right, 0});
            }
        }
        return result;
    }
};

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

37. 二叉树的最大深度

https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/

遍历是二叉树的核心操作。本题中，每个节点需要收集结果，采用后序遍历。先递归地计算左子树高度 lheight 和右子树高度 rheight，再计算出当前树高度 max(lheight, rheight) + 1 并返回。

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

时间复杂度 $O(n)$，空间复杂度 $O(height)$。

38. 翻转二叉树

https://leetcode.cn/problems/invert-binary-tree/description/

本题采用前/后序遍历均可，效果是一样的，以后序遍历为例。从根结点开始，对每个节点，先递归地翻转左子树和右子树，然后再交换左右子树。

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return nullptr;
        root->left = invertTree(root->left);
        root->right = invertTree(root->right);
        swap(root->left, root->right);
        return root;
    }
};

39. 对称二叉树

https://leetcode.cn/problems/symmetric-tree/description/

本题采用后序遍历。我们需要从根结点开始，检查关于中心线镜像的两个节点 A 和 B 是否对称：如果 A 和 B 都是空，当然对称；如果只有一个为空，则不对称；如果均不为空，则先检查 A 和 B 节点的值是否相等，再递归地检查 A 的左子树和 B 的右子树是否对称、A 的右子树和 B 的左子树是否对称，如果都满足则对称。

class Solution {
public:
    bool isSym(TreeNode *lnode, TreeNode *rnode) {
        if (!lnode || !rnode) return !lnode && !rnode;
        return lnode->val == rnode->val && isSym(lnode->left, rnode->right) && isSym(lnode->right, rnode->left);
    }

    bool isSymmetric(TreeNode* root) {
        return isSym(root, root);
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

40. 二叉树的直径

https://leetcode.cn/problems/diameter-of-binary-tree/description/

本题的实质是求二叉树的深度。在后序遍历二叉树的同时，维护一个当前直径 diameter，对每个节点，先递归地计算左、右子树深度 lheight 和 rheight，然后计算 lheight + rheight，如果结果大于 diameter，则更新该参数。

class Solution {
public:
    int depthOfBinaryTree(TreeNode *root, int &diameter) {
        if (!root) return 0;
        int lheight = depthOfBinaryTree(root->left, diameter);
        int rheight = depthOfBinaryTree(root->right, diameter);
        diameter = max(diameter, lheight + rheight);
        return max(lheight, rheight) + 1;
    }

    int diameterOfBinaryTree(TreeNode* root) {
        int diameter = 0;
        depthOfBinaryTree(root, diameter);
        return diameter;
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(height)$。

41. 二叉树的层序遍历

https://leetcode.cn/problems/binary-tree-level-order-traversal/description/

二叉树的层序遍历，属于基本算法，使用一个队列维护要处理的节点。本题需要分开收集每一层的节点，可以用一个 bdth 变量记录每一层的节点数量。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        vector<vector<int>> result;
        if (root) q.push(root);
        while (!q.empty()) {
            int bdth = q.size();
            vector<int> nodes;
            while (bdth--) {
                TreeNode *cur = q.front(); q.pop();
                nodes.push_back(cur->val);
                if (cur->left) q.push(cur->left);
                if (cur->right) q.push(cur->right);
            }
            result.push_back(nodes);
        }
        return result;
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

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

https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/

本题需要递归地构建平衡二叉搜索树。我们从完整的数组开始，找到中间元素作为根结点，用左侧数组递归地构建左子树，用右侧数组递归地构建右子树即可。

class Solution {
public:
    TreeNode* buildBST(vector<int> &nums, int left, int right) {
        if (left > right) return nullptr;
        int mid = (left + right) / 2;
        TreeNode *leftChild = buildBST(nums, left, mid - 1);
        TreeNode *rightChild = buildBST(nums, mid + 1, right);
        TreeNode *root = new TreeNode(nums[mid], leftChild, rightChild);
        return root;
    }

    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return buildBST(nums, 0, nums.size() - 1);
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(\log n)$。

43. 验证二叉搜索树

https://leetcode.cn/problems/validate-binary-search-tree/description/

二叉搜索树的特性是，中序遍历序列单调递增。利用这个性质，我们就可以完成二叉搜索树的验证。在中序遍历二叉树的同时，维护一个当前最大值 curMax，检查当前节点值是否大于该值，并更新该值为当前节点值。如果能够完成整个遍历，则验证通过。

class Solution {
public:
    long curMax = LONG_MIN;

    bool isValidBST(TreeNode* root) {
        if (!root) return true;
        bool leftValid = isValidBST(root->left);
        if (!leftValid) return false;
        if (root->val <= curMax) return false;
        curMax = root->val;
        bool rightValid = isValidBST(root->right);
        return rightValid;
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

44. 二叉搜索树中第 K 小的元素

https://leetcode.cn/problems/kth-smallest-element-in-a-bst/description/

采用中序遍历，同时对遍历过的数字计数，直到达到第 $k$ 个。对于每一个顶点，如果没有到达第 $k$ 个，则返回 -1；否则返回第 $k$ 个的数值。

class Solution {
public:
    int cnt = 0;
    
    int kthSmallest(TreeNode* root, int k) {
        if (!root) return -1;
        int leftResult = kthSmallest(root->left, k);
        if (leftResult != -1) return leftResult;
        if (++cnt == k) return root->val;
        int rightResult = kthSmallest(root->right, k);
        return rightResult;
    }
};

时间复杂度 $O(H+k)$，空间复杂度 $O(H)$，其中 $H$ 是树的高度。

45. 二叉树的右视图

https://leetcode.cn/problems/binary-tree-right-side-view/description/

本题是基于二叉树的层序遍历的，每一层输出最右侧节点即可，也就是队列中最后弹出的节点。

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        queue<TreeNode*> q;
        if (root) q.push(root);
        while (!q.empty()) {
            int bdth = q.size();
            while (bdth--) {
                TreeNode *cur = q.front(); q.pop();
                if (bdth == 0) result.push_back(cur->val);
                if (cur->left) q.push(cur->left);
                if (cur->right) q.push(cur->right);
            }
        }
        return result;
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

46. 二叉树展开为链表

https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/description/

采用后序遍历：对每个非叶节点，先分别展开左子树和右子树，如果左子树的链表存在，则将该链表插入根结点和右子树的链表之间。

class Solution {
public:
    void flatten(TreeNode* root) {
        if (!root) return;
        flatten(root->left);
        flatten(root->right);
        TreeNode *lnode = root->left, *rnode = root->right;
        if (lnode) {
            root->left = nullptr;
            root->right = lnode;
            while (lnode->right) lnode = lnode->right;
            lnode->right = rnode;
        }
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

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

https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/

采用前序遍历。对于一段前序序列和一段中序序列，先根据前序序列的第一个数字构造根结点，在中序序列中找到该数字，以确定左右子树的范围和大小，分别划分出前序序列和中序序列中左子树和右子树的部分，进而递归地构造左右子树。

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return buildTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }

    TreeNode* buildTree(vector<int>& preorder, int prestart, int preend, vector<int>& inorder, int instart, int inend) {
        if (prestart > preend) return nullptr;
        TreeNode *root = new TreeNode(preorder[prestart]);
        int rootPos;
        for (rootPos = instart; rootPos <= inend; rootPos++) {
            if (inorder[rootPos] == root->val) break;
        }
        int leftSize = rootPos - instart;
        root->left = buildTree(preorder, prestart + 1, prestart + leftSize, inorder, instart, rootPos - 1);
        root->right = buildTree(preorder, prestart + leftSize + 1, preend, inorder, rootPos + 1, inend);
        return root;
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

48. 路径总和 III

https://leetcode.cn/problems/path-sum-iii/description/

采用前序遍历：对于每个节点，先检查是否存在以当前节点为终点的满足总和要求的路径，然后分别检查左右子树中是否存在以其中节点为终点的满足总和要求的路径，将路径数量求和返回。

本题的关键在于，如何找到以当前节点为终点的满足总和要求的路径的数量。考虑使用前缀和，即用前缀表 ht 保存从根结点到当前节点的路径上每个节点的前缀和，然后用当前前缀与 target 相减，如果结果在 ht 中存在，表明存在和为 target 的路径。

class Solution {
public:
    unordered_map<long long, int> ht;

    int traversal(TreeNode *cur, long long prefix, int target) {
        if (!cur) return 0;
        prefix += cur->val;
        int result = 0;
        if (ht.find(prefix - target) != ht.end()) result += ht[prefix - target];
        ht[prefix]++;
        result += traversal(cur->left, prefix, target);
        result += traversal(cur->right, prefix, target);
        ht[prefix]--;
        return result;
    }

    int pathSum(TreeNode* root, int targetSum) {
        ht[0] = 1;
        return traversal(root, 0, targetSum);
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

49. 二叉树的最近公共祖先

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/

本题采用后序遍历。对于每一个节点，如果是 p 或者 q，直接返回当前节点；否则先检查其左子树和右子树是否包含 p 和 q，有三种情况：左子树同时包含 p 和 q，这时左子树会返回其最近公共祖先，我们只需要直接返回左子树结果即可；右子树同时包含 p 和 q，同样只需要直接返回右子树结果；左子树包含 p 且右子树包含 q，那么返回当前节点，因为当前节点是其最近公共祖先。通过这样一个递归的过程，我们就可以找到最近公共祖先。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root) return nullptr;
        if (root == p || root == q) return root;
        TreeNode *lresult = lowestCommonAncestor(root->left, p, q);
        TreeNode *rresult = lowestCommonAncestor(root->right, p, q);
        if (lresult && rresult) return root;
        else if (lresult) return lresult;
        else if (rresult) return rresult;
        else return nullptr;
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

50. 二叉树中的最大路径和

https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/

对于一条路径，应当从一个节点开始，一路向上到一个根结点，再一路向下到一个节点。我们把除了根结点之外的两段分别称为“半路径”，它只包含一个向上或向下的过程，我们把“半路径”的最上层顶点称为“上顶点”。

本题同样采用后序遍历。我们维护一个全局的最大路径和 curMax，对于每个节点 cur，先分别递归地获取左、右子树的最大“半路径和” leftHalfSum 和 rightHalfSum，从而获得以该节点为根的最大路径和 cur->val + leftHalfSum + rightHalfSum，更新 curMax 并返回以该节点为“上顶点”的最大的“半路径和” cur->val + max(leftHalfSum, rightHalfSum)。

注意，在获取子树的最大“半路径和”时，不能使用函数结果，而是将调用结果与 0 比较，如果小于 0，则不取下面的“半路径”，直接使用 0。

class Solution {
public:
    int curMax = INT_MIN;

    int maxHalfSum(TreeNode *root) {
        if (!root) return 0;
        int leftHalfSum = max(maxHalfSum(root->left), 0);
        int rightHalfSum = max(maxHalfSum(root->right), 0);
        curMax = max(curMax, root->val + leftHalfSum + rightHalfSum);
        return root->val + max(leftHalfSum, rightHalfSum);
    }

    int maxPathSum(TreeNode* root) {
        maxHalfSum(root);
        return curMax;
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

图论

51. 岛屿数量

https://leetcode.cn/problems/number-of-islands/description/

基础图论题，求连通分量数，用 BFS 或者 DFS 都可以。

class Solution {
public:
    int dirs[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};

    bool inGrid(int x, int y, int m, int n) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }

    void bfs(vector<vector<char>> &grid, vector<vector<bool>> &visited, int m, int n, int x, int y) {
        queue<pair<int, int>> q;
        q.emplace(x, y); visited[x][y] = true;
        while (!q.empty()) {
            int i = q.front().first, j = q.front().second; q.pop();
            for (int dir = 0; dir < 4; dir++) {
                int newx = i + dirs[dir][0], newy = j + dirs[dir][1];
                if (inGrid(newx, newy, m, n) && grid[newx][newy] == '1' && !visited[newx][newy]) {
                    q.emplace(newx, newy);
                    visited[newx][newy] = true;
                }
            }
        }
        return;
    }

    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        int result = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '0' || visited[i][j]) continue;
                bfs(grid, visited, m, n, i, j);
                result++;
            }
        }
        return result;
    }
};

这里使用 BFS，时间复杂度 $O(mn)$，空间复杂度 $O(mn)$。

52. 腐烂的橘子

https://leetcode.cn/problems/rotting-oranges/description/

不难想到，本题应该使用 BFS，以腐烂的橘子为起点，逐层向外搜索。首先记录所有新鲜橘子个数 fresh。再以所有的腐烂橘子为中心（即先在队列中插入所有腐烂橘子），开始进行广度优先搜索，直至队列为空。此时检查新鲜橘子个数是否为 0，如果不为 0，则不可能全部腐烂。

class Solution {
public:
    int dirs[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};

    bool inGrid(int x, int y, int m, int n) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }

    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int fresh = 0;
        queue<pair<int, int>> q;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) fresh++;
                else if (grid[i][j] == 2) q.emplace(i, j);
            }
        }
        int minute = 0;
        while (!q.empty()) {
            int sz = q.size();
            bool rotted = false;
            while (sz--) {
                auto [i, j] = q.front(); q.pop();
                for (int dir = 0; dir < 4; dir++) {
                    int newx = i + dirs[dir][0], newy = j + dirs[dir][1];
                    if (inGrid(newx, newy, m, n) && grid[newx][newy] == 1) {
                        grid[newx][newy] = 2; 
                        fresh--; rotted = true;
                        q.emplace(newx, newy);
                    }
                }
            }
            if (rotted) minute++;
        }
        return fresh == 0 ? minute : -1;
    }
};

时间复杂度 $O(mn)$，空间复杂度 $O(mn)$。

53. 课程表

https://leetcode.cn/problems/course-schedule/description/

本题考查拓扑排序。首先，创建一个邻接表 adj 记录各条边，并记录各顶点的入度。使用广度优先搜索，先将所有入度为 0 的顶点加入队列。每次访问一个顶点，删除其所有出边，检查是否有顶点入度变为 0，如有则加入队列，直到队列为空。此时检查是否所有顶点已经全部访问，如果是，则可以完成所有课程的学习。

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> adj(numCourses);
        vector<int> indeg(numCourses, 0);
        for (auto &p : prerequisites) {
            int a = p[0], b = p[1];
            adj[b].push_back(a);
            indeg[a]++;
        }
        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (indeg[i] == 0) q.push(i);
        }
        int cnt = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            cnt++;
            for (int v : adj[u]) {
                if (--indeg[v] == 0) q.push(v);
            }
        }
        return cnt == numCourses;
    }
};

时间复杂度 $O(n + m)$，空间复杂度 $O(n + m)$，其中 $n$ 为课程数，$m$ 为先修课程的要求数。

54. 实现 Trie (前缀树)

https://leetcode.cn/problems/implement-trie-prefix-tree/description/

本题需要实现一个标准的字典树。其核心思想是：每个节点代表一个前缀，往下走一条边就多一个字符。对于每个节点，需要一个指向子节点的指针 children[26] 和一个标志 isEnd 来标记是否有单词在这里结束。

class Trie {
public:
    struct Node {
        Node *child[26];
        bool isEnd;
        Node() : isEnd(false) {
            for (int i = 0; i < 26; i++) child[i] = nullptr;
        }
    };

    Node *root;

    Trie() {
        root = new Node();
    }
    
    void insert(string word) {
        Node *cur = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!cur->child[idx]) cur->child[idx] = new Node();
            cur = cur->child[idx];
        }
        cur->isEnd = true;
    }
    
    bool search(string word) {
        Node *cur = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!cur->child[idx]) return false;
            cur = cur->child[idx];
        }
        return cur->isEnd;
    }
    
    bool startsWith(string prefix) {
        Node *cur = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (!cur->child[idx]) return false;
            cur = cur->child[idx];
        }
        return true;
    }
};

时间复杂度：初始化 $O(1)$，其余 $O(|S|)$，其中 $∣S∣$ 是插入或查询的字符串的长度；空间复杂度：$O(∣T∣\cdot\Sigma)$，其中 $∣T∣$ 为所有插入字符串的长度之和，$\Sigma$ 为字符集的大小（本题中为 26）。

回溯

55. 全排列

https://leetcode.cn/problems/permutations/description/

本题使用回溯来收集所有排列。当所有数字都已经使用时，收集结果；否则，依次加入还没有使用的数字，并递归地选择接下来的数字。所谓回溯，就是在递归返回后，撤销当前的选择，并选择下一个候选数字再次递归。

为了避免重复使用数字，我们使用一个数组 used 记录当前已经使用的数字，这样可以在选择下一个数字时跳过已经使用的。

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;

    void backtracking(vector<int> &nums, vector<bool> &used) {
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (used[i]) continue;
            used[i] = true;
            path.push_back(nums[i]);
            backtracking(nums, used);
            path.pop_back();
            used[i] = false;
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};

时间复杂度 $O(n \times n!)$，空间复杂度 $O(n)$。

56. 子集

https://leetcode.cn/problems/subsets/description/

使用回溯法，依次考虑每个数字是否使用。当所有数字都被考虑了之后，收集结果；否则考虑下一个数字，分为“使用”和“不使用”两种情况，分别递归和回溯。代码中 idx 表示当前处理到下标为 idx 的数字。

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;

    void backtracking(vector<int> &nums, int idx) {
        if (idx == nums.size()) {
            result.push_back(path);
            return;
        }
        path.push_back(nums[idx]);
        backtracking(nums, idx + 1);
        path.pop_back();
        backtracking(nums, idx + 1);
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        backtracking(nums, 0);
        return result;
    }
};

时间复杂度：$O(n \times 2^n)$，一共 $2^n$ 个状态，每个状态要 $O(n)$ 时间构造子集；空间复杂度：$O(n)$，path 的空间代价及递归栈空间均为 $O(n)$。

57. 电话号码的字母组合

https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/

本题采用回溯法，思路和之前几题相似。每次转换 1 位数字，递归直至整个字符串都被转换，收集结果，再逐层回溯，遍历所有可能的字母。

class Solution {
public:
    unordered_map<char, vector<char>> ht = {
        {'2', {'a', 'b', 'c'}}, {'3', {'d', 'e', 'f'}},
        {'4', {'g', 'h', 'i'}}, {'5', {'j', 'k', 'l'}},
        {'6', {'m', 'n', 'o'}}, {'7', {'p', 'q', 'r', 's'}},
        {'8', {'t', 'u', 'v'}}, {'9', {'w', 'x', 'y', 'z'}}
    };

    string cur;
    vector<string> result;

    void backtracking(string &digits, int idx) {
        if (idx == digits.length()) {
            result.push_back(cur);
            return;
        }
        for (char c : ht[digits[idx]]) {
            cur.push_back(c);
            backtracking(digits, idx + 1);
            cur.pop_back();
        }
    }

    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return result;
        backtracking(digits, 0);
        return result;
    }
};

时间复杂度 $O(n \times 4^n)$，空间复杂度 $O(n)$。

58. 组合总和

https://leetcode.cn/problems/combination-sum/description/

采用回溯法。依次往结果中加入每个数字，直至和超过 target，收集结果（若和等于 target），然后开始回溯，遍历每个位置所有的候选数字。为了避免重复，不能往结果中加入当前位置之前的数字，这一规则用变量 idx 控制。

class Solution {
public:
    int sum;
    vector<int> cur;
    vector<vector<int>> result;

    void backtracking(vector<int>& candidates, int target, int idx) {
        if (sum >= target) {
            if (sum == target) result.push_back(cur);
            return;
        }
        for (int i = idx; i < candidates.size(); i++) {
            cur.push_back(candidates[i]);
            sum += candidates[i];
            backtracking(candidates, target, i);
            sum -= candidates[i];
            cur.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backtracking(candidates, target, 0);
        return result;
    }
};

时间复杂度 $O(n^{\mathrm{target} / \mathrm{min}})$，空间复杂度 $O(\mathrm{target} / \mathrm{min})$，其中 $\mathrm{min}$ 是 candidates 中的最小值。

59. 括号生成

https://leetcode.cn/problems/generate-parentheses/description/

本题采用回溯法。每一步考虑放 ( 或 )，如果所有括号都放完，收集结果，然后回溯。注意约束条件，当剩余 ) 数量不多于 ( 时，只能放 (。代码中 left 和 right 分别表示剩余 ( 和 ) 的数量。

class Solution {
public:
    string cur;
    vector<string> result;

    void backtracking(int n, int left, int right) {
        if (right == 0) {
            result.push_back(cur);
            return;
        }
        if (left > 0) {
            cur.push_back('(');
            backtracking(n, left - 1, right);
            cur.pop_back();
        }
        if (right > left) {
            cur.push_back(')');
            backtracking(n, left, right - 1);
            cur.pop_back();
        }
    }

    vector<string> generateParenthesis(int n) {
        backtracking(n, n, n);
        return result;
    }
};

时间复杂度 $O(\dfrac{4^n}{\sqrt{n}})$，因为有效括号组合数由第 $n$ 个卡特兰数 $\dfrac{1}{n+1}\dbinom{2 n}{n}$ 给出；空间复杂度 $O(n)$。

60. 单词搜索

https://leetcode.cn/problems/word-search/description/

采用回溯的方法。当匹配到和 word 长度相等时，收集结果；否则，向四个方向分别递归地尝试匹配，匹配到错误或成功后回溯。需要注意的是，要用一个 visited 数组记录每个单元格是否使用过，以避免重复使用。

class Solution {
public:
    int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    bool inGrid(vector<vector<char>>& board, int x, int y) {
        return x >= 0 && x < board.size() && y >= 0 && y < board[0].size();
    }

    bool backtracking(vector<vector<char>>& board, vector<vector<bool>> &visited, string &word, int x, int y, int idx) {
        if (idx == word.length() - 1) return true;
        visited[x][y] = true;
        bool result = false;
        for (auto dir: dirs) {
            int newx = x + dir[0], newy = y + dir[1];
            if (inGrid(board, newx, newy) && !visited[newx][newy] && board[newx][newy] == word[idx + 1]) {
                if (backtracking(board, visited, word, newx, newy, idx + 1)) {
                    result = true;
                    break;
                }
            }
        }
        visited[x][y] = false;
        return result;
    }

    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size(), n = board[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] != word[0]) continue;
                if (backtracking(board, visited, word, i, j, 0)) return true; 
            }
        }
        return false;
    }
};

时间复杂度 $O(mn \times 3^L)$，其中 $L$ 是 word 的长度；空间复杂度 $O(mn)$。

61. 分割回文串

https://leetcode.cn/problems/palindrome-partitioning/description/

采用回溯法。当所有字符都被分割完后，收集结果；否则，从当前位置继续向后，尝试递归地分割回文串，然后回溯，并尝试下一种分割方法。

class Solution {
public:
    vector<string> cur;
    vector<vector<string>> result;

    bool isPalindrome(const string &s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) {
                return false;
            } else {
                left++;
                right--;
            }
        }
        return true;
    }

    void backtracking(const string &s, int left) {
        if (left == s.length()) {
            result.push_back(cur);
            return;
        }
        for (int right = left; right < s.length(); right++) {
            if (!isPalindrome(s, left, right)) continue;
            cur.push_back(s.substr(left, right - left + 1));
            backtracking(s, right + 1);
            cur.pop_back();
        }
    }

    vector<vector<string>> partition(string s) {
        backtracking(s, 0);
        return result;
    }
};

时间复杂度 $O(n \times 2^n)$，空间复杂度 $O(n)$。

62. N 皇后

https://leetcode.cn/problems/n-queens/description/

采用回溯法。为每一行依次挑选 Q 的位置，当所有行的 Q 都已经选好位置，收集结果；否则，依次尝试当前行的每一列是否可以放置 Q，如果合法，则递归并回溯。

isValid 函数用于检查在当前位置摆放 Q 是否合法。

class Solution {
public:
    vector<string> path;
    vector<vector<string>> result;

    bool isValid(int n, int row, int column) {
        for (int i = 0; i < row; i++) {
            if (path[i][column] == 'Q') return false;
        }
        for (int i = row - 1, j = column - 1; i >= 0 && j >= 0; i--, j--) {
            if (path[i][j] == 'Q') return false;
        }
        for (int i = row - 1, j = column + 1; i >= 0 && j < n; i--, j++) {
            if (path[i][j] == 'Q') return false;
        }
        return true;
    }

    void backtracking(int n, int row) {
        if (row == n) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!isValid(n, row, i)) continue;
            path[row][i] = 'Q';
            backtracking(n, row + 1);
            path[row][i] = '.';
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        string row(n, '.');
        for (int i = 0; i < n; i++)
            path.push_back(row);
        backtracking(n, 0);
        return result;
    }
};

时间复杂度 $O(n^2 \times n!)$，空啊金复杂度 $O(n^2)$。

二分查找

63. 搜索插入位置

https://leetcode.cn/problems/search-insert-position/description/

本题是最基本的二分查找题，但要注意终止条件及返回值。搜素区间是 [left, right]，所以终止条件是 left > right。如果查找失败，此时 left 在 right 右侧一格，left 左侧的元素都小于 target，right 右侧的元素都大于 target，所以应该插入的位置是 left。

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

时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。

64. 搜索二维矩阵

https://leetcode.cn/problems/search-a-2d-matrix/description/

在本题中，下一行的元素全部大于上一行的元素，性质非常好。先在行的维度上做二分查找，再在该行中做二分查找。第一轮二分查找的不变量是，left 左侧的数字都小于 target，right 右侧的数字都大于 target，因此终止条件是 left > right，且 target 可能所在行是 right。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int left = 0, right = m - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (matrix[mid][0] == target) return true;
            else if (matrix[mid][0] < target) left = mid + 1;
            else right = mid - 1;
        }
        int row = right;
        if (row < 0 || row >= m) return false;
        left = 0, right = n - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (matrix[row][mid] == target) return true;
            else if (matrix[row][mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return false;
    }
};

时间复杂度 $O(\log mn)$，空间复杂度 $O(1)$。

65. 在排序数组中查找元素的第一个和最后一个位置

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/

本题使用二分查找，抓住不变量即可。可以使用两次二分搜索法，第一次：left 左侧的数字都小于 target，right 右侧的数字都大于或等于 target，找到左边界；第二次：left 左侧的数字都小于或等于 target，right 右侧的数字都大于 target，找到右边界。

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

时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。

66. 搜索旋转排序数组

https://leetcode.cn/problems/search-in-rotated-sorted-array/description/

这道题的时间要求是 $O(\log n)$，表明要使用类似二分查找的算法。每次从中间 mid 处将数组分为两半，至少有一个是顺序区间（可以通过左右端点值判断）。通过对比端点数值和 target 的大小，可以确定 target 在哪一半，这样就可以继续二分查找，直到进入顺序区间，采用二分法即可。

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

时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。

67. 寻找旋转排序数组中的最小值

https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/

和上一题类似，采用二分查找得到答案，目标是找到交界点。不变量是：left 左侧的元素都大于等于 nums[0]，right 右侧的元素都小于等于 nums[-1]，终止条件为 left > right，最终 left 即为答案。注意，如果 left == nums.size()，表明最小的数字是 nums[0]。

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

时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。

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

https://leetcode.cn/problems/median-of-two-sorted-arrays/description/

这道题的基本思路是，取出两个数组各自的中位数 nums1[mid1] 和 nums2[mid2] 比较，如果 nums1[mid1] < nums2[mid2]，那么 nums1[0:mid1] 不可能是中位数，接着继续在 nums1[mid1+1:] 和 nums2 中继续类似过程。

函数 find() 的作用是找到 nums1[l1:] 和 nums2[l2:] 合并后的序列中第 k 个元素。

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int len = nums1.size() + nums2.size();;
        if (len % 2 == 1) return find(nums1, 0, nums2, 0, len / 2 + 1);
        else {
            int left = find(nums1, 0, nums2, 0, len / 2);
            int right = find(nums1, 0, nums2, 0, len / 2 + 1);
            return (left + right) / 2.0;
        }
    }

    int find(vector<int> &nums1, int l1, vector<int> &nums2, int l2, int k) {
        int m = nums1.size(), n = nums2.size();
        if (l1 == m) return nums2[l2 + k - 1];
        if (l2 == n) return nums1[l1 + k - 1];
        if (k == 1) return min(nums1[l1], nums2[l2]);
        int mid1 = min(l1 + k / 2 - 1, m - 1), mid2 = min(l2 + k / 2 - 1, n - 1);
        if (nums1[mid1] < nums2[mid2]) {
            return find(nums1, mid1 + 1, nums2, l2, k - (mid1 - l1 + 1));
        } else {
            return find(nums1, l1, nums2, mid2 + 1, k - (mid2 - l2 + 1));
        }
    }
};

时间复杂度 $O(\log mn)$，空间复杂度 $O(1)$。

栈

69. 有效的括号

https://leetcode.cn/problems/valid-parentheses/description/

一道简单的括号匹配题。从左至右依次扫描各个括号，如果是左括号，压入栈中；如果是右括号，检查其与栈顶的左括号是否匹配，若匹配则弹出，否则不能匹配。最后需要检查栈是否为空，即是否有多余的左括号。

class Solution {
public:
    unordered_map<char, char> ht = {{')', '('}, {']', '['}, {'}', '{'}};

    bool isValid(string s) {
        stack<char> st;
        for (char &ch : s) {
            if (!ht.count(ch)) st.push(ch);
            else if (!st.empty() && st.top() == ht[ch]) st.pop();
            else return false;
        }
        return st.empty();
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(n + |\Sigma|)$，其中 $\Sigma$ 表示字符集。

70. 最小栈

https://leetcode.cn/problems/min-stack/description/

本题要求在普通栈的基础上增加一个功能，即在常数时间内检索到最小元素。我们可以借助一个辅助栈，两个栈同步进行 push 和 pop 操作，辅助栈的对应位置存放该元素作为栈顶时的最小元素。当一个元素入栈时，辅助栈加入辅助栈栈顶和该元素中更小的一个。

class MinStack {
private:
    stack<int> st;
    stack<int> minst;
public:
    MinStack() {
        minst.push(INT_MAX);
    }
    
    void push(int val) {
        st.push(val);
        minst.push(min(minst.top(), val));
    }
    
    void pop() {
        st.pop();
        minst.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return minst.top();
    }
};

时间复杂度 $O(1)$，空间复杂度 $O(n)$，其中 $n$ 为总操作数。

71. 字符串解码

https://leetcode.cn/problems/decode-string/description/

本题使用栈来递归地处理子结构，栈中存放 {cur, num} 对，其中 cur 是当前已经构造的字符串，num 是当前重复次数。从左到右扫描字符串：当遇到数字时，更新 num 以处理多位数；当遇到普通字符时，加入 cur；当遇到 [ 时，表明进入子结构，把当前状态压栈，然后重置 cur = "" 及 num = 0；当遇到 ] 时，表明一个子串结束，弹出栈顶 {prev, k}，我们将 cur 拼接 k 次并连接到 prev 之后，作为新的 cur。

class Solution {
public:
    string decodeString(string s) {
        stack<pair<string, int>> st;
        int num = 0;
        string cur;
        for (char c : s) {
            if (isdigit(c)) {
                num = 10 * num + (c - '0');
            } else if (c == '[') {
                st.push({cur, num});
                num = 0; cur = "";
            } else if (c == ']') {
                auto [prev, k] = st.top(); st.pop();
                while (k--) prev += cur;
                cur = prev;
            } else {
                cur += c;
            }
        }
        return cur;
    }
};

时间复杂度 $O(S)$，空间复杂度 $O(S)$，其中 $S$ 时

72. 每日温度

https://leetcode.cn/problems/daily-temperatures/description/

这是一道经典的单调栈题目。维护一个单调栈，从栈底到栈顶的气温单调递减。从左到右扫描数组，对于每一个元素，弹出栈顶所有比它低的温度，这些弹出元素的下一个更高气温就是当前元素，再将该元素加入栈顶。

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

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

73. 柱状图中最大的矩形

https://leetcode.cn/problems/largest-rectangle-in-histogram/description/

简单的想法是，对于每个柱子 i，把 heights[i] 当作矩形高度，向左扩展直到遇到比它矮的柱子，向右扩展直到遇到比它矮的柱子，于是可以求出面积。因此问题变成，如何对每个 i，找到左边第一个更小元素以及右边死一个更小元素。其实这就和“每日温度”差不多了。

维护一个单调栈，从栈底到栈顶，高度单调递增。对于每个柱子，如果比栈顶更矮，表明栈顶部分柱子的右边界确定了。弹出栈顶元素 mid，此时左边界是新的栈顶，右边界是当前柱子，高度是 heights[mid]，就可以计算面积了。

注意，最好在初始数组的首尾加 0 作为哨兵，避免写很多特判，并且末尾 0 会把所有柱子弹出来计算面积。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.insert(heights.begin(), 0);
        heights.push_back(0);

        stack<int> st;
        int result = 0;

        for (int i = 0; i < heights.size(); i++) {
            while (!st.empty() && heights[st.top()] > heights[i]) {
                int mid = st.top(); st.pop();
                if (!st.empty()) {
                    int h = heights[mid];
                    int w = i - st.top() - 1;
                    result = max(result, h * w);
                }
            }
            st.push(i);
        }
        
        return result;
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

堆

74. 数组中的第 K 个最大元素

https://leetcode.cn/problems/kth-largest-element-in-an-array/description/

这道题有两种经典的做法。首先是快速选择算法。选择一个枢轴 pivot，将数组划分为小于 pivot 和大于 pivot 的两个，然后根据 k 的位置选择其中一边，递归操作，直到找到第 k 大的元素。为了让算法性能更好，我们每次随机选择枢轴。划分的具体方法是：使用双指针，一个从左向右扫描，一个从右向左扫描，分别找到第一个左侧大于 pivot 的数和右侧小于 pivot 的数，然后交换，直到两个指针相遇。

class Solution {
public:
    int partition(vector<int> &nums, int left, int right) {
        int idx = left + rand() % (right - left + 1);
        swap(nums[left], nums[idx]);
        int pivot = nums[left];
        int i = left + 1, j = right;
        while (i <= j) {
            while (i <= j && nums[i] < pivot) i++;
            while (i <= j && nums[j] > pivot) j--;
            if (i <= j) swap(nums[i++], nums[j--]);
        }
        swap(nums[left], nums[j]);
        return j;
    }

    int quickSelect(vector<int>& nums, int left, int right, int target) {
        if (left == right) return nums[target];
        int pivot = partition(nums, left, right);
        if (pivot == target) return nums[pivot];
        else if (pivot < target) return quickSelect(nums, pivot + 1, right, target);
        else return quickSelect(nums, left, pivot - 1, target);
    }

    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        return quickSelect(nums, 0, n - 1, n - k);
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(\log n)$（递归用栈）。

第二种方法是用堆来做。我们建立一个大小为 k 的小根堆，堆顶元素即为第 k 大的元素。

class Solution {
public:
    void buildHeap(vector<int> &heap, int len) {
        for (int i = len / 2; i > 0; i--) {
            heapAjust(heap, i, len);
        }
    }

    void heapAjust(vector<int> &heap, int i, int len) {
        heap[0] = heap[i];
        for (int j = 2 * i; j <= len; j *= 2) {
            if (j < len && heap[j] > heap[j + 1]) j++;
            if (heap[0] <= heap[j]) break;
            heap[i] = heap[j];
            i = j;
        } 
        heap[i] = heap[0];
    }

    int findKthLargest(vector<int>& nums, int k) {
        vector<int> heap(k + 1, 0);
        for (int i = 1; i <= k; i++) heap[i] = nums[i - 1];
        buildHeap(heap, k);
        for (int i = k; i < nums.size(); i++) {
            if (nums[i] > heap[1]) heap[1] = nums[i];
            heapAjust(heap, 1, k);
        }
        return heap[1];
    }
};

事实上，我们不需要自己实现小顶堆。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> pq;
        for (int x : nums) {
            if (pq.size() < k) pq.push(x);
            else if (pq.top() < x) {
                pq.pop();
                pq.push(x);
            }
        }
        return pq.top();
    }
};

时间复杂度 $O(n \log k)$，空间复杂度 $O(k)$。

75. 前 K 个高频元素

https://leetcode.cn/problems/top-k-frequent-elements/description/

和上一题类似，但要增加一个哈希表来记录每个元素出现的次数。使用一个小顶堆，存储 (元素，出现次数) 的二元组，并按照出现次数排序。当有一个出现次数大于堆顶元素出现次数的元素时，弹出堆顶元素，并将当前元素加入队列。

class Solution {
public:
    struct cmp {
        bool operator()(pair<int, int> &a, pair<int, int> &b) {
            return a.second > b.second;
        }
    };

    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> ht;
        for (int x : nums) ht[x]++;

        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
        for (auto &[num, count] : ht) {
            if (pq.size() < k) pq.push({num, count});
            else if (pq.top().second < count) {
                pq.pop();
                pq.push({num, count});
            }
        }
        vector<int> result;
        while (!pq.empty()) {
            result.push_back(pq.top().first); pq.pop();
        }
        return result;
    }
};

时间复杂度 $O(n \log k)$，空间复杂度 $O(n)$。

76. 数据流的中位数

https://leetcode.cn/problems/find-median-from-data-stream/description/

使用一个大顶堆 qmin 记录更小的一半元素，一个小顶堆 qmax 记录更大的一半元素，qmin 中元素数量和 qmax 相等或多一个。

当查找中位数时，如果元素总数是奇数，返回 qmin 的堆顶元素；如果元素总数是偶数，返回两堆堆顶元素的平均值。

当插入元素 num 时，比较其和 qmin 堆顶元素的大小，如果 num 更大，则插入 qmax，否则插入 qmin。插入后，需要平衡两个堆中的元素数量，保证元素数量关系。

class MedianFinder {
public:
    priority_queue<int> qmin;
    priority_queue<int, vector<int>, greater<int>> qmax;

    MedianFinder() {}
    
    void addNum(int num) {
        if (qmin.empty() || num <= qmin.top()) {
            qmin.push(num);
            if (qmin.size() - qmax.size() > 1) {
                qmax.push(qmin.top());
                qmin.pop();
            }
        } else {
            qmax.push(num);
            if (qmin.size() < qmax.size()) {
                qmin.push(qmax.top());
                qmax.pop();
            }
        }
    }
    
    double findMedian() {
        if (qmin.size() > qmax.size()) return qmin.top();
        else return (qmin.top() + qmax.top()) / 2.0;
    }
};

时间复杂度：addNum 为 $O(\log n)$，findMedian 为 $O(1)$；空间复杂度：$O(n)$，其中 $n$ 为累计添加的数的数量。

贪心算法

77. 买卖股票的最佳时机

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/

这题比较直观，采用贪心的思路，在最低点买入，最高点卖出。我们只要维护一个过去的最低价格 low，以及当前能获得的最大利润 profit 即可。

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

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

78. 跳跃游戏

https://leetcode.cn/problems/jump-game/description/

采用贪心的方法。维护一个变量 max_reach 表示当前能到达的最大距离，从左到右遍历数组，如果当前下标超过 max_reach，表明无法达到终点，返回 false；否则，更新 max_reach。

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

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

79. 跳跃游戏 II

https://leetcode.cn/problems/jump-game-ii/description/

与上一题的做法类似，但是要加入步数的记录。cur_step 表示当前步数，max_step 记录当前步数能到达的最远距离，next_step 是增加一步能到达的已知最远距离。从左到右遍历数组，当超过 max_step 时，增加当前步数 cur_step，并用 next_step 更新 max_step；否则，更新 next_step。

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int cur_step = 0, max_reach = 0, next_reach = 0;
        for (int i = 0; i < n; i++) {
            if (i > max_reach) {
                cur_step++;
                max_reach = next_reach;
            }
            next_reach = max(next_reach, i + nums[i]);
        }
        return cur_step;
    }
};

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

80. 划分字母区间

https://leetcode.cn/problems/partition-labels/description/

采用贪心的做法。考虑我们看到一个字母，如果这个字母之后还会出现，那么当前片段必须延伸到那个位置。也就是说问题变为，每个字母最后出现的位置在哪里。

我们先统计每个字母最后出现的位置，保存在哈希表 farthest 中，再从左向右扫描字符串，当看到一个字符 s[i] 时，这个字符串的至少要延伸到 farthest[s[i]]，变量 expectEnd 维护了当前字符串至少延伸到的位置。当到达 expectEnd 位置时，切割字符串。

class Solution {
public:
    vector<int> partitionLabels(string s) {
        unordered_map<char, int> farthest;
        for (int i = 0; i < s.length(); i++) farthest[s[i]] = i;
        vector<int> result;
        int start = 0, expectEnd = 0;
        for (int i = 0; i < s.length(); i++) {
            expectEnd = max(expectEnd, farthest[s[i]]);
            if (i == expectEnd) {
                result.push_back(expectEnd - start + 1);
                start = expectEnd + 1;
            }
        }
        return result;
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(|\Sigma|)$。

动态规划

81. 爬楼梯

https://leetcode.cn/problems/climbing-stairs/description/

动态规划题目注意：dp 数组含义、递推公式、初始化、遍历顺序。

本题中，dp[i] 表示到达第 i 个台阶的方法数；递推公式是 dp[i] = dp[i - 1] + dp[i - 2]；初始化 dp[0] = dp[1] = 1；遍历顺序是从小到大。

可以采用滚动数组优化空间。

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp = {1, 1};
        for (int i = 2; i <= n; i++) {
            int sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];
    }
};

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

82. 杨辉三角

https://leetcode.cn/problems/pascals-triangle/description/

本题模拟过程即可。dp[i][j] 表示第 i 行第 j 个元素；递推公式是 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]；初始化 dp[i][0] = dp[i][i] = 1；遍历顺序是 i 从小到大。

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> dp(numRows);
        for (int i = 0; i < numRows; i++) {
            dp[i].resize(i + 1);
            dp[i][0] = dp[i][i] = 1;
            for (int j = 1; j < i; j++) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            }
        }
        return dp;
    }
};

时间复杂度 $O(numRows^2)$，空间复杂度 $O(1)$。

83. 打家劫舍

https://leetcode.cn/problems/house-robber/description/

dp[i] 表示前 i 家偷到的最大金额；递推公式 dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])；初始化 dp[0] = nums[0]、dp[1] = max(nums[0], nums[1])；遍历顺序 i 从小到大。

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

时间复杂度 $O(n)$；空间复杂度 $O(n)$，可以使用滚动数组优化到 $O(1)$。

84. 完全平方数

https://leetcode.cn/problems/perfect-squares/description/

本题是完全背包问题的变体。

dp[i] 表示和为 i 的完全平方数的最少数量；递推公式为

$$dp[i] = 1 + \min_{j=1}^{\sqrt{i}} dp[i - j^2]$$

；初始化 dp[0] = 0；遍历顺序：对于每个从小到大的 i，从小到大遍历 j。

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

时间复杂度 $O(n \sqrt{n})$，空间复杂度 $O(n)$。

85. 零钱兑换

https://leetcode.cn/problems/coin-change/description/

本题和上题非常之像，也是完全背包的变体。

dp[i] 表示凑成 i 所需要的最少硬币个数；递推公式为

$$dp[i] = 1 + \min_{j=0}^{n-1} dp[i - coins[j]]$$

；初始化 dp[0] = 0；遍历顺序：对于每个从小到大的 i，从小到大遍历 j。

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

时间复杂度 $O(Sn)$，空间复杂度 $O(S)$，其中 $S$ 是金额。

86. 单词拆分

https://leetcode.cn/problems/word-break/description/

和前两题类似，本题是完全背包问题的变体。

dp[i] 表示前 i 个字符是否能被 wordDict 中的字符串表示；递推公式是

$$dp[i] = \bigvee_{j = 0}^{i-1} dp[j] \wedge check(s[j..i-1])$$

其中 $check(s[j...i-1])$ 表示子串 $s[j...i-1]$ 出现在 wordDict 中；初始化 dp[0] = true；遍历顺序：对于每个从小到大的 i，从小到大遍历 j。

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> ht;
        for (auto word: wordDict) ht.insert(word); 
        vector<bool> dp(s.length() + 1, false);
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && ht.find(s.substr(j, i - j)) != ht.end()) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
};

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$，其中 $n$ 为字符串 $s$ 的长度。

87. 最长递增子序列

https://leetcode.cn/problems/longest-increasing-subsequence/description/

这是一道经典动态规划题目。

基本做法是：dp[i] 表示以第 i 个数结尾的最长递增子序列长度；递推公式是

$$dp[i] = \max_{j < i, a_j < a_i}\{dp[j] + 1\}$$

初始化 dp[0] = 0；遍历顺序是 i 从小到大。该方法的时间复杂度为 $O(n^2)$。

考虑使用优先级队列优化。维护一个潜在前缀列表 dp，其中 dp[len] 表示长度为 len 的递增子序列的最小末尾值。由于该列表单调递增，查找过程可优化为二分搜索。算法步骤为：

1. 初始化 dp[0] = INT_MIN
2. 对每个 nums[i]：
   • 二分查找使得 nums[i] > dp[len] 的最大 len
   • 更新 dp[len + 1] = nums[i]
3. 输出更新过的最大 len

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp = {INT_MIN};
        for (int i = 0; i < nums.size(); i++) {
            int left = 0, right = dp.size() - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (nums[i] > dp[mid]) left = mid + 1;
                else right = mid - 1;
            }
            if (right + 1 < dp.size()) dp[right + 1] = nums[i];
            else dp.push_back(nums[i]);
        }
        return dp.size() - 1;
    }
};

时间复杂度 $O(n \log n)$，空间复杂度 $O(n)$。

88. 乘积最大子数组

https://leetcode.cn/problems/maximum-product-subarray/description/

维护两个 dp 数组，dp1[i] 表示以 nums[i] 结尾的最大乘积子数组的乘积，dp2[i] 表示以 nums[i] 结尾的最小乘积子数组的；递推公式是 dp1[i] = max(dp1[i-1] * nums[i], dp2[i-1] * nums[i], nums[i])，dp2[i] = min(dp1[i-1] * nums[i], dp2[i-1] * nums[i], nums[i])；初始化 dp1[0] = dp2[0] = nums[0]；遍历顺序 i 从小到大。

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        vector<int> dp1(nums.size()), dp2(nums.size());
        dp1[0] = dp2[0] = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            dp1[i] = max(dp1[i-1] * nums[i], max(dp2[i-1] * nums[i], nums[i]));
            dp2[i] = min(dp1[i-1] * nums[i], min(dp2[i-1] * nums[i], nums[i]));
        }
        int result = INT_MIN;
        for (int i = 0; i < nums.size(); i++)
            result = max(result, dp1[i]);
        return result;
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

89. 分割等和子集

https://leetcode.cn/problems/partition-equal-subset-sum/description/

这道题是 0-1 背包问题的变体。假设所有元素和为 sum，那么问题等价于，是否能从集合中选出一些元素，使得它们的和等于 sum/2。

dp[i][j] 表示从 dp[0:i]（包含 i）中选取数字，是否能组成和为 j；递推公式是

$$dp[j] = \begin{cases} dp[i-1][j] \lor dp[i-1][j - nums[i]], & j \ge nums[i] \\ dp[i-1][j] , & j < nums[i] \end{cases}$$

初始化 dp[i][0] = true；遍历顺序为外层 i 从小到大，内层 j 从小到大。

也可以进行状态压缩，递推公式变为：

$$dp[j] = \begin{cases} dp[j] \lor dp[j - nums[i]], & j \ge nums[i] \\ dp[j] , & j < nums[i] \end{cases}$$

初始化 dp[0] = dp[nums[0]] = true，其余为 false；遍历顺序为外层 i 从小到大，内层 j 从大到小。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        int max_num = *max_element(nums.begin(), nums.end());
        int target = sum / 2;
        if (sum % 2 == 1 || max_num > target) return false;
        vector<bool> dp(target + 1, false);
        dp[0] = dp[nums[0]] = true;
        for (int i = 1; i < nums.size(); i++) {
            for (int j = target; j > 0; j--) {
                if (j < nums[i]) continue;
                dp[j] = dp[j] || dp[j - nums[i]];
            }
        }
        return dp[target];
    }
};

时间复杂度 $O(n \times target)$，空间复杂度 $O(target)$。

90. 最长有效括号

https://leetcode.cn/problems/longest-valid-parentheses/description/

dp[i] 表示以下标 i 结尾的最长有效括号长度；递推公式是：

• 如果 s[i] == '('，那么 dp[i] = 0；
• 如果 s[i] == ')' 且 s[i-1] == '('，那么 dp[i] = dp[i - 2] + 2；
• 如果 s[i] == ')' 且 s[i-1] == ')'，如果 s[i-dp[i-1]-1] == '('，那么 dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2；

初始化 dp[0] = 0；遍历顺序 i 从小到大。

class Solution {
public:
    int longestValidParentheses(string s) {
        if (s.length() == 0) return 0;
        vector<int> dp(s.length(), 0);
        for (int i = 1; i < s.length(); i++) {
            if (s[i] == '(') continue;
            if (s[i - 1] == '(') {
                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
            } else {
                if (i > dp[i - 1] && s[i - dp[i - 1] - 1] == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
            }
        }
        int result = *max_element(dp.begin(), dp.end());
        return result;
    }
};

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

多维动态规划

91. 不同路径

https://leetcode.cn/problems/unique-paths/description/

dp[i][j] 表示走到 [i, j] 的路径数；递推公式 dp[i][j] = dp[i-1][j] + dp[i][j-1]；初始化 dp[i][0] = dp[0][j] = 1；遍历顺序 i 和 j 都从小到大。

使用滚动数组优化。递推公式 dp[j] = dp[j] + dp[j-1]；初始化 dp[j] = 1；遍历顺序为外层 i 从小到大，内层 j 从小到大。

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

时间复杂度 $O(mn)$，空间复杂度 $O(n)$。

92. 最小路径和

https://leetcode.cn/problems/minimum-path-sum/description/

dp[i][j] 表示走到 [i, j] 的最小路径和；递推公式 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]；初始化首行和首列；遍历顺序 i 和 j 都从小到大。

使用滚动数组优化。递推公式 dp[j] = min(dp[j], dp[j-1]) + grid[i][j]；按意义初始化；遍历顺序为外层 i 从小到大，内层 j 从小到大。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<int> dp(n);
        int sum = 0;
        for (int j = 0; j < n; j++) {
            sum += grid[0][j];
            dp[j] = sum;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[j] = (j > 0 ? min(dp[j], dp[j-1]) : dp[j]) + grid[i][j];
            }
        }
        return dp[n-1];
    }
};

时间复杂度 $O(mn)$，空间复杂度 $O(n)$。

93. 最长回文子串

https://leetcode.cn/problems/longest-palindromic-substring/description/

dp[i][j] 表示 s[i:j] 是回文串；递推公式 dp[i][j] = dp[i+1][j-1] && (s[i] == s[j])；初始化 dp[i][i] = true，dp[i][i+1] = (s[i] == s[j])；遍历顺序外层 k = j - i 从小到大，内层 i 从小到大。

class Solution {
public:
    string longestPalindrome(string s) {
        vector<vector<bool>> dp(s.length(), vector<bool>(s.length(), false));
        pair<int, int> result;
        for (int k = 0; k < s.length(); k++) {
            for (int i = 0; i + k < s.length(); i++) {
                int j = k + i;
                if (k == 0) dp[i][i] = true;
                else if (k == 1) dp[i][i+1] = (s[i] == s[i+1]);
                else dp[i][j] = dp[i+1][j-1] && (s[i] == s[j]);
                if (dp[i][j]) result = {i, j};
            }
        }
        auto [start, end] = result;
        return s.substr(start, end - start + 1);
    }
};

时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$。

94. 最长公共子序列

https://leetcode.cn/problems/longest-common-subsequence/description/

dp[i][j] 表示 text1[0:i] 和 text2[0:j]（均左闭右开）的最长公共子序列的长度；递推公式是

$$dp[i][j] = \begin{cases} dp[i-1][j-1] + 1, & text1[i] == text2[j] \\ \max(dp[i-1][j], dp[i][j-1]), & \text{otherwise} \end{cases}$$

初始化 dp[i][0] = dp[0][j] = 0；遍历顺序 i 和 j 分别从小到大。

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, 0));
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1[i - 1] == text2[j - 1]) {
                    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];
    }
};

时间复杂度 $O(mn)$，空间复杂度 $O(mn)$。

95. 编辑距离

https://leetcode.cn/problems/edit-distance/description/

引入空格字符，那么插入相当将一个空格替换为字符，删除相当于将一个字符替换为空格，替换相当于将一个字符替换为字符。因此，我们需要寻找引入空格后两个字符串最好的对齐方式。具体讲解可以参考算法笔记。

dp[i][j] 表示 word1[0:i] 和 word2[0:j]（均左闭右开）的编辑距离；递推公式为

$$dp[i][j] = \min\{dp[i-1][j-1] + \mathbb{I}(word1[i] == word2[j]), dp[i-1][j] + 1, dp[i][j-1] + 1\}$$

初始化 dp[i][0] = i，dp[0][j] = j；遍历顺序为外层 i 从小到大，内层 j 从小到大。

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, 0));
        for (int i = 0; i <= m; i++) dp[i][0] = i;
        for (int j = 0; j <= n; j++) dp[0][j] = j;
        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] = min(min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1]);
                } else {
                    dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        return dp[m][n];
    }
};

时间复杂度 $O(mn)$，空间复杂度 $O(mn)$。

技巧

96. 只出现一次的数字

https://leetcode.cn/problems/single-number/description/

本题是位运算的经典习题。考虑异或运算的性质：

• 任何数与自身做异或运算，结果是 0；
• 异或运算满足交换律和结合律；
• 任何数和 0 做异或运算，结果仍然是原来的数；

因此，我们只要将数组中的所有元素进行异或运算即得到答案。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int x = 0;
        for (int num : nums) x ^= num;
        return x;
    }
};

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

97. 多数元素

https://leetcode.cn/problems/majority-element/description/

这道题比较巧妙的做法是使用摩尔投票法。这个方法基于一个观察：从数组中任意删去两个不同的数，剩下数组的多数元素不变。

因此，我们可以直接选当前的数字作为候选，维护一个计数器，每次出现相等的数字就加 1，出现不同的数字就减 1。如果计数器变为 0，表明前面的元素已经全部抵消，后面数组的多数元素就是整个数组的多数元素，所以只要再次选中当前元素作为候选就可以。最后留下来的候选元素一定就是多数元素，因为它在最后一段中是多数元素，也就在整个数组中是多数元素。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate, vote = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (vote == 0) candidate = nums[i];
            if (nums[i] == candidate) vote++;
            else vote--;
        }
        return candidate;
    }
};

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

98. 颜色分类

https://leetcode.cn/problems/sort-colors/description/

这是经典的荷兰国旗问题。我们维护三个指针：left 表示下一个 0 该放的位置，i 表示当前扫描位置，right 表示下一个 2 该放的位置，从而 [0...left-1] 全是 0，[left...i-1] 全是 1，[i...right] 未处理，[right+1...end] 全是 2。

如果 nums[i] == 0，交换 i 和 left 上的数，并将两个指针向后移动；如果 nums[i] == 1，直接将 i 向后移动；如果 nums[i] == 2，交换 i 和 right 上的数，并将 right 指针向前移动。

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int left = 0, i = 0, right = nums.size() - 1;
        while (i <= right) {
            if (nums[i] == 0) swap(nums[i++], nums[left++]);
            else if (nums[i] == 1) i++;
            else swap(nums[i], nums[right--]);
        }
    }
};

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

99. 下一个排列

https://leetcode.cn/problems/next-permutation/description/

观察可以发现，求解下一个排列的思路是：从右向左扫描数组，找到第一个下降的数 x，在它右边序列中找出大于 x 的最小的数 y，将这两个数交换位置，再把这一段有序数组反转，就能得到下一个排列。这个思路类似计数的原理。

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i;
        for (i = nums.size() - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) break;
        }
        if (i >= 0) {
            int left = i + 1, right = nums.size() - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (nums[mid] > nums[i]) left = mid + 1;
                else right = mid - 1;
            }
            swap(nums[i], nums[right]);
        }
        reverse(nums.begin() + i + 1, nums.end());
    }
};

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

100. 寻找重复数

https://leetcode.cn/problems/find-the-duplicate-number/description/

本题可以使用快慢指针法，这个方法参考“环形链表 II”那题。所以我们只需要把这题转换为那道题的题干就可以。

建立 i -> nums[i] 的边。由于存在一个重复数字，这个数字一定有两个指向它的边，也就是存在一个环。而这个数字恰好在环的入口。这样我们就将问题转化好了。剩下的仿照那题找到环的入口就可以了。

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = nums[0], fast = nums[0];
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        fast = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
};

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