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

一、哈希

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.

• 题面：

解法 1解法 2

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

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

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

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