LeetCode HOT 100

LeetCode
Start: 2024.10.23
End: Doing
Plan: PM 10:00 - 12:00 (After taking a shower everyday)
Check:

1	2	3	4	5	6	7	8	9	10
10.23	10.23	10.23	10.24	10.24	10.24	10.25	10.25	10.25	10.27
10.27	10.28	10.28	10.28	10.29	10.29	10.29	11.1	11.1	11.1
11.4	11.5	11.5	11.5	11.6	11.6	11.6	11.7	11.7	11.9
11.9	11.9	11.10	11.10	11.11	11.11	11.11	11.12	11.12	11.12
11.13	11.13	11.13	11.14	11.14	11.14	11.16	01.06	01.07	01.08
02.09	02.09	02.09	02.17	02.17	02.17	02.18	02.18	02.18	02.18
02.18	02.19	02.19	02.20	02.20	02.21	02.21	02.21	02.21

一、哈希

1. 两数之和

• 题面：

  给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

  你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

  你可以按任意顺序返回答案。

  • 只会存在一个有效答案

• 示例 1：

  输入：nums = [2,7,11,15], target = 9
  输出：[0,1]
  解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

  示例 2：

  输入：nums = [3,2,4], target = 6
  输出：[1,2]

  示例 3：

  输入：nums = [3,3], target = 6
  输出：[0,1]

解法 1解法 2

暴力枚举肯定是可以的，但二重循环，时间复杂度高。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return {};
    }
};

时间复杂度：$O(N^2)$.

空间复杂度：$O(1)$.

哈希表

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 哈希表
        unordered_map<int, int> hashtable;
        for(int i=0; i<nums.size(); ++i){
            auto it = hashtable.find(target-nums[i]);
            if(it != hashtable.end())
                return {it->second, i};
            // 没找到的插入，以数值为键，索引为值
            hashtable[nums[i]] = i;
        }
        return {};
    }
};

时间复杂度：$O(N)$.

空间复杂度：$O(N)$.

2. 字母异位词分组

• 题面：

  给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

  字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

  • strs[i] 仅包含小写字母

• 示例 1:

  输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
  输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

  示例 2:

  输入: strs = [""]
  输出: [[""]]

  示例 3:

  输入: strs = ["a"]
  输出: [["a"]]

解法 1解法 2

字符串自身排序作为键

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // 把字符串自身排序，作为键，原字符串数组作为值
        unordered_map<string, vector<string>> hashtable;
        for(string &s : strs){
            string key = s;
            sort(key.begin(), key.end());
            hashtable[key].emplace_back(s);
        }
        // 插入完毕就完成了
        vector<vector<string>> ans;
        for(auto it=hashtable.begin(); it!=hashtable.end(); ++it){
            ans.emplace_back(it->second);
        }
        return ans;
    }
};

时间复杂度：$O(n k\log k)，其中，n字符串数量，k最长字符串长度$.

空间复杂度：$O(nk)$.

还可以计数 26 个字母出现的次数，成为一个数组，这个数组作为键。

写的太复杂，这里不给代码了。

3. 最长连续序列

• 题面：

  给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

  请你设计并实现时间复杂度为 $O(n)$ 的算法解决此问题。

• 示例 1：

  输入：nums = [100,4,200,1,3,2]
  输出：4
  解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

  示例 2：

  输入：nums = [0,3,7,2,5,8,4,6,0,1]
  输出：9

解法 1

注意点：

1. 使用 unordered_set

2. 不要重复查找，有前序数字的数字肯定不会是最长序列的开端。

   例如，有4,5,6,7,那么，5 肯定不会是最长序列的开端，同理，6,7也不会是。

   怎么判断：看是不是存在前序数字即可，比如 5 看是不是存在 4。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        // 存入 hash 集合
        unordered_set<int> hashset;
        for(int &x : nums)
            hashset.insert(x);
        // 遍历
        int maxlen = 0;
        for(int x : hashset){
            // 若有前序，则本次数字不会是最长序列的开端
            if(hashset.find(x-1) != hashset.end())
                continue;
            // 若可为开端，则依次查到最长序列为止
            int len = 0;
            while(hashset.find(x+len) != hashset.end())
                len++;
            maxlen = max(maxlen, len);
        }
        return maxlen;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

二、双指针

4. 移动零

• 题面：

  给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

  请注意 ，必须在不复制数组的情况下原地对数组进行操作。

• 示例 1:

  输入: nums = [0,1,0,3,12]
  输出: [1,3,12,0,0]

  示例 2:

  输入: nums = [0]
  输出: [0]

解法 1

双指针法

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        // 不用管 0，看到非 0 的搬到前面即可
        // 从头扫一遍，p 记录下一个非 0 可以放的位置
        int n = nums.size(), p = 0;
        for(int i=0; i<n; i++)
            if(nums[i] != 0)
                nums[p++] = nums[i];
        // 剩余是末尾全 0
        while(p < n) nums[p++] = 0;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(1)$.

5. 盛最多水的容器

• 题面：

  给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

  找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

  返回容器可以储存的最大水量。

  说明：你不能倾斜容器。

• 示例 1：

  

  输入：[1,8,6,2,5,4,8,3,7]
  输出：49 
  解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

  示例 2：

  输入：height = [1,1]
  输出：1

解法 1

关键在于思考怎么移动指针。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int L = 0, R = n-1, maxS = 0;
        while(L < R){
            int S = (R - L)* min(height[L], height[R]);
            if(S > maxS)
                maxS = S;
            // 总是移动 L,R 中目前高度更小的那个，保留高的
            if(height[L] < height[R]) L++;
            else R--;
        }
        return maxS;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(1)$.

6. 三数之和

• 题面：

  给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

  注意：答案中不可以包含重复的三元组。

• 示例 1：

  输入：nums = [-1,0,1,2,-1,-4]
  输出：[[-1,-1,2],[-1,0,1]]
  解释：
  nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
  nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
  nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
  不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
  注意，输出的顺序和三元组的顺序并不重要。

  示例 2：

  输入：nums = [0,1,1]
  输出：[]
  解释：唯一可能的三元组和不为 0 。

  示例 3：

  输入：nums = [0,0,0]
  输出：[[0,0,0]]
  解释：唯一可能的三元组和为 0 。

解法 1

三重循环查找不可避免。

1. 查找时，同一个位置不能出现相同的数字，因此先排序是必要的。
2. 可以发现，要 a+b+c = 0 那么，确定a的情况下，b和c是对立的，此消彼长，因此不需要完完全全的三重循环，二重循环即可。
3. 注意 c 下标应该大于 b 下标。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> ans;
        // 为了不重复，先排序
        sort(nums.begin(), nums.end());
        // 开始查找
        for(int i=0; i<n; i++){
            // 注意，不能重复，因此下一次的数字应与前一个数字不一样
            if(i!=0 && nums[i-1]==nums[i])
                continue;
            for(int j=i+1, k=n-1; j<n && j<k; j++){
                if(j!=i+1 && nums[j-1]==nums[j])
                    continue;
                while(nums[i]+nums[j]+nums[k] > 0 && j<k) k--;
                if(nums[i]+nums[j]+nums[k] == 0 && j<k)
                    ans.push_back({nums[i], nums[j], nums[k]});
            }
        }
        return ans;
        // 注意理解，若原数组是[-4,-1,-1,0,1,2],那么[-1,-1,0]是可以的
        // 不能重复是三元组本身不能重复，不是说三元组内的数字不能重复
    }
};

时间复杂度：$O(n^2)$.

空间复杂度：$O(\log n) 或 O(n)$. 主要是排序的消耗。

7. 接雨水

• 题面：

  给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

• 示例 1：

  

  输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
  输出：6
  解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

  示例 2：

  输入：height = [4,2,0,3,2,5]
  输出：9

解法 1解法 2

动态规划

class Solution {
public:
    int trap(vector<int>& height) {
        // 动态规划
        // 下标i处能接的最多水 = 下标i左右两侧最高度的较小值 - 下标i的高度
        // 1. 动态规划得到每个i的左右两侧最高度
        int n = height.size();
        vector<int> lmax(n), rmax(n);
        // 顺着求 lmax
        lmax[0] = height[0];
        for(int i=1; i<n; i++)
            lmax[i] = max(lmax[i-1], height[i]);
        // 逆着求 rmax
        rmax[n-1] = height[n-1];
        for(int i=n-2; i>=0; i--)
            rmax[i] = max(rmax[i+1], height[i]);

        // 2. 计算即可
        int Sum = 0;
        for(int i=0; i<n; i++)
            Sum += min(lmax[i], rmax[i]) - height[i];

        return Sum;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

双指针，可以降低空间复杂度

class Solution {
public:
    int trap(vector<int>& height) {
        // 双指针
        // 双方轮流占据最高点，低的一方移动
        int n = height.size();
        int lp = 0, rp = n-1;
        int lmax = 0, rmax = 0;
        int Sum = 0;
        while(lp < rp){
            lmax = max(lmax, height[lp]), rmax = max(rmax, height[rp]);
            if(lmax < rmax){
                Sum += lmax - height[lp];
                lp++;
            }
            else{
                Sum += rmax - height[rp];
                rp--;
            }
        }
        return Sum;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(1)$.

三、滑动窗口

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

• 题面：

  给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

  子串：是字符串中连续的 非空 字符序列。

• 示例 1:

  输入: s = "abcabcbb"
  输出: 3 
  解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

  示例 2:

  输入: s = "bbbbb"
  输出: 1
  解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

  示例 3:

  输入: s = "pwwkew"
  输出: 3
  解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
       请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解法 1

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // 滑动窗口 + 哈希集合（用来检测是否存在）
        int n = s.size();
        unordered_set<char> lookup;
        int maxlen = 0, left = 0;
        for(int i=0; i<n; i++){
            // 当前的 i 字符无论如何，必须进去
            // 那么窗口左侧一直滑动，滑到可以为止
            while(lookup.find(s[i]) != lookup.end()){
                lookup.erase(s[left]);
                left++;
            }
            maxlen = max(maxlen, i-left+1);
            lookup.insert(s[i]);
        }

        return maxlen;
    }
};

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

• 题面：

  给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。

  不考虑答案输出的顺序。

• 示例 1:

  输入: s = "cbaebabacd", p = "abc"
  输出: [0,6]
  解释:
  起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
  起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

  示例 2:

  输入: s = "abab", p = "ab"
  输出: [0,1,2]
  解释:
  起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
  起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
  起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

解法 1

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        // 滑动窗口
        // 窗口固定大小，把p也看做窗口，直接检测整个窗口是否一样即可
        // 全是小写字母，转成 26 字母计数
        vector<int> SW(26);
        vector<int> PW(26);
        vector<int> ans;
        int n = s.size(), m = p.size();
        // swin pwin 都有固定大小m，后续移动，一定是直接整体移动
        if(n < m)
            return {};
        for(int i=0; i<m; i++)
            SW[s[i]-'a']++, PW[p[i]-'a']++;
        // 开始滑动
        if(SW == PW) ans.emplace_back(0);
        for(int i=0; i<n-m; i++){
            SW[s[i+m]-'a']++, SW[s[i]-'a']--;
            if(SW == PW) ans.emplace_back(i+1); // 已移动，左侧是 i+1
        }
        return ans;
    }
};

四、子串

10. 和为 K 的子数组

• 题面：

  给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

  子数组是数组中元素的连续非空序列。

• 示例 1：

  输入：nums = [1,1,1], k = 2
  输出：2

  示例 2：

  输入：nums = [1,2,3], k = 3
  输出：2

解法 1解法 2解法 3

首先，朴素做法：

不佳，会报出：超出内存限制。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        // 找出 [i,j] 和为 k
        int n = nums.size();
        int ans = 0;
        vector<vector<int>> Sum(n, vector<int>(n, 0));
        // 初始化
        for(int i=0; i<n; i++){
            Sum[i][i] = nums[i];
            if(Sum[i][i] == k) ans++;
        }
        // 更新
        for(int i=0; i<n; i++){
            for(int j=i+1; j<n; j++){
                Sum[i][j] = Sum[i][j-1] + nums[j];  // 动态规划
                if(Sum[i][j] == k) ans++;
            }
        }
        return ans;
    }
};

时间复杂度：$O(n^2)$.

空间复杂度：$O(n^2)$.

改进变量使用：

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        // 找出 [i,j] 和为 k
        int n = nums.size();
        int ans = 0;
        // 原本动态规划，实际上发现，每次只会用到前一次的计算，那么一个变量就够
        for(int i=0; i<n; i++){
            int Sum = 0;
            for(int j=i; j<n; j++){
                Sum += nums[j];
                if(Sum == k) ans++;
            }
        }
        return ans;
    }
};

时间复杂度：$O(n^2)$.

空间复杂度：$O(1)$.

只求前缀和，并且用哈希表存储：

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        // 关键在于希望不要每次[i, j] 每次到j，要匹配前面的i出来
        // 能不能直接得到满足条件的i数量？
        // [i, j] = [0, j] - [0, i]  (其中，i <= j)
        // 那么    [i, j] == k 
        // 可以转为 [0, i] == [0, j] - k 每次要找到这个的数量即可
        int n = nums.size(), pre = 0, ans = 0;
        unordered_map<int, int> mp;  // 哈希表，键是前缀和，值是次数
        mp[pre]++;
        // 很巧妙，计算的同时插入mp，顺利保证了不会出现序列下标的错误
        for(int &num : nums){
            pre += num;
            if(mp.find(pre - k) != mp.end())  ans += mp[pre - k];
            mp[pre]++;  // 应该放后面，否则可能出现给自己加次数
        }
        return ans;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

11.滑动窗口最大值

• 题面：

  给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

  返回 滑动窗口中的最大值 。

• 示例 1：

  输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
  输出：[3,3,5,5,6,7]
  解释：
  滑动窗口的位置                最大值
  ---------------             -----
  [1  3  -1] -3  5  3  6  7       3
   1 [3  -1  -3] 5  3  6  7       3
   1  3 [-1  -3  5] 3  6  7       5
   1  3  -1 [-3  5  3] 6  7       5
   1  3  -1  -3 [5  3  6] 7       6
   1  3  -1  -3  5 [3  6  7]      7

  示例 2：

  输入：nums = [1], k = 1
  输出：[1]

解法 1解法 2解法 3解法 4

朴素做法，超出时间限制：

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> ans;
        deque<int> Q;
        // 初始窗口
        for(int i=0; i<k; i++)  Q.push_back(nums[i]);
        int m = Q[0];
        for(int i=1; i<k; i++)  m = max(m, Q[i]);
        ans.emplace_back(m);
        // 移动窗口
        for(int i=k; i<n; i++){
            Q.pop_front(), Q.push_back(nums[i]);
            int m = Q[0];
            for(int i=1; i<k; i++)  m = max(m, Q[i]);
            ans.emplace_back(m);
        }
        return ans;
    }
};

时间复杂度：$O(nk)$.

空间复杂度：$O(n+k)$.

优先队列是最应该想到的正确方法：

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        // 优先队列，大根堆（默认）
        int n = nums.size();
        vector<int> ans;
        priority_queue<pair<int, int>> Q;   // 用 (nums[i], i) 作为一个 pair 来记录
        // 初始
        for(int i=0; i<k; i++)  Q.push({nums[i], i});
        ans.emplace_back(Q.top().first);
        for(int i=k; i<n; i++){
            // 如何判断当前最大值应该pop？看下标是否已经拉出了
            Q.push({nums[i], i});
            while(Q.top().second + k <= i)  Q.pop();   // 这里应该是while而不是if ！！！
            ans.emplace_back(Q.top().first);
        }
        return ans;
    }
};

时间复杂度：$O(n\log n)其中插入一个元素进入队列需要 \log n 的时间$.

空间复杂度：$O(n+n)$.

优化算法，可以只用单调队列（要用双端队列，队头队尾都能插入删除，但人为保持单调特性）

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        // 单调队列
        int n = nums.size();
        vector<int> ans;
        deque<int> Q;   
        // 保持需要加入的才入队， i>a 且 nums[i] >= nums[a] 时，a就没必要了，pop除去a
        // 初始
        for(int i=0; i<k; i++){
            // 保持性质 1: 在窗口内 (只需要看front，因为是按顺序进来的，肯定是前面的index更小)
            while(!Q.empty() && Q.front()+k<=i)  Q.pop_front();
            // 保持性质 2: 末尾新加入的数字若比末尾数字大，则末尾数字退出（最终导致 整个队列递减）
            while(!Q.empty() && nums[i] >= nums[Q.back()])  Q.pop_back();
            // 现在可以插入了（插入的是比末尾数字更小的）
            Q.push_back(i);
        }
        // 取出队头就是当前最大的
        ans.emplace_back(nums[Q.front()]);
        // 更新
        for(int i=k; i<n; i++){
            while(!Q.empty() && Q.front()+k<=i)  Q.pop_front();
            while(!Q.empty() && nums[i] >= nums[Q.back()])  Q.pop_back();
            Q.push_back(i);
            ans.emplace_back(nums[Q.front()]);  // 每次都有一个ans
        }
        return ans;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n+k)$.

此题还可以使用“分块+预处理”，由于前面算法足够好，这里不写了。

参考：参考链接

时间复杂度：$O(n)$.

空间复杂度：$O(n+n)$.

12. 最小覆盖子串

• 题面：

  给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

  注意：

  • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串，我们保证它是唯一的答案。

• 示例 1：

  输入：s = "ADOBECODEBANC", t = "ABC"
  输出："BANC"
  解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

  示例 2：

  输入：s = "a", t = "a"
  输出："a"
  解释：整个字符串 s 是最小覆盖子串。

  示例 3:

  输入: s = "a", t = "aa"
  输出: ""
  解释: t 中两个字符 'a' 均应包含在 s 的子串中，
  因此没有符合条件的子字符串，返回空字符串。

解法 1

1. 哈希表的数量检测不可避免
2. 滑动窗口，右指针 r 扩大，直到 check true。再左指针l 缩小，直到 check false。

class Solution {
public:
    // 两个哈希表
    unordered_map<char, int> tmap, wmap;
    // 检测
    bool check(){
        for(auto &x : tmap)
            if(wmap[x.first] < x.second)
                return false;
        return true;
    }
    // 题解函数
    string minWindow(string s, string t) {
        int n = s.size();
        // 初始化 tmap
        for(auto &c : t)  tmap[c]++;
        // 左右两个指针，l缩小，r 扩大
        int l = 0, r = 0;
        int ansL = 0, len = n+1;
        // r 扩大，直到check true
        while(r < n){
            // 先本次记录
            wmap[s[r]]++;
            // l 缩小，直到check false
            while(check()){
                // 先记录当前 true
                if(r-l+1 < len)  len = r-l+1, ansL = l;
                // 再 l 缩小
                wmap[s[l]]--;
                l++;
            }
            // 再 r 扩大
            r++;
        }
        return len == n+1 ? "" : s.substr(ansL, len);
    }
};

时间复杂度：$O(C\cdot |s| + |t|)，其中 C 是字符集大小，26 或 52$.

空间复杂度：$O(C)$.

五、普通数组

13. 最大子数组和

• 题面：

  给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

  子数组 是数组中的一个连续部分。

  **进阶：**如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

• 示例 1：

  输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
  输出：6
  解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

  示例 2：

  输入：nums = [1]
  输出：1

  示例 3：

  输入：nums = [5,4,-1,7,8]
  输出：23

解法 1解法 2解法 3

滑动窗口，自己想的

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // 滑动窗口
        int n = nums.size();
        int l = 0, r = 0;
        int maxS = nums[0], S = 0;
        while(r < n){
            S += nums[r];
            maxS = max(maxS, S);
            while(S < 0){
                S -= nums[l];
                l++;
            }
            if(l < r)  maxS = max(maxS, S);
            r++;
        }
        return maxS;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(1)$.

不用记录那么多，动态规划即可

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // 改进，动态规划求前序的最佳即可
        int pre = 0, ans = nums[0];
        for(int &num : nums){
            pre = max(pre + num, num);
            ans = max(ans, pre);
        }
        return ans;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(1)$.

还可以有更加精妙的分治法，精妙在可以求任意区间。

参考：链接

时间复杂度：$O(n)$.

空间复杂度：$O(\log n)$.

14. 合并区间

• 题面：

  以数组 intervals 表示若干个区间的集合，其中单个区间为 $intervals[i] = [start_i, end_i]$ 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

• 示例 1：

  输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
  输出：[[1,6],[8,10],[15,18]]
  解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

  示例 2：

  输入：intervals = [[1,4],[4,5]]
  输出：[[1,5]]
  解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

解法 1

时间安排问题，都是先按照开始时间排序再合并。

class Solution {
public:
    // 注意需要加上 static
    static bool compare(const vector<int> &a, const vector<int> &b){
        return a[0] < b[0];
    }
    // 题解函数
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int n = intervals.size();
        // 先按 start 升序
        sort(intervals.begin(), intervals.end(), compare);
        // 那么依次从左到右融合即可
        vector<vector<int>> ans;
        ans.push_back(intervals[0]);
        for(int i=1; i<n; i++){
            // 可衔接时，扩并 (因为已经按照 start 升序，肯定可以直接选 ans 中最后一个来合并即可)
            if(intervals[i][0] <= ans.back()[1]){
                ans.back()[1] = max(ans.back()[1], intervals[i][1]);    // 注意选 max 的
            }
            // 不可衔接时，加入
            else{
                ans.push_back(intervals[i]);
            }
        }
        return ans;
    }
};

时间复杂度：$O(n \log n)，主要是排序时间$.

空间复杂度：$O(\log n)，此处只统计额外空间，不含ans$.

15. 轮转数组

• 题面：

  给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

  进阶：

  尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
  你可以使用空间复杂度为 $O(1)$ 的 原地 算法解决这个问题吗？

• 示例 1:

  输入: nums = [1,2,3,4,5,6,7], k = 3
  输出: [5,6,7,1,2,3,4]
  解释:
  向右轮转 1 步: [7,1,2,3,4,5,6]
  向右轮转 2 步: [6,7,1,2,3,4,5]
  向右轮转 3 步: [5,6,7,1,2,3,4]

  示例 2:

  输入：nums = [-1,-100,3,99], k = 2
  输出：[3,99,-1,-100]
  解释: 
  向右轮转 1 步: [99,-1,-100,3]
  向右轮转 2 步: [3,99,-1,-100]

解法 1解法 2

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        // 先来个蠢办法，牺牲一下空间
        int n = nums.size();
        vector<int> rotate(n);
        // 使用模数
        for(int i=0; i<n; i++)
            rotate[(i+k) % n] = nums[i];
        // 移回数组
        nums.assign(rotate.begin(), rotate.end());
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        // 直接秒了
        k = k % nums.size();
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin()+k);
        reverse(nums.begin()+k, nums.end());
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(1)$.

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

• 题面：

  给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

  题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

  请 **不要使用除法，**且在 O(n) 时间复杂度内完成此题。

  进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

• 示例 1:

  输入: nums = [1,2,3,4]
  输出: [24,12,8,6]

  示例 2:

  输入: nums = [-1,1,0,-3,3]
  输出: [0,0,9,0,0]

解法 1解法 2解法 3

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        // 先来个蠢办法
        vector<int> ans;
        int All = 1, zero = 0, n = nums.size(), pos = -1;
        for(int i=0; i<n; i++)
            if(nums[i] != 0) All *= nums[i];    // 注意 0 
            else zero++, pos = i;
        // 有 0 存在
        if(zero >= 2)    
            ans.assign(n, 0);
        // 只有一个 0 时，那么只有这个位置结果非 0
        else if(zero == 1){
            ans.assign(n, 0);
            ans[pos] = All;
        }
        // 无 0 时
        else{
            for(int &num : nums)
                ans.push_back(All / num);
        }
        return ans;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(1)$.

但是违规了，题目要求不能除法。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        // 不允许除法，那么我们记录前缀乘积，后缀乘积
        int n = nums.size();
        vector<int> L(n), R(n), ans;
        L[0] = 1, R[n-1] = 1;
        for(int i=1; i<n; i++)
            L[i] = L[i-1] * nums[i-1];
        for(int i=n-2; i>=0; i--)
            R[i] = R[i+1] * nums[i+1];
        // 结果 = 前缀 * 后缀
        for(int i=0; i<n; i++)
            ans.push_back(L[i] * R[i]);
        return ans;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        // 更进一步，省空间
        int n = nums.size();
        // 1. 把ans当做 L 使用
        vector<int> ans(n);
        ans[0] = 1;
        for(int i=1; i<n; i++)
            ans[i] = ans[i-1] * nums[i-1];
        // 2. 后缀乘积用一个变量即可
        int R = 1;
        for(int i=n-1; i>=0; i--){
            ans[i] *= R;
            R *= nums[i];
        }
        return ans;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(1)$.

17. 缺失的第一个正数

• 题面：

  给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

  请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

• 示例 1：

  输入：nums = [1,2,0]
  输出：3
  解释：范围 [1,2] 中的数字都在数组中。

  示例 2：

  输入：nums = [3,4,-1,1]
  输出：2
  解释：1 在数组中，但 2 没有。

  示例 3：

  输入：nums = [7,8,9,11,12]
  输出：1
  解释：最小的正数 1 没有出现。

解法 1解法 2解法 3解法 4

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        // 当然，先违规做一下，排序就行，默认升序
        sort(nums.begin(), nums.end());
        int ans = 1, i = 0, n = nums.size();
        // 先到正数
        for(i=0; i<n; i++)
            if(nums[i] > 0)
                break;
        // 检验正数存在性
        for(; i<n; i++){
            if(nums[i] == ans)
                ans++;
            else if(nums[i] < ans)
                continue;
            else
                break;
        }
        return ans;
    }
};

时间复杂度：$O(n \log n)$.

空间复杂度：$O(1)$.

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        // 哈希表
        unordered_set<int> table;
        for(int &num : nums)
            table.insert(num);
        // 正数依次查找
        int ans = 1;
        while(table.find(ans) != table.end())
            ans++;
        return ans;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        // 构造某种意义上的哈希表
        int n = nums.size();
        // 1. 把所有负数改为 N+1（答案只会是 [1, N+1] 的数）
        for(int &num : nums)  if(num <= 0)  num = n+1;
        // 2. 现在所有数字都是正数了，所以符号已经不用管了
        // 那我们把符号用来标记这个索引下标i+1表示的数字是否存在
        for(int &num : nums)
            if(abs(num) < n+1)  // 注意，num在动态变，因此需要加 abs 来判断
                nums[abs(num)-1] = - abs(nums[abs(num)-1]);   // 仔细体会，是把 num 看做下标
        // 3. 检索下标，第一个正数所在的下标，就是答案（下标+1 是答案，不是数字是答案）
        int idx = 0;
        for(; idx<n; idx++)
            if(nums[idx] > 0)  break;
        return idx+1;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(1)$.

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        // 条件换位
        int n = nums.size();
        // 1. 把[1,N] 的数字放到对应下标 [0, N-1] 的位置上
        for(int i=0; i<n; i++){
            while(nums[i] >=1 && nums[i] <= n){
                int x = nums[i];
                if(nums[x-1] == x)
                    break;
                else
                    swap(nums[x-1], nums[i]);
            }
        }
        //  2. 那么下标与数字不对应的第一个，就是答案
        int idx = 0;
        for(; idx<n; idx++)
            if(nums[idx] != idx+1) break;
        return idx+1;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(1)$.

18. 矩阵置零

• 题面：

  给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。

  请使用 原地 算法。

  进阶：

  • 一个直观的解决方案是使用 O(m*n) 的额外空间，但这并不是一个好的解决方案。
  • 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
  • 你能想出一个仅使用常量空间的解决方案吗？

• 示例 1：

  

  输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
  输出：[[1,0,1],[0,0,0],[1,0,1]]

  示例 2：

  

  输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
  输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

解法 1

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        // 开两个集合，用来存储需要改 0 的那些行、列
        int m = matrix.size(), n = matrix[0].size();
        set<int> row, column;
        for(int i=0; i<m; i++)
            for(int j=0; j<n; j++)
                if(matrix[i][j] == 0)  row.insert(i), column.insert(j);
        for(int r : row)  for(int j=0; j<n; j++)  matrix[r][j] = 0;
        for(int c : column)  for(int i=0; i<m; i++)  matrix[i][c] = 0;
    }
};

时间复杂度：$O(mn)$.

空间复杂度：$O(m+n)$.

19. 螺旋矩阵

• 题面：

  给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

• 示例 1：
  

  输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
  输出：[1,2,3,6,9,8,7,4,5]

  示例 2：

  

  输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
  输出：[1,2,3,4,8,12,11,10,9,5,6,7]

解法 1

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        int count = 0;
        // flag 指示当前的运动方向
        int i = 0, j = 0, flag = 1; 
        // 分别记录行列的边界 ist ied 行开始 结束   jst jed 列开始 结束
        int ist = 0, ied = m, jst = 0, jed = n;
        vector<int> ans;
        while(count < m * n){
            ans.push_back(matrix[i][j]);
            switch(flag){
                // 从左到右
                case 1:
                    j++;
                    if(j >= jed)  j = jed-1, i++, flag = 2, ist++;
                    break;
                // 从上到下
                case 2:
                    i++;
                    if(i >= ied)  i = ied-1, j--, flag = 3, jed--;
                    break;
                // 从右到左
                case 3:
                    j--;
                    if(j < jst)  j = jst, i--, flag = 4, ied--;
                    break;
                // 从下到上
                case 4:
                    i--;
                    if(i < ist)  i = ist, j++, flag = 1, jst++;
                    break;
            }
            // 根据已输出的数量判断是否结束
            count++;
        }
        return ans;
    }
};

时间复杂度：$O(mn)$.

空间复杂度：$O(mn+1)$.

20. 旋转图像

• 题面：

  给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

  你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

• 示例 1：

  

  输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
  输出：[[7,4,1],[8,5,2],[9,6,3]]

  示例 2：

  

  输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
  输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

解法 1解法 2

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        // 先来一个违规方法
        int n = matrix.size();
        vector<vector<int>> mr(n, vector<int>(n));
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                mr[j][n-i-1] = matrix[i][j];
        // 赋值回去
        matrix.assign(mr.begin(), mr.end());
    }
};

时间复杂度：$O(n^2)$.

空间复杂度：$O(n^2)$.

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        // 每转一圈，是四个数字，只需要转整个矩阵 1/4 的左上角即可
        int n = matrix.size();
        for(int i=0; i<n/2; i++){
            for(int j=0; j<(n+1)/2; j++){
                // 本次四个位置轮转
                int x = 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] = x;
            }
        }
    }
};

时间复杂度：$O(n^2)$.

空间复杂度：$O(1)$.

21. 搜索二维矩阵 II

• 题面：

  编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

• 示例 1：
  

  输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
  输出：true

  示例 2：
  

  输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
  输出：false

解法 1解法 2解法 3

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // 首先肯定暴力
        // 从左到右的列，从上到下的行
        int m = matrix.size(), n = matrix[0].size();
        for(int i=0; i<m; i++)
            for(int j=0; j<n; j++)
                if(matrix[i][j] == target)  return true;    // 找到
        // 退出循环则是没找到
        return false;
    }
};

时间复杂度：$O(mn)$.

空间复杂度：$O(1)$.

class Solution {
public:
    // 二分查找
    bool query(vector<int>& M, int target){
        int n = M.size();
        int L = -1, R = n;
        while(L+1 != R){
            int mid = L + R >> 1;   // 别写错了，除以 2 是右移 1 位
            if(M[mid] == target)  return true;
            if(M[mid] > target) R = mid;
            else L = mid; 
        }
        return false;
    }

    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // 再来二分法
        int m = matrix.size(), n = matrix[0].size();
        // 先找到正确的右边界
        int R = m-1;
        while(matrix[R][0] > target && R > 0)  R--;
        // 然后对每个数组采用二分查找
        for(int i=0; i<=R; i++)
            if(query(matrix[i], target))  return true;
        // 一直未找到
        return false;
    }
};

时间复杂度：$O(m\log n)$.

空间复杂度：$O(1)$.

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // 充分利用特性，Z 字形查找
        // 当前状态下明确知道应该往哪边走，则走一步，有点像梯度下降
        int m = matrix.size(), n = matrix[0].size();
        int x = 0, y = n-1;
        while(x <= m-1 && y >= 0){
            // 找到
            if(matrix[x][y] == target)  return true;
            // 当前数字更大，明确知道同一行的偏左数字更小，因此向左走
            else if(matrix[x][y] > target)  y--;
            // 当前数字更小，明确知道同一列的偏下数字更大，因此向下走
            else x++;
        }
        // 没找到
        return false;
    }
};

时间复杂度：$O(m+n)$.

空间复杂度：$O(1)$.

六、链表

22. 相交链表

• 题面：

  给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

  图示两个链表在节点 c1 开始相交：

  

  题目数据 保证 整个链式结构中不存在环。

  注意，函数返回结果后，链表必须 保持其原始结构 。

解法 1解法 2

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // 哈希表
        unordered_set<ListNode *> table;
        // 把 A 全存入
        ListNode *pa = headA;
        while(pa != NULL){
            table.insert(pa);
            pa = pa->next;
        }
        // 依次查找 B, 第一个找到的 pb 就是答案
        ListNode *pb = headB;
        while(pb != NULL){
            if(table.find(pb) != table.end())  return pb;
            else  pb = pb->next;
        }
        return NULL;
    }
};

时间复杂度：$O(m+n)$.

空间复杂度：$O(m)$.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // 双指针，走完自己的则走对方的
        ListNode *pa = headA, *pb = headB;
        // 若是有相交，则 pa 走了 a+c+b，pb 走了 b+c+a ，会相遇，相遇点就是答案
        // 若是无相交，则 pa, pb 会都把两个链表走完，然后到了 null
        // 无论如何，结束时，都是 pa == pb
        while(pa != pb){
            // pa 向后走，走完则走 B
            if(pa == NULL)  pa = headB;
            else  pa = pa->next;
            // pb 向后走，走完则走 A
            if(pb == NULL)  pb = headA;
            else  pb = pb->next;
        }
        // 无论什么情况，出来的时候，都就是答案
        return pa;
    }
};

时间复杂度：$O(m+n)$.

空间复杂度：$O(1)$.

23. 反转链表

• 题面：
  给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

• 示例 1：
  

解法 1

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 改即可
        ListNode *pre = NULL, *cur = head;
        while(cur != NULL){
            // 当前节点的 next 改为前节点，要先把 正常走的下一个节点存储下来
            ListNode *t = cur->next;
            cur->next = pre;
            pre = cur;
            cur = t;
        }
        // 头节点是最后一个pre
        return pre;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(1)$.

24. 回文链表

• 题面：
  给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

• 示例 1：

  

解法 1

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        // 1. 先复制到数组中
        vector<int> arr;
        ListNode *p = head;
        while(p != NULL)  
            arr.emplace_back(p->val), p = p->next;
        // 2. 用两个指针，一头一尾的对比是不是一样的
        int l = 0, r = arr.size()-1;
        while(l < r)
            if(arr[l] == arr[r])  l++, r--;
            else  return false;
        return true;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

25. 环形链表

• 题面：
  给你一个链表的头节点 head ，判断链表中是否有环。

  如果链表中存在环 ，则返回 true 。 否则，返回 false 。

  

解法 1解法 2

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        // 哈希表鉴别
        unordered_set<ListNode*> table;
        ListNode *p = head;
        while(p != NULL){
            // 若有重复的指针，说明有环
            if(table.find(p) != table.end())
                return true;
            table.insert(p);
            p = p->next;
        }
        // 出来则无环
        return false;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        // 龟兔指针，兔子会先进入环，乌龟也会慢慢进入环
        // 进入环之后，肯定兔子会碰到乌龟(进入环之后，龟兔的相对距离一直是以 1 递减的，肯定会相遇)
        ListNode *p1 = head, *p2 = head;
        // 特例，如果只有0或1个元素
        if(head == NULL)  return false;
        if(head->next == NULL)  return false;
        while(p1 != NULL && p2 != NULL){
            // p1 走一步， p2 走两步
            p1 = p1->next;
            p2 = p2->next;
            if(p2)  p2 = p2->next;
            else  return false;
            if(p1 == p2)
                return true;
        }
        // 如若有环，是不会走出循环的；走出循环，则无环
        return false;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(1)$.

26. 环形链表 II

• 题面：

  给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

  不允许修改 链表。

  

解法 1解法 2

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        // 哈希表，第一个检测出来的就是环开始点
        unordered_set<ListNode*> table;
        ListNode *p = head;
        while(p != NULL){
            if(table.find(p) != table.end())
                return p;
            table.insert(p);
            p = p->next;
        }
        return NULL;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        // 有数量关系 兔子 = 2 乌龟
        // a + n(b+c) + b = 2 [ a + b ]
        // 则 a = (n-1)(b+c) + c 
        // 因此，相遇后，再用 ptr 去从开头往后记录，那么乌龟会和ptr在入环点相遇
        ListNode *p1 = head, *p2 = head, *ptr = head;
        if(head == NULL || head->next == NULL)  return NULL;
        while(p1!=NULL && p2!=NULL){
            // p1走一步，p2走两步
            p1 = p1->next;
            p2 = p2->next;
            if(p2)  p2 = p2->next;
            else  return NULL;
            // 相遇了，ptr 开始走，和 p1 相遇就是入环点
            if(p1 == p2){
                while(ptr != p1)
                    ptr = ptr->next, p1 = p1->next;
                return ptr;
            }
        }
        return NULL;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(1)$.

27. 合并两个有序链表

• 题面：

  将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

  

解法 1解法 2

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        // 新建 head 为开头，返回结果是 head.next
        ListNode *p1 = list1, *p2 = list2;
        ListNode head = ListNode(0), *pre = &head;
        while(p1 != NULL || p2 != NULL){
            // 若有空 NULL，则只需要接上，就结束了
            if(p1 == NULL){
                pre->next = p2;
                break;
            }
            else if(p2 == NULL){
                pre->next = p1;
                break;
            }
            // p2 更小，把 p2 拼接到 pre
            else if(p1->val >= p2->val){
                pre->next = p2;
                pre = p2;
                p2 = p2->next;
            }
            // p1 更小
            else{
                pre->next = p1;
                pre = p1;
                p1 = p1->next;
            }
        }
        // 结果就是
        return head.next;
    }
};

时间复杂度：$O(m+n)$.

空间复杂度：$O(1)$.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // 递归法
        if(l1 == NULL)  
            return l2;
        else if(l2 == NULL)  
            return l1;
        else if(l1->val < l2->val){
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else{
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

时间复杂度：$O(m+n)$.

空间复杂度：$O(m+n)$.

28. 两数相加

• 题面：
  给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

  请你将两个数相加，并以相同形式返回一个表示和的链表。

• 示例：

  

  输入：l1 = [2,4,3], l2 = [5,6,4]
  输出：[7,0,8]
  解释：342 + 465 = 807.

解法 1

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        // 开一个 head 做开头
        ListNode *pre = new ListNode(0);
        ListNode *p1 = l1, *p2 = l2, *head = pre;
        int carry = 0;
        while(p1 != NULL || p2 != NULL){
            // 计算
            int v1 = p1 ? p1->val : 0;
            int v2 = p2 ? p2->val : 0;
            int sum = carry + v1 + v2;
            carry = sum / 10;
            sum = sum % 10;
            // 创建数据结构存储
            ListNode *data = new ListNode(sum);
            pre->next = data;
            pre = pre->next;
            // 下一位
            if(p1)  p1 = p1->next;
            if(p2)  p2 = p2->next;
        }
        // 还有进位，则需要再创建一位
        if(carry != 0){
            ListNode *tail = new ListNode(carry);
            pre->next = tail;
        }
        return head->next;
    }
};

时间复杂度：$O(m+n)$.

空间复杂度：$O(1)$.

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

• 题面：

  给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

• 示例：

  

  输入：head = [1,2,3,4,5], n = 2
  输出：[1,2,3,5]

解法 1解法 2解法 3

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // 先来蠢办法，先计算长度，就知道需删除的正序位置
        // 1. 计算长度
        ListNode *myhead = new ListNode(0);  // 创建一个不存储值的头指针，处理特殊情况会方便很多
        myhead->next = head;
        ListNode *p = myhead;
        int len = -1;
        while(p)  len++, p = p->next;
        // 2. 抵达位置
        int pos = len - n;
        ListNode *pre = myhead;
        p = head;
        while(pos) pos--, pre = p, p = p->next;
        // 3. 删除
        pre->next = p->next;
        delete p;
        // 返回答案
        return myhead->next;
    }
};

时间复杂度：$O(L)$.

空间复杂度：$O(1)$.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // 使用栈，弹出时刚好是反序
        ListNode *dummy = new ListNode(0, head);
        stack<ListNode*> stk;
        ListNode *p = dummy;
        // 1. 入栈
        while(p)
            stk.push(p), p = p->next;
        // 2. 出栈
        for(int i=0; i<n; i++)
            stk.pop();
        // 3. 删除
        ListNode *pre = stk.top();
        pre->next = pre->next->next;
        return dummy->next;
    }
};

时间复杂度：$O(L)$.

空间复杂度：$O(L)$.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // 不预处理计算链表长度：
        // 两个指针，既然要找到倒数第 n 个
        //  1. 初始时，p2 就比 p1 早 n 步，那么两个都一步一步走
        ListNode *dummy = new ListNode(0, head);
        ListNode *p1 = dummy, *p2= head;    // 注：p1 要多留一步，从dummy开始
        for(int i=0; i<n; i++)
            p2 = p2->next;
        // 2. p2到末尾，p1就是删除的位置
        while(p2)
            p1 = p1->next, p2 = p2->next;
        // 3. 删除
        p1->next = p1->next->next;
        // 返回
        return dummy->next;
    }
};

时间复杂度：$O(L)$.

空间复杂度：$O(1)$.

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

• 题面：

  给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

• 示例：

  

解法 1解法 2

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        // 从头到尾，依次数出两个，交换
        ListNode *dummy = new ListNode(0, head);   // 老规矩，先来一个空头
        ListNode *p1 = dummy, *p2 = head, *pre;
        // 先进入第一轮
        pre = p1;
        if(p1)  p1 = p1->next;
        if(p2)  p2 = p2->next;
        // 依次处理每一轮
        while(p1 != NULL && p2 != NULL){
            pre->next = p2;
            ListNode *t = p2->next;
            p2->next = p1;
            p1->next = t;
            pre = p1;
            // 再下一轮两个数字(注意，现在已经交换过位置了)
            if(p1)  p1 = p1->next;
            if(p1)  p2 = p1->next;
        }
        // 有 dummy 的好处就在于不需要单独处理开头 head 的特殊处理
        return dummy->next;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(1)$.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        // 递归，我笨脑子是想不出来的
        // 1. 只有 0 或 1 个则直接返回当前
        if(head == NULL || head->next == NULL)
            return head;
        // 2. 交换
        ListNode *newhead = head->next;
        head->next = swapPairs(newhead->next);
        newhead->next = head;
        // 3. 返回
        return newhead;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

31. K 个一组翻转链表

• 题面：

  给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

  k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

  你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

• 示例：

  

  

解法 1

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        // 一眼用栈
        stack<ListNode*> stk;
        ListNode *dummy = new ListNode(0, head);
        ListNode *pre = dummy, *p = head;
        // 多轮交换，每轮交换 k 个
        while(p != NULL){
            int i = 0;
            // 压入 k 个
            for(i=0; i<k && p; i++){
                stk.push(p);
                p = p->next;
            }
            // 弹出 k 个
            if(i == k){
                for(i=0; i<k; i++){
                    ListNode *t = stk.top();    // 注意，这里必须是重新定义一个 t，不可沿用p
                    pre->next = t;              // 因为前面的 p 刚好作为 while 的条件，不可动
                    pre = t;
                    stk.pop();
                }
                // 本轮结束，刚好可以用 pre 接上下一轮开头的 p
                pre->next = p;
            }
        }
        // 返回最终
        return dummy->next;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

32. 随机链表的复制

• 题面：

  给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

  构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

  例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。如果不指向任何节点，则为 null 。

  返回复制链表的头节点。

  你的代码 只 接受原链表的头节点 head 作为传入参数。

• 示例：

  

  

  

解法 1

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        // 哈希表
        unordered_map<Node*, Node*> table;
        // 1. 创建整个新链表，并把每个节点对应的新节点存入哈希表
        Node *dummy = new Node(0);
        Node *p = head;
        Node *pre = dummy, *newp;
        while(p != NULL){
            // 创建
            newp = new Node(p->val);
            pre->next = newp;
            pre = newp;
            // 存入
            if(p)  table[p] = newp;  // 注意 null 不存
            // 下一个
            p = p->next;
        }
        // 2. 依次编写正确的 random
        p = head, newp = dummy->next;
        while(newp != NULL){
            // 注意寻找的是 p->random
            if(table.find(p->random) != table.end())
                newp->random = table[p->random];
            // 下一个
            p = p->next;
            newp = newp->next;
        }
        // 3. 返回
        return dummy->next;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

33. 排序链表

• 题面：

  给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

• 示例：

  

  

解法 1解法 2解法 3

插入排序，超出时间限制。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        // 插入排序
        if(head == NULL || head->next == NULL)  return head;    // 只有 0/1 个元素
        ListNode *dummy = new ListNode(0, head);
        // 默认第一个元素是已排好序，从第二个开始，去已排好序的部分里面找到自己的位置，插入
        ListNode *cur = head->next;
        head->next = NULL;  // NULL 用来隔开已排序的部分
        // 开始插入排序
        while(cur){
            // 从头开始寻找已排序部分里面自己的位置，最多到已排序部分的 NULL 就会停下
            ListNode *pre = dummy;  
            while(pre->next && pre->next->val < cur->val)
                pre = pre->next;
            // 插入
            ListNode *tmp = pre->next;  // 记录交换值
            ListNode *next = cur->next; // 记录下一轮待排序的数
            pre->next = cur;
            cur->next = tmp;
            // 下一个
            cur = next;
        }
        // 返回答案
        return dummy->next;
    }
};

时间复杂度：$O(n^2)$.

空间复杂度：$O(1)$.

归并排序，可以。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        // 归并排序
        return sortSection(head, NULL);
    }
    // 给定区间 [ head, tail ) 排序，返回排序后的 head
    ListNode* sortSection(ListNode* head, ListNode* tail){
        // 1. 无元素、一个元素（递归结束条件）
        if(head == NULL)  return NULL;
        if(head->next == tail){ // 注意，并不排序 tail
            head->next = NULL;
            return head;
        }
        // 2. 找到中间点（快慢指针）
        ListNode *slow = head, *fast = head;
        while(fast != tail){    // 注意，由于我们有区间，不能用 NULL
            slow = slow->next;
            fast = fast->next;
            if(fast != tail)  fast = fast->next;
        }
        // 3. 分开排序
        ListNode *head1 = sortSection(head, slow);
        ListNode *head2 = sortSection(slow, tail);
        // 4. 归并
        ListNode *newhead = mergeSection(head1, head2);
        // 5. 返回
        return newhead;
    }
    // 归并两个已经排序的链表，返回新的链表头
    ListNode* mergeSection(ListNode *head1, ListNode *head2){
        ListNode *dummy = new ListNode(0);
        ListNode *p1 = head1, *p2 = head2, *pre = dummy;
        // 1. 这里可以使用 null 判断，因为排序后各个区间已经是使用 null 打散的
        while(p1 != NULL && p2 != NULL){
            if(p1->val < p2->val)
                pre->next = p1, pre = p1, p1 = p1->next;
            else
                pre->next = p2, pre = p2, p2 = p2->next;
        }
        // 2. 出循环后，没有走完的链表，就直接接上即可
        if(p1 != NULL)  pre->next = p1;
        if(p2 != NULL)  pre->next = p2;
        // 返回
        return dummy->next;
    }
};

时间复杂度：$O(n\log n)$.

空间复杂度：$O(\log n)$.

注：若改为自底向上归并排序，还可以空间复杂度降为 $O(1)$，但是没必要。
参考：链接

耍赖也未尝不可！

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        // 当然，还可以偷懒
        // 1. 转成 vector
        vector<int> arr;
        ListNode *p = head;
        while(p){
            arr.push_back(p->val);
            p = p->next;
        }
        // 2. 排序
        sort(arr.begin(), arr.end());
        // 3. 填回去
        p = head;
        for(int num : arr){
            p->val = num;
            p = p->next;
        }
        return head;
    }
};

时间复杂度：$O(n \log n)$.

空间复杂度：$O(n)$.

34. 合并 K 个升序链表

• 题面：

  给你一个链表数组，每个链表都已经按升序排列。

  请你将所有链表合并到一个升序链表中，返回合并后的链表。

• 示例：

  输入：lists = [[1,4,5],[1,3,4],[2,6]]
  输出：[1,1,2,3,4,4,5,6]
  解释：链表数组如下：
  [
    1->4->5,
    1->3->4,
    2->6
  ]
  将它们合并到一个有序链表中得到。
  1->1->2->3->4->4->5->6

解法 1解法 2

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // K 次归并即可
        int k = lists.size();
        if(k == 0)  return NULL;
        ListNode *newhead = lists[0];
        for(int i=1; i<k; i++)
            newhead = mergeSection(newhead, lists[i]);
        // 返回
        return newhead;
    }
    // 归并两个已排序的链表，返回排序完成的新链表头
    ListNode* mergeSection(ListNode *head1, ListNode *head2){
        ListNode *dummy = new ListNode(0);
        ListNode *p1 = head1, *p2 = head2, *pre = dummy;
        // 选择小的连接
        while(p1 != NULL && p2 != NULL){
            if(p1->val < p2->val)
                pre->next = p1, pre= p1, p1 = p1->next;
            else
                pre->next = p2, pre= p2, p2 = p2->next;
        }
        // 未完成的直接连上
        if(p1 != NULL)  pre->next = p1;
        if(p2 != NULL)  pre->next = p2;
        // 返回
        return dummy->next;
    }
};

时间复杂度：$O(k^2 n)$.

空间复杂度：$O(1)$.

耍赖未尝不可。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // 流氓还是有的
        if(lists.size() == 0)  return NULL;
        // 1. 转为 arr
        vector<int> arr;
        ListNode *pre = NULL, *first = NULL;
        for(ListNode* head : lists){
            // 并且直接把全部链表串起来
            if(head == NULL)
                continue;
            if(first)  pre->next = head;
            else  pre = first = head;
            // 本次读取
            ListNode *t = head;
            while(t != NULL){
                arr.push_back(t->val);
                pre = t;
                t = t->next;
            }
        }
        // 2. 排序
        sort(arr.begin(), arr.end());
        // 3. 填入
        ListNode *p = first;
        for(int num : arr){
            p->val = num;
            p = p->next;
        }
        // 返回
        return first;
    }
};

时间复杂度：$O(kn \log kn)$.

空间复杂度：$O(kn)$.

35. LRU 缓存

• 题面：

  请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
  实现 LRUCache 类：
  LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
  函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

• 示例：

  输入
  ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
  [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
  输出
  [null, null, null, 1, null, -1, null, -1, 3, 4]
  
  解释
  LRUCache lRUCache = new LRUCache(2);
  lRUCache.put(1, 1); // 缓存是 {1=1}
  lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
  lRUCache.get(1);    // 返回 1
  lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
  lRUCache.get(2);    // 返回 -1 (未找到)
  lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
  lRUCache.get(1);    // 返回 -1 (未找到)
  lRUCache.get(3);    // 返回 3
  lRUCache.get(4);    // 返回 4

解法 1

// 本题需要设计数据结构
// 双向链表节点
struct DNode{
    // 数据
    int key, value;
    DNode *prev;
    DNode *next;
    // 构造
    DNode(): key(0), value(0), prev(NULL), next(NULL){}
    DNode(int _key, int _value): key(_key), value(_value), prev(NULL), next(NULL){}
};

// 解题
class LRUCache {
private:
    // 数据
    unordered_map<int, DNode*> cache_map;
    int capacity;
    int size;
    DNode *head;
    DNode *tail;
    
public:
    // 函数
    LRUCache(int _capacity): capacity(_capacity), size(0) {
        // 初始化两个空头尾，方便很多
        head = new DNode();
        tail = new DNode();
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        // 1. 键不存在
        if(!cache_map.count(key))   // count 只返回 0 不存在，1 存在
            return -1;
        // 2. 键存在
        DNode *p = cache_map[key];
        // 添加到最近头
        removeNode(p);
        addToHead(p);
        // 返回值
        return p->value;
    }
    
    void put(int key, int value) {
        // 1. 键不存在
        if(!cache_map.count(key)){
            // 创建、写入、提到头部
            DNode *p = new DNode(key, value);
            cache_map[key] = p;
            addToHead(p);
            // 处理容量问题
            size++;
            if(size > capacity){
                // 删除尾部的
                DNode *t = tail->prev;  // 这里要暂存一下，因为后面操作了之后，会变动关系
                removeNode(t);
                cache_map.erase(t->key);
                delete t;   // 真实删除
                size--;
            }
        }
        // 2. 键存在
        else{
            // 直接改值即可，并提到头部
            DNode *p = cache_map[key];
            p->value = value;
            removeNode(p);
            addToHead(p);
        }
    }

    // 从链表中移除 p (注：并没有删除，只是从链表中移除)
    void removeNode(DNode *p){
        p->prev->next = p->next;
        p->next->prev = p->prev;
    }
    // 添加 p 到最头部
    void addToHead(DNode *p){
        p->prev = head;
        p->next = head->next;
        head->next->prev = p;
        head->next = p;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

时间复杂度：put和get均为$O(1)$.

空间复杂度：$O(capacity)$.

七、二叉树

36. 二叉树的中序遍历

• 题面：

  给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

• 示例：

  

  输入：root = [1,null,2,3]
  输出：[1,3,2]

解法 1

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 数据结构讲过，递归写一下即可
    vector<int> arr;
    vector<int> inorderTraversal(TreeNode* root) {
        if(root == NULL)
            return arr;
        inorderTraversal(root->left);
        arr.push_back(root->val);
        inorderTraversal(root->right);
        return arr;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

37. 二叉树的最大深度

• 题面：

  给定一个二叉树 root ，返回其最大深度。

  二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

• 示例：

  

  输入：root = [3,9,20,null,null,15,7]
  输出：3

解法 1解法 2

DFS

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 递归很简单(本质上是 深度优先遍历 DFS)
    int maxDepth(TreeNode* root) {
        // 结束条件
        if(root == NULL)  
            return 0;
        // 分别找到左右子树的最大深度，+1 即可
        int lmax = maxDepth(root->left);
        int rmax = maxDepth(root->right);
        return max(lmax, rmax) + 1;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

BFS

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 广度优先遍历 BFS 也能做
    int maxDepth(TreeNode* root) {
        if(root == NULL)  return 0;
        queue<TreeNode*> Q;
        int ans = 0;
        Q.push(root);
        // 思想是做到严格按层计算
        while(!Q.empty()){
            int num = Q.size(); // 只记录本层数量
            while(num > 0){
                TreeNode *p = Q.front();
                Q.pop();
                if(p->left)  Q.push(p->left);
                if(p->right)  Q.push(p->right);
                num--;
            }
            // 本层完成，进入下一层，因此深度+1
            ans++;
        }
        return ans;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

38. 翻转二叉树

• 题面：

  给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

• 示例：

  

解法 1

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        // 直接递归改左右指针即可
        if(root == NULL)  return NULL;
        TreeNode *t = root->left;
        root->left = root->right;
        root->right = t;
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

39. 对称二叉树

• 题面：

  给你一个二叉树的根节点 root ， 检查它是否轴对称。

• 示例：

  

  

解法 1解法 2

自己想的使用栈的方法。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == NULL)  return true;
        // 左右两个指针同时向下
        queue<TreeNode*> LQ, RQ;
        if(root->left)  LQ.push(root->left);
        if(root->right)  RQ.push(root->right);
        // 按层收割
        while(LQ.size() == RQ.size() && !LQ.empty()){
            // 依次取出，比较相同
            TreeNode *l = LQ.front();  LQ.pop();
            TreeNode *r = RQ.front();  RQ.pop();
            if(l && r && l->val != r->val)  
                return false;   // 注意，若是 l/r 均 null 也是 true
            // 压入子树(注意压入顺序, 且会压入null) 
            if(l)  LQ.push(l->left), LQ.push(l->right);
            if(r)  RQ.push(r->right), RQ.push(r->left);            
        }
        // 退出循环时，看大小就知道是不是正常对称结束的
        if(LQ.size() != RQ.size())  
            return false;
        return true;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

递归方法，复杂度是一样的，但是逻辑更巧妙。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return check(root->left, root->right);
    }
    // 递归两个指针向下找
    bool check(TreeNode *l, TreeNode *r){
        // 1. 均空
        if(!l && !r)  
            return true;
        // 2. 一空一非空
        if(!l || !r)    // 这个逻辑式本质并不是表示 2，但是有 1 在前面保证 2
            return false;
        // 3. 均非空
        if(l->val == r->val)    // 注意下面的比较
            return check(l->left, r->right) && check(l->right, r->left);
        else
            return false;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

40. 二叉树的直径

• 题面：

  给你一棵二叉树的根节点，返回该树的 直径 。

  二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

  两节点之间路径的 长度 由它们之间边数表示。

• 示例：

  

  输入：root = [1,2,3,4,5]
  输出：3
  解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

解法 1

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int ans = 0;
    int diameterOfBinaryTree(TreeNode* root) {
        // 在求深度的过程中来伴随更新最大直径
        depth(root);
        return ans;
    }
    // 求深度
    int depth(TreeNode *root){
        if(root == NULL)  return 0;
        int ldp = depth(root->left);
        int rdp = depth(root->right);
        // 每次求完，都算一下当前的最大直径
        ans = max(ans, ldp+rdp);
        return max(ldp, rdp) + 1;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(height)$.

41. 二叉树的层序遍历

• 题面：

  给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

• 示例：

  

  输入：root = [3,9,20,null,null,15,7]
  输出：[[3],[9,20],[15,7]]

解法 1解法 2

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 层序遍历: 用队列
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        queue<TreeNode*> Q;
        Q.push(root);
        int count = Q.size();    // 记录本层节点数量
        vector<int> tmp;
        while(!Q.empty()){
            // 节点操作
            TreeNode *node = Q.front();  Q.pop();
            if(node){
                tmp.push_back(node->val);
                Q.push(node->left);
                Q.push(node->right);
            }
            count--;
            // 分割层次
            if(count == 0 && tmp.size()){
                ans.push_back(tmp);
                tmp.clear();
                count = Q.size();
            }
        }
        // 返回
        return ans;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 还是层序遍历，换个写法
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        queue<TreeNode*> Q;
        Q.push(root);
        while(!Q.empty()){
            // 本层遍历
            int count = Q.size();
            vector<int> tmp;
            for(int i=0; i<count; i++){
                TreeNode *node = Q.front();  Q.pop();
                if(node){
                    tmp.push_back(node->val);
                    Q.push(node->left);
                    Q.push(node->right);
                }
            }
            // 本层结束
            if(tmp.size())  ans.push_back(tmp);
        }
        return ans;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

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

• 题面：

  给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

  平衡二叉树 是指该树所有节点的左右子树的深度相差不超过 1。

• 示例：

  

  输入：nums = [-10,-3,0,5,9]
  输出：[0,-3,9,-10,null,5]
  解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

  

解法 1解法 2

题解完整

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 中序遍历，总是选择中间位置左边的数字作为根节点
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return helper(0, nums.size()-1, nums);
    }
    // 根据区间来选数字 [l, r]
    TreeNode* helper(int l, int r, const vector<int>& nums){
        if(l > r)  return NULL;
        int mid = (l+r)/2;
        TreeNode *root = new TreeNode(nums[mid]);
        root->left = helper(l, mid-1, nums);
        root->right = helper(mid+1, r, nums);
        return root;
    }

};

时间复杂度：$O(n)$.

空间复杂度：$O(\log n),主要是递归栈的深度$.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 中序遍历，总是选择中间位置 右 边的数字作为根节点
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return helper(0, nums.size()-1, nums);
    }
    // 根据区间来选数字 [l, r]
    TreeNode* helper(int l, int r, const vector<int>& nums){
        if(l > r)  return NULL;
        int mid = (l+r+1)/2;    // 就改这里一处即可
        TreeNode *root = new TreeNode(nums[mid]);
        root->left = helper(l, mid-1, nums);
        root->right = helper(mid+1, r, nums);
        return root;
    }

};

时间复杂度：$O(n)$.

空间复杂度：$O(\log n),主要是递归栈的深度$.

43. 验证二叉搜索树

• 题面：

  给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

  有效二叉搜索树定义如下：

  • 节点的左子树只包含 小于 当前节点的数。

  • 节点的右子树只包含 大于 当前节点的数。

  • 所有左子树和右子树自身必须也是二叉搜索树。

• 示例1：

  

  输入：root = [2,1,3]
  输出：true

  示例2：

  

  输入：root = [5,1,4,null,null,3,6]
  输出：false
  解释：根节点的值是 5 ，但是右子节点的值是 4 。

解法 1解法 2解法 3

自己想的，感觉通俗易懂。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> arr;
    // 只需中序遍历一遍看是否严格递增即可
    bool isValidBST(TreeNode* root) {
        midSearch(root);
        return check();
    }
    // 中序遍历
    void midSearch(TreeNode* root){
        if(root == NULL)  return;
        midSearch(root->left);
        arr.push_back(root->val);
        midSearch(root->right);
    }
    // 检查是否严格递增
    bool check(){
        int n = arr.size();
        if(n == 0)  return true;
        int Max = arr[0];
        for(int i=1; i<n; i++){
            if(arr[i] == Max)  return false;    // 必须严格递增，不能相等
            Max = max(Max, arr[i]);
            if(arr[i] != Max)  return false;
        }
        return true;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 递归
    bool isValidBST(TreeNode* root) {
        // 从最值开始,由于出现了边界值，那我们用更大的 LONG
        return helper(root, LONG_MIN, LONG_MAX);
    }
    // 判断数值 val 是否在 (low, high) 之间
    bool helper(TreeNode *root, long low, long high){
        if(root == NULL)  return true;
        long value = root->val;
        if(value >= high || value <= low)   // 注意也不能等于
            return false;
        // 左子树要比自己还小
        bool l = helper(root->left, low, value);
        bool r = helper(root->right, value, high);
        return l && r;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

用栈实现的中序遍历，不如我想的方法，复杂度一样。

但是栈实现中序遍历的思想要学会。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 还是中序遍历，换个写法，栈
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> stk;
        long premax = LONG_MIN;
        TreeNode *node = root;
        while(!stk.empty() || node != NULL){    // 思考为什么！因为每次当前节点是还未压入栈的。
            // 不断压入左子树
            while(node != NULL){
                stk.push(node);
                node = node->left;
            }
            // 取出节点
            node = stk.top();  stk.pop();
            long val = node->val;
            if(premax >= val)
                return false;
            premax = val;
            // 走向右子树，压入会在下一轮循环操作
            node = node->right;
        }
        return true;
    }

};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

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

• 题面：

  给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

• 示例 1：

  

  输入：root = [3,1,4,null,2], k = 1
  输出：1

  示例 2：

  

  输入：root = [5,3,6,2,4,null,null,1], k = 3
  输出：3

解法 1解法 2解法 3

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> arr;
    int kthSmallest(TreeNode* root, int k) {
        // 1. 中序遍历
        inorderSearch(root);
        // 2. 取出第 k 小的（从 1 开始）
        return arr[k-1];
    }
    // 中序遍历出来
    void inorderSearch(TreeNode *root){
        if(root == NULL)  return;
        inorderSearch(root->left);
        arr.push_back(root->val);
        inorderSearch(root->right);
    }

};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        // 中序遍历：栈实现
        stack<TreeNode*> stk;
        TreeNode *node = root;
        int count = k;
        while(!stk.empty() || node != NULL){
            // 向左走
            while(node != NULL){
                stk.push(node);
                node = node->left;
            }
            // 弹出当前栈顶节点
            node = stk.top();  stk.pop();
            k--;
            if(k == 0)  break;
            // 向右走
            node = node->right;
        }
        return node->val;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

平衡二叉搜索树（AVL树）

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

45. 二叉树的右视图

• 题面：

  给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

• 示例:

  

  输入: [1,2,3,null,5,null,4]
  输出: [1,3,4]

解法 1

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 也就是返回最右侧的那些节点（即，每层的最后一个节点）
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        queue<TreeNode*> Q;
        if(root)  Q.push(root);
        while(!Q.empty()){
            int levelNum = Q.size();    // 本层节点数量
            TreeNode *node;
            for(int i=0; i<levelNum; i++){
                node = Q.front();  Q.pop();
                if(node->left)  Q.push(node->left);
                if(node->right)  Q.push(node->right);
            }
            ans.push_back(node->val);   // 只填写最后一个节点
        }
        return ans;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

46. 二叉树展开为链表

• 题面：

  给你二叉树的根结点 root ，请你将它展开为一个单链表：

  • 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。

  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。

• 示例：

  

  输入：root = [1,2,5,3,4,null,6]
  输出：[1,null,2,null,3,null,4,null,5,null,6]

解法 1解法 2解法 3解法 4

class Solution {
public:
    void flatten(TreeNode* root) {
        helper(root, NULL);
    }
    // 递归：把以 root 为根的树拉平后，右侧再接 next
    TreeNode* helper(TreeNode* root, TreeNode* next){
        if(root == NULL)  return next;  // 已经没有了，那么返回给上层需要接的就是 next

        // 1. 拉平右子树，并连 next。再重新连接为 root 右子树
        root->right = helper(root->right, next);

        // 2. 拉平左子树，并连 right。再转为 root 右子树
        root->right = helper(root->left, root->right);
        root->left = NULL;

        // 3. 返回当前 root 用于上层的连接
        return root;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

class Solution {
public:
    // 依次改正一个一个
    void flatten(TreeNode* root) {
        if(root == NULL)  return;
        
        // 1. 有左子树，那么先改正这一个左子树到 right，并且保证改完后整个树还是连接的。
        if(root->left){
            // 左子树如果改到 right，需要找到最右节点来连接原来的 right
            TreeNode *p = root->left;
            while(p->right)  p = p->right;
            p->right = root->right;
            // 现在可以安心地把左子树改到 right 去了
            root->right = root->left;
            root->left = NULL;
        }

        // 2. 无论前面改没改，下一次，都直接进入下一个节点，即 root 的 right（可能是刚刚改过来的左子树）
        flatten(root->right);
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(1)$.

class Solution {
public:
    // 直接记录前序遍历，然后依次改left right即可
    vector<TreeNode*> arr;
    void flatten(TreeNode* root) {
        if(root == NULL)  return;
        // 1. 先序遍历 记录下来
        preTraversal(root);

        // 2.依次更改指针
        int n = arr.size();
        for(int i=0; i<n-1; i++){
            arr[i]->left = NULL;
            arr[i]->right = arr[i+1];
        }
        arr[n-1]->left = NULL;
        arr[n-1]->right = NULL;
    }
    // 先序遍历
    void preTraversal(TreeNode *root){
        if(root == NULL)  return;
        arr.push_back(root);
        preTraversal(root->left);
        preTraversal(root->right);
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

class Solution {
public:
    // 先序遍历借用栈，就可以不使用记录了
    void flatten(TreeNode* root) {
        stack<TreeNode*> stk;
        if(root)  stk.push(root);
        TreeNode *pre = NULL;
        // 开始连接
        while(!stk.empty()){
            // 连接到当前的
            TreeNode *cur = stk.top();  stk.pop();
            if(pre != NULL){
                pre->left = NULL;
                pre->right = cur;
            }
            // 注意：先压right，因为后进先出
            if(cur->right)  stk.push(cur->right);
            if(cur->left)  stk.push(cur->left);
            // 更新 pre
            pre = cur;
        }
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

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

• 题面：

  给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

  • preorder 和 inorder 均 无重复 元素
  • inorder 均出现在 preorder
  • preorder 保证 为二叉树的前序遍历序列
  • inorder 保证 为二叉树的中序遍历序列

• 示例：

  

  输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
  输出: [3,9,20,null,null,15,7]

解法 1解法 2

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        if(n == 0)  return NULL;

        // 栈 + 指针
        stack<TreeNode*> S;
        int I = 0;  // inorder 的索引指针
        TreeNode *root = new TreeNode(preorder[0]);
        S.push(root);

        for(int i=1; i<n; i++){
            int num = preorder[i];
            TreeNode *node = new TreeNode(num);

            // 当前节点是左子树
            if(S.top()->val != inorder[I])
                S.top()->left = node;

            // 当前节点是右子树
            else{
                TreeNode *parent = NULL;
                while(!S.empty() && S.top()->val == inorder[I]){
                    parent = S.top();
                    S.pop();
                    I++;
                }
                if(parent)  parent->right = node;
            }
            
            // 压入在最后，不能在前面，因为前面需要判断前一次是不是 inorder[I]
            S.push(node);
        }

        return root;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 哈希表：节点值->中序的索引
    unordered_map<int, int> index;

    // 递归 先序的下标[pl, pr]  中序的下标[il, ir]
    TreeNode* buildSubTree(vector<int>& preorder, vector<int>& inorder, 
    int pl, int pr, int il, int ir){
        // 由于是采用下标，当前准备构建的就是 pl 节点
        if(pl > pr)  return NULL;

        // 根节点
        int InRoot = index[preorder[pl]];    // 中序所在的位置
        TreeNode *root = new TreeNode(preorder[pl]);

        // 左子树
        int LSize = InRoot - il;
        root->left = buildSubTree(preorder, inorder, pl+1, pl+LSize, il, InRoot-1);

        // 右子树
        root->right = buildSubTree(preorder, inorder, pl+LSize+1, pr, InRoot+1, ir);

        // 返回本次构建的节点
        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // 构造哈希表
        int n = preorder.size();
        for(int i=0; i<n; i++)
            index[inorder[i]] = i;
            
        // 构建树
        return buildSubTree(preorder, inorder, 0, n-1, 0, n-1);
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

48. 路径总和 III

• 题面：
  给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

  路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

• 示例：

  

  输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
  输出：3
  解释：和等于 8 的路径有 3 条，如图所示。

解法 1解法 2

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // DFS 计算一个当前节点为根向下可能有多少种
    int rootSum(TreeNode* p, long targetSum){   // 这里用 long
        if(!p)  return 0;
        int ret = 0;
        // 当前节点已经达到
        if(p->val == targetSum)  ret++;
        // 当前节点向左达到
        ret += rootSum(p->left, targetSum - p->val);
        // 当前节点向右达到
        ret += rootSum(p->right, targetSum - p->val);
        return ret;
    }
    // DFS 把所有节点都作为根，求出所有可能，加和
    int pathSum(TreeNode* root, int targetSum) {
        if(!root)  return 0;
        // 当前节点为根求出可能
        int ans = rootSum(root, targetSum);
        // 左右子树的所有可能
        ans += pathSum(root->left, targetSum);
        ans += pathSum(root->right, targetSum);
        return ans;
    }
};

时间复杂度：$O(N^2)$.

空间复杂度：$O(N)$.

借用哈希表，存储前面已经计算的结果。
每次借用前缀和出现的次数，来寻找本次能满足条件的数量。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 哈希表存储目前的前缀和数值的数量
    unordered_map<long long, int> prefix;

    // DFS 若有 前缀和 + targetSum = 当前前缀和，说明中间有路径到当前可以满足=targetSum
    int dfs(TreeNode* root, long long curr, int targetSum){
        if(!root)  return 0;
        int ret = 0;
        curr += root->val;
        // 看前缀和有多少个满足条件
        if(prefix.count(curr - targetSum))
            ret = prefix[curr - targetSum];
        // 进入更深
        prefix[curr]++;
        ret += dfs(root->left, curr, targetSum);
        ret += dfs(root->right, curr, targetSum);
        // 要回退了，因此把当前的 curr 值删去
        prefix[curr]--;
        // 返回
        return ret;
    }
    // 答案就是从根开始，一直向下dfs即可
    int pathSum(TreeNode* root, int targetSum) {
        int curr = 0;
        prefix[curr]++;  // 注意，最开始只有前缀和为 0
        return dfs(root, curr, targetSum);
    }
};

时间复杂度：$O(N)$.

空间复杂度：$O(N)$.

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

• 题面：
  给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

  百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

• 示例 1：

  

  输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
  输出：3
  解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

  示例 2：

  

  输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
  输出：5
  解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

解法 1解法 2

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *ans = NULL;
    // DFS 深度优先遍历
    bool dfs(TreeNode *root, TreeNode *p, TreeNode *q){
        if(root == NULL)  return false;
        bool lson = dfs(root->left, p, q);
        bool rson = dfs(root->right, p, q);
        bool self = root->val == p->val || root->val == q->val;
        // 答案在过程中:两种可能，1.在左右子树 2.自身是其中一个
        if( (lson && rson) || (self && (lson || rson)) )
            ans = root;
        // 返回当前树是否包含 p 或 q
        return lson || rson || self;
    }
    // 题目
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root, p, q);
        return ans;
    }
};

时间复杂度：$O(N)$.

空间复杂度：$O(N)$.

哈希表存储父节点。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    // 哈希表存储法，把父节点按照值存储下来，每个值可以直接查自己的父节点
    unordered_map<int, TreeNode*> father;
    // p依次把父节点全部访问一遍，q再访问，第一次遇到相同的，就是 LCA
    unordered_map<int, bool> visit;
    // 先 DFS 遍历把所有父节点记录下来
    void dfs(TreeNode *root){
        // 下面都会保证进入子树的dfs前自身都不是null，
        // 因此最初调用dfs要保证root不null即可
        if(root->left){
            father[root->left->val] = root;
            dfs(root->left);
        }
        if(root->right){
            father[root->right->val] = root;
            dfs(root->right);
        }
    }
    // 题目函数
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL)  return NULL;
        // 记得存最初的根无父亲
        father[root->val] = NULL;
        dfs(root);  // 注意这里 root 最初不能是 null
        // 开始遍历
        TreeNode *t = p;
        while(t){
            visit[t->val] = true;
            t = father[t->val];
        }
        // 当 q 再向上遍历时，第一个公共的就是 LCA
        t = q;
        while(t){
            if(visit[t->val])  return t;
            t = father[t->val];
        }
        // 未找到
        return NULL;
    }
};

时间复杂度：$O(N)$.

空间复杂度：$O(N)$.

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

• 题面：

  二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

  路径和 是路径中各节点值的总和。

  给你一个二叉树的根节点 root ，返回其 最大路径和 。

• 示例：
  

  输入：root = [-10,9,20,null,null,15,7]
  输出：42
  解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

解法 1

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 答案
    int ans = INT_MIN;
    // 递归获取每个节点的最大单程贡献值（即从这个节点向下的最大贡献）
    int maxGain(TreeNode* root){
        if(root == NULL)  return 0;
        // 左右向下的最大可能值（若负，则不选，即 0）
        int lmax = max(maxGain(root->left), 0);
        int rmax = max(maxGain(root->right), 0);

        // 当前完全路径的最大可能值
        int curr = root->val + lmax + rmax;
        ans = max(ans, curr);

        // 返回当前的单程最大贡献
        return root->val + max(lmax, rmax);
    }
    // 题目
    int maxPathSum(TreeNode* root) {
        maxGain(root);
        return ans;
    }
};

时间复杂度：$O(N)$.

空间复杂度：$O(N)$.

八、图论

51. 岛屿数量

• 题面：
  给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

  岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

  此外，你可以假设该网格的四条边均被水包围。

• 示例 1：

  输入：grid = [
    ["1","1","1","1","0"],
    ["1","1","0","1","0"],
    ["1","1","0","0","0"],
    ["0","0","0","0","0"]
  ]
  输出：1

  示例 2：

  输入：grid = [
    ["1","1","0","0","0"],
    ["1","1","0","0","0"],
    ["0","0","1","0","0"],
    ["0","0","0","1","1"]
  ]
  输出：3

解法 1

class Solution {
public:
    // 网格问题通用做法（参考二叉树思想）
    void traverse(vector<vector<char>>& grid, int r, int c){
        // 判断 base case
        if(!inArea(grid, r, c))
            return ;

        // 是岛屿才继续访问四周
        if(grid[r][c]!='1')
            return;
        // 如何避免重复访问（用标记2）
        grid[r][c] = '2';
        
        // 依次遍历四周
        traverse(grid, r-1, c);
        traverse(grid, r+1, c);
        traverse(grid, r, c-1);
        traverse(grid, r, c+1);
    }
    // 是否在区域内
    bool inArea(vector<vector<char>>& grid, int r, int c){
        int R = grid.size(), C = grid[0].size();
        return 0<=r && r<R && 0<=c && c<C; 
    }

    int numIslands(vector<vector<char>>& grid) {
        // 下面就把所有的情况都访问即可
        int ans = 0;
        int R = grid.size(), C = grid[0].size();
        for(int i=0; i<R; i++){
            for(int j=0; j<C; j++){
                if(grid[i][j]=='1'){
                    traverse(grid, i, j);
                    ans++;      // 完全遍历完这个空间，那就是一个岛屿
                }
            }
        }
        return ans;
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(1)$.

52. 腐烂的橘子

• 题面：
  在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

  值 0 代表空单元格；

  值 1 代表新鲜橘子；

  值 2 代表腐烂的橘子。

  每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

  返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

• 示例 1：

  输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
  输出：4

  
  示例 2：

  输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
  输出：-1

  解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。

  示例 3：

  输入：grid = [[0,2]]
  输出：0

  解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

解法 1解法 2

class Solution {
public:
    int curRot = 2; // 当前轮次的可感染标志（最初是标号 2 可以感染，第二轮是 3...）
    // 感染四周
    int Rot4(vector<vector<int>>& grid, int r, int c){
        // 判断 base case
        if(!inArea(grid, r, c))
            return 0;
        // 是本轮感染标号的，则感染四周
        if(grid[r][c]==curRot){
            int rotNum = 0;
            if(inArea(grid, r-1, c) && grid[r-1][c]==1)
                grid[r-1][c] = curRot+1, rotNum++;
            if(inArea(grid, r+1, c) && grid[r+1][c]==1)
                grid[r+1][c] = curRot+1, rotNum++;
            if(inArea(grid, r, c-1) && grid[r][c-1]==1)
                grid[r][c-1] = curRot+1, rotNum++;
            if(inArea(grid, r, c+1) && grid[r][c+1]==1)
                grid[r][c+1] = curRot+1, rotNum++;
            return rotNum;
        }
        return 0;
    }
    bool inArea(vector<vector<int>>& grid, int r, int c){
        int R = grid.size(), C = grid[0].size();
        return 0<=r && r<R && 0<=c && c<C;
    }
    // 感染一轮
    int RotEpoch(vector<vector<int>>& grid){
        int sum = 0;
        int R = grid.size(), C = grid[0].size();
        for(int i=0; i<R; i++){
            for(int j=0; j<C; j++){
                if(grid[i][j]==curRot)
                    sum += Rot4(grid, i, j);
            }
        }
        return sum;
    }
    // 检测是否全部腐烂
    bool allRotted(vector<vector<int>>& grid){
        int R = grid.size(), C = grid[0].size();
        for(int i=0; i<R; i++)
            for(int j=0; j<C; j++)
                if(grid[i][j]==1)  return false;
        return true;
    }

    int orangesRotting(vector<vector<int>>& grid) {
        int sum = -1;
        // 一轮一轮腐烂
        while(sum!=0){
            sum = RotEpoch(grid);
            curRot++;
        }
        // 检测最终
        if(allRotted(grid))
            return curRot-3;
        else
            return -1;
    }
};

时间复杂度：$O(k*mn)$.

空间复杂度：$O(1)$.

官方方法，使用了记录，要确保橘子数量不超过10*10大小

class Solution {
private:
    // 记录全部橘子各自的腐烂时间
    int badTime[10][10];
    int cnt = 0;    // 新鲜橘子数量
    // 方向向量
    int dirX[4] = {0, 0, 1, -1};
    int dirY[4] = {1, -1, 0, 0};

public:
    // 初始化 badTime 和 cnt， 生成一个初始的腐烂队列 Q
    void init(vector<vector<int>>& grid, queue<pair<int, int>>& Q){
        int R = grid.size(), C = grid[0].size();
        memset(badTime, -1, sizeof(badTime));   // 初始-1
        //（注意实际上是按字节填写的，只不过刚好无论是单字节/四字节，都刚好是-1）
        for(int i=0; i<R; i++){
            for(int j=0; j<C; j++){
                if(grid[i][j]==1)       // 新鲜橘子
                    cnt++;
                else if(grid[i][j]==2){ // 腐烂橘子
                    badTime[i][j] = 0;
                    Q.push({i, j});
                }
            }
        }
    }
    // 该位置是否是一个有效的新鲜橘子
    bool validGood(vector<vector<int>>& grid, int x, int y){
        int R = grid.size(), C = grid[0].size();
        return 0<=x && x<R && 0<=y && y<C && grid[x][y]==1 && badTime[x][y]==-1;
    }

    int orangesRotting(vector<vector<int>>& grid) {
        queue<pair<int, int>> Q;
        // 初始化变量
        init(grid, Q);
        // 依次取队列
        int ans = 0;
        while(!Q.empty()){
            // 取出一个腐烂橘子
            pair<int, int> pos = Q.front();
            Q.pop();
            int x = pos.first, y = pos.second;
            // 感染四周
            for(int t=0; t<4; t++){
                int tx = x + dirX[t], ty = y + dirY[t];
                if(validGood(grid, tx, ty)){
                    // 感染
                    badTime[tx][ty] = badTime[x][y] + 1;
                    cnt--;
                    Q.push({tx, ty});
                    ans = badTime[tx][ty];
                }
            }
        }
        return cnt==0? ans : -1;
    }
};

时间复杂度：$O(mn)$.

空间复杂度：$O(k)$.

53. 课程表

• 题面：
  你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

  在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

  例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

  请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

• 示例 1：

  输入：numCourses = 2, prerequisites = [[1,0]]
  输出：true

  解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

  示例 2：

  输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
  输出：false

  解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

解法 1

class Solution {
private:
    vector<vector<int>> preCourse;  // 先修课程
    vector<int> state;              // 修读状态（0 未修读，1 正在准备修读，2 修读完成）
    bool flag = true;               // 是否能完成

public:
    // 深度优先去修读这个课程（把先修课程修完，然后修读本课程）
    void study(int course){
        // 进入正在修读状态
        state[course] = 1;
        // 把所有先修课程修读完毕
        for(int i=0; i<preCourse[course].size(); i++){
            int pre = preCourse[course][i];
            if(state[pre]==0)       // 未修读，现在就去先修读
                study(pre);
            else if(state[pre]==1)  // 先修课程也正在修读，说明冲突了
                flag = false;
            // 每次都看是否已经失败了，失败提前退
            if(flag == false)
                return;
        }
        // 先修课程都修完了，现在修读本课程，修读完毕
        state[course] = 2;
    }


    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // 初始化
        preCourse.resize(numCourses);
        state.resize(numCourses);
        for(int i=0; i<prerequisites.size(); i++){
            int u = prerequisites[i][0], v = prerequisites[i][1];
            preCourse[v].push_back(u);  // 修读 v 需要先修 u
        }
        // 开始依次学习
        for(int i=0; i<numCourses; i++){
            if(!state[i]){
                study(i);
            }
        }
        // 返回结果
        return flag;
    }
};

时间复杂度：$O(n+m),n 课程数,m先修课程对$.

空间复杂度：$O(n+m)$.

54. 实现 Trie (前缀树)

• 题面：
  Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

  请你实现 Trie 类：

  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word 。
  • boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

• 示例：

  输入
  ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
  [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
  输出
  [null, null, true, false, true, null, true]
  解释
  Trie trie = new Trie();
  trie.insert("apple");
  trie.search("apple");   // 返回 True
  trie.search("app");     // 返回 False
  trie.startsWith("app"); // 返回 True
  trie.insert("app");
  trie.search("app");     // 返回 True

解法 1

class Trie {
private:
    // 这里是自动补全、拼写检查的那种功能，思考一下
    // 设计字典树：每一个节点是一个有 26 个空指针的数组，其中哪个不空，就意为那个字符(a-z)
    // (但是并不存储字符，而是存储下一个字母的指针，本身字符是什么，由哪个不空来表示)
    vector<Trie*> next;
    bool isEnd;         // 表示到当前字符，是否结束
    //（即便结束，也还有可以指向后续的，表示多种字符串，不矛盾）

    // 寻找匹配前缀的节点
    Trie* searchPrefix(string word){
        Trie* node = this;  // 从最开始
        for(char ch : word){
            ch -= 'a';
            if(node->next[ch] == NULL)
                return NULL;
            else
                node = node->next[ch];
        }
        // 返回完全匹配前缀的最后一个字符
        return node;
    }

public:
    // 初始化，每个节点是一个 26位空指针 的数组 
    Trie() : next(26), isEnd(false) {
        
    }
    
    void insert(string word) {
        // 从最初开始插入
        Trie* node = this;
        for(char ch : word){
            ch -= 'a';
            if(node->next[ch] == NULL){
                node->next[ch] = new Trie();
            }
            node = node->next[ch];
        }
        // 到最后一个字符，可以结束
        node->isEnd = true;
    }
    
    bool search(string word) {
        // 找到完全匹配的前缀，且返回的最后一个字符是结束的
        Trie* node = this->searchPrefix(word);
        return node!=NULL && node->isEnd;
    }
    
    bool startsWith(string prefix) {
        // 找到完全匹配的前缀存在即可
        Trie* node = this->searchPrefix(prefix);
        return node!=NULL;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

时间复杂度：$O(1), O(|S|)$.

空间复杂度：$O(|T| \cdot \sum), 其中|T|是所有字符串的总长度$.

九、回溯

55. 全排列

• 题面：
  给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

• 示例 1：

  输入：nums = [1,2,3]
  输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

  示例 2：

  输入：nums = [0,1]
  输出：[[0,1],[1,0]]

  示例 3：

  输入：nums = [1]
  输出：[[1]]

解法 1

class Solution {
// 回溯法：按照一定顺序尽可能探索出所有的解
private:
    vector<vector<int>> ans;
    vector<bool> visit;
    vector<int> output;

public:
    // 回溯: 把所有的可能情况按顺序依次填入0-n 个空格中，每次回溯时，记得维护访问
    void backtrace(vector<int>& nums, int s, int e){
        // 若已经完成一个完整的组合
        if(s == e){
            ans.emplace_back(output);
            return;
        }
        // 还未完成，那么把可选的都放入当前位置做一遍
        for(int i=0; i<e; i++){
            if(!visit[i]){
                output[s] = nums[i];
                visit[i] = true;
                backtrace(nums, s+1, e);
                visit[i] = false;
            }
        }
        return;
    }

    vector<vector<int>> permute(vector<int>& nums) {
        visit.resize(nums.size());
        output.resize(nums.size());
        backtrace(nums, 0, nums.size());
        return ans;        
    }
};

时间复杂度：$O(n * n!)$.

空间复杂度：$O(n)$.

56. 子集

• 题面：
  给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

  解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

• 示例 1：

  输入：nums = [1,2,3]
  输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

  示例 2：

  输入：nums = [0]
  输出：[[],[0]]

解法 1解法 2

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

public:
    // 采用 二进制数字 mask 刚好对应 0/1 序列 选/不选（数字逻辑的内容）
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        int MaxMask = 1 << n;   // 即 2^n
        for(int mask=0; mask<MaxMask; mask++){
            // 每个 mask 对应一个完整的序列，按位来查看是否选用
            t.clear();
            for(int i=0; i<n; i++)
                if(mask & (1<<i))  t.emplace_back(nums[i]);
            // 完成一次
            ans.emplace_back(t);
        }
        // 遍历结束即可
        return ans;
    }
};

时间复杂度：$O(n * 2^n), 一共 2^n 个答案，每个答案需要 n 次判断选/不选$.

空间复杂度：$O(n)$.

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

public:
    // 关于选/不选，也可以采用深度优先遍历的过程中来完成
    void dfs(int cur, vector<int>& nums){
        // 已经完成一次完整的序列
        if(cur == nums.size()){
            ans.emplace_back(t);
            return;
        }
        // 按照是否选用当前i所在字符
        // 选：先选入，再进入下一个的判断
        t.push_back(nums[cur]);
        dfs(cur+1, nums);
        t.pop_back();   // 恢复
        // 不选：不选，直接进入下一个的判断
        dfs(cur+1, nums);
    }

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

时间复杂度：$O(n * 2^n)$.

空间复杂度：$O(n)$.

57. 电话号码的字母组合

• 题面：
  给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

  给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

  

• 示例 1：

  输入：digits = "23"
  输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

  示例 2：

  输入：digits = ""
  输出：[]

  示例 3：

  输入：digits = "2"
  输出：["a","b","c"]

解法 1

class Solution {
private:
    // 哈希表存储
    unordered_map<char, string> map{
        {'2', "abc"},
        {'3', "def"},
        {'4', "ghi"},
        {'5', "jkl"},
        {'6', "mno"},
        {'7', "pqrs"},
        {'8', "tuv"},
        {'9', "wxyz"}
    };
    // 存储答案
    string output;
    vector<string> ans;

public:
    // 深度优先遍历
    void dfs(const string& digits, int k){
        // 集满则放入
        if(digits.size() == k){
            ans.emplace_back(output);
            return;
        }
        // 每次选取一个
        char num = digits[k];
        for(char ch: map[num]){
            output.push_back(ch);
            dfs(digits, k+1);
            output.pop_back();
        }
    }
    // 题目
    vector<string> letterCombinations(string digits) {
        // 题目特殊情况空时，不能输出空串，要空数组
        if(digits.size() == 0)  return ans;

        // 从 k=0 开始dfs
        dfs(digits, 0);
        return ans;
    }
};

时间复杂度：$O(3^m * 4^n), 这里m为 6，n为2$.

空间复杂度：$O(m+n)$.

58. 组合总和

• 题面：
  给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

  candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

  对于给定的输入，保证和为 target 的不同组合数少于 150 个。

• 示例 1：

  输入：candidates = [2,3,6,7], target = 7
  输出：[[2,2,3],[7]]
  解释：
  2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
  7 也是一个候选， 7 = 7 。
  仅有这两种组合。

  示例 2：

  输入: candidates = [2,3,5], target = 8
  输出: [[2,2,2,2],[2,3,3],[3,5]]

  示例 3：

  输入: candidates = [2], target = 1
  输出: []

解法 1解法 2

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

public:
    // dfs: 接下来选 k，当前还剩 cur 大小
    void dfs(int k, int cur, vector<int>& candidates){
        if(k >= candidates.size())  return;
        // 已经满足
        if(cur == 0){
            ans.emplace_back(output);
            return;
        }
        // 选用 k (会重复选，也可能不选)
        if(candidates[k] <= cur){
            output.push_back(candidates[k]);
            dfs(k, cur-candidates[k], candidates);
            output.pop_back();
        }
        // 选用 k+1
        dfs(k+1, cur, candidates);
    }

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

时间复杂度：$O(S) 或 O(n*2^n)，其中 S 为所有可行解的长度，n为位置长度$.

空间复杂度：$O(target)，最差情况的栈深度$.

class Solution {
public:
    // 动态规划：空间需求高
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        // dp[i] 表示所有和为 i 的组合
        vector<vector<vector<int>>> dp(target+1);
        dp[0] = {{}};

        // 每次选用数字都更新一次所有可以更新的组合
        for(int candidate: candidates){
            // 如何更新：加上当前candidate 可以到达的新组合，都更新一遍（但是不要超过target）
            for(int i=0; candidate+i<=target; i++){
                for(vector<int>& group: dp[i]){   // 和为 i 的所有组合都取出来看看
                    vector<int> newgroup = group;
                    newgroup.push_back(candidate);  // 原来是 i 加上 candidate
                    dp[candidate+i].push_back(newgroup);
                }
            }
        }
        // 和为 target 的所有组合就是答案
        return dp[target];
    }
};

时间复杂度：$O(n*target*2^n)$.

空间复杂度：$O(target * 2^n),主要是dp耗费空间$.

59. 括号生成

• 题面：
  数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

• 示例 1：

  输入：n = 3
  输出：["((()))","(()())","(())()","()(())","()()()"]

  示例 2：

  输入：n = 1
  输出：["()"]

解法 1解法 2

class Solution {
private:
    vector<string> ans;
public:
    // 暴力法：一共 2^{2n} 个解，检测所有解是否正确即可
    // 检测方法：用 flag 表示 '('数量 - ')'数量，这个数字只能 >=0 且最终 =0
    bool check(int mask, int n, string& output){
        int flag = 0;
        for(int i=0; i<2*n; i++){
            // 左括号
            if(mask & (1<<i)){
                output.push_back('(');
                flag++;
            }
            // 右括号
            else{
                output.push_back(')');
                flag--;
            }
            // 过程中都不能 <0
            if(flag < 0)  break;
        }
        return flag==0;
    }
    // 题目
    vector<string> generateParenthesis(int n) {
        int MaxMask = 1<<(2*n);
        for(int mask=0; mask<=MaxMask; mask++){
            string output;
            if(check(mask, n, output))
                ans.push_back(output);
        }
        return ans;
    }
};

时间复杂度：$O(2^{2n}*n)$.

空间复杂度：$O(n)栈深度最差 2n$.

class Solution {
private:
    vector<string> ans;

public:
    // 深度优先遍历：当前是output，还需要 lc个( 和 rc个)
    void dfs(string output, int lc, int rc){
        // 满足条件
        if(lc==0 && rc==0){
            ans.emplace_back(output);
            return;
        }
        // 加 (
        if(lc > 0)  dfs(output+'(', lc-1, rc);
        // 加 ) ：注意应该是还需要的 rc 更多
        if(rc > 0 && rc-lc > 0) dfs(output+')', lc, rc-1); 
    }
    // 题目
    vector<string> generateParenthesis(int n) {
        dfs("", n, n);
        return ans;
    }
};

时间复杂度：$低于O(2^{2n}*n)，因为相当于有剪枝$.

空间复杂度：$O(n)$.

60. 单词搜索

• 题面：
  给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

  单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

  board 和 word 仅由大小写英文字母组成

• 示例 1：
  

  输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
  输出：true

  示例 2：
  

  输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
  输出：true

  示例 3：
  

  输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
  输出：false

解法 1

class Solution {
private:
    vector<vector<int>> visited;    // 标记是否访问过
    int DIRS[4][2] = { {0,-1}, {0,1}, {-1,0}, {1,0} };  // 左右上下

public:
    // 是否为可行位置: 没有越界，且还未访问过
    bool feasible(int i, int j, const vector<vector<char>>& board){
        return i>=0 && i<board.size() && j>=0 && j<board[0].size() && !visited[i][j];
    }

    // 检测从 i,j 位置出发，能否搜索到字符串 word[k:]
    bool check(int i, int j, int k, const vector<vector<char>>& board, const string& word){
        // 当前位置不符，直接退出
        if(board[i][j] != word[k])  return false;
        // 当前位置符合
        // 1. 已经完成
        if(k == word.size()-1)  return true;
        // 2. 还能四方向探索
        visited[i][j] = true;
        for(auto& [dx, dy]: DIRS){
            int newi = i+dx, newj = j+dy;
            if(feasible(newi, newj, board)){            // 是可行区域，那么探索
                if(check(newi, newj, k+1, board, word)) // 探索则从 k+1 开始的字符串即可
                    return true;    // 只要有一个成功，就提前退出
            }
        }
        visited[i][j] = false;
        return false;   // 到此，肯定是失败了
    }

    // 题目
    bool exist(vector<vector<char>>& board, string word) {
        // 初始化 visited 为 m * n 大小
        int m = board.size(), n = board[0].size();
        visited.resize(m);
        for(int i=0; i<m; i++)  visited[i].resize(n, 0);
        // 把每个位置作为起始都探索一遍即可
        for(int i=0; i<m; i++)
            for(int j=0; j<n; j++)
                if(check(i, j, 0, board, word))
                    return true;   // 有一个位置成功，就算成功
        return false;   // 全都失败
    }
};

时间复杂度：$宽松上界O(m*n*3^L),mn 为 board 大小，L 为 word 长度$.

空间复杂度：$O(mn)$.

61. 分割回文串

• 题面：
  给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串。返回 s 所有可能的分割方案。

  s 仅由小写英文字母组成

• 示例 1：

  输入：s = "aab"
  输出：[["a","a","b"],["aa","b"]]

  示例 2：

  输入：s = "a"
  输出：[["a"]]

解法 1

class Solution {
private:
    // dp[i][j] 表示 子串s[i:j] 是否为回文串
    vector<vector<int>> dp;
    // 存储答案
    vector<vector<string>> ans;
    vector<string> path;    // 一次的答案

public:
    // 1. 先动态规划预处理把所有子字符串s[i:j] 是否为回文串的判断做完
    void DP(const string& s){
        int n = s.size();
        // 初始化全为true 主要是把 i>=j 的都赋值为 true
        dp.assign(n, vector<int>(n, true));
        // 动态规划改值
        for(int i=n-1; i>=0; i--)   // 如何判断 i,j 怎么变化？看状态转移方程的需求
            for(int j=i+1; j<n; j++)
                dp[i][j] = dp[i+1][j-1] && (s[i]==s[j]);
    }
    
    // 2. 再使用深度优先遍历回溯枚举，假定 k 前面已经完成分割，从 k 为起始分割后面的
    void dfs(int k, const string& s){
        // 已经完成
        if(k == s.size()){
            ans.emplace_back(path);
            return;
        }
        // 分割出回文串 s[k:j] 那么需要枚举 j
        for(int j=k; j<s.size(); j++){
            if(dp[k][j]){
                path.push_back(s.substr(k, j-k+1)); // s.substr(start, len)
                dfs(j+1, s);    // 然后继续深度优先把 j+1 起始往后的补全
                path.pop_back();    // 回溯，吐出来
            }
        }
    }

    // 题目
    vector<vector<string>> partition(string s) {
        DP(s);      // 动态规划预处理
        dfs(0, s);  // 深度优先回溯，从0起始开始分割
        return ans;
    }
};

时间复杂度：$O(n * 2^n)最差情况下，字符串 n长度但全是相同字符，因此可以2^{n-1}种划分$.

空间复杂度：$O(n^2)$.

62. N 皇后

• 题面：
  按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

  n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

  给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

  每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

• 示例 1：
  

  输入：n = 4
  输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
  解释：如上图所示，4 皇后问题存在两个不同的解法。

  示例 2：

  输入：n = 1
  输出：[["Q"]]

解法 1

class Solution {
private:
    vector<vector<string>> ans;
    vector<string> path;
    vector<pair<int, int>> cur;

public:
    // 判断是否可摆放
    bool check(int i, int j){
        // 同行、同列、斜线
        for(auto& [x, y]: cur)
            if(x==i || y==j || abs(i-x)==abs(j-y))
                return false;
        return true;
    }

    // 回溯法: k行之前已经完成可行，接下来在第k行开始摆放后续的皇后
    void backtrace(int k, int n){
        // 完成
        if(k == n){
            ans.emplace_back(path);
            return;
        }
        // 在第 k 行依次摆放，记得撤回
        for(int i=0; i<n; i++){
            if(check(k, i)){    // 检查这个位置是否可以摆放
                string s(n, '.');  s[i] = 'Q';
                path.push_back(s);  cur.push_back({k, i});
                backtrace(k+1, n);  // 下面再填写 k+1 行即可
                path.pop_back();  cur.pop_back();
            }
        }
    }
    // 题目
    vector<vector<string>> solveNQueens(int n) {
        backtrace(0, n);
        return ans;
    }
};

时间复杂度：$O(n!)$.

空间复杂度：$O(n)$.

十、二分查找

63. 搜索插入位置

• 题面：
  给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

  请必须使用时间复杂度为 O(log n) 的算法。

  nums 为 无重复元素 的 升序 排列数组。

• 示例 1:

  输入: nums = [1,3,5,6], target = 5
  输出: 2

  示例 2:

  输入: nums = [1,3,5,6], target = 2
  输出: 1

  示例 3:

  输入: nums = [1,3,5,6], target = 7
  输出: 4

解法 1

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        // 直接写循环二分
        int lc = 0, rc = nums.size()-1;
        while(lc <= rc){
            int mid = (lc+rc)/2;
            if(target <= nums[mid])
                rc = mid-1;
            else
                lc = mid+1;
        }
        return lc;
    }
};

时间复杂度：$O(\log n)$.

空间复杂度：$O(1)$.

64. 搜索二维矩阵

• 题面：
  给你一个满足下述两条属性的 m x n 整数矩阵：

  每行中的整数从左到右按非严格递增顺序排列。

  每行的第一个整数大于前一行的最后一个整数。

  给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

• 示例 1：
  

  输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
  输出：true

  示例 2：
  

  输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
  输出：false

解法 1解法 2解法 3

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // 两次二分查找
        // 第一次：找到可能包含的那一行
        int li = 0, ri = matrix.size()-1;
        while(li <= ri){
            int mi = (li+ri)/2;
            if(target == matrix[mi][0])
                return true;
            else if(target < matrix[mi][0])
                ri = mi-1;
            else
                li = mi+1;
        }
        int row = max(0, min(li, ri));
        // 第二次：找到这一行里面有没有
        int lj = 0, rj = matrix[0].size()-1;
        while(lj <= rj){
            int mj = (lj+rj)/2;
            if(target == matrix[row][mj])
                return true;
            else if(target < matrix[row][mj])
                rj = mj-1;
            else
                lj = mj+1;
        }
        int col = max(0, min(lj, rj));
        // 最终判断
        return matrix[row][col] == target;
    }
};

时间复杂度：$O(\log m + \log n = \log mn)$.

空间复杂度：$O(1)$.

class Solution {
public:
    // 完美使用 STL
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // 编写二维数组大小判断的 lambda 函数
        // 函数指针 = [捕获外界变量表](函数参数表) -> 返回类型 { 函数体 };
        auto f = [](int a, vector<int>& b) -> bool { return a < b[0]; };
        // 找到第一个大于 target 的所在行
        auto row = upper_bound(matrix.begin(), matrix.end(), target, f);
        // 判断:注意 row 是指针
        if(row == matrix.begin())
            return false;   // 第一行就更大，说明不存在
        // 否则，应该回退一行，才是所在行
        row--;
        // 下面直接在所在行二分查找即可
        return binary_search(row->begin(), row->end(), target);
    }
};

时间复杂度：$O(\log mn)$.

空间复杂度：$O(1)$.

class Solution {
public:
    // 还有办法，直接一次二分查找（关键看如何处理行列：取整、取余）
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int lc = 0, rc = m*n-1;
        while(lc <= rc){    // 注意有等于
            int mid = (lc+rc)/2;
            int x = matrix[mid/n][mid%n];   // 关键点！！！
            if(target == x)
                return true;
            else if(target < x)
                rc = mid-1;
            else
                lc = mid+1;
        }
        // 最终失败
        return false;
    }
};

时间复杂度：$O(\log mn)$.

空间复杂度：$O(1)$.

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

• 题面：
  给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

  如果数组中不存在目标值 target，返回 [-1, -1]。

  你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

• 示例 1：

  输入：nums = [5,7,7,8,8,10], target = 8
  输出：[3,4]

  示例 2：

  输入：nums = [5,7,7,8,8,10], target = 6
  输出：[-1,-1]

  示例 3：

  输入：nums = [], target = 0
  输出：[-1,-1]

解法 1解法 2

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        // 空单独处理
        int n = nums.size();
        if(n==0)  
            return vector<int>{-1, -1};
        // 正常处理
        int lc = 0, rc = n-1;
        int ansl = -1, ansr = -1;
        // 仍然套用二分查找：目标是找到第一个 target 所在位置
        while(lc <= rc){
            int mid = (lc+rc)/2;
            if(target <= nums[mid])
                rc = mid-1;
            else
                lc = mid+1;
        }
        // 若有找到，那么继续增大到第一个不是 target 的即可
        if(lc<=n-1 && nums[lc] == target){          // 注意超界
            ansl = lc;
            ansr = ansl;
            while(ansr<=n-1 && nums[ansr]==target)  // 注意超界
                ansr++;
            ansr--;
        }
        // 返回
        return vector<int>{ansl, ansr};
    }
};

时间复杂度：$O(\log n)$.

空间复杂度：$O(1)$.

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        // 直接无脑两次二分查找也可以
        if(nums.size()==0)  return vector<int>{-1, -1};
        // 第一次找左边界
        int l = 0, r = nums.size()-1;
        while(l <= r){
            int mid = (l+r)/2;
            if(target <= nums[mid])
                r = mid-1;
            else
                l = mid+1; 
        }
        int ansl = l;
        if(ansl > nums.size()-1 || nums[ansl] != target)    // 注意超界
            return vector<int>{-1, -1};
        // 第二次找右边界
        l = 0, r = nums.size()-1;
        while(l <= r){
            int mid = (l+r)/2;
            if(target >= nums[mid])
                l = mid+1;
            else
                r = mid-1;
        }
        int ansr = r;
        return vector<int>{ansl, ansr};
    }
};

时间复杂度：$O(\log n)$.

空间复杂度：$O(1)$.

66. 搜索旋转排序数组

• 题面：
  整数数组 nums 按升序排列，数组中的值 互不相同 。

  在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

  给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

  你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

• 示例 1：

  输入：nums = [4,5,6,7,0,1,2], target = 0
  输出：4

  示例 2：

  输入：nums = [4,5,6,7,0,1,2], target = 3
  输出：-1

  示例 3：

  输入：nums = [1], target = 0
  输出：-1

解法 1

class Solution {
public:
    // 仍然可以二分法，有一半可以拿来作为条件支撑
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size()-1;
        while(l <= r){
            int mid = (l+r)/2;
            if(target == nums[mid])
                return mid;
            // 看哪边有序，就拿来判断(前提：不能有相同元素)
            else{
                // 1. 左一半有序
                if(nums[l] <= nums[mid]){    // 这里必须是 <= 
                    if(nums[l] <= target && target < nums[mid])
                        r = mid-1;
                    else
                        l = mid+1;
                }
                // 2. 右一半有序
                else{
                    if(nums[mid] < target && target <= nums[r])
                        l = mid+1;
                    else
                        r = mid-1;
                }
            }
        }
        // 出循环是失败
        return -1;
    }
};

时间复杂度：$O(\log n)$.

空间复杂度：$O(1)$.

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

• 题面：
  已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

  若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]

  若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

  注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

  给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。

  你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

• 示例 1：

  输入：nums = [3,4,5,1,2]
  输出：1
  解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

  示例 2：

  输入：nums = [4,5,6,7,0,1,2]
  输出：0
  解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

  示例 3：

  输入：nums = [11,13,15,17]
  输出：11
  解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。

解法 1解法 2解法 3

class Solution {
public:
    // 违规方法
    int findMin(vector<int>& nums) {
        auto p = min_element(nums.begin(), nums.end());
        return *p;  // 若空，则 p == nums.end()，这里不用考虑
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(1)$.

class Solution {
public:
    // 仍然二分法
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size()-1;
        int ans = nums[0];
        while(l <= r){
            int mid = (l+r)/2;
            if(nums[mid] < ans)
                ans = nums[mid];
            // 哪边边界最小，往那边走
            int left = min(nums[l], nums[max(mid-1, l)]);   // 注意防止超界
            int right = min(nums[min(mid+1, r)], nums[r]);
            if(left < right)
                r = mid-1;
            else
                l = mid+1;
        }
        return ans;
    }
};

时间复杂度：$O(\log n)$.

空间复杂度：$O(1)$.

class Solution {
public:
    // 二分法：右边界判别，若 nums[r] 比 nums[mid] 更大了，那么右边肯定是有序递增。 
    // 原因：由于旋转，nums[r] 一定是 小于 nums[l] 的。再思考一下。
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size()-1;
        while(l < r){   // 等于时退出
            int mid = (l+r)/2;
            if(nums[mid] < nums[r])     // 右边界大，右边肯定是递增，因此抛弃右边
                r = mid;
            else                        // 否则，是最小值卡在右边，因此抛弃左边
                l = mid+1;
        }
        // 最终答案
        return nums[l];
    }
};

时间复杂度：$O(\log n)$.

空间复杂度：$O(1)$.

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

• 题面：
  给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

  算法的时间复杂度应该为 O(log (m+n)) 。

• 示例 1：

  输入：nums1 = [1,3], nums2 = [2]
  输出：2.00000
  解释：合并数组 = [1,2,3] ，中位数 2

  示例 2：

  输入：nums1 = [1,2], nums2 = [3,4]
  输出：2.50000
  解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

解法 1解法 2解法 3

class Solution {
public:
    // 违规方法：先合并排序，再找到中位数即可
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        // 合并
        vector<int> nums;
        nums.insert(nums.end(), nums1.begin(), nums1.end());
        nums.insert(nums.end(), nums2.begin(), nums2.end());
        // 排序
        sort(nums.begin(), nums.end());
        int n = nums.size();
        if(n%2 == 0)
            return (nums[n/2-1] + nums[n/2]) / 2.0;     // 注意是 2.0
        else
            return nums[n/2];
    }
};

时间复杂度：$O(m+n)$.

空间复杂度：$O(m+n)$.

class Solution {
public:
    // 获得第 k 小的数字
    int getKth(vector<int>& nums1, vector<int>& nums2, int k){
        int m = nums1.size(), n = nums2.size();
        int s1 = 0, s2 = 0;
        // 每次排除前 k-2 个数字
        while(true){
            // 边界情况
            if(s1 == m)
                return nums2[s2 + k-1];
            if(s2 == n)
                return nums1[s1 + k-1];
            // 结束情况
            if(k == 1)
                return min(nums1[s1], nums2[s2]);
            // 一般情况
            int p1 = min(s1 + k/2-1, m-1);
            int p2 = min(s2 + k/2-1, n-1);
            if(nums1[p1] <= nums2[p2])
                k -= p1-s1+1, s1 = p1+1;    // 已经排除 s1--p1之间的数字了
            else
                k -= p2-s2+1 , s2 = p2+1;
        }
    }
    // 题目
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int N = nums1.size() + nums2.size();
        if(N%2 == 1)
            return getKth(nums1, nums2, N/2+1);
        else{
            int a = getKth(nums1, nums2, N/2);
            int b = getKth(nums1, nums2, N/2+1);
            return (a+b)/2.0;
        }
    }
};

时间复杂度：$O(\log (m+n))$.

空间复杂度：$O(1)$.

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

    // 每次寻找第k小的数，每次先去除前k/2小的数
    double GetK(vector<int>& nums1, vector<int>& nums2, int k, int start1, int start2){
        int len1 = nums1.size()-start1, len2 = nums2.size()-start2;
        if(len1==0)
            return nums2[start2+k-1];
        if(len2==0)
            return nums1[start1+k-1];
        
        if(k==1)
            return min(nums1[start1], nums2[start2]);

        int k2 = min(k/2, len1);
        k2 = min(k2, len2);
        if(nums1[start1+k2-1] <= nums2[start2+k2-1])
            return GetK(nums1, nums2, k-k2, start1+k2, start2);
        else
            return GetK(nums1, nums2, k-k2, start1, start2+k2);
    }
};

时间复杂度：$O(\log (m+n))$.

空间复杂度：$O(m+n)$.

69. 有效的括号

• 题面：
  给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

  有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。

  2. 左括号必须以正确的顺序闭合。

  3. 每个右括号都有一个对应的相同类型的左括号。

• 示例 1：

  输入：s = "()"
  输出：true

  示例 2：

  输入：s = "()[]{}"
  输出：true

  示例 3：

  输入：s = "(]"
  输出：false

  示例 4：

  输入：s = "([])"
  输出：true

解法 1解法 2

class Solution {
private:
    vector<char> stack;

public:
    bool check(char ch){
        // 左括号直接加入
        if(ch == '(' || ch == '[' || ch == '{'){
            stack.push_back(ch);
            return true;
        }
        // 右括号时
        // 若空，则直接失败
        if(stack.empty())
            return false;
        // 不空，则需要匹配
        char top = stack[stack.size()-1];
        switch(ch){
            case ')':
                if(top == '('){
                    stack.pop_back();
                    return true;
                }
                break;
            case ']':
                if(top == '['){
                    stack.pop_back();
                    return true;
                }
                break;
            case '}':
                if(top == '{'){
                    stack.pop_back();
                    return true;
                }
                break;
        }
        
        // 未成功匹配
        return false;
    }

    // 模拟栈空间
    bool isValid(string s) {
        int n = s.size();
        for(int i=0; i<n; i++)
            if(!check(s[i]))
                return false;
        // 最后还需要是空的
        return stack.empty();
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

class Solution {
public:
    // 直接用栈 STL
    bool isValid(string s) {
        // 优化：若 s 奇数，必然失败
        int n = s.size();
        if(n%2)  return false;
        
        // 一般情况
        stack<char> stk;
        unordered_map<char, char> map = { {')', '('}, {']', '['}, {'}', '{'} };
        // 开始匹配
        for(int i=0; i<n; i++){
            char ch = s[i];
            // 右括号
            if(map.count(ch))
                // 空或无法匹配，都失败
                if(stk.empty() || stk.top() != map[ch])
                    return false;
                else
                    stk.pop();
            // 左括号
            else
                stk.push(ch);
        }
        // 返回
        return stk.empty();
    }
};

时间复杂度：$O(n)$.

空间复杂度：$O(n)$.

70.

• 题面：

解法 1解法 2

时间复杂度：$O()$.

空间复杂度：$O()$.

时间复杂度：$O()$.

空间复杂度：$O()$.