Hot 100总结【leetcode】

时间复杂度：O(n)，其中 n 是数组height 的长度。从 0 到 n−1 的每个下标最多只会入栈和出栈各一次。

空间复杂度：O(n)，其中 n 是数组height 的长度。空间复杂度主要取决于栈空间，栈的大小不会超过n

滑动窗口

8. 3 无重复的最长子串

解法一：滑动窗口+哈希表
哈希表 dic： 指针 j 遍历字符 s ，哈希表统计字符 s[j] 最后一次出现的索引 。

更新左指针 i： 根据上轮左指针 i 和 dic[s[j]] ，每轮更新左边界 i ，保证区间 [i+1,j] 内无重复字符且最大。

$i=\max (dic[s[j]],i)$
更新结果 res ： 取上轮 res 和本轮双指针区间 [i+1,j] 的宽度（即 j−i）中的最大值。

res=max⁡(res,j−i)

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //s[j],以及最后一次出现的索引号
        unordered_mapdic;
        int i=-1,res=0,len=s.size();
        for(int j=0;j
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

时间复杂度：O(N)，其中 N 是字符串的长度。左指针和右指针分别会遍历整个字符串一次。

空间复杂度：$O(|\Sigma |)$，其中 Σ 表示字符集（即字符串中可以出现的字符），$|\Sigma |$表示字符集的大小。在本题中没有明确说明字符集，因此可以默认为所有 ASCII 码在 [0,128) 内的字符，即 $|\Sigma |=128$。我们需要用到哈希集合来存储出现过的字符，而字符最多有 $|\Sigma |\mid$ 个，因此空间复杂度为 $O(|\Sigma |)$。

解法二：动态规划+哈希表

状态定义： 设动态规划列表 dp ，dp[j]代表以字符 s[j]为结尾的 “最长不重复子字符串” 的长度。
转移方程： 固定右边界 j ，设字符 s[j] 左边距离最近的相同字符为 s[i] ，即 s[i]=s[j]。
当 i<0 ，即 s[j]左边无相同字符，则 dp[j]=dp[j−1]+1。

当 dp[j−1]

当 dp[j−1]≥j−i ，说明字符 s[i]在子字符串 dp[j−1]区间之中 ，则 dp[j] 的左边界由 s[i]决定，即 dp[j]=j−i。

当 i<0时，由于 dp[j−1]≤j 恒成立，因而 dp[j−1]

$dp[j]=\{\begin{array}{ll}dp[j-1]+1& ,dp[j-1]<j-i\\ j-i& ,dp[j-1]\ge j-i\end{array}$

返回值： max⁡(dp) ，即全局的 “最长不重复子字符串” 的长度。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_mapdic;
        int res=0,tmp=0,len=s.size(),i;
        for(int j=0;j
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

状态压缩：
由于返回值是取 dp列表最大值，因此可借助变量 tmp 存储 dp[j] ，变量 res每轮更新最大值即可。
此优化可节省 dp 列表使用的 O(N) 大小的额外空间。
哈希表记录：
观察转移方程，可知关键问题：每轮遍历字符 s[j]时，如何计算索引 i ？

哈希表统计： 遍历字符串 s 时，使用哈希表（记为 dic ）统计 各字符最后一次出现的索引位置 。
左边界 i 获取方式： 遍历到 s[j] 时，可通过访问哈希表 dic[s[j]] 获取最近的相同字符的索引 i。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_mapdic;
        int res=0,tmp=0,len=s.size(),i;
        for(int j=0;j
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

解法：滑动窗口

思路

根据题目要求，我们需要在字符串 s 寻找字符串 p 的异位词。因为字符串 p 的异位词的长度一定与字符串 p 的长度相同，所以我们可以在字符串 s 中构造一个长度为与字符串 p的长度相同的滑动窗口，并在滑动中维护窗口中每种字母的数量；当窗口中每种字母的数量与字符串 p 中每种字母的数量相同时，则说明当前窗口为字符串 p 的异位词。

算法

在算法的实现中，我们可以使用数组来存储字符串 p 和滑动窗口中每种字母的数量。

细节

当字符串 s 的长度小于字符串 p 的长度时，字符串 s 中一定不存在字符串 p 的异位词。但是因为字符串 sss 中无法构造长度与字符串 p 的长度相同的窗口，所以这种情况需要单独处理。

class Solution {
public:
    vector findAnagrams(string s, string p) {
        vectorresult;
        int sLen=s.size();
        int pLen=p.size();
        if(sLenschars(26);
        vectorpchars(26);
        for(int i=0;i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

时间复杂度：$O(m+(n-m)\times \Sigma )$，其中 n 为字符串 s 的长度，m 为字符串 p 的长度，Σ 为所有可能的字符数。我们需要O(m) 来统计字符串 p 中每种字母的数量；需要 O(m) 来初始化滑动窗口；需要判断 n−m+1 个滑动窗口中每种字母的数量是否与字符串 p 中每种字母的数量相同，每次判断需要 $O(\Sigma )$。因为 s 和 p 仅包含小写字母，所以$\Sigma =26$。

空间复杂度：$O(\Sigma )$。用于存储字符串 p 和滑动窗口中每种字母的数量。

解法二：优化后的滑动窗口

思路和算法

在方法一的基础上，我们不再分别统计滑动窗口和字符串 ppp 中每种字母的数量，而是统计滑动窗口和字符串 ppp 中每种字母数量的差；并引入变量 differ 来记录当前窗口与字符串 ppp 中数量不同的字母的个数，并在滑动窗口的过程中维护它。

在判断滑动窗口中每种字母的数量与字符串 ppp 中每种字母的数量是否相同时，只需要判断 differ 是否为零即可。

class Solution {
public:
    vector findAnagrams(string s, string p) {
        int sLen = s.size(), pLen = p.size();

        if (sLen < pLen) {
            return vector();
        }

        vector ans;
        vector count(26);
        for (int i = 0; i < pLen; ++i) {
            ++count[s[i] - 'a'];
            --count[p[i] - 'a'];
        }

        int differ = 0;
        for (int j = 0; j < 26; ++j) {
            if (count[j] != 0) {
                ++differ;
            }
        }

        if (differ == 0) {
            ans.emplace_back(0);
        }
      //表示字母出现次数差距
        //count[x] = 0  表示 s与p中字母x出现次数相同 都出现了n次(n>=0)
        //count[x] = n  表示 在s中字母x出现次数比p多 多出现了n次(n>0)
        //count[x] = -n 表示 在s中字母x出现次数比p少 少出现了n次(n>0)
        for (int i = 0; i < sLen - pLen; ++i) {
          
           //缩减时只考虑count[x]==1与count[x]==0的情况
            //因为缩减时字母x减少，count[x]会减去1
            //(1)count[x]==1时(次数差距1次，不相同)  
            //count[x]==0 -> 次数相同 -> 不相同变相同，字母差异个数减少1 -> differ--

            //(2)count[x]==0时(次数相同)  
            //count[x]==-1 -> 次数差距变为1次->相同变不相同 ，字母差异个数增加1 -> differ++

            //(3)count[x]==-1时(次数不相同) -> count[x]==-2 次数还是不相同-> 字母差异数不变

            //(4)count[x]==2时(次数不相同)  -> count[x]==1 次数还是不相同-> 字母差异数不变
            if (count[s[i] - 'a'] == 1) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
                --differ;
            } else if (count[s[i] - 'a'] == 0) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
                ++differ;
            }
            --count[s[i] - 'a'];

            if (count[s[i + pLen] - 'a'] == -1) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从不同变得相同
                --differ;
            } else if (count[s[i + pLen] - 'a'] == 0) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从相同变得不同
                ++differ;
            }
            ++count[s[i + pLen] - 'a'];
            
            if (differ == 0) {
                ans.emplace_back(i + 1);
            }
        }

        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

子串

10. 560 和为k的子数组

image-20231220211015272

解法一：前缀和+哈希表

假设nums数组中[j,i]组成的子数组的和为k(j<=i)，首先定义前缀和pre[i]表示[0…i]里所有数的和，则pre[i]可以由pre[i-1]递推而来：

$$pre[i]=pre[i-1]+nums[i]$$

那么如果[j,…,i]的这个子数组的和为k,其实等价于在前缀和数组中

$$pre[i]-pre[j-1]==k$$

即：$pre[j-1]==pre[i]-k$

所以我们考虑以 i结尾的和为 k 的连续子数组个数时只要统计有多少个前缀和为pre[i]−k 的 pre[j] 即可。我们建立哈希表 prefixSumCount以和为键，出现次数为对应的值，记录 pre[i] 出现的次数，从左往右边更新prefixSumCount 边计算答案，那么以 i 结尾的答案prefixSumCount[pre[i]−k] 即可在 O(1) 时间内得到。最后的答案即为所有下标结尾的和为 k 的子数组个数之和。

需要注意的是，从左往右边更新边计算的时候已经保证了prefixSumCount[pre[i]−k] 里记录的 pre[j] 的下标范围是 0≤j≤i 。同时，由于pre[i] 的计算只与前一项的答案有关，因此我们可以不用建立 pre 数组，直接用 pre 变量来记录 pre[i−1] 的答案即可。

代码：

class Solution {
public:
    int subarraySum(vector& nums, int k) {
        unordered_mapprefixSumCount;
        int count=0;
        int pre=0;
        //初始化，表示前缀和为0的个数为1
        prefixSumCount[0]=1;
        for(int i=0;i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时间复杂度：O(n) 其中 n 为数组的长度。我们遍历数组的时间复杂度为O(n)，中间利用哈希表查询删除的复杂度均为O(1)，因此总时间复杂度为 O(n)。

空间复杂度：O(n) 其中 n为数组的长度。哈希表在最坏情况下可能有 n个不同的键值，因此需要 O(n) 的空间复杂度。

解法二：枚举，方法通过重循环遍历得到以索引位置为i结尾的连续子数组的个数和，其中[j…i]的这个子数组的和恰好为k。详细见官方题解：

560. 和为 K 的子数组 - 力扣（LeetCode）

11. 239 滑动窗口最大值

解法一：滑动窗口+暴力遍历 超时

class Solution {
public:
    vector maxSlidingWindow(vector& nums, int k) {
        vectorresult;
        if(k==1)
        return nums;
        int maxNum=-10e5;
        int secondNum=-10e5;
        for(int i=0;imaxNum){
                
            }
            maxNum=max(nums[i],maxNum);
        }
        result.emplace_back(maxNum);
        int len=nums.size()-k;    
        for(int i=0;imaxNum){
                    maxNum=nums[i+k];
                    result.emplace_back(maxNum);
                }
                else{
                    maxNum=-10e5;
                    for(int j=i+1;j<=i+k;j++){
                        maxNum=max(maxNum,nums[j]);
                    }
                    result.emplace_back(maxNum);
                }
            }
        }
        return result;    
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

解法一优化策略：单调队列

回忆 最小栈 ，其使用 单调栈 实现了随意入栈、出栈情况下的 O(1)时间获取 “栈内最小值” 。本题同理，不同点在于 “出栈操作” 删除的是 “列表尾部元素” ，而 “窗口滑动” 删除的是 “列表首部元素” 。因此应该使用单调队列～

由于我们需要求出的是滑动窗口的最大值，如果当前的滑动窗口中有两个下标 i 和 j，其中 i 在 j 的左侧（i

当滑动窗口向右移动时，只要 i还在窗口中，那么 j 一定也还在窗口中，这是 i 在 j 的左侧所保证的。因此，由于 nums[j]的存在，nums[i]一定不会是滑动窗口中的最大值了，我们可以将 nums[i] 永久地移除。

因此我们可以使用一个队列存储所有还没有被移除的下标。在队列中，这些下标按照从小到大的顺序被存储，并且它们在数组nums 中对应的值是严格单调递减的。因为如果队列中有两个相邻的下标，它们对应的值相等或者递增，那么令前者为 i，后者为 j，就对应了上面所说的情况，即 nums[i]会被移除，这就产生了矛盾。

当滑动窗口向右移动时，我们需要把一个新的元素放入队列中。为了保持队列的性质，我们会不断地将新的元素与队尾的元素相比较，如果前者大于等于后者，那么队尾的元素就可以被永久地移除，我们将其弹出队列。我们需要不断地进行此项操作，直到队列为空或者新的元素小于队尾的元素。

class Solution {
public:
    vector maxSlidingWindow(vector& nums, int k) {
        int n=nums.size();
        dequeque;
        for(int i=0;i=nums[que.back()]){
                que.pop_back();
            }
            que.push_back(i);
        }
        vectorans={nums[que.front()]};
        for(int i=k;i=nums[que.back()]){
                que.pop_back();
            }
            que.push_back(i);
            while(que.front()<=i-k){
                que.pop_front();
            }
            ans.push_back(nums[que.front()]);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

时间复杂度：O(n)，其中 n 是数组 nums 的长度。每一个下标恰好被放入队列一次，并且最多被弹出队列一次，因此时间复杂度为 O(n)。

空间复杂度：O(k)。与方法一不同的是，在方法二中我们使用的数据结构是双向的，因此「不断从队首弹出元素」保证了队列中最多不会有超过 k+1 个元素，因此队列使用的空间为 O(k)

解法三：优先队列（堆）

对于「最大值」，我们可以想到一种非常合适的数据结构，那就是优先队列（堆），其中的大根堆可以帮助我们实时维护一系列元素中的最大值。

对于本题而言，初始时，我们将数组 nums 的前 k 个元素放入优先队列中。每当我们向右移动窗口时，我们就可以把一个新的元素放入优先队列中，此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能并不在滑动窗口中，在这种情况下，这个值在数组 nums 中的位置出现在滑动窗口左边界的左侧。因此，当我们后续继续向右移动窗口时，这个值就永远不可能出现在滑动窗口中了，我们可以将其永久地从优先队列中移除。

我们不断地移除堆顶的元素，直到其确实出现在滑动窗口中。此时，堆顶元素就是滑动窗口中的最大值。为了方便判断堆顶元素与滑动窗口的位置关系，我们可以在优先队列中存储二元组 (num,index)，表示元素 num 在数组中的下标为index。

class Solution {
public:
    vector maxSlidingWindow(vector& nums, int k) {
       priority_queue>pq;
       for(int i=0;ians{pq.top().first};
       for(int i=k;i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

时间复杂度：O(nlog⁡n)，其中 n 是数组 nums 的长度。在最坏情况下，数组 nums 中的元素单调递增，那么最终优先队列中包含了所有元素，没有元素被移除。由于将一个元素放入优先队列的时间复杂度为 O(log⁡n)，因此总时间复杂度为 O(nlog⁡n)。

空间复杂度：O(n)，即为优先队列需要使用的空间。这里所有的空间复杂度分析都不考虑返回的答案需要的 O(n) 空间，只计算额外的空间使用。

c++优先队列(priority_queue)用法详解_c++ 优先队列-CSDN博客

12. 76 最小覆盖子串

解法：滑动窗口

滑动窗口的思想：
用l,r表示滑动窗口的左边界和右边界，通过改变i,j来扩展和收缩滑动窗口，可以想象成一个窗口在字符串上游走，当这个窗口包含的元素满足条件，即包含字符串T的所有元素，记录下这个滑动窗口的长度r-l+1，这些长度中的最小值就是要求的结果。

步骤一
不断增加r使滑动窗口增大，直到窗口包含了T的所有元素

步骤二
不断增加l使滑动窗口缩小，因为是要求最小字串，所以将不必要的元素排除在外，使长度减小，直到碰到一个必须包含的元素，这个时候不能再扔了，再扔就不满足条件了，记录此时滑动窗口的长度，并保存最小值

步骤三
让i再增加一个位置，这个时候滑动窗口肯定不满足条件了，那么继续从步骤一开始执行，寻找新的满足条件的滑动窗口，如此反复，直到j超出了字符串S范围。

面临的问题：
如何判断滑动窗口包含了T的所有元素？
我们用一个map,num2Count来表示当前滑动窗口中需要的各元素的数量，一开始滑动窗口为空，用T中各元素来初始化这个num2Count，当滑动窗口扩展或者收缩的时候，去维护这个num2Count，例如当滑动窗口包含某个元素，我们就让num2Count中这个元素的数量减1，代表所需元素减少了1个；当滑动窗口移除某个元素，就让num2Count中这个元素的数量加1。
记住一点：num2Count始终记录着当前滑动窗口下，我们还需要的元素数量，我们在改变l,r时，需同步维护num2Count。
值得注意的是，只要某个元素包含在滑动窗口中，我们就会在num2Count中存储这个元素的数量，如果某个元素存储的是负数代表这个元素是多余的。比如当num2Count等于{‘A’:-2,‘C’:1}时，表示当前滑动窗口中，我们有2个A是多余的，同时还需要1个C。这么做的目的就是为了步骤二中，排除不必要的元素，数量为负的就是不必要的元素，而数量为0表示刚刚好。
回到问题中来，那么如何判断滑动窗口包含了T的所有元素？结论就是当need中所有元素的数量都小于等于0时，表示当前滑动窗口不再需要任何元素。
优化
如果每次判断滑动窗口是否包含了T的所有元素，都去遍历num2Count看是否所有元素数量都小于等于0，这个会耗费O(k的时间复杂度，k代表字典长度，最坏情况下，k可能等于len(S)。
其实这个是可以避免的，我们可以维护一个额外的变量numCnt来记录所需元素的总数量，当我们碰到一个所需元素c，不仅num2Count[c]的数量减少1，同时numCnt，这样我们通过numCnt就可以知道是否满足条件，而无需遍历字典了。
前面也提到过，num2Count记录了遍历到的所有元素，而只有仅num2Count[c]>0大于0时，代表c就是所需元素

代码：

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_mapchar2Count;
        for(auto c:t){
            char2Count[c-'A']++;
        }
        int numCnt=t.size();
        int minlen=10e5;
        int l=0,r=0;
        int ansL=-1;
        while(r=0){
            numCnt--;
         }
         //numCnt=0说明包含
         while(numCnt==0){
            if(++char2Count[s[l]-'A']>0){
                //此时左指针的位置在t中，不能收缩
                if(r-l+1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

时间复杂度：我们会用r扫描一遍S，也会用l扫描一遍S，最多扫描2次S，所以时间复杂度是O(n)，

空间复杂度为O(k)，k为S和T中的字符集合。

普通数组

13. 53 最大子数组和

解法一：动态规划【步骤】

• 定义dp[i]表示数组中前i+1（注意这里的i是从0开始的）个元素构成的连续子数组的最大和。
• 如果要计算前i+1个元素构成的连续子数组的最大和，也就是计算dp[i]，只需要判断dp[i-1]+num[i]和num[i]哪个大，如果dp[i-1]+num[i]大，则dp[i]=dp[i-1]+num[i]，否则令dp[i]=nums[i]。
• 在递推过程中，可以设置一个值max，用来保存子序列的最大值，最后返回即可。
• 转移方程：dp[i]=Math.max(nums[i], nums[i]+dp[i-1])；
• 边界条件判断，当i等于0的时候，也就是前1个元素，他能构成的最大和也就是他自己，所以dp[0]=num[0];

代码：

class Solution {
public:
    int maxSubArray(vector& nums) {
        int res=nums[0];
        int n=nums.size();
        vectordp(nums);
        for(int i=1;i
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度：O(n)，其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。
空间复杂度：O(1)。我们只需要常数空间存放若干变量。

解法二：分治法

分治法的思路是这样的，其实也是分类讨论。

连续子序列的最大和主要由这三部分子区间里元素的最大和得到：

第 1 部分：子区间 [left, mid]；
第 2 部分：子区间 [mid + 1, right]；
第 3 部分：包含子区间 [mid , mid + 1] 的子区间，即 nums[mid] 与 nums[mid + 1] 一定会被选取。
对这三个部分求最大值即可。

说明：考虑第 3 部分跨越两个区间的连续子数组的时候，由于 nums[mid] 与 nums[mid + 1] 一定会被选取，可以从中间向两边扩散，扩散到底 选出最大值。

代码：

class Solution {
public:
    int maxSubArray(vector& nums) {
       int len=nums.size();
       if(len==0)
       return 0;
       return maxSubArraySum(nums,0,len-1);
    }
    int maxCrossingSum(vector& nums,int left,int mid,int right){
        //一定包含nums[mid]元素
        int sum=0;
        int leftSum=-1e6;
        //左半边包含nums[mid]元素，最多可以到达的地方
        for(int i=mid;i>=left;i--){
            sum+=nums[i];
            if(sum>leftSum){
                leftSum=sum;
            }
        }
        sum=0;
        int rightsum=-1e6;
        for(int i=mid+1;i<=right;i++){
            sum+=nums[i];
            if(sum>rightsum){
                rightsum=sum;
            }
        }
        return leftSum+rightsum;
    }
    int maxSubArraySum(vector& nums,int left,int right){
        if(left==right)
        return nums[left];
        int mid=left+(right-left)/2;
        return max3(maxSubArraySum(nums,left,mid),maxSubArraySum(nums,mid+1,right),maxCrossingSum(nums,left,mid,right));
    }
    int max3(int num1,int num2,int num3){
        return max(num1,max(num2,num3));
    }

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

时间复杂度：O(Nlog⁡N)，这里递归的深度是对数级别的，每一层需要遍历一遍数组（或者数组的一半、四分之一）；
空间复杂度：O(log⁡N)，需要常数个变量用于选取最大值，需要使用的空间取决于递归栈的深度.

14. 56 合并区间

解法：排序+贪心

用数组res存储最终的答案。

首先，我们将列表中的区间按照左端点升序排序。然后我们将第一个区间加入 res 数组中，并按顺序依次考虑之后的每个区间：

如果当前区间的左端点在数组res 中最后一个区间的右端点之后，那么它们不会重合，我们可以直接将这个区间加入数组 merged 的末尾；

否则，它们重合，我们需要用当前区间的右端点更新数组 merged 中最后一个区间的右端点，将其置为二者的较大值。

其正确性可见官方题解：

56. 合并区间 - 力扣（LeetCode）

代码：

class Solution {
public:
    vector> merge(vector>& intervals) {
        vector>res;
        if(intervals.size()==1)
        return intervals;
        sort(intervals.begin(),intervals.end());
         res.push_back(intervals[0]);
        for(int i=1;iright){
                    res.pop_back();
                     res.push_back({left,intervals[i][1]});
                }   
            }
            else{
                res.push_back(intervals[i]);
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

时间复杂度：O(nlogn)，其中 n 为区间的数量。除去排序的开销，我们只需要一次线性扫描，所以主要的时间开销是排序的O(nlogn)。

空间复杂度：O(logn)，其中 n 为区间的数量。这里计算的是存储答案之外，使用的额外空间。O(logn) 即为排序所需要的空间复杂度。

15. 189 轮转数组

解法：最开始解法使用就地移位的方式，n=数组的长度，那么每次都将前n-1个数字后移，然后将最后一个放到第一个位置。即按照题目的要去每次翻转一次。但是这种方式在37个案例的时候超时。

解法二：就地翻转。题目的意思就是将后k个数组移动到前k个上。

以例1为例：[1,2,3,4,5,6,7]

首先可以将整个数组翻转=>[7,6,5,4,3,2,1]

然后将前k个数字翻转：[5,6,7,4,3,2,1]

再将后n-k个数字翻转：[5,6,7,1,2,3,4]

class solution_18 {
public:
    //打算向后移动位数的方法 超时
    void rotate2(vector& nums, int k) {
        int temp;
        int n=nums.size()-1;
        while(k){
            temp=nums[n];
            for(int i=n-1;i>=0;i--){
                nums[i+1]=nums[i];
            }
            nums[0]=temp;
            k--;
        }
//        for(int num:nums){
//            cout<& nums, int k) {
        int n=nums.size()-1;
        k=k%nums.size();
        reverse(nums,0,n);
        reverse(nums,0,k-1);
        reverse(nums,k,n);
    }
    void reverse(vector&nums,int start,int end){
        while(start
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

时间复杂度：O(n)，其中 n 为数组的长度。每个元素被翻转两次，一共 n 个元素，因此总时间复杂度为 O(2n)=O(n)。

空间复杂度：O(1)

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

解法：注意题目要求不能使用除法，如果要求一个nums中除nums[i]之外的其余各元素的乘积。

一种方法是所有乘积除以nums[i]，因为题目要求不能使用除法，所以这种方法不行。

因此可以换一种方式：nums[i]的左侧的数字乘积乘以nums[i]右侧的数字乘积。

通过预处理的方式得到两个数组，分别表示索引i位置左侧的乘积和右侧的乘积。

初始化两个空数组 L 和 R。对于给定索引 i，L[i] 代表的是 i 左侧所有数字的乘积，R[i] 代表的是 i 右侧所有 数字的乘积。
用两个循环来填充 L 和 R 数组的值。对于数组 L，L[0] 应该是 1，因为第一个元素的左边没有元素。对于其他元素：L[i] = L[i-1] * nums[i-1]。
同理，对于数组 R，R[nums.size()-1] 应为 1。length 指的是输入数组的大小。

其他元素：R[i] = R[i+1] * nums[i+1]。
当 R 和 L 数组填充完成，我们只需要在输入数组上迭代，且索引 i 处的值为：L[i] * R[i]。

代码：

class solution_28 {
public:
    vector productExceptSelf(vector& nums) {
        vectorresult(nums.size());
        vectorleft(nums.size(),0);
        vectorright(nums.size(),0);
        left[0]=1;
        //left[i]表示索引i左侧所有元素乘积
        for(int i=1;i=0;i--){
            right[i]=right[i+1]*nums[i+1];
        }
        for(int i=0;i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

时间复杂度：O(N)，其中 N 指的是数组 nums 的大小。预处理 L 和 R 数组以及最后的遍历计算都是 O(N) 的时间复杂度。

空间复杂度：O(N)，其中 N指的是数组 nums 的大小。使用了 L 和 R 数组去构造答案，L 和 R 数组的长度为数组 nums 的大小。

17. 41 缺失的第一个正数

解法：当然暴力解法也能够解决问题，但是不满足在时间复杂度为O（n）。

我们还可以把每个元素存放到对应的位置，比如1存放到数组的第一个位置，3存放到数组的第3个位置，如果是非正数或者大于数组的长度的值，我们不做处理，最后在遍历一遍数组，如果位置不正确，说明这个位置没有这个数，我们就直接返回。

代码：

int firstMissingPositive(vector& nums) {
int index=0;
while(index=nums.size()) {
index++;
}
else{
if(tmp==nums[tmp-1]){
index++;
continue;
}
int cnt=nums[tmp-1];
nums[tmp-1]=nums[index];
nums[index]=cnt;

}
}
for(int i=0;i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

时间复杂度：O（n）

空间复杂度：O（1）

矩阵

18. 73 矩阵置零

解法：简单标记，循环遍历矩阵，将矩阵为0的位置的行和列记录下来，放入set集合中去重，然后

再次遍历矩阵，若这个位置的行或者列在set集合中，那么就将这个位置置为1。

代码：

class solution_24 {
public:
    void setZeroes(vector>& matrix) {
        setrow;
        setcol;
        for(int i=0;i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

时间复杂度：O(mn)，其中 m是矩阵的行数，n 是矩阵的列数。我们至多只需要遍历该矩阵两次。

空间复杂度：O(m+n)，其中 m 是矩阵的行数，n 是矩阵的列数。我们需要分别记录每一行或每一列是否有零出现。

19. 54 螺旋矩阵

解法：因为观察到顺时针方向是按照右、下、左、上的顺序执行的，因此可以用递归的方式按照此顺序遍历矩阵，只有在遍历位置超出矩阵长度范围，或者此节点已经访问过，才会改变下一个方向。

因此设置direction数组，表示右、下、左、上四个方向。status表示此次取到的direction的方向索引，可例2可以看到，当5遍历到1时，发现已经访问呢，因此会转向右方向，因此可以用取余的方式遇到阻碍需要转向。

需要注意dfs递归的终点是当result的结果等于矩阵的大小，说明已经遍历结束，可以返回。

代码：

const int direction[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
class solution_20 {
public:
    vector spiralOrder(vector>& matrix) {
        vectorresult;
        vector>flag(matrix.size(),vector(matrix[0].size(),0));
        int status=0;
        dfs(matrix,flag,result,0,0,status);
        for(int num:result){
            cout<>&matrix,vector>&flag,vector &result,int i,int j,int status){
        flag[i][j]=1;
        result.push_back(matrix[i][j]);
        if(result.size()==matrix.size()*matrix[0].size()){
            return ;
        }
        int nextI=i+direction[status][0];
        int nextJ=j+direction[status][1];
        if(nextI<0||nextI>=matrix.size()||nextJ<0||nextJ>=matrix[0].size()||flag[nextI][nextJ]==1){
            status=(status+1)%4;
        }
        dfs(matrix,flag,result,i+direction[status][0],j+direction[status][1],status);
    }
};

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

时间复杂度：O(mn)，其中 m 和 n 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。

空间复杂度：O(mn)。需要创建一个大小为 m×n 的矩阵 visited 记录每个位置是否被访问过。

20. 48 旋转图像

解法一：递推公式，分组旋转

首先我们由示例2可以观察到如下图所示，矩阵顺时针旋转 90º 后，可找到以下规律：

「第 i 行」元素旋转到「第 n−1−i列」元素；
「第 j列」元素旋转到「第 j 行」元素；

因此，对于矩阵任意第 i行、第 j 列元素 $matrix[i][j]$ ，矩阵旋转 90º 后「元素位置旋转公式」为：

$\begin{array}{rl}matrix[i][j]& \to matrix[j][n-1-i]\end{array}$

$\begin{array}{rl}原索引位置& \to 旋转后索引位置\end{array}$

• 以位于矩阵四个角点的元素为例，设矩阵左上角元素 A 、右上角元素 B 、右下角元素 C 、左下角元素 D 。矩阵旋转 90º 后，相当于依次先后执行 D→A , C→D , B→C, A→B修改元素，即如下「首尾相接」的元素旋转操作：

如上图所示，由于第 1 步 D→A 已经将 A覆盖（导致 A丢失），此丢失导致最后第 A→B 无法赋值。为解决此问题，考虑借助一个「辅助变量 tmp预先存储 A ，此时的旋转操作变为：

暂存 tmp=A
A←D←C←B←tmp

如上图所示，一轮可以完成矩阵 4 个元素的旋转。因而，只要分别以矩阵左上角 1/4 的各元素为起始点执行以上旋转操作，即可完整实现矩阵旋转。

具体来看，当矩阵大小 n 为偶数时，取前$\frac{n}{2}$ 行、前 $\frac{n}{2} $列的元素为起始点；当矩阵大小 n 为奇数时，取前 $\frac{n}{2} $行、前 $\frac{n + 1}{2} $ 列的元素为起始点。

令 $matrix[i][j]=A$，根据文章开头的元素旋转公式，可推导得适用于任意起始点的元素旋转操作：

暂存

$tmp=matrix[i[j]$

$matrix[i[j]\leftarrow matrix[n-1-j][i]\leftarrow matrix[n-1-i][n-1-j]\leftarrow matrix[j][n-1-i]\leftarrow tmp$

代码：

class Solution {
public:
    void rotate(vector>& matrix) {
        int n=matrix.size();
        for(int i=0;i
1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度 O(N^2) ： 其中 N 为输入矩阵的行（列）数。需要将矩阵中每个元素旋转到新的位置，即对矩阵所有元素操作一次，使用 O(N^2)时间。
空间复杂度 O(1) ： 临时变量 tmp 使用常数大小的额外空间。值得注意，当循环中进入下轮迭代，上轮迭代初始化的 tmp 占用的内存就会被自动释放，因此无累计使用空间。

解法二：用翻转代替旋转

见官方题解：48. 旋转图像 - 力扣（LeetCode）

代码：

class Solution {
public:
    void rotate(vector>& matrix) {
       int n=matrix.size();
       //水平翻转
       for(int i=0;i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

时间复杂度：O(N^2)，其中 N 是 matrix 的边长。对于每一次翻转操作，我们都需要枚举矩阵中一半的元素。

空间复杂度：O(1)。为原地翻转得到的原地旋转。

21. 240 搜索二维矩阵||

解法一：二叉树遍历

如下图所示，我们将矩阵逆时针旋转 45° ，并将其转化为图形式，发现其类似于 二叉搜索树 ，即对于每个元素，其左分支元素更小、右分支元素更大。因此，通过从 “根节点” 开始搜索，遇到比 target 大的元素就向左，反之向右，即可找到目标值 target 。

“根节点” 对应的是矩阵的 “左下角” 和 “右上角” 元素，本文称之为 标志数 ，以 matrix 中的 左下角元素 为标志数 flag ，则有:

若 flag > target ，则 target 一定在 flag 所在 行的上方 ，即 flag 所在行可被消去。
若 flag < target ，则 target 一定在 flag 所在 列的右方 ，即 flag 所在列可被消去。
算法流程：
从矩阵 matrix 左下角元素（索引设为 (i, j) ）开始遍历，并与目标值对比：
当 matrix[i][j] > target 时，执行 i-- ，即消去第 i 行元素。
当 matrix[i][j] < target 时，执行 j++ ，即消去第 j 列元素。
当 matrix[i][j] = target 时，返回 true ，代表找到目标值。
若行索引或列索引越界，则代表矩阵中无目标值，返回 false 。
每轮 i 或 j 移动后，相当于生成了“消去一行（列）的新矩阵”， 索引(i,j) 指向新矩阵的左下角元素（标志数），因此可重复使用以上性质消去行（列）。

代码：

class Solution {
public:
    bool searchMatrix(vector>& matrix, int target) {
        int i=matrix.size()-1;
        int j=0;
        while(i>=0&&jtarget){
                i--;
            }
            else if(matrix[i][j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时间复杂度 O(M+N) ：其中，N 和 M分别为矩阵行数和列数，此算法最多循环 M+N 次。
空间复杂度 O(1) : i, j 指针使用常数大小额外空间。

解法二：暴力查找，不详细介绍

解法三：二分查找

由于矩阵 matrix 中每一行的元素都是升序排列的，因此我们可以对每一行都使用一次二分查找，判断 target 是否在该行中，从而判断}target 是否出现。

class Solution {
public:
    bool searchMatrix(vector>& matrix, int target) {
        for (const auto& row: matrix) {
            auto it = lower_bound(row.begin(), row.end(), target);
            if (it != row.end() && *it == target) {
                return true;
            }
        }
        return false;
    }
};

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

时间复杂度：O(mlogn)。对一行使用二分查找的时间复杂度为 O(log⁡n)，最多需要进行 m次二分查找。

空间复杂度：O(1)。

链表

22. 160 相交链表

解法一：哈希集合

判断两个链表是否相交，可以使用哈希集合存储链表节点。

首先遍历链表 headA，并将链表 headA 中的每个节点加入哈希集合中。然后遍历链表 headB，对于遍历到的每个节点，判断该节点是否在哈希集合中：

如果当前节点不在哈希集合中，则继续遍历下一个节点；

如果当前节点在哈希集合中，则后面的节点都在哈希集合中，即从当前节点开始的所有节点都在两个链表的相交部分，因此在链表 headB中遍历到的第一个在哈希集合中的节点就是两个链表相交的节点，返回该节点。

如果链表 headB中的所有节点都不在哈希集合中，则两个链表不相交，返回 null。

/**
 * 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_setvisited;
       ListNode*tmp=headA;
       while(tmp!=nullptr){
        visited.insert(tmp);
        tmp=tmp->next;
       }
       tmp=headB;
       while(tmp!=nullptr){
        if(visited.count(tmp)){
            return tmp;
        }
        tmp=tmp->next;
       }
       return nullptr;
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

时间复杂度：O(m+n)，其中 m 和 n 是分别是链表 headA 和 headB 的长度。需要遍历两个链表各一次。

空间复杂度：O(m），其中 m 是链表 headA 的长度。需要使用哈希集合存储链表 headA中的全部节点。

解法二优化：双指针

使用双指针的方法，可以将空间复杂度降至 O(1。

只有当链表 headA和headB 都不为空时，两个链表才可能相交。因此首先判断链表headA 和 headB 是否为空，如果其中至少有一个链表为空，则两个链表一定不相交，返回 null。

当链表 headA 和 headB 都不为空时，创建两个指针 pA和 pB，初始时分别指向两个链表的头节点 headA 和 headB，然后将两个指针依次遍历两个链表的每个节点。具体做法如下：

每步操作需要同时更新指针 pA和 pB。

如果指针 pA不为空，则将指针 pA 移到下一个节点；如果指针 pB不为空，则将指针 pB 移到下一个节点。

如果指针 pA 为空，则将指针 pA 移到链表 headB 的头节点；如果指针 pB 为空，则将指针 pB移到链表headA 的头节点。

当指针pA 和 pB 指向同一个节点或者都为空时，返回它们指向的节点或者 null。

证明上述方法的正确性

下面提供双指针方法的正确性证明。考虑两种情况，第一种情况是两个链表相交，第二种情况是两个链表不相交。

情况一：两个链表相交

链表 headA和 headB 的长度分别是 m 和 n。假设链表 headA的不相交部分有 a 个节点，链表 headB 的不相交部分有 b 个节点，两个链表相交的部分有 c 个节点，则有 a+c=m，b+c=n。

如果 a=b，则两个指针会同时到达两个链表相交的节点，此时返回相交的节点；

如果 a≠b，则指针 pA 会遍历完链表 headA，指针 pB会遍历完链表 headB，两个指针不会同时到达链表的尾节点，然后指针 pA 移到链表 headB 的头节点，指针 pB 移到链表 headA 的头节点，然后两个指针继续移动，在指针 pA 移动了 a+c+b 次、指针 pB移动了 b+c+a 次之后，两个指针会同时到达两个链表相交的节点，该节点也是两个指针第一次同时指向的节点，此时返回相交的节点。

情况二：两个链表不相交

链表 headA和 headB 的长度分别是 m 和 n。考虑当 m=n 和 m≠n 时，两个指针分别会如何移动：

如果 m=n，则两个指针会同时到达两个链表的尾节点，然后同时变成空值 null，此时返回 null；

如果 m≠n，则由于两个链表没有公共节点，两个指针也不会同时到达两个链表的尾节点，因此两个指针都会遍历完两个链表，在指针 pA移动了 m+n次、指针 pB 移动了 n+m次之后，两个指针会同时变成空值 null，此时返回 null

/**
 * 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) {
        if(headA==nullptr||headB==nullptr){
            return nullptr;
        }
       ListNode*pa=headA;
       ListNode*pb=headB;
       while(pa!=pb){
        if(pa==nullptr)
        pa=headB;
        else
        pa=pa->next;
        if(pb==nullptr)
        pb=headA;
        else
        pb=pb->next;
       }
       return pa;
       }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

时间复杂度：O(m+n)，其中 m 和 n 是分别是链表 headA 和 }headB 的长度。两个指针同时遍历两个链表，每个指针遍历两个链表各一次。

空间复杂度：O(1)。

23. 206 反转链表

解法一：另外栈空间解决

根据栈的先进后出的特性，将节点顺序入栈，按照其出栈的顺序连接节点，即得到反转后的链表。栈顶节点为头节点，注意栈中最后一个节点需要指向null指针，否则成环。

代码：

/**
 * 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) {
        stacks;
        ListNode* newHead;
        if(head==nullptr||head->next==nullptr)
        return head;
        while(head!=nullptr){
            s.push(head);
            head=head->next;
        }
        newHead=s.top();
        s.pop();
        ListNode* cur=newHead;
        while(!s.empty()){
            cur->next=s.top();
            s.pop();
            cur=cur->next;
        }
        cur->next=nullptr;
        return newHead;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

时间复杂度：O(n)

空间复杂度：O(n)

解法二：迭代【在原来空间上操作，不需要额外的内存空间】

假设链表为 1→2→3→∅，我们想要把它改成 ∅←1←2←3。

在遍历链表时，将当前节点的next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

代码：

/**
 * 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=nullptr;
        ListNode*cur=head;
        while(cur!=nullptr){
            ListNode*tmp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=tmp;
        }
        return pre;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

时间复杂度：O(n)

空间复杂度：O(1)

解法三：递归

见题解：206. 反转链表 - 力扣（LeetCode）

代码：

/**
 * 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) {
        return recur(head,nullptr);
    }
private:
ListNode*recur(ListNode*cur,ListNode*pre){
    if(cur==nullptr)
        return pre;
    ListNode*res=recur(cur->next,cur);
    cur->next=pre;
    return res;    
}   
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

时间复杂度 O(N ： 遍历链表使用线性大小时间。
空间复杂度 O(N) ： 遍历链表的递归深度达到 N ，系统使用 O(N) 大小额外空间。

24. 234 回文链表

解法一：将链表内容复制到数组中，判断数组是否为回文

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
		 if(head==null||head.next==null)
			 return true;
		 	List<Integer>list=new ArrayList<Integer>();
		 	ListNode tmp=head;
		 	while(tmp!=null)
		 	{
		 		list.add(tmp.val);
		 		tmp=tmp.next;
		 	}
		 	int l=0;
		 	int r=list.size()-1;
		 	while(l<r)
		 	{
		 		if(list.get(l)!=list.get(r))
		 			return false;
		 		l++;
		 		r--;
		 	}
		 	return true;
	    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

时间复杂度：O(n)

空间复杂度：O(1)

解法二：快慢指针

思路

避免使用 O(n) 额外空间的方法就是改变输入。

我们可以将链表的后半部分反转（修改链表结构），然后将前半部分和后半部分进行比较。比较完成后我们应该将链表恢复原样。虽然不需要恢复也能通过测试用例，但是使用该函数的人通常不希望链表结构被更改。

该方法虽然可以将空间复杂度降到 O(1)，但是在并发环境下，该方法也有缺点。在并发环境下，函数运行时需要锁定其他线程或进程对链表的访问，因为在函数执行过程中链表会被修改。

算法

整个流程可以分为以下五个步骤：

找到前半部分链表的尾节点。
反转后半部分链表。
判断是否回文。
恢复链表。
返回结果。
执行步骤一，我们可以计算链表节点的数量，然后遍历链表找到前半部分的尾节点。

我们也可以使用快慢指针在一次遍历中找到：慢指针一次走一步，快指针一次走两步，快慢指针同时出发。当快指针移动到链表的末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。

若链表有奇数个节点，则中间的节点应该看作是前半部分。

步骤二可以使用「206. 反转链表」问题中的解决方法来反转链表的后半部分。

步骤三比较两个部分的值，当后半部分到达末尾则比较完成，可以忽略计数情况中的中间节点。

步骤四与步骤二使用的函数相同，再反转一次恢复链表本身。

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == nullptr) {
            return true;
        }

        // 找到前半部分链表的尾节点并反转后半部分链表
        ListNode* firstHalfEnd = endOfFirstHalf(head);
        ListNode* secondHalfStart = reverseList(firstHalfEnd->next);

        // 判断是否回文
        ListNode* p1 = head;
        ListNode* p2 = secondHalfStart;
        bool result = true;
        while (result && p2 != nullptr) {
            if (p1->val != p2->val) {
                result = false;
            }
            p1 = p1->next;
            p2 = p2->next;
        }        

        // 还原链表并返回结果
        firstHalfEnd->next = reverseList(secondHalfStart);
        return result;
    }

    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr != nullptr) {
            ListNode* nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    ListNode* endOfFirstHalf(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast->next != nullptr && fast->next->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/palindrome-linked-list/solutions/457059/hui-wen-lian-biao-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

25. 141 环形链表

解法：快慢指针

本方法需要读者对「Floyd 判圈算法」（又称龟兔赛跑算法）有所了解。

假想「乌龟」和「兔子」在链表上移动，「兔子」跑得快，「乌龟」跑得慢。当「乌龟」和「兔子」从链表上的同一个节点开始移动时，如果该链表中没有环，那么「兔子」将一直处于「乌龟」的前方；如果该链表中有环，那么「兔子」会先于「乌龟」进入环，并且一直在环内移动。等到「乌龟」进入环时，由于「兔子」的速度快，它一定会在某个时刻与乌龟相遇，即套了「乌龟」若干圈。

我们可以根据上述思路来解决本题。具体地，我们定义两个指针，一快一慢。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。

为什么我们要规定初始时慢指针在位置 head，快指针在位置 head.next，而不是两个指针都在位置 head（即与「乌龟」和「兔子」中的叙述相同）？

观察下面的代码，我们使用的是 while 循环，循环条件先于循环体。由于循环条件一定是判断快慢指针是否重合，如果我们将两个指针初始都置于 head，那么 while 循环就不会执行。因此，我们可以假想一个在 head 之前的虚拟节点，慢指针从虚拟节点移动一步到达 head，快指针从虚拟节点移动两步到达 head.next，这样我们就可以使用 while 循环了。

/**
 * 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) {
        if(head==nullptr||head->next==nullptr){
            return false;
        }
        ListNode*slow=head;
        ListNode*fast=head->next;
        cout<<"1"<next==nullptr||fast->next->next==nullptr)
            return false;
            slow=slow->next;
            fast=fast->next->next;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

时间复杂度：O(N)，其中 N 是链表中的节点数。

当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次。

当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动 N 轮。

空间复杂度：O(1)。我们只使用了两个指针的额外空间

26. 142 环形链表||

解法二：双指针

详细动态示例见图解：142. 环形链表 II - 力扣（LeetCode）

双指针的第一次相遇：
设两指针 fast，slow 指向链表头部 head 。
令 fast 每轮走 2 步，slow 每轮走 1 步。
执行以上两步后，可能出现两种结果：

第一种结果： fast 指针走过链表末端，说明链表无环，此时直接返回 null。

如果链表存在环，则双指针一定会相遇。因为每走 1 轮，fast 与 slow 的间距 +1，fast 一定会追上 slow 。

第二种结果： 当fast == slow时， 两指针在环中第一次相遇。下面分析此时 fast 与 slow 走过的步数关系：

设链表共有 a+b，其中 链表头部到链表入口 有 a 个节点（不计链表入口节点）， 链表环 有 b 个节点（这里需要注意，a 和 b 是未知数，例如图解上链表 a=4 , b=5）；设两指针分别走了 f，s 步，则有：

fast 走的步数是 slow 步数的 2倍，即 f=2s；（解析： fast 每轮走 2 步）
fast 比 slow 多走了 n 个环的长度，即 f=s+nb；（ 解析： 双指针都走过 a 步，然后在环内绕圈直到重合，重合时 fast 比 slow 多走 环的长度整数倍 ）。
将以上两式相减得到 f=2nb，s=nb，即 fast 和 slow 指针分别走了 2n，n 个环的周长。

接下来该怎么做呢？

如果让指针从链表头部一直向前走并统计步数k，那么所有 走到链表入口节点时的步数 是：k=a+nb ，即先走 a 步到入口节点，之后每绕 1 圈环（ b 步）都会再次到入口节点。而目前 slow 指针走了 nb步。因此，我们只要想办法让 slow 再走 a 步停下来，就可以到环的入口。

但是我们不知道 a 的值，该怎么办？依然是使用双指针法。考虑构建一个指针，此指针需要有以下性质：此指针和 slow 一起向前走 a 步后，两者在入口节点重合。那么从哪里走到入口节点需要 a 步？答案是链表头节点head。

双指针第二次相遇：
令 fast 重新指向链表头部节点。此时 f=0，s=nb。
slow 和 fast 同时每轮向前走 1 步。
当 fast 指针走到 f=a步时，slow 指针走到 s=a+nb 步。此时两指针重合，并同时指向链表环入口，返回 slow 指向的节点即可。

/**
 * 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) {
        if(head==nullptr||head->next==nullptr)
        return  nullptr;
        ListNode*slow=head;
        ListNode*fast=head;
        while(fast!=nullptr&&fast->next!=nullptr){
            fast=fast->next->next;
            slow=slow->next;
            if(fast==slow)
            break;
        }
        if(fast==nullptr||fast->next==nullptr){
            return nullptr;
        }
        fast=head;
        while(fast!=slow){
            fast=fast->next;
            slow=slow->next;
        }
        return fast;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

时间复杂度：O(N)，其中 N 为链表中节点的数目。在最初判断快慢指针是否相遇时，slow指针走过的距离不会超过链表的总长度；随后寻找入环点时，走过的距离也不会超过链表的总长度。因此，总的执行时间为 O(N)+O(N)=O(N)。

空间复杂度：O(1)。我们只使用了 slow,fast两个指针

27. 21 合并两个有序链表

image-20230917181810793

解法一：迭代

• 对于合并有序链表，可以和合并两个有序数组的相同处理方式，利用first的second指针分别指向list1和list2的头节点

• 同时设置哑节点dumpy，为了避免格外一些特殊情况判断

• 初始化时，cur=dumpy

• 那么则移动first和second指针，将其val值较小的节点连在cur之后，并且将这个指针后移动

  如果两个指针指向的val相同，则两个指针都需要向后移动，并且这两个节点都需要移到cur之后

• 当first或者second有一个为null结束循环，对于非空的指针，直接将cur->next与其相连

代码：

/**
 * 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) {
        ListNode * dump=new ListNode();
        ListNode*first=list1;
        ListNode*second=list2;
        ListNode*cur=dump;
        while(first!=nullptr&&second!=nullptr){
            if(first->valval){
                ListNode*tmp=first;
                first=first->next;
                cur->next=tmp;
                cur=cur->next;
            }
            else if(first->val>second->val){
                ListNode*tmp=second;
                second=second->next;
                cur->next=tmp;
                cur=cur->next;
            }
            else{
                ListNode*tmp1=first;
                first=first->next;
                ListNode*tmp2=second;
                second=second->next;
                cur->next=tmp1;
                cur=cur->next;
                cur->next=tmp2;
                cur=cur->next;
            }
        }
        if(first==nullptr&&second!=nullptr){
            cur->next=second;
        }
        else {
            cur->next=first;
        }
        return dump->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

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

空间复杂度：O(1)

解法二：递归 见官方题解21. 合并两个有序链表 - 力扣（LeetCode）

28. 2 两数相加

解法：

• 首先采用哑节点dumpy，dumpy的next即我们需要返回的头节点，之后由节点相加产生的新节点都连接在dumpy之后。

• 由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。

• 我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。具体而言，如果当前两个链表处相应位置的数字为 n1,n2，进位值为 carry，则它们的和n1+n2+carry；其中，答案链表处相应位置的数字为 $(n1+n2+carry)mod10$，而新的进位值为$\lfloor \frac{n1+n2+\text{carry}}{10}\rfloor$

• 如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 0 。

注意容易错的位置：

如果链表遍历结束后，有carry>0，还需要在答案链表的后面附加一个节点，节点的值为 carry。

代码：

/**
 * 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) {
         ListNode*dumpy=new ListNode();
         ListNode*cur;
         cur=dumpy;
         int carry=0;
         while(l1||l2){
             int n1=l1?l1->val:0;
             int n2=l2?l2->val:0;
             int sum=n1+n2+carry;
             carry=sum/10;
             sum=sum%10;
             ListNode*node=new ListNode(sum);
             cur->next=node;
             cur=cur->next;
             if(l1)
             l1=l1->next;
             if(l2)
             l2=l2->next;
         }
        if(carry>0){
            cur->next=new ListNode(carry);
        }
        return dumpy->next;  
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

时间复杂度：O(max(m,n))其中m和n分别为两个链表的长度。

空间复杂度：O(1)

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

解法一：双指针（使用）

• 引入虚拟头节点dumpy，以及快慢指针【也常用的判断链表有环的场景】first,second，first领先second指针n个节点
• 那么当first指针的next为null的时候，second正好指在待删除节点的前驱节点，按照链表删除节点的逻辑进行删除即可

代码：

/**
 * 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);
        ListNode *first,*second;
        first=dummy;
        second=dummy;
        for(int i=0;inext;
        }
        while(first->next!=NULL){
            first=first->next;
            second=second->next;
        }
        ListNode * tmp=second->next;
        second->next=tmp->next;
        delete tmp;
        ListNode*ans=dummy->next;
        delete dummy;
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

时间复杂度：o(n)

空间复制度：o(1)

解法二：计算链表长度

最容易的方法：从头节点开始对链表进行一次遍历，得到链表的长度L。然后就能得到要删除的节点的位置是L-n+1。

删除链表的其中的一个节点的话,最经常会添加一个虚拟头节点。这样会使得删除的节点不管是否为头节点的逻辑相同。

解法三：用栈

我们也可以在遍历链表的同时将所有节点依次入栈。根据栈「先进后出」的原则，我们弹出栈的第 nnn 个节点就是需要删除的节点，并且目前栈顶的节点就是待删除节点的前驱节点。

解法二和三见：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

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

解法一：迭代

创建哑节点dummpy,dummpy->next-head.cur表示当前带大的节点，初始化的时候cur=dummpy，每次需要交换其后的两个节点。如果cur的候选没有节点或者只有一个节点，结束交换。否则更新其之后的指针关系。

代码：

/**
 * 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 *dummpy=new ListNode();
        dummpy->next=head;    
        ListNode*cur=dummpy;
        ListNode*tmp1,*tmp2;
        while(cur->next!=nullptr&&cur->next->next!=nullptr){
            tmp1=cur->next;
            tmp2=cur->next->next;
            cur->next=tmp2;
            tmp1->next=tmp2->next;
            tmp2->next=tmp1;
            cur=tmp1;
        }
        return dummpy->next;
    }

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

• 时间复杂度：O(n)，其中 n 是链表的节点数量。需要对每个节点进行更新指针的操作。
• 空间复杂度：O(1)

解法二：递归

可以通过递归的方式实现两两交换链表中的节点。

递归的终止条件是链表中没有节点，或者链表中只有一个节点，此时无法进行交换。

如果链表中至少有两个节点，则在两两交换链表中的节点之后，原始链表的头节点变成新的链表的第二个节点，原始链表的第二个节点变成新的链表的头节点。链表中的其余节点的两两交换可以递归地实现。在对链表中的其余节点递归地两两交换之后，更新节点之间的指针关系，即可完成整个链表的两两交换。

用 head 表示原始链表的头节点，新的链表的第二个节点，用 newHead 表示新的链表的头节点，原始链表的第二个节点，则原始链表中的其余节点的头节点是 newHead.next。令 head.next = swapPairs(newHead.next)，表示将其余节点进行两两交换，交换后的新的头节点为 head 的下一个节点。然后令 newHead.next = head，即完成了所有节点的交换。最后返回新的链表的头节点 newHead。

见官方题解：24. 两两交换链表中的节点 - 力扣（LeetCode）

31. 25 K个一组翻转链表

解法：本题需要对局部区间链表进行翻转，主要抓住四个关键节点位置：

• reversePre：反转区间的前一个节点；
• reverseHead：反转区间的头节点；
• reverseTail：反转区间的尾节点；
• reverseNext：反转区间的下一个节点；

首先，引入dumpy节点，dumpy->next=head;

初始化:

• rPre=dumpy;
• rHead=dumpy->next;
• rTail=rPre;

然后移动rTail指针k次，移动的过程中判断是否rTail指针为空，若为空，则直接返回dumpy->next为翻转链表的头节点。

移动k次之后，我们翻转【rHead,rTail】之间的链表。

反转区间链表的过程：

• pre=rHead;

• cur=rHead->next;

• 注意cur的循环退出条件为当前rTail的next节点，因为反转过程中rTail的next节点会改变，可能造成问题。

  因此，while循环前，需要用rNext记录当前rTail的next节点。

• 翻转链表的过程如就是将cur指向pre的过程，然后移动pre和cur指针。

区间循环结束之后，此时的cur指针恰好为rNext位置，pre的位置是当前区间的头指针即rTail，

此时将rPre连接pre,rHead连接cur;

然后更新rTail和rPre指针的位置为rHead，rHead的位置为rNext

代码：

class solution75 {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode *dumpy=new ListNode();
        dumpy->next=head;
        ListNode*rPre=dumpy;
        ListNode*rHead=dumpy->next;
        ListNode*rTail=dumpy;
        while(rTail!=nullptr){
            for(int i=0;inext;
                if(rTail==nullptr)
                {
                    return dumpy->next;
                }
            }
            //翻转rHead,rtail的链表
            ListNode*pre=rHead;
            ListNode*cur=rHead->next;
            ListNode*rNext=rTail->next;
            while(cur!=rNext){
                ListNode* tmp=cur->next;
                cur->next=pre;
                pre=cur;
                cur=tmp;
            }
            rPre->next=pre;
            rHead->next=cur;
            rTail=rHead;
            rPre=rHead;
            rHead=cur;
        }
        return dumpy->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

​

时间复杂度：O(n)，其中 n 为链表的长度。

空间复杂度：O(1，我们只需要建立常数个变量。

32. 138 随机链表的复制

解法1:哈希表

因为单链表的复制比较简单，只需要扫描一遍。但是这个链表多了一个Random指针，有可能顺序复制的时候，Radom指针指向的位置的节点还未创建。因此，利用哈希表的查询特点，考虑构建 原链表节点 和 新链表对应节点 的键值对映射关系，提前创建好所有的复制节点，再遍历构建新链表各节点的 next 和 random 引用指向即可。

算法流程：

• 若头节点 head 为空节点，直接返回 lnull 。

• 初始化： 哈希表 map,节点 cur 指向头节点。

• 复制链表：

  • 建立新节点，并向 map添加键值对 (原 cur 节点, 新 cur 节点【为新建节点】）。

  • cur 遍历至原链表下一节点。

• 构建新链表的引用指向：

  • 构建新节点的 next 和 random 引用指向。

  • cur 遍历至原链表下一节点。

• 返回值： 新链表的头节点。

/*
// 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) {
      if(head==nullptr)
      return nullptr;  
       Node*cur=head;
       Node*copyhead=new Node(cur->val);
       unordered_mapmap;
       map[cur]=copyhead;
       cur=cur->next;
       while(cur!=nullptr){
           map[cur]=new Node(cur->val);
           cur=cur->next;
       }
       cur=head;
       while(cur!=nullptr){
           map[cur]->next=map[cur->next];
           map[cur]->random=map[cur->random];
           cur=cur->next;
       }
       return copyhead;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

时间复杂度 O(N) ： 两轮遍历链表，O(N) 时间。
空间复杂度 O(N) ： 哈希表 map使用线性大小的额外空间。

解法二：递归+哈希表

本题要求我们对一个特殊的链表进行深拷贝。如果是普通链表，我们可以直接按照遍历的顺序创建链表节点。而本题中因为随机指针的存在，当我们拷贝节点时，「当前节点的随机指针指向的节点」可能还没创建，因此我们需要变换思路。一个可行方案是，我们利用回溯的方式，让每个节点的拷贝操作相互独立。对于当前节点，我们首先要进行拷贝，然后我们进行「当前节点的后继节点」和「当前节点的随机指针指向的节点」拷贝，拷贝完成后将创建的新节点的指针返回，即可完成当前节点的两指针的赋值。

具体地，我们用哈希表记录每一个节点对应新节点的创建情况。遍历该链表的过程中，我们检查「当前节点的后继节点」和「当前节点的随机指针指向的节点」的创建情况。如果这两个节点中的任何一个节点的新节点没有被创建，我们都立刻递归地进行创建。当我们拷贝完成，回溯到当前层时，我们即可完成当前节点的指针赋值。注意一个节点可能被多个其他节点指向，因此我们可能递归地多次尝试拷贝某个节点，为了防止重复拷贝，我们需要首先检查当前节点是否被拷贝过，如果已经拷贝过，我们可以直接从哈希表中取出拷贝后的节点的指针并返回即可。

见官方题解：138. 随机链表的复制 - 力扣（LeetCode）

解法三：迭代+节点拆分【可以将空间复杂度降为O(1)】
见：138. 随机链表的复制 - 力扣（LeetCode）

33. 148 排序链表

解法一：利用插入排序，[147. 对链表进行插入排序 ](###14. 147 对链表进行插入排序) 超出时间限制

解法二：归并排序+递归
题目要求时间空间复杂度分别为 O(nlogn) 和 O(1)，根据时间复杂度我们自然想到二分法，从而联想到归并排序；

对数组做归并排序的空间复杂度为 O(n)，分别由新开辟数组 O(n) 和递归函数调用 O(logn)组成，而根据链表特性：

数组额外空间：链表可以通过修改引用来更改节点顺序，无需像数组一样开辟额外空间；
递归额外空间：递归调用函数将带来 O(logn)的空间复杂度，因此若希望达到 O(1) 空间复杂度，则不能使用递归。
通过递归实现链表归并排序，有以下两个环节：

分割 cut 环节： 找到当前链表 中点，并从 中点 将链表断开（以便在下次递归 cut 时，链表片段拥有正确边界）；
我们使用 fast,slow 快慢双指针法，奇数个节点找到中点，偶数个节点找到中心左边的节点。
找到中点 slow 后，执行 slow.next = None 将链表切断。
递归分割时，输入当前链表左端点 head 和中心节点 slow 的下一个节点 tmp(因为链表是从 slow 切断的)。
cut 递归终止条件： 当 head.next == None 时，说明只有一个节点了，直接返回此节点。
合并 merge 环节： 将两个排序链表合并，转化为一个排序链表。
双指针法合并，建立辅助 ListNode* h 作为头部。
设置两指针 left, right 分别指向两链表头部，比较两指针处节点值大小，由小到大加入合并链表头部，指针交替前进，直至添加完两个链表。
返回辅助ListNode h 作为头部的下个节点 h.next。
时间复杂度 O(l + r)，l, r 分别代表两个链表长度。
当题目输入的 head == None 时，直接返回 None。

/**
 * 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==nullptr||head->next==nullptr){
            return head;
        }
        ListNode* fast=head->next;
        ListNode* slow=head;
        while(fast!=nullptr&&fast->next!=nullptr){
            slow=slow->next;
            fast=fast->next->next;
        }
        ListNode*tmp=slow->next;
        slow->next=nullptr;
        ListNode* left=sortList(head);
        ListNode* right=sortList(tmp);
        ListNode* h=new ListNode(0);
        ListNode* res=h;
        while(left!=nullptr&&right!=nullptr){
            if(left->valval){
                h->next=left;
                left=left->next;
            }
            else{
                h->next=right;
                right=right->next;
            }
            h=h->next;
        }
        h->next=left!=nullptr?left:right;
        return res->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

时间复杂度：O（nlogn）

空间复杂度:O（1）

34. 合并K个升序链表

解法一：分治合并
思路

考虑优化方法一，用分治的方法进行合并。

将 k 个链表配对并将同一对中的链表合并；
第一轮合并以后， kkk 个链表被合并成了 $\frac{k}{2}$ 个链表，平均长度为 $\frac{2n}{k}$，然后是 $\frac{k}{4}$ 个链表， $\frac{k}{8}$ 个链表等等；
重复这一过程，直到我们得到了最终的有序链表。

/**
 * 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) {
        ListNode * dump=new ListNode();
        ListNode*first=list1;
        ListNode*second=list2;
        ListNode*cur=dump;
        while(first!=nullptr&&second!=nullptr){
            if(first->valval){
                ListNode*tmp=first;
                first=first->next;
                cur->next=tmp;
                cur=cur->next;
            }
            else if(first->val>second->val){
                ListNode*tmp=second;
                second=second->next;
                cur->next=tmp;
                cur=cur->next;
            }
            else{
                ListNode*tmp1=first;
                first=first->next;
                ListNode*tmp2=second;
                second=second->next;
                cur->next=tmp1;
                cur=cur->next;
                cur->next=tmp2;
                cur=cur->next;
            }
        }
        if(first==nullptr&&second!=nullptr){
            cur->next=second;
        }
        else {
            cur->next=first;
        }
        return dump->next;
    }
    ListNode*merge(vector& lists,int l,int r){
        if(l==r)
        return lists[l];
        if(l>r)
        return nullptr;
        int mid=(l+r)/2;
        return mergeTwoLists(merge(lists,l,mid),merge(lists,mid+1,r));
    }
    ListNode* mergeKLists(vector& lists) {
       return merge(lists,0,lists.size()-1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

时间复杂度：考虑递归「向上回升」的过程——第一轮合并 $\frac{k}{2}$ 组链表，每一组的时间代价是 O(2n)；第二轮合并 $\frac{k}{4}$ 组链表，每一组的时间代价是 O(4n)…所以总的时间代价是 $O({\sum }_{i=1}^{\infty }\frac{k}{2^i}\times 2^{i}n)=O(kn\times \log k)$，故渐进时间复杂度为 $O(kn\times \log k)$。
空间复杂度：递归会使用到 $O(\log k)$ 空间代价的栈空间。

解法二：顺序合并

解法三：优先队列合并

见：23. 合并 K 个升序链表 - 力扣（LeetCode）

35. 146 LRU缓存

解法一：哈希表+双向链表

算法

LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。

双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。

哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。

这样以来，我们首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在 O(1)的时间内完成 get 或者 put 操作。具体的方法如下：

对于 get 操作，首先判断 key 是否存在：

如果 key 不存在，则返回 −1；

如果 key 存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。

对于 put 操作，首先判断 key 是否存在：

如果 key 不存在，使用 key 和 value 创建一个新的节点，在双向链表的头部添加该节点，并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；

如果 key 存在，则与 get 操作类似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部。

上述各项操作中，访问哈希表的时间复杂度为 O(1)O(1)O(1)，在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也为 O(1)。而将一个节点移到双向链表的头部，可以分成「删除该节点」和「在双向链表的头部添加节点」两步操作，都可以在 O(1) 时间内完成。

struct DlinkedNode{
    int key,value;
    DlinkedNode* prev;
    DlinkedNode* next;
    DlinkedNode():key(0),value(0),prev(nullptr),next(nullptr){}
    DlinkedNode(int _key,int _value):key(_key),value(_value),prev(nullptr),next(nullptr){}
};

class LRUCache {
private:
unordered_mapcache;    
DlinkedNode*head;
DlinkedNode*tail;
int size;
int capacity;
public:
    LRUCache(int capacity) {
        this->capacity=capacity;
        this->size=0;
        head=new DlinkedNode();
        tail=new DlinkedNode();
        head->next=tail;
        tail->prev=head;
    }
    
    int get(int key) {
        if(!cache.count(key))
        return -1;
        DlinkedNode* node=cache[key];
        moveToHead(node);
        return node->value;
       
    }
    
    void put(int key, int value) {
        if(cache.count(key)){
            DlinkedNode* node=cache[key];
            moveToHead(node);
            node->value=value;
        }
        else{
            size++;
            DlinkedNode*node=new DlinkedNode(key,value);
            cache[key]=node;

            if(size>capacity){
                DlinkedNode*tmp=tail->prev;
                removeNode(tail->prev);
                cache.erase(tmp->key);
                addToHead(node);
                size--;
                delete tmp;
            }
            else{
            addToHead(node);
            }
            
        }
    }
    void removeNode(DlinkedNode*node){
        node->prev->next=node->next;
        node->next->prev=node->prev;
    }
    void moveToHead(DlinkedNode*node){
        removeNode(node);
        addToHead(node);
    } 
    void addToHead(DlinkedNode*node){
        node->next=head->next;
        head->next->prev=node;
        head->next=node;
        node->prev=head;
    }

};

/**
 * 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);
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

时间复杂度：对于 put 和 get 都是O(1)。

空间复杂度：O(capacity)，因为哈希表和双向链表最多存储 capacity+1 个元素。

二叉树

36. 94 二叉树的中序遍历

解法一：递归

首先我们需要了解什么是二叉树的中序遍历：按照访问左子树——根节点——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。

定义 inorder(root) 表示当前遍历到 root 节点的答案，那么按照定义，我们只要递归调用 inorder(root.left) 来遍历 root 节点的左子树，然后将 root节点的值加入答案，再递归调用inorder(root.right) 来遍历 root 节点的右子树即可，递归终止的条件为碰到空节点。

/**
 * 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 inorderTraversal(TreeNode* root) {
        vectorresult;
        inorder(root,result);
        return result;        
    }
    void inorder(TreeNode*root,vector&result){
    if(root==nullptr)
        {
            return;
        }
      inorder(root->left,result);
      result.emplace_back(root->val);
      inorder(root->right,result);  
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。

空间复杂度：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 inorderTraversal(TreeNode* root) {
     vectorres;
     stackstk;
     while(root!=nullptr||!stk.empty()){
        while(root!=nullptr){
        stk.push(root);
        root=root->left;
        }    
        root=stk.top();
        stk.pop();
        res.push_back(root->val);
        root=root->right;
     }
     return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

时间复杂度：O(n)，其中 n 为二叉树节点的个数。二叉树的遍历中每个节点会被访问一次且只会被访问一次。

空间复杂度：O(n)。空间复杂度取决于栈深度，而栈深度在二叉树为一条链的情况下会达到 O(n)的级别。

解法三：Morris 中序遍历

见：94. 二叉树的中序遍历 - 力扣（LeetCode）

37. 104 二叉树的最大深度

解法一：DFS(改造后序遍历)

树的后序遍历 / 深度优先搜索往往利用 递归 或 栈 实现，本文使用递归实现。

关键点： 此树的深度和其左（右）子树的深度之间的关系。显然，此树的深度 等于 左子树的深度 与 右子树的深度中的 最大值 +1 。

算法解析：
终止条件： 当 root 为空，说明已越过叶节点，因此返回 深度 0 。
递推工作： 本质上是对树做后序遍历。
计算节点 root 的 左子树的深度 ，即调用 maxDepth(root.left)。
计算节点 root 的 右子树的深度 ，即调用 maxDepth(root.right)。
返回值： 返回 此树的深度 ，即 max(maxDepth(root.left), maxDepth(root.right)) + 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 maxDepth(TreeNode* root) {
        return maxPostOrder(root);
    }
    int maxPostOrder(TreeNode*root){
        if(root==nullptr){
            return 0;
        }
        return max(maxPostOrder(root->left),maxPostOrder(root->right))+1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

复杂度分析：
时间复杂度 O(N) ： N 为树的节点数量，计算树的深度需要遍历所有节点。
空间复杂度 O(N) ： 最差情况下（当树退化为链表时），递归深度可达到 N 。

解法二：BFS

树的层序遍历 / 广度优先搜索往往利用 队列 实现。

关键点： 每遍历一层，则计数器 +1 ，直到遍历完成，则可得到树的深度。

算法解析：
特例处理： 当 root 为空，直接返回 深度 0 。
初始化： 队列 queue （加入根节点 root ），计数器 res = 0。
循环遍历： 当 queue 为空时跳出。
初始化一个空列表 tmp ，用于临时存储下一层节点。
遍历队列： 遍历 queue 中的各节点 node ，并将其左子节点和右子节点加入 tmp。
更新队列： 执行 queue = tmp ，将下一层节点赋值给 queue。
统计层数： 执行 res += 1 ，代表层数加 1。
返回值： 返回 res 即可。

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        queue Q;
        Q.push(root);
        int ans = 0;
        while (!Q.empty()) {
            int sz = Q.size();
            while (sz > 0) {
                TreeNode* node = Q.front();
              	Q.pop();
                if (node->left) Q.push(node->left);
                if (node->right) Q.push(node->right);
                sz -= 1;
            }
            ans += 1;
        } 
        return ans;
    }
};

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

时间复杂度：O(N)，其中 N 为二叉树节点的数目。我们会遍历二叉树中的每一个节点，对每个节点而言，我们在常数时间内交换其两棵子树。

空间复杂度：O(N)。使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，即 O(log⁡N)。而在最坏情况下，树形成链状，空间复杂度为 O(N)。

38. 226 翻转二叉树

解法一：经典递归
思路与算法

这是一道很经典的二叉树问题。显然，我们从根节点开始，递归地对树进行遍历，并从叶子节点先开始翻转。如果当前遍历到的节点 root 的左右两棵子树都已经翻转，那么我们只需要交换两棵子树的位置，即可完成以 root 为根节点的整棵子树的翻转。

/**
 * 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==nullptr){
            return root;
        }
        TreeNode*left=invertTree(root->left);
        TreeNode*right=invertTree(root->right);
        root->left=right;
        root->right=left;
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

时间复杂度：O(N)，其中 N 为二叉树节点的数目。我们会遍历二叉树中的每一个节点，对每个节点而言，我们在常数时间内交换其两棵子树。

空间复杂度：O(N)。使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，即 O(log⁡N)。而在最坏情况下，树形成链状，空间复杂度为 O(N)。

39. 101 对称二叉树

解法一：递归

对称二叉树定义： 对于树中 任意两个对称节点 L 和 R ，一定有：

L.val = R.val ：即此两对称节点值相等。
L.left.val = R.right.val ：即 L 的 左子节点 和 R 的 右子节点 对称。
L.right.val = R.left.val ：即 L 的 右子节点 和 R 的 左子节点 对称。
根据以上规律，考虑从顶至底递归，判断每对左右节点是否对称，从而判断树是否为对称二叉树。

算法流程：
函数 isSymmetric(root) ：

特例处理： 若根节点 root 为空，则直接返回 true 。
返回值： 即 recur(root.left, root.right) ;
函数 recur(L, R) ：

终止条件：
当 L 和 R 同时越过叶节点： 此树从顶至底的节点都对称，因此返回 true 。
当 L 或 R 中只有一个越过叶节点： 此树不对称，因此返回 false 。
当节点 L 值 ≠ 节点 R 值： 此树不对称，因此返回 false。
递推工作：
判断两节点 L.left 和 R.right 是否对称，即 recur(L.left, R.right) 。
判断两节点 L.right 和 R.left 是否对称，即 recur(L.right, R.left) 。
返回值： 两对节点都对称时，才是对称树，因此用与逻辑符 && 连接。

/**
 * 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==nullptr)
        {
            return true;
        }
        return recur(root->left,root->right);
    
    }
    bool recur(TreeNode*L,TreeNode*R){
        if(L==nullptr&& R==nullptr)return true;
        if(L==nullptr||R==nullptr||L->val!=R->val)return false;
        return recur(L->left,R->right)&&recur(L->right,R->left);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

时间复杂度：这里遍历了这棵树，渐进时间复杂度为 O(n)。
空间复杂度：这里的空间复杂度和递归使用的栈空间有关，这里递归层数不超过 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) {
        if(root==nullptr)
        return true;
        queuequeue;
        queue.push(root->left);
        queue.push(root->right);
        TreeNode*left;
        TreeNode*right;
        while(!queue.empty()){
            right=queue.front();
            queue.pop();
            left=queue.front();
            queue.pop();
            if(!left&&!right)
                continue;
            if((!left)||(!right)||(left->val!=right->val))
                return false;
            queue.push(left->right);
            queue.push(right->left);
            queue.push(left->left);
              queue.push(right->right);     
        }
        return true;  
    }
    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

时间复杂度：O(n)，同「方法一」。
空间复杂度：这里需要用一个队列来维护节点，每个节点最多进队一次，出队一次，队列中最多不会超过n 个点，故渐进空间复杂度为 O(n)。

40. 543 二叉树的直径

解法一：递归

官方的题解有点绕，简单来说，如果是以根节点为中间节点的直径，就是根节点的左深度和右深度相加，因为叶子结点的深度定义为1；这里的直径说的是边的个数，以示例1为例子，因为左子树的深度为2，右子树的深度为1；其实左子树的2已经包含了叶子结点到根节点的边数，右子树的深度也包含了其到根节点的边数，总的直径为L+R。

但是注意到，最长的路径不一定是经过根节点的，有可能没经过，因此在递归的过程中，需要比较每个节点的左子树的深度和右子树的深度之和。

代码：

/**
 * 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 {
int ans;    
public:
    int diameterOfBinaryTree(TreeNode* root) {
       ans=0;
       dfs(root);
       return ans;
    }
    int dfs(TreeNode*root){
        if(root==nullptr)
        return 0;
        int L=dfs(root->left);//以左子树为根的子树的深度
        int R=dfs(root->right);//右儿子为根的子树的深度
        ans=max(L+R,ans);//将每个节点最大直径（左子树+右子树的深度）当前最大值并取最大值
        return max(L,R)+1;//返回该节点为根的子树的深度
    }

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

时间复杂度：O(N)，其中 N 为二叉树的节点数，即遍历一棵二叉树的时间复杂度，每个结点只被访问一次。

空间复杂度：O(Height)，其中 Height 为二叉树的高度。由于递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，而递归的深度显然为二叉树的高度，并且每次递归调用的函数里又只用了常数个变量，所以所需空间复杂度为 O(Height)

41. 102 二叉树的层序遍历

解法：BFS层序遍历

I. 按层打印： 题目要求的二叉树的 从上至下 打印（即按层打印），又称为二叉树的 广度优先搜索（BFS）。BFS 通常借助 队列 的先入先出特性来实现。

II. 每层打印到一行： 将本层全部节点打印到一行，并将下一层全部节点加入队列，以此类推，即可分为多行打印。

算法流程：
特例处理： 当根节点为空，则返回空列表 [] 。
初始化： 打印结果列表 res = [] ，包含根节点的队列 queue = [root] 。
BFS 循环： 当队列 queue 为空时跳出。
新建一个临时列表 tmpres ，用于存储当前层打印结果。
当前层打印循环： 循环次数为当前层节点数（即队列 queue 长度）。
出队： 队首元素出队，记为 node。
打印： 将 node.val 添加至 tmp 尾部。
添加子节点： 若 node 的左（右）子节点不为空，则将左（右）子节点加入队列 queue 。
将当前层结果 tmpres 添加入 res 。

/**
 * 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> levelOrder(TreeNode* root) {
        vector>res;
        if(root==nullptr)
        return res;
        queueque;
        que.push(root);
        while(!que.empty()){
            int sz=que.size();
            vectortmpres;
            while(sz){
                TreeNode* tmp=que.front();
                tmpres.emplace_back(tmp->val);
                que.pop();
                sz--;
                if(tmp->left)
                que.push(tmp->left);
                if(tmp->right)
                que.push(tmp->right);
            }
            res.push_back(tmpres);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

时间复杂度 O(N) ： N 为二叉树的节点数量，即 BFS 需循环 N 次。
空间复杂度 O(N) ： 最差情况下，即当树为平衡二叉树时，最多有 N/2个树节点同时在 queue 中，使用 O(N) 大小的额外空间。

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

解法：解释见官方题解

前言
二叉搜索树的中序遍历是升序序列，题目给定的数组是按照升序排序的有序数组，因此可以确保数组是二叉搜索树的中序遍历序列。

给定二叉搜索树的中序遍历，是否可以唯一地确定二叉搜索树？答案是否定的。如果没有要求二叉搜索树的高度平衡，则任何一个数字都可以作为二叉搜索树的根节点，因此可能的二叉搜索树有多个。

如果增加一个限制条件，即要求二叉搜索树的高度平衡，是否可以唯一地确定二叉搜索树？答案仍然是否定的。

直观地看，我们可以选择中间数字作为二叉搜索树的根节点，这样分给左右子树的数字个数相同或只相差 1，可以使得树保持平衡。如果数组长度是奇数，则根节点的选择是唯一的，如果数组长度是偶数，则可以选择中间位置左边的数字作为根节点或者选择中间位置右边的数字作为根节点，选择不同的数字作为根节点则创建的平衡二叉搜索树也是不同的。

当然，这只是我们直观的想法，为什么这么建树一定能保证是「平衡」的呢？这里可以参考「1382. 将二叉搜索树变平衡」，这两道题的构造方法完全相同，这种方法是正确的，1382 题解中给出了这个方法的正确性证明：1382 官方题解，感兴趣的同学可以戳进去参考。

递归的基准情形是平衡二叉搜索树不包含任何数字，此时平衡二叉搜索树为空。

在给定中序遍历序列数组的情况下，每一个子树中的数字在数组中一定是连续的，因此可以通过数组下标范围确定子树包含的数字，下标范围记为 [left,right]。对于整个中序遍历序列，下标范围从 left=0 到 right=nums.length−1。当 left>right 时，平衡二叉搜索树为空。

以下三种方法中，方法一总是选择中间位置左边的数字作为根节点，方法二总是选择中间位置右边的数字作为根节点，方法三是方法一和方法二的结合，选择任意一个中间位置数字作为根节点。

解法一：中序遍历，总是选择中间位置左边的数字作为根节点
选择中间位置左边的数字作为根节点，则根节点的下标为 mid=(left+right)/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& nums) {
        return dfsTree(nums,0,nums.size()-1);
    }
    TreeNode* dfsTree(const vector&nums,int left,int right){
        if(left>right)
        return nullptr;
        //总是选择中间位置左边的节点作为根接待您
        int mid=(left+right)/2;
        TreeNode* root=new TreeNode(nums[mid]);
        root->left=dfsTree(nums,left,mid-1);
        root->right=dfsTree(nums,mid+1,right);
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

时间复杂度：O(n)，其中 n 是数组的长度。每个数字只访问一次。

空间复杂度：O(log⁡n)，其中 n 是数组的长度。空间复杂度不考虑返回值，因此空间复杂度主要取决于递归栈的深度，递归栈的深度是 O(log⁡n)

43. 98 验证二叉搜索树

解法一：二叉搜索树中序遍历递增，首先递归实现中序遍历，判断数组是否递增，如果递增则是二叉搜索树，否则不是

代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
public:
    vectorsortNum;
    bool isValidBST(TreeNode* root) {
       Inorder(root);
       for(int i=0;i=sortNum[i+1])
            return false;
       }
       return true;
    }
    void Inorder(TreeNode*root){
        if(root==nullptr)
        return;
        Inorder(root->left);
        sortNum.emplace_back(root->val);
        Inorder(root->right);
    }
};


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

时间复杂度：O(n)

空间复杂度：O(n)

解法二：不使用数组，使用中序遍历的非递归算法

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack stack;
        long long inorder = (long long)INT_MIN - 1;

        while (!stack.empty() || root != nullptr) {
            while (root != nullptr) {
                stack.push(root);
                root = root -> left;
            }
            root = stack.top();
            stack.pop();
            // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            if (root -> val <= inorder) {
                return false;
            }
            inorder = root -> val;
            root = root -> right;
        }
        return true;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/validate-binary-search-tree/solutions/230256/yan-zheng-er-cha-sou-suo-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

解法二：递归

要解决这道题首先我们要了解二叉搜索树有什么性质可以给我们利用，由题目给出的信息我们可以知道：如果该二叉树的左子树不为空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；它的左右子树也为二叉搜索树。

这启示我们设计一个递归函数 helper(root, lower, upper) 来递归判断，函数表示考虑以 root 为根的子树，判断子树中所有节点的值是否都在 (l,r)的范围内（注意是开区间）。如果 root 节点的值 val 不在 (l,r) 的范围内说明不满足条件直接返回，否则我们要继续递归调用检查它的左右子树是否满足，如果都满足才说明这是一棵二叉搜索树。

那么根据二叉搜索树的性质，在递归调用左子树时，我们需要把上界 upper 改为 root.val，即调用 helper(root.left, lower, root.val)，因为左子树里所有节点的值均小于它的根节点的值。同理递归调用右子树时，我们需要把下界 lower 改为 root.val，即调用 helper(root.right, root.val, upper)。

函数递归调用的入口为 helper(root, -inf, +inf)， inf 表示一个无穷大的值。

class Solution {
public:
    bool helper(TreeNode* root, long long lower, long long upper) {
        if (root == nullptr) {
            return true;
        }
        if (root -> val <= lower || root -> val >= upper) {
            return false;
        }
        return helper(root -> left, lower, root -> val) && helper(root -> right, root -> val, upper);
    }
    bool isValidBST(TreeNode* root) {
        return helper(root, LONG_MIN, LONG_MAX);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时间复杂度：O(n)，其中 n 为二叉树的节点个数。在递归调用的时候二叉树的每个节点最多被访问一次，因此时间复杂度为 O(n)。

空间复杂度：O(n)，其中 n 为二叉树的节点个数。递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，即二叉树的高度。最坏情况下二叉树为一条链，树的高度为 n ，递归最深达到 n 层，故最坏情况下空间复杂度为 O(n) 。

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

解法一：普通解法，得到中序遍历的数组，返回其中的第k个

/**
 * 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) {
        vectorresult;
        preOrder(root,result);
        return result[k-1];
    }
    void preOrder(TreeNode*root,vector&result){
        if(root==nullptr)
        return;
        preOrder(root->left,result);
        result.emplace_back(root->val);
        preOrder(root->right,result);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

时间复杂度：O(N)

空间复杂度：O(N)

解法1.2:中序遍历的迭代方式，只需要计数到第k个，不需要遍历所有的元素

/**
 * 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) {
        stackstack;
        while(root!=nullptr||stack.size()>0){
            while(root!=nullptr){
                stack.push(root);
                root=root->left;
            }
            root=stack.top();
            stack.pop();
            --k;
            if(k==0){
                break;
            }
            root=root->right;
        }
        return root->val;
    }
    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

时间复杂度：O(H+k)，其中 H 是树的高度。在开始遍历之前，我们需要 O(H) 到达叶结点。当树是平衡树时，时间复杂度取得最小值 O(log⁡N+k；当树是线性树（树中每个结点都只有一个子结点或没有子结点）时，时间复杂度取得最大值 O(N+k)。

空间复杂度：O(H)，栈中最多需要存储 H 个元素。当树是平衡树时，空间复杂度取得最小值 O(log⁡N)；当树是线性树时，空间复杂度取得最大值 O(N)

解法二：如果你需要频繁地查找第 k 小的值，你将如何优化算法？

在方法一中，我们之所以需要中序遍历前 k 个元素，是因为我们不知道子树的结点数量，不得不通过遍历子树的方式来获知。

因此，我们可以记录下以每个结点为根结点的子树的结点数，并在查找第 k 小的值时，使用如下方法搜索：

令 node 等于根结点，开始搜索。

对当前结点 node 进行如下操作：

如果 node 的左子树的结点数left 小于 k−1，则第 k 小的元素一定在node 的右子树中，令node 等于其的右子结点，k 等于 k−left−1，并继续搜索；
如果 node 的左子树的结点数 left 等于 k−1，则第 k小的元素即为 node ，结束搜索并返回 node 即可；
如果 node 的左子树的结点数 left 大于 k−1，则第 k 小的元素一定在 node 的左子树中，令node 等于其左子结点，并继续搜索。

class MyBst {
public:
    MyBst(TreeNode *root) {
        this->root = root;
        countNodeNum(root);
    }

    // 返回二叉搜索树中第k小的元素
    int kthSmallest(int k) {
        TreeNode *node = root;
        while (node != nullptr) {
            int left = getNodeNum(node->left);
            if (left < k - 1) {
                node = node->right;
                k -= left + 1;
            } else if (left == k - 1) {
                break;
            } else {
                node = node->left;
            }
        }
        return node->val;
    }

private:
    TreeNode *root;
    unordered_map nodeNum;

    // 统计以node为根结点的子树的结点数
    int countNodeNum(TreeNode * node) {
        if (node == nullptr) {
            return 0;
        }
        nodeNum[node] = 1 + countNodeNum(node->left) + countNodeNum(node->right);
        return nodeNum[node];
    }

    // 获取以node为根结点的子树的结点数
    int getNodeNum(TreeNode * node) {
        if (node != nullptr && nodeNum.count(node)) {
            return nodeNum[node];
        }else{
            return 0;
        }
    }
};

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        MyBst bst(root);
        return bst.kthSmallest(k);
    }
};

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

45. 199 二叉树的右视图

解法：二叉树的层次遍历

对二叉树进行层次遍历，那么对于每层来说，最右边的结点一定是最后被遍历到的。二叉树的层次遍历可以用广度优先搜索实现。

算法

执行广度优先搜索，左结点排在右结点之前，这样，我们对每一层都从左到右访问。因此，只保留每个深度最后访问的结点，我们就可以在遍历完整棵树后得到每个深度最右的结点。层次队列一般用队列实现，就先记录每层的节点个数，然后将每层的节点的左右节点入队列，因此每次最后pop的节点是每层最右边的节点。

/**
 * 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 rightSideView(TreeNode* root) {
        if(root==nullptr)
        return vector{};
        queueque;
        que.push(root);
        vectorresult;
        while(!que.empty()){
            int sz=que.size();
            while(sz>0){
                TreeNode* node=que.front();
                que.pop();
                if(node->left)
                    que.push(node->left);
                if(node->right)
                    que.push(node->right);
                sz--;
                if(sz==0){
                    result.emplace_back(node->val);
                }
            }
        }
        return result;
    }
    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

时间复杂度 : O(n)。 每个节点最多进队列一次，出队列一次，因此广度优先搜索的复杂度为线性。

空间复杂度 : O(n)。每个节点最多进队列一次，所以队列长度最大不不超过 n，所以这里的空间代价为 O(n)

46. 114 二叉树展开为链表

进阶：O(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:
    void flatten(TreeNode* root) {
        vectorlistNode;
        preOrder(root,listNode);
        int n=listNode.size();
        TreeNode *next,*cur;
        for(int i=0;ileft=nullptr;
            cur->right=next;
        }
    }
    void preOrder(TreeNode*root,vector&listNode){
        if(root==nullptr)
        return;
        listNode.push_back(root);
        preOrder(root->left,listNode);
        preOrder(root->right,listNode);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

时间复杂度：O(n)，其中 n 是二叉树的节点数。前序遍历的时间复杂度是 O(n)，前序遍历之后，需要对每个节点更新左右子节点的信息，时间复杂度也是 O(n)。

空间复杂度：O(n)，其中 n是二叉树的节点数。空间复杂度取决于栈（递归调用栈或者迭代中显性使用的栈）和存储前序遍历结果的列表的大小，栈内的元素个数不会超过 n，前序遍历列表中的元素个数是 n

解法二：优化方法O(1)空间

可以发现展开的顺序其实就是二叉树的先序遍历。算法和 94 题中序遍历的 Morris 算法有些神似，我们需要两步完成这道题。

将左子树插入到右子树的地方
将原来的右子树接到左子树的最右边节点
考虑新的右子树的根节点，一直重复上边的过程，直到新的右子树为 null

/**
 * 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:
    void flatten(TreeNode* root) {
       if(root==nullptr)
       return;
       while(root!=nullptr){
        //左子树为null,直接考虑下一个节点
        if(root->left==nullptr){
            root=root->right;
        }else{
            //找左子树最右边的节点
            TreeNode*pre=root->left;
            while(pre->right!=nullptr){
                pre=pre->right;
            }
            //将原来的右子树接到左子树的最右边节点
            pre->right=root->right;
            //将左子树插入右子树的地方
            root->right=root->left;
            root->left=nullptr;
            //考虑下一个节点
            root=root->right;
        }

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

时间复杂度：O(n)

空间复杂度：O(1)

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

解法：对于任意一颗树而言，前序遍历的形式总是

[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是

[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位。

这样以来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。

细节

在中序遍历中对根节点进行定位时，一种简单的方法是直接扫描整个中序遍历的结果并找出根节点，但这样做的时间复杂度较高。我们可以考虑使用哈希表来帮助我们快速地定位根节点。对于哈希映射中的每个键值对，键表示一个元素（节点的值），值表示其在中序遍历中的出现位置。在构造二叉树的过程之前，我们可以对中序遍历的列表进行一遍扫描，就可以构造出这个哈希映射。在此后构造二叉树的过程中，我们就只需要 O(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:
    unordered_mapnum2Index;
    TreeNode* buildTree(vector& preorder, vector& inorder) {
        for(int i=0;i& preorder,vector& inorder,int preleft,int preright,int inleft){
        if(preleft>preright)
        return nullptr;
        int preroot=preleft;
        //在中序遍历中定位根节点
        int inroot=num2Index[preorder[preroot]];
        TreeNode *root=new TreeNode(preorder[preroot]);
        int size_left_subtree=inroot-inleft;
        root->left=setTree(preorder,inorder,preleft+1,preleft+size_left_subtree,inleft);
        root->right=setTree(preorder,inorder,preleft+size_left_subtree+1,preright,inroot+1);
        return root;
    }

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

时间复杂度：O(n)，其中 n 是树中的节点个数。

空间复杂度：O(n)，除去返回的答案需要的 O(n) 空间之外，我们还需要使用 O(h)（其中 h 是树的高度）的空间存储栈。这里 h

48. 437 路径总和|||

解法一：深度优先搜索DFS 按照要求递归即可 如果root.val == targetSum 记录一下答案

1.递归表达式
dfs(root.left, targetSum - root.val);
dfs(root.right, targetSum - root.val);
2.出口
root==null 就返回0
3.函数定义
dfs就是就当前root是否符合答案，如果root.val == targetSum 记录一下答案

/**
 * 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 count=0;
    void dfs(TreeNode*root,long long targetSum){
        if(root==nullptr)
        return ;
        if(root->val==targetSum)
            count++;
        dfs(root->left,targetSum-root->val);    
        dfs(root->right,targetSum-root->val);
    }
    int pathSum(TreeNode* root, int targetSum) {
        if(root==nullptr)
        return 0;
        dfs(root,targetSum);
        pathSum(root->left,targetSum);
        pathSum(root->right,targetSum);
        return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

• 时间复杂度：O(n2)
• 空间复杂度：忽略递归带来的额外空间开销，复杂度为 O(1)

解法二：DFS过程中的前缀和

在「解法一」中，我们统计的是以每个节点为根的（往下的）所有路径，也就是说统计的是以每个节点为「路径开头」的所有合法路径。

本题的一个优化切入点为「路径只能往下」，因此如果我们转换一下，统计以每个节点为「路径结尾」的合法数量的话，配合原本就是「从上往下」进行的数的遍历（最完整的路径必然是从原始根节点到当前节点的唯一路径），相当于只需要在完整路径中找到有多少个节点到当前节点的路径总和为 targetSum。

于是这个树上问题彻底转换一维问题：求解从原始起点（根节点）到当前节点 b 的路径中，有多少节点 a 满足 sum[a…b]=target，由于从原始起点（根节点）到当前节点的路径唯一，因此这其实是一个「一维前缀和」问题。

具体的，我们可以在进行树的遍历时，记录下从原始根节点 root 到当前节点 cur 路径中，从 root到任意中间节点 x 的路径总和，配合哈希表，快速找到满足以 cur为「路径结尾」的、使得路径总和为 targetSum 的目标「路径起点」有多少个。

一些细节：由于我们只能统计往下的路径，但是树的遍历会同时搜索两个方向的子树。因此我们应当在搜索完以某个节点为根的左右子树之后，应当回溯地将路径总和从哈希表中删除，防止统计到跨越两个方向的路径。

注意 必须用long 类型，不然测试案例过不去

/**
 * 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 count=0;
    unordered_mapmap;
    void dfs(TreeNode*root,long targetSum,long  sum){
        if(root==nullptr)
        return ;
        //计算前缀和
        sum+=root->val;
        if(map.count(sum-targetSum))
        count+=map[sum-targetSum];
        //将当前前缀和加入map中
        map[sum]++;
        //递归调用left和right
        dfs(root->left,targetSum,sum);    
        dfs(root->right,targetSum,sum);
        //遍历结束移除当前的前缀和
        map[sum]--;
    }
    int pathSum(TreeNode* root, long targetSum) {
        if(root==nullptr)
        return 0;
        map[0]=1;
        dfs(root,targetSum,0);
        return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

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

解法一：递归

解题思路：
祖先的定义： 若节点 p 在节点 root的左（右）子树中，或 p=root，则称 root是 p 的祖先。

最近公共祖先的定义： 设节点 root为节点 p,q的某公共祖先，若其左子节点 root.left 和右子节点 root.right 都不是 p,q的公共祖先，则称 root 是 “最近的公共祖先” 。

根据以上定义，若 root是 p,q 的 最近公共祖先 ，则只可能为以下情况之一：

p 和 q 在 root 的子树中，且分列 root的 异侧（即分别在左、右子树中）；
p=root ，且 q 在 root 的左或右子树中；
q=root，且 p 在 root的左或右子树中；

考虑通过递归对二叉树进行先序遍历，当遇到节点 p 或 q时返回。从底至顶回溯，当节点 p,q在节点 root 的异侧时，节点 root 即为最近公共祖先，则向上返回 root 。

递归解析：
终止条件：
当越过叶节点，则直接返回 nul；
当 root 等于 p,q ，则直接返回 root ；
递推工作：
开启递归左子节点，返回值记为 left；
开启递归右子节点，返回值记为 right；
返回值： 根据 left 和 right ，可展开为四种情况；
当 left 和 right 同时为空 ：说明 root的左 / 右子树中都不包含 p,q，返回 null ；
当 left 和 right 同时不为空 ：说明 p,q分列在 root的 异侧 （分别在 左 / 右子树），因此 root为最近公共祖先，返回 root ；
当 left为空 ，right 不为空 ：p,q都不在 root 的左子树中，直接返回 right 。具体可分为两种情况：
p,q 其中一个在 root 的 右子树 中，此时 right 指向 p（假设为 p ）；
p,q 两节点都在 root 的 右子树 中，此时的 right 指向 最近公共祖先节点 ；
当 left 不为空 ， right 为空 ：与情况 3. 同理；

代码：

/**
 * 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==nullptr||root==p||root==q)
        return root;
         TreeNode *left=lowestCommonAncestor(root->left,p,q);
         TreeNode *right=lowestCommonAncestor(root->right,p,q);
         if(left!=nullptr&&right!=nullptr)
         return root;
         else if(left==nullptr)
         return right;
         else
         return left;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

时间复杂度：O(N)，其中 N 是二叉树的节点数。二叉树的所有节点有且只会被访问一次，因此时间复杂度为 O(N)。

空间复杂度：O(N) ，其中 N 是二叉树的节点数。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为 N，因此空间复杂度为 O(N)。

解法二：存储父节点，注意到题目给的条件中，有每个节点的值各不相同，可以使用哈希表存储父节点

思路

我们可以用哈希表存储所有节点的父节点，然后我们就可以利用节点的父节点信息从 p 结点开始不断往上跳，并记录已经访问过的节点，再从 q 节点开始不断往上跳，如果碰到已经访问过的节点，那么这个节点就是我们要找的最近公共祖先。

算法

从根节点开始遍历整棵二叉树，用哈希表记录每个节点的父节点指针。
从 p 节点开始不断往它的祖先移动，并用数据结构记录已经访问过的祖先节点。
同样，我们再从 q 节点开始不断往它的祖先移动，如果有祖先已经被访问过，即意味着这是 p 和 q 的深度最深的公共祖先，即 LCA 节点。

/**
 * 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_mapfa;
    unordered_mapvisited;
    void dfs(TreeNode*root){
        if(root->left!=nullptr){
            fa[root->left->val]=root;
            dfs(root->left);
        }
         if(root->right!=nullptr){
            fa[root->right->val]=root;
            dfs(root->right);
        }
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        fa[root->val]=nullptr;
        dfs(root);
        while(p!=nullptr){
            visited[p->val]=true;
            p=fa[p->val];
        }
        while(q!=nullptr){
            if(visited[q->val])
            return q;
            q=fa[q->val];
        }
        return nullptr;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

时间复杂度：O(N)，其中 N 是二叉树的节点数。二叉树的所有节点有且只会被访问一次，从 p 和 q 节点往上跳经过的祖先节点个数不会超过 N，因此总的时间复杂度为 O(N)。

空间复杂度：O(N) ，其中 N 是二叉树的节点数。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为 N，因此空间复杂度为 O(N)，哈希表存储每个节点的父节点也需要 O(N)的空间复杂度，因此最后总的空间复杂度为 O(N)。

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

解法：递归

方法一：递归
首先，考虑实现一个简化的函数 maxGain(node)，该函数计算二叉树中的一个节点的最大贡献值，具体而言，就是在以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大。

具体而言，该函数的计算如下。

空节点的最大贡献值等于 0。

非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和（对于叶节点而言，最大贡献值等于节点值）。

例如，考虑如下二叉树。

-10
/
9 20
/
15 7
叶节点 9、15、7 的最大贡献值分别为 9、15、7。

得到叶节点的最大贡献值之后，再计算非叶节点的最大贡献值。节点 20 的最大贡献值等于 20+max⁡(15,7)=35，节点 −10 的最大贡献值等于 −10+max⁡(9,35)=25。

上述计算过程是递归的过程，因此，对根节点调用函数 maxGain，即可得到每个节点的最大贡献值。

根据函数 maxGain 得到每个节点的最大贡献值之后，如何得到二叉树的最大路径和？对于二叉树中的一个节点，该节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值，如果子节点的最大贡献值为正，则计入该节点的最大路径和，否则不计入该节点的最大路径和。维护一个全局变量 maxSum 存储最大路径和，在递归过程中更新 maxSum 的值，最后得到的 maxSum 的值即为二叉树中的最大路径和。。

/**
 * 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 maxSum=INT_MIN;
    int dfs(TreeNode*root){
        if(root==nullptr)
        return 0;
        //递归计算左右子节点的最大贡献值
        //只有在最大贡献值大于0的时候，才取得对应自己饿点
        int leftMax=max(dfs(root->left),0);
        int rightMax=max(dfs(root->right),0);
        //节点的最大路径取决于该节点的值和该节点的左右子节点的最大贡献值
        int rootMax=root->val+leftMax+rightMax;
        maxSum=max(maxSum,rootMax);
        //返回节点的最大贡献值
        return root->val+max(leftMax,rightMax);
    }
     int maxPathSum(TreeNode* root) {
        dfs(root);
        return maxSum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

时间复杂度：O(N)，其中 N 是二叉树中的节点个数。对每个节点访问不超过 2 次。

空间复杂度：O(N)，其中 N 是二叉树中的节点个数。空间复杂度主要取决于递归调用层数，最大层数等于二叉树的高度，最坏情况下，二叉树的高度等于二叉

图论

51. 200 岛屿数量

### 51. 200 岛屿数量

解法：DFS
我们可以将二维网格看成一个无向图，竖直或水平相邻的 1 之间有边相连。

为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，使用visited标记每个节点是否访问，【也可以在grid数组上直接标记,每个搜索到的节每个搜索到的 1 都会被重新标记为 0】。

最终岛屿的数量就是我们进行深度优先搜索的次数。

class Solution {
public:
    int count=0;
    vector>visited;
    vector>direct{{1,0},{0,1},{-1,0},{0,-1}};
    void dfs(vector>& grid,int r,int c){
        if(r>=grid.size()||r<0||c>=grid[0].size()||c<0)
        return;
        if(grid[r][c]!='1'||visited[r][c])
        return;
         visited[r][c]=true;
        for(int i=0;i<4;i++){
            dfs(grid,r+direct[i][0],c+direct[i][1]);
        }
        
    }
    int numIslands(vector>& grid) {
        visited.resize(grid.size(), vector(grid[0].size(), false));
        for(int i=0;i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

时间复杂度：O(MN)，其中 M 和 N 分别为行数和列数。

空间复杂度：O(MN)，在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 MN

解法二： 并查集和BFS 见200. 岛屿数量 - 力扣（LeetCode）

52. 994 腐烂的橘子

解法：BFS（类似二叉树的层次遍历）

察到对于所有的腐烂橘子，其实它们在广度优先搜索上是等价于同一层的节点的。

即首先记录下新鲜橘子的个数为cnt,然后将腐烂节点加入队列中，进行广度优先遍历【四个方向，上下左右】，若是有橘子由新鲜变成腐烂，则cnt–；注意在搜索过程中如果橘子由新鲜变成腐烂，则橘子的值从1改为2。队列中每层的腐烂水果的遍历就经过了一分钟，如果最后队列为空，cnt仍然大于0，则返回-1.

class Solution {
    int cnt;
    vector>gap{{0,1},{1,0},{0,-1},{-1,0}};
public:
    int rotting(vector>&grid,int x,int y,queue>&que){
        if(x<0||x>=grid.size()||y<0||y>=grid[0].size()||grid[x][y]!=1){
            return 0;
        }
        grid[x][y]=2;
        que.push(make_pair(x,y));
        return 1;
    }
    int orangesRotting(vector>& grid) {
        queue>que;
        int r=grid.size();
        int c=grid[0].size();
        for(int i=0;i0?-1:minutes;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

时间复杂度：O(nm)
即进行一次广度优先搜索的时间，其中 n=grid.length, m=grid[0].length。

空间复杂度：O(nm)
需要额外的 dis 数组记录每个新鲜橘子被腐烂的最短时间，大小为 O(nm)，且广度优先搜索中队列里存放的状态最多不会超过 nm 个，最多需要 O(nm) 的空间，所以最后的空间复杂度为 O(nm)。

53. 207 课程表

解法一：DFS

方法一：深度优先搜索
思路

我们可以将深度优先搜索的流程与拓扑排序的求解联系起来，用一个栈来存储所有已经搜索完成的节点。

对于一个节点 u，如果它的所有相邻节点都已经搜索完成，那么在搜索回溯到 u 的时候，u 本身也会变成一个已经搜索完成的节点。这里的「相邻节点」指的是从 u出发通过一条有向边可以到达的所有节点。

假设我们当前搜索到了节点 u，如果它的所有相邻节点都已经搜索完成，那么这些节点都已经在栈中了，此时我们就可以把 u 入栈。可以发现，如果我们从栈顶往栈底的顺序看，由于 u 处于栈顶的位置，那么 u 出现在所有 u的相邻节点的前面。因此对于 u这个节点而言，它是满足拓扑排序的要求的。

这样以来，我们对图进行一遍深度优先搜索。当每个节点进行回溯的时候，我们把该节点放入栈中。最终从栈顶到栈底的序列就是一种拓扑排序。

算法

对于图中的任意一个节点，它在搜索的过程中有三种状态，即：

「未搜索」：我们还没有搜索到这个节点；

「搜索中」：我们搜索过这个节点，但还没有回溯到该节点，即该节点还没有入栈，还有相邻的节点没有搜索完成）；

「已完成」：我们搜索过并且回溯过这个节点，即该节点已经入栈，并且所有该节点的相邻节点都出现在栈的更底部的位置，满足拓扑排序的要求。

通过上述的三种状态，我们就可以给出使用深度优先搜索得到拓扑排序的算法流程，在每一轮的搜索搜索开始时，我们任取一个「未搜索」的节点开始进行深度优先搜索。

我们将当前搜索的节点 u 标记为「搜索中」，遍历该节点的每一个相邻节点 v：

如果 v为「未搜索」，那么我们开始搜索 v，待搜索完成回溯到 u；

如果 v 为「搜索中」，那么我们就找到了图中的一个环，因此是不存在拓扑排序的；

如果 v 为「已完成」，那么说明 v已经在栈中了，而 u 还不在栈中，因此 u 无论何时入栈都不会影响到 (u,v) 之前的拓扑关系，以及不用进行任何操作。

当 uuu 的所有相邻节点都为「已完成」时，我们将 u 放入栈中，并将其标记为「已完成」。

在整个深度优先搜索的过程结束后，如果我们没有找到图中的环，那么栈中存储这所有的 n 个节点，从栈顶到栈底的顺序即为一种拓扑排序。

代码：

class Solution {
public:
    vector>edges;
    vectorvisited;
    bool valid=true;
    //0表示未搜索 1
    void dfs(int u){
        visited[u]=1;
        for(int v:edges[u]){
            if(visited[v]==0)
            {
                dfs(v);
                if(!valid)
                return;
            }
            else if(visited[v]==1){
                valid=false;
                return;
            }
        }
         visited[u]=2;
    }
    bool canFinish(int numCourses, vector>& prerequisites) {
        edges.resize(numCourses);
        visited.resize(numCourses);
        for(auto &info:prerequisites){
            edges[info[1]].push_back(info[0]);
        }
        for(int i=0;i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

时间复杂度: O(n+m)，其中 n 为课程数，m 为先修课程的要求数。这其实就是对图进行深度优先搜索的时间复杂度。

空间复杂度: O(n+m)。题目中是以列表形式给出的先修课程关系，为了对图进行深度优先搜索，我们需要存储成邻接表的形式，空间复杂度为 O(n+m)。在深度优先搜索的过程中，我们需要最多 O(n) 的栈空间（递归）进行深度优先搜索，因此总空间复杂度为 O(n+m))。

解法二：广度优先搜索

207. 课程表 - 力扣（LeetCode）

方法一的深度优先搜索是一种「逆向思维」：最先被放入栈中的节点是在拓扑排序中最后面的节点。我们也可以使用正向思维，顺序地生成拓扑排序，这种方法也更加直观。

我们考虑拓扑排序中最前面的节点，该节点一定不会有任何入边，也就是它没有任何的先修课程要求。当我们将一个节点加入答案中后，我们就可以移除它的所有出边，代表着它的相邻节点少了一门先修课程的要求。如果某个相邻节点变成了「没有任何入边的节点」，那么就代表着这门课可以开始学习了。按照这样的流程，我们不断地将没有入边的节点加入答案，直到答案中包含所有的节点（得到了一种拓扑排序）或者不存在没有入边的节点（图中包含环）。

上面的想法类似于广度优先搜索，因此我们可以将广度优先搜索的流程与拓扑排序的求解联系起来。

算法

我们使用一个队列来进行广度优先搜索。初始时，所有入度为 0 的节点都被放入队列中，它们就是可以作为拓扑排序最前面的节点，并且它们之间的相对顺序是无关紧要的。

在广度优先搜索的每一步中，我们取出队首的节点 u：

我们将 u 放入答案中；

我们移除 u 的所有出边，也就是将 u 的所有相邻节点的入度减少 1。如果某个相邻节点 v 的入度变为 0，那么我们就将 v放入队列中。

在广度优先搜索的过程结束后。如果答案中包含了这 nnn 个节点，那么我们就找到了一种拓扑排序，否则说明图中存在环，也就不存在拓扑排序了。

下面的幻灯片给出了广度优先搜索的可视化流程。

class Solution {
private:
    vector> edges;
    vector indeg;

public:
    bool canFinish(int numCourses, vector>& prerequisites) {
        edges.resize(numCourses);
        indeg.resize(numCourses);
        for (const auto& info: prerequisites) {
            edges[info[1]].push_back(info[0]);
            ++indeg[info[0]];
        }

        queue q;
        for (int i = 0; i < numCourses; ++i) {
            if (indeg[i] == 0) {
                q.push(i);
            }
        }

        int visited = 0;
        while (!q.empty()) {
            ++visited;
            int u = q.front();
            q.pop();
            for (int v: edges[u]) {
                --indeg[v];
                if (indeg[v] == 0) {
                    q.push(v);
                }
            }
        }

        return visited == numCourses;
    }
};

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

54. 207 实现Trie(前缀树)

解法：前缀树结构模拟

方法一：字典树
Trie，又称前缀树或字典树，是一棵有根树，其每个节点包含以下字段：

指向子节点的指针数组 children。对于本题而言，数组长度为 262626，即小写英文字母的数量。此时 children[0]对应小写字母 a，children[1] 对应小写字母 b，…，children[25] 对应小写字母 z。
布尔字段isEnd，表示该节点是否为字符串的结尾。
插入字符串

我们从字典树的根开始，插入字符串。对于当前字符对应的子节点，有两种情况：

子节点存在。沿着指针移动到子节点，继续处理下一个字符。
子节点不存在。创建一个新的子节点，记录在 children 数组的对应位置上，然后沿着指针移动到子节点，继续搜索下一个字符。
重复以上步骤，直到处理字符串的最后一个字符，然后将当前节点标记为字符串的结尾。

查找前缀

我们从字典树的根开始，查找前缀。对于当前字符对应的子节点，有两种情况：

子节点存在。沿着指针移动到子节点，继续搜索下一个字符。
子节点不存在。说明字典树中不包含该前缀，返回空指针。
重复以上步骤，直到返回空指针或搜索完前缀的最后一个字符。

若搜索到了前缀的末尾，就说明字典树中存在该前缀。此外，若前缀末尾对应节点的 isEnd\textit{isEnd}isEnd 为真，则说明字典树中存在该字符串。

代码：

class Trie {
public:
    vectorchildren;
    bool isEnd;
    Trie() :children(26),isEnd(false){ }
    
    void insert(string word) {
        Trie*node=this;
        for(char ch:word){
            ch-='a';
            if(node->children[ch]==nullptr){
                node->children[ch]=new Trie();
            }
            node=node->children[ch];
        }
        node->isEnd=true;
    }
    Trie* searchPrefix(string word){
        Trie*node=this;
        for(char ch:word){
            ch-='a';
            if(node->children[ch]==nullptr){
                return nullptr;
            }
            node=node->children[ch];
        }
        return node;
    }
    bool search(string word) {
        Trie*node=this->searchPrefix(word);
        return node!=nullptr&&node->isEnd;
    }
    
    bool startsWith(string prefix) {
        return searchPrefix(prefix)!=nullptr;
    }
};

/**
 * 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);
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

时间复杂度：初始化为 O(1)，其余操作为 O(∣S∣)，其中 ∣S∣是每次插入或查询的字符串的长度。

空间复杂度：$O(|T|\cdot \Sigma )$，其中 ∣T∣ 为所有插入字符串的长度之和，Σ 为字符集的大小，本题 Σ=26。

回溯

55. 46 全排列

解法一：DFS递归，使用visited数组记录该元素是否被访问

class Solution {
public:
    vector>res;
    void dfs(vectorcur_res,vectorvisited,vector& nums,int i){
          cur_res.emplace_back(nums[i]);
          visited[i]=true;\
        if(cur_res.size()==visited.size()){
            res.push_back(cur_res);
            return;
        }
        for(int i=0;i> permute(vector& nums) {
        vectorvisited(nums.size(),false);
        for(int i=0;icur_res;
            dfs(cur_res,visited,nums,i);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

解法二：DFS的递归优化方法，不使用visited数组，使用标记的方法

46. 全排列 - 力扣（LeetCode）

56. 78. 子集

解法一：DFS

dfs(cur,n) 参数表示当前位置是 cur，原序列总长度为 n。原序列的每个位置在答案序列中的状态有被选中和不被选中两种，我们用 t 数组存放已经被选出的数字。在进入 dfs(cur,n) 之前 [0,cur−1] 位置的状态是确定的，而 [cur,n−1] 内位置的状态是不确定的，dfs(cur,n) 需要确定}cur 位置的状态，然后求解子问题 dfs(cur+1,n)。对于cur 位置，我们需要考虑 a[cur] 取或者不取，如果取，我们需要把 a[cur] 放入一个临时的答案数组中（即上面代码中的 t），再执行 dfs(cur+1,n)，执行结束后需要对 t 进行回溯；如果不取，则直接执行 dfs(cur+1,n)。在整个递归调用的过程中，cur 是从小到大递增的，当 cur 增加到 n 的时候，记录答案并终止递归。可以看出二进制枚举的时间复杂度是 $O(2^n)$

class Solution {
public:
    vector>ans;
    vectort;
    void dfs(int cur,vector&nums){
        if(cur==nums.size()){
            ans.push_back(t);
            return;
        }
        //取和不取两种情况
        t.push_back(nums[cur]);
        dfs(cur+1,nums);
        t.pop_back();
        dfs(cur+1,nums);
    }
    vector> subsets(vector& nums) {
        dfs(0,nums);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

时间复杂度：$O(n\times 2^n)$个状态，每种状态需要 O(n)的时间来构造子集。

空间复杂度：O(n)。临时数组 t 的空间代价是 O(n)，递归时栈空间的代价为 O(n)。

解法二：迭代法实现子集枚举（二进制）$[0，2^n-1]$的二进制，位置为1表示取，位置为2表示不取

78. 子集 - 力扣（LeetCode）

57. 17. 电话号码的字母组合

image-20240229002330269

解法：dfs回溯

首先使用哈希表存储每个数字对应的所有可能的字母，然后进行回溯操作。

回溯过程中维护一个字符串，表示已有的字母排列（如果未遍历完电话号码的所有数字，则已有的字母排列是不完整的）。该字符串初始为空。每次取电话号码的一位数字，从哈希表中获得该数字对应的所有可能的字母，并将其中的一个字母插入到已有的字母排列后面，然后继续处理电话号码的后一位数字，直到处理完电话号码中的所有数字，即得到一个完整的字母排列。然后进行回退操作，遍历其余的字母排列。

回溯算法用于寻找所有的可行解，如果发现一个解不可行，则会舍弃不可行的解。回溯的过程其实就是DFS后依照条件退出递归的过程，很明显，上述退出递归的过程是取到电话的最后一个数字。

在这道题中，由于每个数字对应的每个字母都可能进入字母组合，因此不存在不可行的解，直接穷举所有的解即可。

代码：

class Solution {
public:
    vectornumStr;

    int dight_depth;
    void dfs(vector&result,int depth,string &digits,string res){
        if(depth==dight_depth){
            result.push_back(res);
            return;
        }
        depth++;
        string tmp=numStr[digits[depth-1]-'0'];
        for(int i=0;i letterCombinations(string digits) {
        if(digits.empty())
        {
            return vector{};
        }
        numStr.resize(10);
        numStr[2]="abc";
        numStr[3]="def";
        numStr[4]="ghi";
        numStr[5]="jkl";
        numStr[6]="mno";
        numStr[7]="pqrs";
        numStr[8]="tuv";
        numStr[9]="wxyz";
        vectorresult;
        string res="";
        dight_depth=digits.size();
        string tmp=numStr[digits[0]-'0'];
        for(int i=0;i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

时间复杂度：$O(3^m\times 4^n)$，其中 m 是输入中对应 3 个字母的数字个数（包括数字 2、3、4、5、6、8），n 是输入中对应 4 个字母的数字个数（包括数字 7、9），m+n是输入数字的总个数。当输入包含 m 个对应 3 个字母的数字和 n 个对应 44个字母的数字时，不同的字母组合一共有 $3^m\times 4^n$ 种，需要遍历每一种字母组合。

空间复杂度：O(m+n)，其中 m 是输入中对应 3 个字母的数字个数，nnn 是输入中对应 4 个字母的数字个数，m+n是输入数字的总个数。除了返回值以外，空间复杂度主要取决于哈希表以及回溯过程中的递归调用层数，哈希表的大小与输入无关，可以看成常数，递归调用层数最大为 m+n。

58. 39 组合总和

解法：DFS搜索+回溯

方法一：搜索回溯
思路与算法

对于这类寻找所有可行解的题，我们都可以尝试用「搜索回溯」的方法来解决。

回到本题，我们定义递归函数 dfs(target,cur_res,idx), 表示当前在 candidates数组的第 idx 位，还剩 target 要组合，已经组合的列表为 cur_res。递归的终止条件为 target≤0 或者 candidates 数组被全部用完。那么在当前的函数中，每次我们可以选择跳过不用第idx 个数，即执行 dfs(target,combine,idx+1)。也可以选择使用第 idx 个数，即执行 dfs(target−candidates[idx],cur_res,idx)，注意到每个数字可以被无限制重复选取，因此搜索的下标仍为 idx。

更形象化地说，如果我们将整个搜索过程用一个树来表达，即如下图呈现，每次的搜索都会延伸出两个分叉，直到递归的终止条件，这样我们就能不重复且不遗漏地找到所有可行解：

class Solution {
public:
    vector>res;
    void dfs(int target,vector& candidates,vector&cur_res,int idx){
        if(idx==candidates.size())
        {
            return;
        }
        if(target==0)
        {
            res.push_back(cur_res);
            return;
        }
        //直接跳过
        dfs(target,candidates,cur_res,idx+1);
        if(target-candidates[idx]>=0){
            cur_res.push_back(candidates[idx]);
            dfs(target-candidates[idx],candidates,cur_res,idx);
            cur_res.pop_back();          
        }
            
    }
    vector> combinationSum(vector& candidates, int target) {
        vectorcur_res;
        dfs(target,candidates,cur_res,0);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

时间复杂度：O(S)，其中 S 为所有可行解的长度之和。从分析给出的搜索树我们可以看出时间复杂度取决于搜索树所有叶子节点的深度之和，即所有可行解的长度之和。在这题中，我们很难给出一个比较紧的上界，我们知道 $O(n\times 2^n)$ 是一个比较松的上界，即在这份代码中，n 个位置每次考虑选或者不选，如果符合条件，就加入答案的时间代价。但是实际运行的时候，因为不可能所有的解都满足条件，递归的时候我们还会用 $\text{target}-\text{candidates}[\text{idx}]\ge 0$ 进行剪枝，所以实际运行情况是远远小于这个上界的。

空间复杂度：$O(\text{target})$。除答案数组外，空间复杂度取决于递归的栈深度，在最差情况下需要递归 $O(\text{target})$层。

59. 22 括号生成

解法一：DFS深搜+剪枝

这一类问题是在一棵隐式的树上求解，可以用深度优先遍历，也可以用广度优先遍历。
一般用深度优先遍历。原因是：代码好写，使用递归的方法，直接借助系统栈完成状态的转移；广度优先遍历得自己编写结点类和借助队列。
这里的「状态」是指程序执行到 隐式树 的某个结点的语言描述，在程序中用不同的 变量 加以区分。

以n=2为例，画出树形结构图，方法是记录左括号和右括号剩余的次数

可以得出结论：

• 当前左右括号都有大于 0 个可以使用的时候，才产生分支；
• 产生左分支的时候，只看当前是否还有左括号可以使用；
• 产生右分支的时候，还受到左分支的限制，右边剩余可以使用的括号数量一定得在严格大于左边剩余的数量的时候，才可以产生分支；
• 在左边和右边剩余的括号数都等于 0 的时候结算。

class Solution {
public:
    void dfs(string curStr,int left,int right,vector&res){
        if(left==0&&right==0){
            res.push_back(curStr);
            return;
        }
        if(left>right)
        {
            return;
        }
        if(left>0){
            dfs(curStr+"(",left-1,right,res);
        }
        if(right>0){
            dfs(curStr+")",left,right-1,res);
        }
    }
    vector generateParenthesis(int n) {
        vectorres;
        dfs("",n,n,res);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

我们的复杂度分析依赖于理解$\text{generateParenthesis}(n)$中有多少个元素。这个分析超出了本文的范畴，但事实证明这是第 n 个卡特兰数 1n+1(2nn)\d$frac1n+1\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ ，这是由 $\frac{4^n}{n\sqrt{n}}$ 渐近界定的。

时间复杂度：$O(\frac{4^n}{\sqrt{n}})$，在回溯过程中，每个答案需要 O(n) 的时间复制到答案数组中。

空间复杂度：O(n)，除了答案数组之外，我们所需要的空间取决于递归栈的深度，每一层递归函数需要 O(1)的空间，最多递归 2n 层，因此空间复杂度为 O(n)。

60. 79 单词搜索

解法：DFS+剪枝

本问题是典型的回溯问题，需要使用深度优先搜索（DFS）+ 剪枝解决。

深度优先搜索： 即暴力法遍历矩阵中所有字符串可能性。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。
剪枝： 在搜索中，遇到“这条路不可能和目标字符串匹配成功”的情况，例如当前矩阵元素和目标字符不匹配、或此元素已被访问，则应立即返回，从而避免不必要的搜索分支。

算法解析：
递归参数： 当前元素在矩阵 board 中的行列索引 i 和 j ，当前目标字符在 word 中的索引 k 。
终止条件：
返回 false ： (1) 行或列索引越界 或 (2) 当前矩阵元素与目标字符不同 或 (3) 当前矩阵元素已访问过 （ (3) 可合并至 (2) ） 。
返回 truet ： k = len(word) - 1 ，即字符串 word 已全部匹配。
递推工作：
标记当前矩阵元素： 将 board[i][j] 修改为 空字符 ‘’ ，代表此元素已访问过，防止之后搜索时重复访问。
搜索下一单元格： 朝当前元素的 上、下、左、右 四个方向开启下层递归，使用 或 连接 （代表只需找到一条可行路径就直接返回，不再做后续 DFS ），并记录结果至 res 。
还原当前矩阵元素： 将 board[i][j] 元素还原至初始值，即 word[k] 。
返回值： 返回布尔量 res ，代表是否搜索到目标字符串。
使用空字符（Python: ‘’ , Java/C++: ‘\0’ ）做标记是为了防止标记字符与矩阵原有字符重复。当存在重复时，此算法会将矩阵原有字符认作标记字符，从而出现错误。

class Solution {
public:
    int row,cols;
    vector>gap{{1,0},{0,1},{-1,0},{0,-1}};
    bool exist(vector>& board, string word) {
        row=board.size();
        cols=board[0].size();
        for(int i=0;i>& board, string word,int x,int y,int cnt){
        if(cnt==word.size())
        return true;
        if(x>=row||x<0||y>=cols||y<0||board[x][y]!=word[cnt]){
            return false;
        }
        board[x][y]='\0';
        bool res=false;
        for(int i=0;i<4;i++){
            res=dfs(board,word,x+gap[i][0],y+gap[i][1],cnt+1);
           // cout<<"res:"<
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

时间复杂度 $O(3^{K}MN$) ： 最差情况下，需要遍历矩阵中长度为 K 字符串的所有方案，时间复杂度为 $O(3^K)$)；矩阵中共有 MN 个起点，时间复杂度为 O(MN) 。
方案数计算： 设字符串长度为 K ，搜索中每个字符有上、下、左、右四个方向可以选择，舍弃回头（上个字符）的方向，剩下 3 种选择，因此方案数的复杂度为 $O(3^K)$。
空间复杂度 O(K) ： 搜索过程中的递归深度不超过 K ，因此系统因函数调用累计使用的栈空间占用 O(K) （因为函数返回后，系统调用的栈空间会释放）。最坏情况下 K=MN，递归深度为 MN，此时系统栈使用 O(MN) 的额外空间。

60. 79 单词搜索

解法：DFS+剪枝

本问题是典型的回溯问题，需要使用深度优先搜索（DFS）+ 剪枝解决。

深度优先搜索： 即暴力法遍历矩阵中所有字符串可能性。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。
剪枝： 在搜索中，遇到“这条路不可能和目标字符串匹配成功”的情况，例如当前矩阵元素和目标字符不匹配、或此元素已被访问，则应立即返回，从而避免不必要的搜索分支。

算法解析：
递归参数： 当前元素在矩阵 board 中的行列索引 i 和 j ，当前目标字符在 word 中的索引 k 。
终止条件：
返回 false ： (1) 行或列索引越界 或 (2) 当前矩阵元素与目标字符不同 或 (3) 当前矩阵元素已访问过 （ (3) 可合并至 (2) ） 。
返回 truet ： k = len(word) - 1 ，即字符串 word 已全部匹配。
递推工作：
标记当前矩阵元素： 将 board[i][j] 修改为 空字符 ‘’ ，代表此元素已访问过，防止之后搜索时重复访问。
搜索下一单元格： 朝当前元素的 上、下、左、右 四个方向开启下层递归，使用 或 连接 （代表只需找到一条可行路径就直接返回，不再做后续 DFS ），并记录结果至 res 。
还原当前矩阵元素： 将 board[i][j] 元素还原至初始值，即 word[k] 。
返回值： 返回布尔量 res ，代表是否搜索到目标字符串。
使用空字符（Python: ‘’ , Java/C++: ‘\0’ ）做标记是为了防止标记字符与矩阵原有字符重复。当存在重复时，此算法会将矩阵原有字符认作标记字符，从而出现错误。

class Solution {
public:
    int row,cols;
    vector>gap{{1,0},{0,1},{-1,0},{0,-1}};
    bool exist(vector>& board, string word) {
        row=board.size();
        cols=board[0].size();
        for(int i=0;i>& board, string word,int x,int y,int cnt){
        if(cnt==word.size())
        return true;
        if(x>=row||x<0||y>=cols||y<0||board[x][y]!=word[cnt]){
            return false;
        }
        board[x][y]='\0';
        bool res=false;
        for(int i=0;i<4;i++){
            res=dfs(board,word,x+gap[i][0],y+gap[i][1],cnt+1);
           // cout<<"res:"<
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

时间复杂度 $O(3^{K}MN$) ： 最差情况下，需要遍历矩阵中长度为 K 字符串的所有方案，时间复杂度为 $O(3^K)$)；矩阵中共有 MN 个起点，时间复杂度为 O(MN) 。
方案数计算： 设字符串长度为 K ，搜索中每个字符有上、下、左、右四个方向可以选择，舍弃回头（上个字符）的方向，剩下 3 种选择，因此方案数的复杂度为 $O(3^K)$。
空间复杂度 O(K) ： 搜索过程中的递归深度不超过 K ，因此系统因函数调用累计使用的栈空间占用 O(K) （因为函数返回后，系统调用的栈空间会释放）。最坏情况下 K=MN，递归深度为 MN，此时系统栈使用 O(MN) 的额外空间。

61. 131 分割回文串

解法：DFS+动态规划【有点没懂】

方法一：回溯 + 动态规划预处理
思路与算法

由于需要求出字符串 s 的所有分割方案，因此我们考虑使用搜索 + 回溯的方法枚举所有可能的分割方法并进行判断。

假设我们当前搜索到字符串的第 i 个字符，且 s[0…i−1] 位置的所有字符已经被分割成若干个回文串，并且分割结果被放入了答案数组 ans 中，那么我们就需要枚举下一个回文串的右边界 j，使得 s[i…j]是一个回文串。

因此，我们可以从 i 开始，从小到大依次枚举 j。对于当前枚举的 j 值，我们使用双指针的方法判断 s[i…j] 是否为回文串：如果 s[i…j] 是回文串，那么就将其加入答案数组ans 中，并以 j+1 作为新的 i 进行下一层搜索，并在未来的回溯时将 s[i…j] 从 ans 中移除。

如果我们已经搜索完了字符串的最后一个字符，那么就找到了一种满足要求的分割方法。

细节

当我们在判断 s[i…j] 是否为回文串时，常规的方法是使用双指针分别指向 i 和 j，每次判断两个指针指向的字符是否相同，直到两个指针相遇。然而这种方法会产生重复计算，例如下面这个例子：

当 s=aab 时，对于前 2 个字符 aa，我们有 2 种分割方法 [[aa] 和 [a,a]，当我们每一次搜索到字符串的第 i=2个字符 b 时，都需要对于每个 s[i…j]使用双指针判断其是否为回文串，这就产生了重复计算。

因此，我们可以将字符串 s的每个子串 s[i…j] 是否为回文串预处理出来，使用动态规划即可。设 f(i,j)表示 s[i…j]是否为回文串，那么有状态转移方程：

$$f(i,j)=\{\begin{array}{ll}\text{True},& i\ge j\\ f(i+1,j-1)\wedge (s[i]=s[j]),& \text{otherwise}\end{array}$$

其中 ∧ 表示逻辑与运算，即 s[i…j]为回文串，当且仅当其为空串（i>j），其长度为 1（i=j），或者首尾字符相同且 s[i+1…j−1] 为回文串。

预处理完成之后，我们只需要 O(1)的时间就可以判断任意 s[i…j]是否为回文串了。

class Solution {
public:
    vector>f;
    vector>ret;
    vectorans;
    int n;
    void dfs(const string &s,int i){
        if(i==n)
        {
            ret.push_back(ans);
            return;
        }
        for(int j=i;j> partition(string s) {
        n=s.size();
        f.assign(n,vector(n,true));
        for(int i=n-1;i>=0;--i){
            for(int j=i+1;j
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

时间复杂度：$O(n\cdot 2^n)$，其中 n 是字符串 s 的长度。在最坏情况下，s 包含 n 个完全相同的字符，因此它的任意一种划分方法都满足要求。而长度为 n 的字符串的划分方案数为 $2^{n-1}=O(2^n)$，每一种划分方法需要 O(n)的时间求出对应的划分结果并放入答案，因此总时间复杂度为 $O(n\cdot 2^n)$。尽管动态规划预处理需要 $O(n^2)$ 的时间，但在渐进意义下小于 $O(n\cdot 2^n)$，因此可以忽略。

空间复杂度：$O(n^2)$，这里不计算返回答案占用的空间。数组 fff 需要使用的空间为 $O(n^2)$，而在回溯的过程中，我们需要使用 O(n) 的栈空间以及 O(n) 的用来存储当前字符串分割方法的空间。由于 O(n) 在渐进意义下小于 $O(n^2)$，因此空间复杂度为$O(n^2)$

62. 51 N皇后

解法：基于集合的回溯
为了判断一个位置所在的列和两条斜线上是否已经有皇后，使用三个集合 columns、diagonals1和 diagonals2分别记录每一列以及两个方向的每条斜线上是否有皇后。

列的表示法很直观，一共有 N 列，每一列的下标范围从 0 到 N−1，使用列的下标即可明确表示每一列。

如何表示两个方向的斜线呢？对于每个方向的斜线，需要找到斜线上的每个位置的行下标与列下标之间的关系。

方向一的斜线为从左上到右下方向，同一条斜线上的每个位置满足行下标与列下标之差相等，例如 (0,0) 和 (3,3) 在同一条方向一的斜线上。因此使用行下标与列下标之差即可明确表示每一条方向一的斜线。

方向二的斜线为从右上到左下方向，同一条斜线上的每个位置满足行下标与列下标之和相等，例如 (3,0) 和 (1,2) 在同一条方向二的斜线上。因此使用行下标与列下标之和即可明确表示每一条方向二的斜线。

每次放置皇后时，对于每个位置判断其是否在三个集合中，如果三个集合都不包含当前位置，则当前位置是可以放置皇后的位置。

class Solution {
public:
    vector> solveNQueens(int n) {
     vector>solutions;
     vectorqueens(n,-1);
     unordered_setcolumns;
     unordered_setdiagonals1;    
     unordered_setdiagonals2;
     dfs(solutions,queens,n,0,columns,diagonals1,diagonals2);   
     return solutions;
    }
    void dfs( vector>&solutions,vector&queens,int n,int row,unordered_set &columns, unordered_set &diagonals1, unordered_set &diagonals2){
        if(row==n)
        {
            vector board=generateBoard(queens,n);
            solutions.push_back(board);
        }
        else{
            for(int i=0;i generateBoard(vector &queens, int n) {
        auto board = vector();
        for (int i = 0; i < n; i++) {
            string row = string(n, '.');
            row[queens[i]] = 'Q';
            board.push_back(row);
        }
        return board;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

时间复杂度：O(N!)，其中 N 是皇后数量。

空间复杂度：O(N)，其中 N 是皇后数量。空间复杂度主要取决于递归调用层数、记录每行放置的皇后的列下标的数组以及三个集合，递归调用层数不会超过 N，数组的长度为 N，每个集合的元素个数都不会超过 N。

二分查找

63. 35 搜索插入位置

解法：二分搜索

class Solution {
public:
    int searchInsert(vector& nums, int target) {
        int left=0;
        int right=nums.size()-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]==target)
            return mid;
            else if(nums[mid]>target){
                right=mid-1;
            }
            else{
                left=mid+1;
            }
        }
        return left;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时间复杂度：$O(\log n)$)，其中 n 为数组的长度。二分查找所需的时间复杂度为 $O(\log n)$。

空间复杂度：O(1)。我们只需要常数空间存放若干变量。

64. 74 搜索二维矩阵

解法一：从右上角开始搜索，每次淘汰一整行或者一整列，因为根据描述

如果>target,则往左移一列，如果

class Solution {
public:
    bool searchMatrix(vector>& matrix, int target) {
        int n=matrix.size();
        int m=matrix[0].size();
        int row=0;
        int col=m-1;
       // cout<<1<=0){
            if(matrix[row][col]==target)
            return true;
            if(matrix[row][col]>target){
                col--;
            }
            else{
                row++;
            }
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间复杂度：O（mn）

空间复杂度：O（1）

解法二：一次二分查找

74. 搜索二维矩阵 - 力扣（LeetCode）

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

解法一：二分查找
直观的思路肯定是从前往后遍历一遍。用两个变量记录第一次和最后一次遇见 target\textit{target}target 的下标，但这个方法的时间复杂度为 O(n)O(n)O(n)，没有利用到数组升序排列的条件。

由于数组已经排序，因此整个数组是单调递增的，我们可以利用二分法来加速查找的过程。

考虑 target 开始和结束位置，其实我们要找的就是数组中「第一个等于 target的位置」（记为 leftIdx）和「第一个大于 target 的位置减一」（记为 rightIdx）。

二分查找中，寻找 leftIdx 即为在数组中寻找第一个大于等于 target 的下标，寻找 rightIdx即为在数组中寻找第一个大于 target 的下标，然后将下标减一。两者的判断条件不同，为了代码的复用，我们定义 binarySearch(nums, target, lower) 表示在 nums数组中二分查找 target 的位置，如果 lower 为 true，则查找第一个大于等于 target 的下标，否则查找第一个大于 target 的下标。

最后，因为 target 可能不存在数组中，因此我们需要重新校验我们得到的两个下标 leftIdx 和 rightIdx，看是否符合条件，如果符合条件就返回 [leftIdx,rightIdx]，不符合就返回[−1,−1]。

class Solution {
public:
    int binarySearch(vector&nums,int target,bool lower){
        int left=0,right=nums.size()-1;
        int ans=nums.size();
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]>target||(lower&&nums[mid]>=target)){
                right=mid-1;
                ans=mid;
            }
            else{
                left=mid+1;
            }
        }
        return ans;
    }
     vector searchRange(vector& nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target) {
            return vector{leftIdx, rightIdx};
        } 
        return vector{-1, -1};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

时间复杂度： O(log⁡n) ，其中 n 为数组的长度。二分查找的时间复杂度为 O(log⁡n)，一共会执行两次，因此总时间复杂度为 O(log⁡n)。

空间复杂度：O(1)。只需要常数空间存放若干变量。

66. 33 搜索旋转排序数组

解法：二分查找

对于有序数组，可以使用二分查找的方法查找元素。

但是这道题中，数组本身不是有序的，进行旋转后只保证了数组的局部是有序的，这还能进行二分查找吗？答案是可以的。

可以发现的是，我们将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的。拿示例来看，我们从 6 这个位置分开以后数组变成了 [4, 5, 6] 和 [7, 0, 1, 2] 两个部分，其中左边 [4, 5, 6] 这个部分的数组是有序的，其他也是如此。

这启示我们可以在常规二分查找的时候查看当前 mid 为分割位置分割出来的两个部分 [l, mid] 和 [mid + 1, r] 哪个部分是有序的，并根据有序的那个部分确定我们该如何改变二分查找的上下界，因为我们能够根据有序的那部分判断出 target 在不在这个部分：

如果 [l, mid - 1] 是有序数组，且 target 的大小满足 [nums[l],nums[mid])，则我们应该将搜索范围缩小至 [l, mid - 1]，否则在 [mid + 1, r] 中寻找。
如果 [mid, r] 是有序数组，且 target 的大小满足 (nums[mid+1]，则我们应该将搜索范围缩小至 [mid + 1, r]，否则在 [l, mid - 1] 中寻找。

需要注意的是，二分的写法有很多种，所以在判断 target 大小与有序部分的关系的时候可能会出现细节上的差别。

class Solution {
public:
    int search(vector& nums, int target) {
        int n = (int)nums.size();
        if (!n) {
            return -1;
        }
        if (n == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) return mid;
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[n - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

时间复杂度： O(log⁡n)，其中 n 为 nums 数组的大小。整个算法时间复杂度即为二分查找的时间复杂度 O(log⁡n)。

空间复杂度： O(1)。我们只需要常数级别的空间存放变量。

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

解法一：二分查找

思路与算法

一个不包含重复元素的升序数组在经过旋转之后，可以得到下面可视化的折线图：

其中横轴表示数组元素的下标，纵轴表示数组元素的值。图中标出了最小值的位置，是我们需要查找的目标。

我们考虑数组中的最后一个元素 x：在最小值右侧的元素（不包括最后一个元素本身），它们的值一定都严格小于 x；而在最小值左侧的元素，它们的值一定都严格大于 x。因此，我们可以根据这一条性质，通过二分查找的方法找出最小值。

在二分查找的每一步中，左边界为wlow，右边界为 high，区间的中点为 pivot，最小值就在该区间内。我们将中轴元素 nums[pivot]与右边界元素 nums[high]进行比较，可能会有以下的三种情况：

第一种情况是 nums[pivot]

因为此时的pivot是最小的可能性无法排除，所以high=pivot;

第二种情况是 nums[pivot]>nums[high]。如下图所示，这说明 nums[pivot]是最小值左侧的元素，因此我们可以忽略二分查找区间的左半部分。

此时已知nums[pivot]至少比nums[high]打，因此已经不是最小的了，所以low=pivot+1

由于数组不包含重复元素，并且只要当前的区间长度不为 1，pivot 就不会与 high重合；而如果当前的区间长度为 1，这说明我们已经可以结束二分查找了。因此不会存在 nums[pivot]=nums[high]的情况。

当二分查找结束时，我们就得到了最小值所在的位置。

class Solution {
public:
    int findMin(vector& nums) {
        int low=0;
        int high=nums.size()-1;
        while(low
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时间复杂度：时间复杂度为 O(log⁡n)，其中 n 是数组 nums 的长度。在二分查找的过程中，每一步会忽略一半的区间，因此时间复杂度为 O(log⁡n)

空间复杂度：O(1)。

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

解法： 如果题目没有要求时间复杂度是O(log(m + n)),则可以采用暴力解法，使用归并排序，将两个有序数组合并为一个有序数组，然后找到这个有序数组的中位数即可。但是题目规定时间复杂度是log级别，可以想到要用二分法去筛选。

中位数有这样的特点，它的左边的数一定都是比它小的数，它的右边的数一定都是比他大的数。因此，如果每次能筛选一半的数，那个就能达到这个时间复杂度。

而找到第k个位置的数时，设置n=k/2,因为nums1和nums2都是有序的，所以如果nums1的第n个位置的数，小于nums2的第n个位置的数，那么可以确定，nums1的前n个数一定不是第k个位置的数，就把这n个数排除了，然后num1从排除的数之后那个数作为起点，求第k个数就变成求第（k-n）位的数，然后继续采用相同的方法，将其除以2，再排除。这明显是一个重复的过程，因此用递归来完成，递归的出口：其中一个数组为空，或者所求的第k和位置的数经过不断除以2，最后变成第1个位置，只要返回两个数组第一个位置中较小的数即可。（其中要注意数组的下标时从0开始的）

此时如果求第4位置的数，将4/2=2，num1[2-1]=2,num2[2-1]=5,显然2<5,我们就可以舍弃数组1中的1和2，求第4位置的数，就变成求新的两个数组中第4-2=2个位置的数，2/2=1，num1[1-1]=3.num2[1-1]=4,3<4,因此，舍弃数组1中的3，此时数组1为空。又变成求新的两个数组中的第2-1=1个位置的数.因为数组1为空，就是求数组二的第一个数，为4.

用递归可以求得两个数组中第k个位置的数，那么怎么求中位数呢？需要分成数组长度是奇数或者偶数来讨论吗？其实需要，假设数组num1的长度是len1,num2的长度是len2，假如len1+len2为偶数，那么其中位数为这两个数组形成的有序数列的（len1+len2+1）/2和（len1+len2+2）/2的位置上的和的值除以2。

但是同时可以观察到如果len1+len2为奇数的话，（len1+len2+1）/2和（len1+len2+2）/2这两个表达式的值是相同的，因此，我们可以不用讨论，直接使用总长度为偶数时使用的式子，而达到相同的效果。

栈

69. 20 有效的括号

解法：利用栈来解决，首先字符串为空或者长度为1，一定返回false；

然后便利字符串中的括号，如果是左括号则入栈，如果碰到右括号，如果栈中非空，并且栈顶有对应的左括号与其匹配，则弹栈;否则将右括号入栈；

最后如果栈为空，说明匹配，否则不匹配

class solution67 {
public:
    bool isValid(string s) {
        vectorstack;
        if(s.empty()||s.size()==1)
            return false;
        for( auto item:s){
            if(item=='('||item=='['||item=='{')
                stack.emplace_back(item);
            else if(item==')'){
                if(stack.empty()||stack.back()!='(')
                    stack.emplace_back(item);
                else
                    stack.pop_back();
            }
            else if(item==']'){
                if(stack.empty()||stack.back()!='[')
                    stack.emplace_back(item);
                else
                    stack.pop_back();

            }
            else if(item=='}'){
                if(stack.empty()||stack.back()!='{')
                    stack.emplace_back(item);
                else
                    stack.pop_back();
            }
        }
        return stack.empty();
    }
};

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

时间复杂度：O(n)

空间复杂度：O(n)

70. 155 最小栈

解法：用一个辅助栈 min_stack，用于存获取 stack 中最小值。

算法流程：

push() 方法： 每当push()新值进来时，如果 小于等于 min_stack 栈顶值，则一起 push() 到 min_stack，即更新了栈顶最小值；
pop() 方法： 判断将 pop() 出去的元素值是否是 min_stack 栈顶元素值（即最小值），如果是则将 min_stack 栈顶元素一起 pop()，这样可以保证 min_stack 栈顶元素始终是 stack 中的最小值。
getMin()方法： 返回 min_stack 栈顶即可。
min_stack 作用分析：

min_stack 等价于遍历 stack所有元素，把升序的数字都删除掉，留下一个从栈底到栈顶降序的栈。
相当于给 stack 中的降序元素做了标记，每当 pop() 这些降序元素，min_stack 会将相应的栈顶元素 pop() 出去，保证其栈顶元素始终是 stack 中的最小元素。

class MinStack {
public:
    ::stack stack;
    ::stack min_stack;
    MinStack() {
    }
    
    void push(int val) {
        stack.push(val);
        if(min_stack.empty()||val<=min_stack.top()){
            min_stack.push(val);
        }
    }
    
    void pop() {
        int val=stack.top();
        stack.pop();
        if(val==min_stack.top()){
            min_stack.pop();
        }
    }
    
    int top() {
        return stack.top();
    }
    
    int getMin() {
        return min_stack.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

时间复杂度 O(1) ：压栈，出栈，获取最小值的时间复杂度都为 O(1) 。
空间复杂度 O(N) ：包含 N 个元素辅助栈占用线性大小的额外空间。

71. 394 字符串解码

解法1：辅助栈

• 首先创建两个栈，数字栈nums和字符串栈str
• 遍历该字符串s，对于其中一个字符c，若为数字，则入数字栈;若为字符[a-z,A-Z]，则继续遍历，知道该位置不为字符类型，将其拼接成字符串，入str栈；
• 若c为"[“，则入str栈，若c为”]"。那么str栈不断弹栈，直到遇到“[”。此时栈中的字符串必须按照逆序拼接组成新的字符串。
• 然后取得数字栈顶数字n，将该字符串重复n次后，加入str栈中“[”必定和数字配对，因此若出现“[”，数字栈顶必有数字
• 最后遍历结束后，将str栈中元素顺序拼接就能得到结果

代码：

class solution72 {
public:
    vectornums;
    vectorstr;
    string laststr="";
    string decodeString(string s) {
        int i=0;
        while(i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

时间复杂度：O(S)
空间复杂度：O(S)

解法2:递归

见官方题解：394. 字符串解码 - 力扣（LeetCode）

72. 739 每日温度

解法一：单调栈

可以维护一个存储下标的单调栈，从栈底到栈顶的下标对应的温度列表中的温度依次递减。如果一个下标在单调栈里，则表示尚未找到下一次温度更高的下标。

正向遍历温度列表。对于温度列表中的每个元素 temperatures[i]，如果栈为空，则直接将 i 进栈，如果栈不为空，则比较栈顶元素 prevIndex 对应的温度 temperatures[prevIndex] 和当前温度 temperatures[i]，如果 temperatures[i] > temperatures[prevIndex]，则将 prevIndex 移除，并将 prevIndex 对应的等待天数赋为 i - prevIndex，重复上述操作直到栈为空或者栈顶元素对应的温度小于等于当前温度，然后将 i 进栈。

为什么可以在弹栈的时候更新 ans[prevIndex] 呢？因为在这种情况下，即将进栈的 i 对应的 temperatures[i] 一定是 temperatures[prevIndex] 右边第一个比它大的元素，试想如果 prevIndex 和 i 有比它大的元素，假设下标为 j，那么 prevIndex 一定会在下标 j 的那一轮被弹掉。

由于单调栈满足从栈底到栈顶元素对应的温度递减，因此每次有元素进栈时，会将温度更低的元素全部移除，并更新出栈元素对应的等待天数，这样可以确保等待天数一定是最小的。

以下用一个具体的例子帮助读者理解单调栈。对于温度列表 [73,74,75,71,69,72,76,73]，单调栈 stack 的初始状态为空，答案 ans 的初始状态是 [0,0,0,0,0,0,0,0]，按照以下步骤更新单调栈和答案，其中单调栈内的元素都是下标，括号内的数字表示下标在温度列表中对应的温度。

当 i=0时，单调栈为空，因此将 0 进栈。

stack=[0(73)

ans=[0,0,0,0,0,0,0,0]

当 i=1 时，由于 74 大于 73，因此移除栈顶元素 0，赋值 ans[0]:=1−0，将 1 进栈。

stack=[1(74)]

ans=[1,0,0,0,0,0,0,0]

当 i=2 时，由于 75 大于 74，因此移除栈顶元素 1，赋值 ans[1]:=2−1，将 2进栈。

stack=[2(75)]

ans=[1,1,0,0,0,0,0,0]

当 i=3 时，由于 71小于 75，因此将 3 进栈。

stack=[2(75),3(71)]

ans=[1,1,0,0,0,0,0,0]

当 i=4 时，由于 69 小于 71，因此将 444 进栈。

stack=[2(75),3(71),4(69)]

ans=[1,1,0,0,0,0,0,0]

当 i=5 时，由于 72大于 69 和 71，因此依次移除栈顶元素 4 和 3，赋值 ans[4]:=5−4和 ans[3]:=5−3，将 5 进栈。

stack=[2(75),5(72)]

ans=[1,1,0,2,1,0,0,0]

当 i=6时，由于 76 大于 72和 75，因此依次移除栈顶元素 5 和 2，赋值 ans[5]:=6−5 和 ans[2]:=6，将 6 进栈。

stack=[6(76)]

ans=[1,1,4,2,1,1,0,0]

当 i=7 时，由于 73小于 76，因此将 7 进栈。

stack=[6(76),7(73)]

ans=[1,1,4,2,1,1,0,0]

class Solution {
public:
    vector dailyTemperatures(vector& temperatures) {
        int n=temperatures.size();
        vectorans(n);
        stackstack;
        for(int i=0;itemperatures[stack.top()]){
                int preIndex=stack.top();
                ans[preIndex]=i-preIndex;
                stack.pop();
            }
            stack.push(i);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

时间复杂度：O(n)，其中 n 是温度列表的长度。正向遍历温度列表一遍，对于温度列表中的每个下标，最多有一次进栈和出栈的操作。

空间复杂度：O(n)，其中 n 是温度列表的长度。需要维护一个单调栈存储温度列表中的下标。

73. 84 柱状图中最大的矩形

解法：单调栈

要搞清楚这个过程，请大家一定要在纸上画图，搞清楚一些细节，这样在编码的时候就不容易出错了。

记录什么信息呢？记录高度是不是可以呢？其实是不够的，因为计算矩形还需要计算宽度，很容易知道宽度是由下标确定的，记录了下标其实对应的高度就可以直接从输入数组中得出，因此，应该记录的是下标。

我们就拿示例的数组 [2, 1, 5, 6, 2, 3] 为例：

1、一开始看到的柱形高度为 2 ，这个时候以这个 2 为高度的最大面积的矩形还不能确定，我们需要继续向右遍历，如下图。

2、然后看到到高度为 1 的柱形，这个时候以这个柱形为高度的矩形的最大面积还是不知道的。但是它之前的以 2 为高度的最大面积的矩形是可以确定的，这是因为这个 1 比 2 小 ，因为这个 1 卡在了这里 2 不能再向右边扩展了，如下图。

我们计算一下以 2 为高度的最大矩形的面积是 2。其实这个时候，求解这个问题的思路其实已经慢慢打开了。如果已经确定了一个柱形的高度，我们可以无视它，将它以虚框表示，如下图。

3、遍历到高度为 5 的柱形，同样的以当前看到柱形为高度的矩形的最大面积也是不知道的，因为我们还要看右边高度的情况。那么它的左右有没有可以确定的柱形呢？没有，这是因为 5 比 1 大，我们看后面马上就出现了 6，不管是 1 这个柱形还是 5 这个柱形，都还可以向右边扩展；

4、接下来，遍历到高度为 6 的柱形，同样的，以柱形 1、5、6 为高度的最大矩形面积还是不能确定下来；

5、再接下来，遍历到高度为 2 的柱形。

发现了一件很神奇的事情，高度为 6 的柱形对应的最大矩形的面积的宽度可以确定下来，它就是夹在高度为 5 的柱形和高度为 2 的柱形之间的距离，它的高度是 6，宽度是 1。

将可以确定的柱形设置为虚线。

接下来柱形 5 对应的最大面积的矩形的宽度也可以确定下来，它是夹在高度为 1 和高度为 2 的两个柱形之间的距离；

确定好以后，我们将它标成虚线。

我们发现了，只要是遇到了当前柱形的高度比它上一个柱形的高度严格小的时候，一定可以确定它之前的某些柱形的最大宽度，并且确定的柱形宽度的顺序是从右边向左边。
这个现象告诉我们，在遍历的时候需要记录的信息就是遍历到的柱形的下标，它一左一右的两个柱形的下标的差就是这个面积最大的矩形对应的最大宽度。

这个时候，还需要考虑的一个细节是，在确定一个柱形的面积的时候，除了右边要比当前严格小，其实还蕴含了一个条件，那就是左边也要比当前高度严格小。

那如果是左边的高度和自己相等怎么办呢？我们想一想，我们之前是只要比当前严格小，我们才可以确定一些柱形的最大宽度。只要是大于或者等于之前看到的那一个柱形的高度的时候，我们其实都不能确定。

因此我们确定当前柱形对应的宽度的左边界的时候，往回头看的时候，一定要找到第一个严格小于我们要确定的那个柱形的高度的下标。这个时候 中间那些相等的柱形其实就可以当做不存在一样。因为它对应的最大矩形和它对应的最大矩形其实是一样的。

说到这里，其实我们的思路已经慢慢清晰了。

我们在遍历的时候，需要记录的是下标，如果当前的高度比它之前的高度严格小于的时候，就可以直接确定之前的那个高的柱形的最大矩形的面积，为了确定这个最大矩形的左边界，我们还要找到第一个严格小于它的高度的矩形，向左回退的时候，其实就可以当中间这些柱形不存在一样。

这是因为我们就是想确定 6 的宽度，6 的宽度确定完了，其实我们就不需要它了，这个 5 的高度和这个 5 的高度确定完了，我们也不需要它了。

我们在缓存数据的时候，是从左向右缓存的，我们计算出一个结果的顺序是从右向左的，并且计算完成以后我们就不再需要了，符合后进先出的特点。因此，我们需要的这个作为缓存的数据结构就是栈。

当确定了一个柱形的高度的时候，我们就将它从栈顶移出，所有的柱形在栈中进栈一次，出栈一次，一开始栈为空，最后也一定要让栈为空，表示这个高度数组里所有的元素都考虑完了。

6、最后遍历到最后一个柱形，即高度为 3 的柱形。

（一次遍历完成以后。接下来考虑栈里的元素全部出栈。）

接下来我们就要依次考虑还在栈里的柱形的高度。和刚才的方法一样，只不过这个时候右边没有比它高度还小的柱形了，这个时候计算宽度应该假设最右边还有一个下标为 len （这里等于 6） 的高度为 0 （或者 0.5，只要比 1 小）的柱形。

7、下标为 5 ，即高度为 3 的柱形，左边的下标是 4 ，右边的下标是 6 ，因此宽度是 6 - 4 - 1 = 1（两边都不算，只算中间的距离，所以减 1）；算完以后，将它标为虚线。

8、下标为 4 ，高度为 2 的柱形，左边的下标是 1 ，右边的下标是 6 ，因此宽度是 6 - 1 - 1 = 4；算完以后，将它标为虚线。

9、最后看下标为 1，高度为 1 的矩形，它的左边和右边其实都没有元素了，它就是整个柱形数组里高度最低的柱形，计算它的宽度，就是整个柱形数组的长度。

到此为止，所有的柱形高度对应的最大矩形的面积就都计算出来了。

在具体的实现过程中，可以在height的头尾各插入一个0，保证栈中的所有元素都是可以出栈的

class Solution {
public:
    int largestRectangleArea(vector& heights) {
        int ans=0;
        vectorst;
        heights.insert(heights.begin(),0);
        heights.push_back(0);
        for(int i=0;iheights[i]){
                int cur=st.back();
                st.pop_back();
                int left=st.back();
                int right=i;
                ans=max(ans,(right-left-1)*heights[cur]);
            }
            st.push_back(i);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

时间复杂度：O(1)

空间复杂度：O(n)

堆

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

解法：改进版的快排

我们可以用快速排序来解决这个问题，先对原数组排序，再返回倒数第 k 个位置，这样平均时间复杂度是 O(nlog⁡n)，但其实我们可以做的更快。

首先我们来回顾一下快速排序，这是一个典型的分治算法。我们对数组 a[l⋯r] 做快速排序的过程是（参考《算法导论》）：

分解： 将数组 a[l⋯r]「划分」成两个子数组 a[l⋯q−1]、a[q+1⋯r]，使得 a[l⋯q−1] 中的每个元素小于等于 a[q]，且 a[q] 小于等于 a[q+1⋯r] 中的每个元素。其中，计算下标 q 也是「划分」过程的一部分。
解决： 通过递归调用快速排序，对子数组 a[l⋯q−1]和 a[q+1⋯r]进行排序。
合并： 因为子数组都是原址排序的，所以不需要进行合并操作，a[l⋯r]已经有序。
上文中提到的 「划分」 过程是：从子数组 a[l⋯r]中选择任意一个元素 x作为主元，调整子数组的元素使得左边的元素都小于等于它，右边的元素都大于等于它， x 的最终位置就是 q。
由此可以发现每次经过「划分」操作后，我们一定可以确定一个元素的最终位置，即 x的最终位置为 q，并且保证 a[l⋯q−1]中的每个元素小于等于 a[q]，且 a[q] 小于等于 a[q+1⋯r]中的每个元素。所以只要某次划分的 q 为第 k-1 个下标的时候，我们就已经找到了答案。 我们只关心这一点，至于 a[l⋯q−1]和 a[q+1⋯r]是否是有序的，我们不关心。

因此我们可以改进快速排序算法来解决这个问题：在分解的过程当中，我们会对子数组进行划分，如果划分得到的 q 正好就是我们需要的下标，就直接返回 a[q]；否则，如果 q 比目标下标大，就递归左子区间，否则递归右子区间。这样就可以把原来递归两个区间变成只递归一个区间，提高了时间效率。这就是「快速选择」算法。

我们知道快速排序的性能和「划分」出的子数组的长度密切相关。直观地理解如果每次规模为 n 的问题我们都划分成 1 和 n−1，每次递归的时候又向 n−1的集合中递归，这种情况是最坏的，时间代价是 O(n ^ 2)。我们可以引入随机化来加速这个过程，它的时间代价的期望是 O(n)，证明过程可以参考「《算法导论》9.2：期望为线性的选择算法」。需要注意的是，这个时间复杂度只有在 随机数据 下才成立，而对于精心构造的数据则可能表现不佳。因此我们这里并没有真正地使用随机数，而是使用双指针的方法，这种方法能够较好地应对各种数据。

注意，我最初使用填坑法来实现快排的时候，基准值选择的是最左边的值，这样对有非常多的重复元素的情况下超时，如示例40

代码：

class Solution {
public:
   int quickSelect(vector&nums,int left,int right,int k){
        int pivotIndex = left + std::rand() % (right - left + 1);  // 随机选择枢轴
        int pivotValue = nums[pivotIndex];
        std::swap(nums[pivotIndex], nums[left]); 
        int i=left,j=right;
        while(ipivotValue)
                i++;
            nums[j]=nums[i];
        }
        nums[i]=pivotValue;
        if(i==k-1)
            return nums[i];
        else if(i& nums, int k) {
        return quickSelect(nums,0,nums.size()-1,k);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

时间复杂度:O(n)

空间复杂度：O(log⁡n)，递归使用栈空间的空间代价的期望为 O(log⁡n)。

解法二：小根堆

c++的stl库中的priority_queue可以实现小根队 【或者自己实现】

class Solution {
public:
   
    int findKthLargest(vector& nums, int k) {
       priority_queue,greater>que;
       for(auto n:nums){
           que.push(n);
           if(que.size()>k){
               que.pop();
           }
       }
       return que.top();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

自己实现一个大根队，做k-1次删除操作之后，就是第k大的

class Solution {
public:
    void maxHeapify(vector& a, int i, int heapSize) {
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        } 
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a[i], a[largest]);
            maxHeapify(a, largest, heapSize);
        }
    }

    void buildMaxHeap(vector& a, int heapSize) {
        for (int i = heapSize / 2; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        } 
    }

    int findKthLargest(vector& nums, int k) {
        int heapSize = nums.size();
        buildMaxHeap(nums, heapSize);
        for (int i = nums.size() - 1; i >= nums.size() - k + 1; --i) {
            swap(nums[0], nums[i]);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

时间复杂度：O(nlogn)

空间复杂度：O(n)

75. 347 前k个高频元素

解法：堆

首先遍历整个数组，并使用哈希表记录每个数字出现的次数，并形成一个「出现次数数组」。找出原数组的前 k 个高频元素，就相当于找出「出现次数数组」的前 k 大的值。

最简单的做法是给「出现次数数组」排序。但由于可能有 O(N)个不同的出现次数（其中 N 为原数组长度），故总的算法复杂度会达到 O(Nlog⁡N)，不满足题目的要求。

在这里，我们可以利用堆的思想：建立一个小顶堆，然后遍历「出现次数数组」：

如果堆的元素个数小于 k，就可以直接插入堆中。
如果堆的元素个数等于k，则检查堆顶与当前出现次数的大小。如果堆顶更大，说明至少有 kkk 个数字的出现次数比当前值大，故舍弃当前值；否则，就弹出堆顶，并将当前值插入堆中。
遍历完成后，堆中的元素就代表了「出现次数数组」中前 k 大的值。

struct Compare {
    bool operator()(const pair& m, const pair& n) {
        return m.second > n.second; // 基于第二个元素的比较逻辑
    }
};
class Solution {
public:
    vector topKFrequent(vector& nums, int k) {
        unordered_mapoccur;
        for(auto &v:nums){
            occur[v]++;
        }
        //pair 第一个元素是数组的值，第二个元素是出现的次数
        priority_queue,vector>,Compare>que;
        for(auto&[num,cnt]:occur){
            if(que.size()==k){
                if(que.top().secondres;
        while(!que.empty()){
            res.emplace_back(que.top().first);
            que.pop();
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

时间复杂度：O(Nlog⁡k)，其中 N 为数组的长度。我们首先遍历原数组，并使用哈希表记录出现次数，每个元素需要 O(1)的时间，共需 O(N)的时间。随后，我们遍历「出现次数数组」，由于堆的大小至多为 k，因此每次堆操作需要 O(log⁡k) 的时间，共需 O(Nlog⁡k) 的时间。二者之和为 O(Nlog⁡k)O(N\log k)O(Nlogk)。
空间复杂度：O(N)。哈希表的大小为 O(N)，而堆的大小为 O(k)，共计为 O(N)。

解法二：基于快排

见：347. 前 K 个高频元素 - 力扣（LeetCode）

class Solution {
public:
    void qsort(vector>& v, int start, int end, vector& ret, int k) {
        int picked = rand() % (end - start + 1) + start;
        swap(v[picked], v[start]);

        int pivot = v[start].second;
        int index = start;
        for (int i = start + 1; i <= end; i++) {
            // 使用双指针把不小于基准值的元素放到左边，
            // 小于基准值的元素放到右边
            if (v[i].second >= pivot) {
                swap(v[index + 1], v[i]);
                index++;
            }
        }
        swap(v[start], v[index]);

        if (k <= index - start) {
            // 前 k 大的值在左侧的子数组里
            qsort(v, start, index - 1, ret, k);
        } else {
            // 前 k 大的值等于左侧的子数组全部元素
            // 加上右侧子数组中前 k - (index - start + 1) 大的值
            for (int i = start; i <= index; i++) {
                ret.push_back(v[i].first);
            }
            if (k > index - start + 1) {
                qsort(v, index + 1, end, ret, k - (index - start + 1));
            }
        }
    }

    vector topKFrequent(vector& nums, int k) {
        // 获取每个数字出现次数
        unordered_map occurrences;
        for (auto& v: nums) {
            occurrences[v]++;
        }

        vector> values;
        for (auto& kv: occurrences) {
            values.push_back(kv);
        }
        vector ret;
        qsort(values, 0, values.size() - 1, ret, k);
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

76. 295 数据流的中位数

解法：两个堆，大顶堆保存小于等于中位数的数，小顶堆保存大于等于中位数的值

一句话题解：左边小顶堆，右边大顶堆，小的加右边，大的加左边，平衡俩堆数，新加就弹出，堆顶给对家，奇数取多的，偶数取除2.

根据以上思路，可以将数据流保存在一个列表中，并在添加元素时 保持数组有序 。此方法的时间复杂度为 O(N) ，其中包括： 查找元素插入位置 O(log⁡N)) （二分查找）、向数组某位置插入元素 O(N) （插入位置之后的元素都需要向后移动一位）。

借助 堆 可进一步优化时间复杂度。

建立一个 小顶堆 A 和 大顶堆 B ，各保存列表的一半元素，且规定：

A 保存 较大 的一半，长度为 $\frac{N}{2}$ （ N 为偶数）或 $\frac{N+1}{2} $（ N 为奇数）。
B 保存 较小 的一半，长度为 $\frac{N}{2} $ （ N 为偶数）或 $\frac{N-1}{2} $（ N 为奇数）。
随后，中位数可仅根据 A,B 的堆顶元素计算得到。

设元素总数为 N=m+n ，其中 m 和 n 分别为 A和 B 中的元素个数。

函数 addNum(num) ：

当 m=n（即 N 为 偶数）：需向 A 添加一个元素。实现方法：将新元素 num 插入至 B ，再将B 堆顶元素插入至 A 。

即为了保证m=n+1,此时添加的元素最终应该在A中，但是其有可能属于B，因此其先加入B,再将B中的最大值加入A

当 m≠n（即 N 为 奇数）：需向 B 添加一个元素。实现方法：将新元素 num 插入至 A ，再将 A 堆顶元素插入至 B 。

即为了保证m=n,此时添加的元素最终应该在B中，但是其有可能属于A，因此其先加入A,再将A中的最小值加入B

假设插入数字 num遇到情况 1. 。由于 num 可能属于 “较小的一半” （即属于 B ），因此不能将 nums 直接插入至 A 。而应先将 num 插入至 B ，再将B 堆顶元素插入至 A 。这样就可以始终保持 A 保存较大一半、 B 保存较小一半。

class MedianFinder {
public:
    priority_queue,greater>Left;//小顶堆记录较大的
    priority_queue,less>Right;//大顶堆记录较小的
    MedianFinder() {

    }
    
    void addNum(int num) {
        if(Left.size()!=Right.size()){
            Left.push(num);
            Right.push(Left.top());
            Left.pop();
        }  
        else{
            Right.push(num);
            Left.push(Right.top());
            Right.pop();
        }
    }
    
    double findMedian() {
        return Left.size()!=Right.size()?Left.top():(Left.top()+Right.top())/2.0;
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

时间复杂度 O(log⁡N)：
查找中位数 O(1) ： 获取堆顶元素使用 O(1) 时间。
添加数字 O(log⁡N ： 堆的插入和弹出操作使用 O(log⁡N) 时间。
空间复杂度 O(N) ： 其中 N 为数据流中的元素数量，小顶堆 A 和大顶堆 B 最多同时保存 N 个元素。

贪心算法

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

解法1：一次遍历

假设给定的数组为：[7, 1, 5, 3, 6, 4]

我们来假设自己来购买股票。随着时间的推移，每天我们都可以选择出售股票与否。那么，假设在第 i 天，如果我们要在今天卖股票，那么我们能赚多少钱呢？

显然，如果我们真的在买卖股票，我们肯定会想：如果我是在历史最低点买的股票就好了，在题目中，我们只要用一个变量记录一个历史最低价格 minPrice，我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minPrice。

因此，我们只需要遍历价格数组一遍，记录历史最低点，然后在每一天考虑这么一个问题：如果我是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，我们就得到了最好的答案。

代码：

class Solution {
public:
    int maxProfit(vector& prices) {
        int len=prices.size();
        if(len<2)
        return 0;
        int minPrice=prices[0],maxProfit=0;
        for(int p:prices){
            maxProfit=max(maxProfit,p-minPrice);
            minPrice=min(p,minPrice);
        }
        return maxProfit;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度：O(n) 只遍历了一次

空间复杂度：O(1) 只使用了常量个变量。

解法2: 动态规划

思路：题目只问最大利润，没有问这几天具体哪一天买、哪一天卖，因此可以考虑使用 动态规划 的方法来解决。

买卖股票有约束，根据题目意思，有以下两个约束条件：

条件 1：你不能在买入股票前卖出股票；
条件 2：最多只允许完成一笔交易。
因此 当天是否持股 是一个很重要的因素，而当前是否持股和昨天是否持股有关系，为此我们需要把 是否持股 设计到状态数组中。

dp[i][j]：下标为 i 这一天结束的时候，手上持股状态为 j 时，我们持有的现金数。换种说法：dp[i][j] 表示天数 [0, i] 区间里，下标 i 这一天状态为 j 的时候能够获得的最大利润。其中：

j = 0，表示当前不持股；
j = 1，表示当前持股。

注意：下标为 i 的这一天的计算结果包含了区间 [0, i] 所有的信息，因此最后输出 dp[len - 1][0]。

使用「现金数」这个说法主要是为了体现 买入股票手上的现金数减少，卖出股票手上的现金数增加 这个事实；
「现金数」等价于题目中说的「利润」，即先买入这只股票，后买入这只股票的差价；

推导状态转移方程：

dp[i][0]：规定了今天不持股，有以下两种情况：

• 昨天不持股，今天什么都不做；

• 昨天持股，今天卖出股票（现金数增加），

dp[i][1]：规定了今天持股，有以下两种情况：

• 昨天持股，今天什么都不做（现金数与昨天一样）；
• 昨天不持股，今天买入股票（注意：只允许交易一次，因此手上的现金数就是当天的股价的相反数）。

代码：

class Solution {
public:
    int maxProfit(vector& prices) {
        int len=prices.size();
        if(len<2)
        return 0;
       int dp[len][2];
        // dp[i][0] 下标为 i 这天结束的时候，不持股，手上拥有的现金数
        // dp[i][1] 下标为 i 这天结束的时候，持股，手上拥有的现金数
       dp[0][0]=0;
       dp[0][1]=-prices[0];
       for(int i=1;i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 时间复杂度：O(N)，遍历股价数组可以得到最优解；
• 空间复杂度：O(N)，状态数组的长度为 N。

78. 55 跳跃游戏

解法：贪心算法

我们可以用贪心的方法解决这个问题。

设想一下，对于数组中的任意一个位置 y，我们如何判断它是否可以到达？根据题目的描述，只要存在一个位置 x，它本身可以到达，并且它跳跃的最大长度为 x+nums[x]，这个值大于等于 yyy，即 x+nums[x]≥y，那么位置 y 也可以到达。

换句话说，对于每一个可以到达的位置 x，它使得 x+1,x+2,⋯ ,x+nums[x] 这些连续的位置都可以到达。

这样以来，我们依次遍历数组中的每一个位置，并实时维护 最远可以到达的位置。对于当前遍历到的位置 x，如果它在 最远可以到达的位置 的范围内，那么我们就可以从起点通过若干次跳跃到达该位置，因此我们可以用 x+nums[x] 更新 最远可以到达的位置。

在遍历的过程中，如果 最远可以到达的位置 大于等于数组中的最后一个位置，那就说明最后一个位置可达，我们就可以直接返回 True 作为答案。反之，如果在遍历结束后，最后一个位置仍然不可达，我们就返回 False 作为答案。

以题目中的示例一

[2, 3, 1, 1, 4]
为例：

我们一开始在位置 0，可以跳跃的最大长度为 2，因此最远可以到达的位置被更新为 2；

我们遍历到位置 1，由于 1≤2，因此位置 1 可达。我们用 1 加上它可以跳跃的最大长度 3，将最远可以到达的位置更新为 4。由于 4 大于等于最后一个位置 4，因此我们直接返回 True。

我们再来看看题目中的示例二

[3, 2, 1, 0, 4]
我们一开始在位置 0，可以跳跃的最大长度为 3，因此最远可以到达的位置被更新为 3；

我们遍历到位置 1，由于 1≤3，因此位置 1可达，加上它可以跳跃的最大长度 2 得到 3，没有超过最远可以到达的位置；

位置 2、位置 3 同理，最远可以到达的位置不会被更新；

我们遍历到位置 4，由于 4>3，因此位置 4 不可达，我们也就不考虑它可以跳跃的最大长度了。

在遍历完成之后，位置 4 仍然不可达，因此我们返回 False。

class Solution {
public:
    bool canJump(vector& nums) {
        int n=nums.size();
        int rightMost=0;
        for(int i=0;i=n-1)
                return true;
            }
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时间复杂度：O(n)，其中 n 为数组的大小。只需要访问 nums 数组一遍，共 n 个位置。

空间复杂度：O(1)，不需要额外的空间开销。

79. 45 跳跃游戏II

解法：贪心 正向查找可到达的最大位置

如果我们「贪心」地进行正向查找，每次找到可到达的最远位置，就可以在线性时间内得到最少的跳跃次数。

例如，对于数组 [2,3,1,2,4,2,3]，初始位置是下标 0，从下标 0 出发，最远可到达下标 2。下标 0 可到达的位置中，下标 1 的值是 3，从下标 1 出发可以达到更远的位置，因此第一步到达下标 1。

从下标 1 出发，最远可到达下标 4。下标 1 可到达的位置中，下标 4 的值是 4 ，从下标 4 出发可以达到更远的位置，因此第二步到达下标 4。

在具体的实现中，我们维护当前能够到达的最大下标位置，记为边界。我们从左到右遍历数组，到达边界时，更新边界并将跳跃次数增加 1。

在遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。如果访问最后一个元素，在边界正好为最后一个位置的情况下，我们会增加一次「不必要的跳跃次数」，因此我们不必访问最后一个元素。

end 维护的是当前这一跳能达到的最右位置，若要超过该位置必须要进行一次跳跃，因此需将跳跃次数加1，并更新这次跳跃能到达的最右位置

class Solution {
public:
    int jump(vector& nums) {
        int max_far=0;//目前能够跳到的最远位置
        int step=0;//跳跃次数
        int end=0;//上次跳跃可达范围右边界（下次的最右起跳点）
        for(int i=0;i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

80. 763 划分字母区间

解法：贪心算法

由于同一个字母只能出现在同一个片段，显然同一个字母的第一次出现的下标位置和最后一次出现的下标位置必须出现在同一个片段。因此需要遍历字符串，得到每个字母最后一次出现的下标位置。

在得到每个字母最后一次出现的下标位置之后，可以使用贪心的方法将字符串划分为尽可能多的片段，具体做法如下。

从左到右遍历字符串，遍历的同时维护当前片段的开始下标 start 和结束下标end，初始时 start=end=0。

对于每个访问到的字母 c，得到当前字母的最后一次出现的下标位置 end ，则当前片段的结束下标一定不会小于 end，因此令 $\text{end}=\max (\text{end},{\text{end}}_c)$。

当访问到下标 end 时，当前片段访问结束，当前片段的下标范围是[start,end]，长度为 end−start+1，将当前片段的长度添加到返回值，然后令 start=end+1，继续寻找下一个片段。

重复上述过程，直到遍历完字符串。

上述做法使用贪心的思想寻找每个片段可能的最小结束下标，因此可以保证每个片段的长度一定是符合要求的最短长度，如果取更短的片段，则一定会出现同一个字母出现在多个片段中的情况。由于每次取的片段都是符合要求的最短的片段，因此得到的片段数也是最多的。

由于每个片段访问结束的标志是访问到下标end，因此对于每个片段，可以保证当前片段中的每个字母都一定在当前片段中，不可能出现在其他片段，可以保证同一个字母只会出现在同一个片段。

class Solution {
public:
    vector partitionLabels(string s) {
        int lastIndex[26];
        int n=s.size();
        for(int i=0;iresult;
        int start=0,end=0;
        for(int i=0;i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间复杂度：O(n)，其中 n 是字符串的长度。需要遍历字符串两次，第一次遍历时记录每个字母最后一次出现的下标位置，第二次遍历时进行字符串的划分。

空间复杂度：O(∣Σ∣)，其中 是字符串中的字符集。这道题中，字符串只包含小写字母，因此 ∣Σ∣=26|。

动态规划

81. 70 爬楼梯

解法：动态规划

我们用 f(x) 表示爬到第 x 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子：

f(x)=f(x−1)+f(x−2)

它意味着爬到第 x 级台阶的方案数是爬到第 x−1 级台阶的方案数和爬到第 x−2 级台阶的方案数的和。很好理解，因为每次只能爬 1 级或 2 级，所以 f(x) 只能从 f(x−1)和 f(x−2)转移过来，而这里要统计方案总数，我们就需要对这两项的贡献求和。

以上是动态规划的转移方程，下面我们来讨论边界条件。我们是从第 000 级开始爬的，所以从第 0 级爬到第 0 级我们可以看作只有一种方案，即 f(0)=1；从第 0 级到第 1 级也只有一种方案，即爬一级，f(1)=1。这两个作为边界条件就可以继续向后推导出第 nnn 级的正确结果。我们不妨写几项来验证一下，根据转移方程得到 f(2)=2，f(3)=3，f(4)=5，……，我们把这些情况都枚举出来，发现计算的结果是正确的。

我们不难通过转移方程和边界条件给出一个时间复杂度和空间复杂度都是 O(n) 的实现，使用dp数组记录，dp[n]表示爬到第n阶需要的次数。

class Solution {
public:
    int climbStairs(int n) {
       vectordp(n+1,0);
       dp[0]=1;
       dp[1]=1;
       for(int i=2;i<=n;i++)
       {
        dp[i]=dp[i-1]+dp[i-2];
       }
       return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度：循环执行 n 次，每次花费常数的时间代价，故渐进时间复杂度为 O(n)。

空间复杂度：这里只用了常数个变量作为辅助空间，故渐进空间复杂度为 O(1)。

但是由于这里的 f(x)只和 f(x−1) 与 f(x−2)有关，所以我们可以用「滚动数组思想」把空间复杂度优化成 O(1)。下面的代码中给出的就是这种实现。

class Solution {
public:
    int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

82. 198 杨辉三角

解法：杨辉三角，除了第一行外，每一行的第一个数以及最后一个数都为1，其他的为上一行的该位置以及下一个位置之和。因此可以进行双重循环$result[j][i]==result[j-1][i-1]+result[j][i]||result[j][i]==0（第一个或者最后一个数字）$

注意：vector中需要使用resize定义vector数组的大小，否则不能进行随机访问

代码：

class Solution {
public:
    vector> generate(int numRows) {
        vector>result(numRows);
        result[0].push_back(1);
        for(int j=1;j
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

时间复杂度：O（n^2）

空间复杂度：O（1）

83. 198 打家劫舍

解法：动态规划
首先考虑最简单的情况。如果只有一间房屋，则偷窃该房屋，可以偷窃到最高总金额。如果只有两间房屋，则由于两间房屋相邻，不能同时偷窃，只能偷窃其中的一间房屋，因此选择其中金额较高的房屋进行偷窃，可以偷窃到最高总金额。

如果房屋数量大于两间，应该如何计算能够偷窃到的最高总金额呢？对于第 k 间房屋，有两个选项：

1. 偷窃第 k间房屋，那么就不能偷窃第 k−1间房屋，偷窃总金额为前 k−2 间房屋的最高总金额与第 k 间房屋的金额之和。

2. 不偷窃第 k 间房屋，偷窃总金额为前 k−1 间房屋的最高总金额。

在两个选项中选择偷窃总金额较大的选项，该选项对应的偷窃总金额即为前 kkk 间房屋能偷窃到的最高总金额。

用dp[i] 表示前 i间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程：

$$dp[i]=max(dp[i-2]+nums[i],dp[i-1])$$
边界条件为：

$$\{\begin{array}{ll}\text{dp}[0]=\text{nums}[0]& 只有一间房屋，则偷窃该房屋\\ \text{dp}[1]=\max (\text{nums}[0],\text{nums}[1])& 只有两间房屋，选择其中金额较高的房屋进行偷窃\end{array}$$

最终的答案即为 dp[n−1]，其中 n 是数组的长度。

class Solution {
public:
    int rob(vector& nums) {
        int n=nums.size();
        if(n==1)
        return nums[0];
        if(n==2)
        return max(nums[0],nums[1]);
        vectordp(n,0);
        dp[0]=nums[0];
        dp[1]=max(nums[0],nums[1]);
        for(int i=2;i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

时间复杂度：O(n)，其中 n 是数组长度。只需要对数组遍历一次。

空间复杂度：O(n)O(1)O(1)。

使用滚动数组，可以只存储前两间房屋的最高总金额，而不需要存储整个数组的结果，因此空间复杂度是 O(1)。

class Solution {
public:
    int rob(vector& nums) {
        if (nums.empty()) {
            return 0;
        }
        int size = nums.size();
        if (size == 1) {
            return nums[0];
        }
        int first = nums[0], second = max(nums[0], nums[1]);
        for (int i = 2; i < size; i++) {
            int temp = second;
            second = max(first + nums[i], second);
            first = temp;
        }
        return second;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

84. 279 完全平方数

解法：动态规划

我们可以依据题目的要求写出状态表达式：f[i]表示最少需要多少个数的平方来表示整数 i。

这些数必然落在区间 $[1,\sqrt{n}]$。我们可以枚举这些数，假设当前枚举到 jjj，那么我们还需要取若干数的平方，构成$i-j^2$。

此时我们发现该子问题和原问题类似，只是规模变小了。这符合了动态规划的要求，于是我们可以写出状态转移方程。

$$f[i]=1+\underset{j=1}{\overset{\lfloor \sqrt{i}\rfloor }{\min }}f[i-j^2]$$

其中 f[0]=0 为边界条件，实际上我们无法表示数字 0，只是为了保证状态转移过程中遇到 j恰为 $\sqrt{i}$ 的情况合法。

同时因为计算 f[i]时所需要用到的状态仅有$f[i-j^2]$，必然小于 i，因此我们只需要从小到大地枚举 i 来计算 f[i]即可。