Leetcode_and_JianZhi日常复习

动态规划

最优子结构：子问题的最优结果推导出更大规模问题的结果。并且子问题之间必须相互独立。

重叠的子问题：通过子问题的重叠性，实现从base case的状态转移。

遇到求最值的题目，往动态规划方向靠。

明确状态=>dp数组的物理意义=>明确状态转移=>明确base case。动态规划就是从最简单的base case，通过状态的链式反应不断地向后推导。

编辑距离

给你两个单词 word1和word2，请返回将 word1转换成word2所使用的最少操作数。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符
输入：word1 = “horse”, word2 = “ros”
输出：3
解释：
horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ‘e’)

递归自顶向下的解法

// 递归自顶向下的解法
// 备忘录记录重复结果
vector<vector<int>> memo;
int minDistance(string word1, string word2) {
    int m = word1.size(), n = word2.size();
    memo.resize(m, vector<int>(n, -1));

    return dp(word1, m - 1, word2, n - 1);
}

int dp(string word1, int i, string word2, int j) {
    // 1、base case
    if (i == -1)    return j + 1;
    if (j == -1)    return i + 1;

    if (memo[i][j] != -1)
        return memo[i][j];
	
   // 字符相同，无需任何操作
    if (word1[i] == word2[j])
        memo[i][j] =  dp(word1, i - 1, word2, j - 1);
	// 字符不同，进行增删改中次数最少的操作
    else {
        memo[i][j] = min(dp(word1, i, word2, j - 1) + 1, 
        min(dp(word1, i - 1, word2, j) + 1,
        dp(word1, i - 1, word2, j - 1) + 1));
    }

    return memo[i][j];
}

BM78 打家劫舍(单路打)

你是一个经验丰富的小偷，准备偷沿街的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家；如果偷了第二家，那么就不能偷第一家和第三家。
给定一个整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。
数据范围：数组长度满足$1≤n≤2×10^5$，数组中每个值满足$1≤num[i]≤5000$

输入：[1,2,3,4]
返回值：6

说明：最优方案是偷第 2，4 个房间

int n;
int rob(vector<int>& nums) {
    n=nums.size();
    vector<vector<int>> dp(n, vector<int>(2, -1));
    
    // 第1间不偷
    dp[0][0]=0;
    // 第1间偷
    dp[0][1]=nums[0];
    for (int i=1;i<n;i++) {
        dp[i][0]=max(dp[i-1][0], dp[i-1][1]);s
        dp[i][1]=dp[i-1][0]+nums[i];
    }
    
    return max(dp[n-1][0], dp[n-1][1]);
}

BM79 打家劫舍(循环路偷)

你是一个经验丰富的小偷，准备偷沿湖的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家，如果偷了第二家，那么就不能偷第一家和第三家。沿湖的房间组成一个闭合的圆形，即第一个房间和最后一个房间视为相邻。
给定一个长度为n的整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。

数据范围：数组长度满足$1≤n≤2×10^5$，数组中每个值满足$1≤nums[i]≤5000$
输入：[1,3,6]
返回值：6
说明：由于 1 和 3 是相邻的，因此最优方案是偷第 3 个房间

int n;
int rob(vector<int>& nums) {
    n=nums.size();
    // 偷第一间，不偷最后一间
    vector<vector<int>> dp1(n-1, vector<int>(2, 0));
    dp1[0][1]=nums[0];
    dp1[0][0]=0;
    dp1[1][0]=dp1[0][1];
    dp1[1][1]=0;
    for (int i=2;i<n-1;i++) {
        dp1[i][0]=max(dp1[i-1][0], dp1[i-1][1]);
        dp1[i][1]=dp1[i-1][0]+nums[i];
    }
    int max1 = max(dp1[n-2][0], dp1[n-2][1]);
    
    // 不偷第一间
    vector<vector<int>> dp2(n-1, vector<int>(2, -1));
    dp2[0][0]=0;
    dp2[0][1]=nums[1];
    for (int i=1;i<n-1;i++) {
        dp2[i][0]=max(dp2[i-1][0], dp2[i-1][1]);
        dp2[i][1]=dp2[i-1][0]+nums[i+1];
    }
    
    int max2=max(dp2[n-2][0], dp2[n-2][1]);
    
    
    return max(max1, max2);
}

地下城游戏

一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
为了尽快到达公主，骑士决定每次只向右或向下移动一步。

编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。
例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。

| -2 (K) |-3 | 3 |
| -5 | -10 | 1 |
| 10 | 30 | -5 (P) |

// 从结果作为base case出发的dp
int m, n;
vector<vector<int>> memo;
int calculateMinimumHP(vector<vector<int>>& dungeon) {
    m = dungeon.size();
    n = dungeon[0].size();
    memo.resize(m, vector<int>(n, -1));

    return dp(dungeon, 0, 0);
}
// 1、dp状态和dp的物理意义：dp(i, j)——从位置(i,j)到右下角位置最少需要多少生命值
// 2、状态转移方程：dp(i, j) = min(dp(i, j + 1), dp(i + 1, j)) - grid[i, j]
// 3、base case是结果
int dp(vector<vector<int>>& dungeon, int i, int j) {
    if (i == m || j == n)      return INT_MAX;
    if (i == m - 1 && j == n - 1)
        return (dungeon[i][j] <= 0 ? -dungeon[i][j] + 1:1);
    if (memo[i][j] != -1)
        return memo[i][j];

    int res = min(dp(dungeon, i + 1, j), 
    dp(dungeon, i, j + 1)) - dungeon[i][j];
    memo[i][j] = res <= 0 ? 1:res;

    return memo[i][j];
}

JZ14 剪绳子

给你一根长度为 n 的绳子，请把绳子剪成整数长的 m 段（ m 、 n 都是整数， n>1 并且 m>1 ， m <= n ），每段绳子的长度记为 k[1],…,k[m]。请问 k[1]×k[2]×…×k[m] 可能的最大乘积是多少？例如，当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18。
数据范围：$2≤n≤60$
进阶：空间复杂度 $O(1)$，时间复杂度 $O(n)$
输入：8
返回值：18
说明：
8 = 2+3+3, 2×3×3=18

dp[i]：长度为i的绳子可以被剪出的最大乘积是dp[i]。 dp[i] = max(dp[i], j*dp[i-j]);

int cutRope(int n) {
    vector<int> dp(n + 1, -1);
    dp[1] = 1, dp[2] = 2, dp[3] = 3;
    if (n <= 3) {
        return dp[n];
    }

    for (int i = 4; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            dp[i] = max(dp[i], j*dp[i-j]);
        }
    }

    return dp[n];

}

乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
子数组 是数组的连续子序列。
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

// 由于负数的存在，当出现负数时，需要交替计算最大值和最小值
// 维护一个最大值的变量即可
int imax=1, imin=1;
int res=INT_MIN;
int maxProduct(vector<int>& nums) {
    for (int i=0;i<nums.size();i++) {
        if (nums[i] < 0) {
            swap(imax, imin);
        }

        imax = max(nums[i], imax*nums[i]);
        imin = min(nums[i], imin*nums[i]);

        res = max(imax, res);
    }

    return res;
}

JZ42 连续子数组的最大和

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。
数据范围:$1 <= n <= 2×10^5, -100 <= a[i] <= 100$
要求:时间复杂度为 $O(n)$，空间复杂度为 $O(n)$
输入：[1,-2,3,10,-4,7,2,-5]
返回值：18
说明：经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18。

int FindGreatestSumOfSubArray(vector<int> array) {
    // dp数组含义：dp[i]表示第i个下标结尾时，前面的i个子数组和的最大值
    // 状态：下标为i-1时的前面子数组和的最大值
    // 选择：下一步是选择array[i]，还是选择dp[i-1]
    // 维护一个最大值变量
    vector<int> dp(array.size(), INT_MIN);
    // base case
    dp[0] = array[0];
    int max_num = array[0];
    for (int i = 1; i < array.size(); i++) {
        dp[i] = max(array[i], dp[i-1]+array[i]);
        max_num = max(max_num, dp[i]);
    }
    
    return max_num;
    
}

JZ85 连续子数组的最大和(二)

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，找到一个具有最大和的连续子数组。
1.子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组
2.如果存在多个最大和的连续子数组，那么返回其中长度最长的，该题数据保证这个最长的只存在一个
3.该题定义的子数组的最小长度为1，不存在为空的子数组，即不存在[]是某个数组的子数组
4.返回的数组不计入空间复杂度计算

数据范围:
$1<=n<=10^5$
$−100<=a[i]<=100$

要求:时间复杂度$O(n)$，空间复杂度$O(n)$
进阶:时间复杂度$O(n)$，空间复杂度$O(1)$

思路：

• 定义dp[i]:以第i个下标结尾时，前面的i个子数组和的最大值；
• 定义左右指针从0出发找到当前下标最大值的区间子数组；
• 定义res的左右指针维护最大的左右指针区间；
• 最后遍历res的左右指针得到结果。

vector<int> res;
vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
    int n = array.size();
    vector<int> dp(n);
    dp[0] = array[0];
    int left = 0, right = 0;
    int res_l = 0, res_r = 0;
    int max_res = array[0];
    for (int i = 1; i < n; i++) {
        right++;
        
        if (dp[i-1] + array[i] < array[i]) {
            dp[i] = array[i];
            left = right;
        }
        else {
            dp[i] = dp[i-1] + array[i];
        }
        
        if (dp[i] > max_res || (dp[i] == max_res 
        && right - left + 1 > res_l - res_r + 1)) {
            max_res = dp[i];
            res_l = left;
            res_r = right;
        }
    }
    
    for (int i = res_l; i <= res_r; i++) {
        res.emplace_back(array[i]);
    }
    
    return res;
}

BM66 最长公共子串

给定两个字符串str1和str2,输出两个字符串的最长公共子串
题目保证str1和str2的最长公共子串存在且唯一。

数据范围：1≤∣str1∣,∣str2∣≤5000
要求：空间复杂度$O(n^2)$，时间复杂度$O(n^2)$
思路：

• dp[i][j]表示str2的第j个字符结尾的时候，str1的第i个字符结尾的最长子串的长度；
• 如果两个字符相等，则最长长度+1，否则置为0；
• 统计最大长度以及最大长度的结束位置。

string LCS(string str1, string str2) {
    int m=str1.size(), n=str2.size();
    vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
    int end=0;
    int max_res=-1;
    for (int i=1; i<=m; i++) {
        for (int j=1; j<=n; j++) {
            if (str1[i-1] == str2[j-1]) {
                dp[i][j]=dp[i-1][j-1]+1;
            }
            else {
                dp[i][j]=0;
            }
            
            if (max_res < dp[i][j]) {
                max_res=dp[i][j];
                end=i-1;
            }
        }
    }
    
    return str1.substr(end-max_res+1, max_res);
}

BM65 最长公共子序列(二)

给定两个字符串str1和str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则返回”-1”。目前给出的数据，仅仅会存在一个最长的公共子序列

数据范围：$0≤∣str1∣,∣str2∣≤2000$
要求：空间复杂度$O(n^2)$，时间复杂度$O(n^2)$
输入：”1A2C3D4B56”,”B1D23A456A”
返回值：”123456”

// 思路：
// 先记下最大的长度
// 通过最大长度反推字符串
vector<vector<int>> dp;
int n, m;
string LCS(string s1, string s2) {
    n=s1.size();
    m=s2.size();
    // dp[i][j]：表示第i个字符结尾的最大长度
    dp.resize(n+1, vector<int>(m+1, 0));
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            if (s1[i-1] == s2[j-1]) {
                dp[i][j] = dp[i-1][j-1]+1;
            }
            else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    
    // 反推结果
    string res;
    for (int i=n,j=m;dp[i][j]>=1;) {
        if (s1[i-1] == s2[j-1]) {
            res += s1[i-1];
            i--;
            j--;
        }
        else if (dp[i][j-1] >= dp[i-1][j]) {
            j--;
        }
        else {
            i--;
        }
    }
    
    reverse(res.begin(), res.end());
    
    return res.empty()?"-1":res;
}

贪心算法

BM95 分糖果问题

一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下：
1.每个孩子不管得分多少，起码分到一个糖果。
2.任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制)

给定一个数组 arr 代表得分数组，请返回最少需要多少糖果。
要求: 时间复杂度为$O(n)$ 空间复杂度为$O(n)$
数据范围：$1≤n≤100000, 1≤a_i≤1000$
输入：[1,1,2]
返回值：4
说明：最优分配方案为1,1,2

#include <bits/stdc++.h>
using namespace std;

int n;
int candy(vector<int>& arr) {
    n=arr.size();
    vector<int> nums(n,1);
    // 从左王右遍历，找出左边的分数高，
    // 遇到分数高的糖果数+1
    for (int i=1;i<n;i++) {
        if (arr[i]>arr[i-1]) {
            nums[i]=nums[i-1]+1;
        }
    }
    
    int total_res=nums[n-1];
    // 从右往左遍历，找出左边的分数高，
    // 左边的糖果数少的样本进行更新
    for (int i=n-2;i>=0;i--) {
        if (arr[i]>arr[i+1] && nums[i]<=nums[i+1]) {
            nums[i] = nums[i+1]+1;
        }
        total_res += nums[i];
    }

    return total_res;
}


vector<int> arr;
string str;
int main() {
getline(cin, str);
int t=0;
for (int i=0;i<str.size();i++) {
    if (str[i]==',') {
        arr.emplace_back(t);
        t=0;
        continue;
    }
    t=t*10+(str[i]-'0');
}
arr.emplace_back(t);


// for (int i=0;i<arr.size();i++) {
//     cout << arr[i] << endl;
// }
cout << candy(arr) << endl;

return 0;
}

股票问题

BM80 买卖股票(买卖一次)

假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天
2.如果不能获取到任何利润，请返回0
3.假设买入卖出均无手续费
数据范围：$0≤val≤10^5, 0≤val≤10^4$
要求：空间复杂度$O(1)$，时间复杂度$O(n)$

输入：[8,9,2,5,4,7,1]
返回值：5
说明：在第3天(股票价格 = 2)的时候买入，在第6天(股票价格 = 7)的时候卖出，最大利润 = 7-2 = 5 ，不能选择在第2天买入，第3天卖出，这样就亏损7了；同时，你也不能在买入前卖出股票。

思路：

• 维护一个购买的变量使得它的值最小；
• 维护一个总收益最大。

int res=0;
int maxProfit(vector<int>& prices) {
    int n=prices.size();
    int buy=prices[0];
    for (int i=1; i<n;i++) {
        if (prices[i] < buy) {
            buy = prices[i];
        }
        else {
            res=max(res, prices[i]-buy);
        }
    }
    
    return res;
}

BM81 买卖股票(买卖无限次)

假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益

1. 你可以多次买卖该只股票，但是再次购买前必须卖出之前的股票
2. 如果不能获取收益，请返回0
3. 假设买入卖出均无手续费

数据范围：$1≤n≤1×10^5, 1≤prices[i]≤10^4$

要求：空间复杂度$O(n)$，时间复杂度$O(n)$
进阶：空间复杂度$O(1)$，时间复杂度$O(n)$

输入：[8,9,2,5,4,7,1]
返回值：7
说明：
在第1天(股票价格=8)买入，第2天(股票价格=9)卖出，获利9-8=1
在第3天(股票价格=2)买入，第4天(股票价格=5)卖出，获利5-2=3
在第5天(股票价格=4)买入，第6天(股票价格=7)卖出，获利7-4=3
总获利1+3+3=7，返回7

int n;
int maxProfit(vector<int>& prices) {
    n=prices.size();
    // dp[i][0]:表示第i天没有股票的收益；
    // dp[i][1]:表示第i天有股票的收益；
    vector<vector<int>> dp(n, vector<int>(2, 0));
    // 第1天无股票的收益是0；
    dp[0][0]=0;
    // 第1天有股票的收益是-price[i]；
    dp[0][1]=-prices[0];
    for (int i=1;i<n;i++) {
        dp[i][0]=max(dp[i-1][0], dp[i-1][1]+prices[i]);
        dp[i][1]=max(dp[i-1][1], dp[i-1][0]-prices[i]);
    }
    
    return dp[n-1][0];
        
    }

BM82 买卖股票(最多买卖两次)

设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益

1. 你最多可以对该股票有两笔交易操作，一笔交易代表着一次买入与一次卖出，但是再次购买前必须卖出之前的股票
2. 如果不能获取收益，请返回0
3. 假设买入卖出均无手续费

数据范围：$1≤n≤10^5$，股票的价格满足$1≤val≤10^4$

要求: 空间复杂度$O(n)$，时间复杂度$O(n)$
进阶：空间复杂度$O(1)$，时间复杂度$O(n)$

输入：[8,9,3,5,1,3]
返回值：4
说明：第三天(股票价格=3)买进，第四天(股票价格=5)卖出，收益为2
第五天(股票价格=1)买进，第六天(股票价格=3)卖出，收益为2
总收益为4。

int n;
int maxProfit(vector<int>& prices) {
    n=prices.size();
    // 注意：股票价格最高有10^4
    vector<vector<int>> dp(n, vector<int>(5, -10000));
    dp[0][0]=0;
    dp[0][1]=-prices[0];
    for (int i=1;i<n;i++) {
        dp[i][0]=dp[i-1][0];
        dp[i][1]=max(dp[i-1][1], dp[i-1][0]-prices[i]);
        dp[i][2]=max(dp[i-1][2], dp[i-1][1]+prices[i]);
        dp[i][3]=max(dp[i-1][3], dp[i-1][2]-prices[i]);
        dp[i][4]=max(dp[i-1][4], dp[i-1][3]+prices[i]);
    }
    
    return max(dp[n-1][2], max(0, dp[n-1][4]));
}

区间调度问题

贪心算法可以认为是动态规划算法的一个特例，相比动态规划，使用贪心算法需要满足更多的条件（贪心选择性质）。

贪心选择性质：每一步都做出一个局部最优的选择，最终的结果就是全局最优。只有一部分问题拥有这个性质。

思路：给你输入若干时间区间，让你计算同一时刻「最多」有几个区间重叠。

• x_end或者x_start按升序排序；
• 统计后面区间个数和关系，更新x_end或者x_start。

无重叠区间（右端点升序）

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

思路：

• 按右端点进行升序排列；
• 统计有几个相互不交叉的区间；
• 总区间长度减去相互不交叉的区间个数。

static bool cmp(const vector<int>& a, const vector<int>& b) {
    return a[1] < b[1];
}

// 寻找至多有几个区间互不重叠
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    // 寻找至多有几个区间互不重叠，要将end按升序排列
    sort(intervals.begin(), intervals.end(), cmp);
    int x_end = intervals[0][1];
    // 至少有一个区间不重叠
    int cnt = 1;
    for (auto& interval : intervals) {
        int start = interval[0];
        if (start >= x_end) {
            x_end = interval[1];
            cnt++;
        }
    }

    // 得到至少要移除几个区间
    return intervals.size() - cnt;
}

用最少数量的箭引爆气球（右端点升序）

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:

• 在x = 2处发射箭，击破气球[1,2]和[2,3]。
• 在x = 4处射出箭，击破气球[3,4]和[4,5]。

思路：

• 该问题可转化为至多有几个不相交的子区间；
• 按照右端点升序排列好；
• 统计相互不相交的区间的个数。

static bool cmp(const vector<int>& a, const vector<int> &b) {
    return a[1] < b[1];
}
// 该问题可转化为至多有几个不重叠的区间
int findMinArrowShots(vector<vector<int>>& points) {
    sort(points.begin(), points.end(), cmp);
    int cnt = 1;
    int x_end = points[0][1];

    for (auto &point:points) {
        int start = point[0];
        if (start > x_end) {
            x_end = point[1];
            cnt++;
        }
    }

    return cnt;
}

视频拼接（左端点升序+左端点相等右端点降序）

你将会获得一系列视频片段，这些片段来自于一项持续时长为 time 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。使用数组 clips 描述所有的视频片段，其中 clips[i] = [starti, endi] 表示：某个视频片段开始于 starti 并于 endi 结束。

甚至可以对这些片段自由地再剪辑：
例如，片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。
我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（[0, time]）。返回所需片段的最小数目，如果无法完成该任务，则返回 -1 。

输入：clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
输出：3
解释：
选中 [0,2], [8,10], [1,9] 这三个片段。
然后，按下面的方案重制比赛片段：
将 [1,9] 再剪辑为 [1,2] + [2,8] + [8,9] 。
现在手上的片段为 [0,2] + [2,8] + [8,10]，而这些覆盖了整场比赛 [0, 10]。

思路：

• 先对序列进行左端点升序排序，如果左端点相等则右端点降序排序；
• 将当前的右端点curEnd和区间的右端点比较，不断更新记录最大的nextEnd右端点；
• 更新当前的端点curEnd以及统计最长序列的出现次数；
• 判断当前的端点curEnd的值是否大于等于总时长。

 static bool cmp(const vector<int>& a, vector<int>& b) {
     return a[0] == b[0] ? a[1] > b[1]:a[0] < b[0];
 }
int videoStitching(vector<vector<int>>& clips, int time) {
    sort(clips.begin(), clips.end(), cmp);
    int i = 0, n = clips.size();
    int curEnd = 0, nextEnd = 0;
    int cnt = 0;
    while (i < n && curEnd >= clips[i][0]) {
        // 贪心下一个区间的最大长度
        while (i < n && curEnd >= clips[i][0]) {
            nextEnd = max(nextEnd, clips[i][1]);
            i++;
        }

        cnt++;
        curEnd = nextEnd;
        if (curEnd >= time) {
            return cnt;
        }
    }

    return -1;

}

区间问题

区间问题的思路：

• 对区间的每个起点进行升序排序（起点相同时，终点进行降序排序）；
• 根据排序后的区间进行画图，找出相邻区间被覆盖，相交，不相交的端点进行解题。

删掉被覆盖的区间

给你一个区间列表，请你删除列表中被其他区间所覆盖的区间。

只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。

在完成所有删除操作后，请你返回列表中剩余区间的数目。
你一个区间列表，请你删除列表中被其他区间所覆盖的区间。

只有当 c <= a 且 b <= d 时，我们才认为区间 [a,b) 被区间 [c,d) 覆盖。

在完成所有删除操作后，请你返回列表中剩余区间的数目。
1 <= intervals.length <= 1000
0 <= intervals[i][0] < intervals[i][1] <= 10^5
对于所有的 i != j：intervals[i] != intervals[j]

private:
    struct cmp{
        bool operator()(const vector<int>& o1, const vector<int>& o2) {
            return o1[0] == o2[0] ? o1[1] > o2[1] : o1[0] < o2[0];
        }
    };
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp());
        int left = intervals[0][0];
        int right = intervals[0][1];
        int res = 0;
        for (int i = 1; i < intervals.size(); i++) {
            vector<int> interval(intervals[i]);
            // 该区间被上一个区间覆盖
            if (interval[0] >= left && interval[1] <= right) {
                res++;
            }
            // 该区间和上一个区间相交
            else if (interval[0] >= left && interval[0] <= right) {
                right = interval[1];
            }
            // 该区间和上一个区间无交集
            else if (interval[0] > right) {
                left = interval[0];
                right = interval[1];
            }
        }

        return intervals.size() - res;
    }

合并区间

对区间的起点进行升序排序后，找出相交区间的终点的最大端点进行更新即可。

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

static bool cmp(const vector<int>& A, const vector<int>& B) { 
    return A[0] < B[0];
}

vector<vector<int>> res;
vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if (intervals.size()==0) {
        return res;
    }
    sort(intervals.begin(), intervals.end(), cmp);
    res.emplace_back(intervals[0]);

    for (int i=1;i<intervals.size();i++) {
        if (res.back()[1] >= intervals[i][0]) {
            res.back()[1] = max(res.back()[1], intervals[i][1]);
        }
        else {
            res.emplace_back(intervals[i]);
        }
    }

    return res;
}

区间的交集

给定两个由一些闭区间组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对不相交的，并且已经排序。
返回这两个区间列表的交集。
形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。

两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。

vector<vector<int>> res;
vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {

    int i = 0, j = 0;
    vector<int> temp;
    while (i < firstList.size() && j < secondList.size()) {
        temp.clear();
        int a1 = firstList[i][0], a2 = firstList[i][1];
        int b1 = secondList[j][0], b2 = secondList[j][1];

        // a2>b1 || a1>b2的逆否命题
        if (a2 >= b1 && a1 <= b2) {
            temp.emplace_back(max(a1,  b1));
            temp.emplace_back(min(a2,  b2));
            res.emplace_back(temp);
        } 
        if (b2 > a2) {
            i++;
        }
        else {
            j++;
        }
    }

    return res;
}

会议室I（左端点升序）

给定一系列的会议时间间隔，包括起始和结束时间[[s1,e1]，[s2,e2]，…(si < ei)，确定一个人是否可以参加所有会议。
(0,8),(8,10)在8这一时刻不冲突

输入: intervals = [(5,8),(9,15)]
输出: true
解释:这两个时间段不会冲突

思路：

• 题目本质是看任意相邻的两个区间是否有重叠；
• 将序列的左端点进行升序排列；
• 判断相邻的两个区间是否有重叠即可。

static bool cmp(const Interval & a, const Interval & b) {
    return a.start < b.start;
}
// 求任意两个区间是否有交叉。
bool canAttendMeetings(vector<Interval> &intervals) {
    if (intervals.size() == 0)  return true;
    sort(intervals.begin(), intervals.end(), cmp);
    int x_end = intervals[0].end;
    for (int i = 1; i < intervals.size(); i++) {
        int start = intervals[i].start;
        if (start >= x_end) {
            x_end = intervals[i].end;
        }
        else {
            return false;
        }
    }

    return true;
}

会议室II（扫描线法）

给定一系列的会议时间间隔intervals，包括起始和结束时间[[s1,e1],[s2,e2],…] (si < ei)，找到所需的最小的会议室数量。
(0,8),(8,10)在8这一时刻不冲突
输入: intervals = [(0,30),(5,10),(15,20)]
输出: 2
解释:
需要两个会议室
会议室1:(0,30)
会议室2:(5,10),(15,20)

思路：

• 题目的本质是求解同一时刻，最多有几个区间相交；
• 单独取出各个会议的左右端点进行升序排序；
• 利用双指针的扫描线法分别扫描左右端点，如果比右端点大，则计数加1，否则计数减一；
• 维护一个最大值的变量。

int minMeetingRooms(vector<Interval> &intervals) {
    int n = intervals.size();
    vector<int> start(n);
    vector<int> end(n);
    for (int i = 0; i < n; i++) {
        start[i] = intervals[i].start;
        end[i] = intervals[i].end;
    }

    sort(start.begin(), start.end());
    sort(end.begin(), end.end());

    int i = 0, j = 0, cnt = 0;
    int res = 0;
    while (i < n && j < n) {
        if (start[i] < end[j]) {
            cnt++;
            i++;
        }
        else {
            cnt--;
            j++;
        }

        res = max(res, cnt);
    }

    return res;
}

跳跃游戏I

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

思路：

• 题目的本质是最大化每一次跳跃的最大长度；
• 维护每次跳跃最远的距离；
• 如果当前位置大于跳跃最远的位置，则表示无法到达最后一个下标。

bool canJump(vector<int>& nums) {
    int fartherest = 0;
    for (int i = 0; i < nums.size() - 1; i++) {
        // 1、贪心每一次跳的位置，每一次要跳的足够远，
        // 维护每个位置的可跳跃的最大长度
        fartherest = max(fartherest, i + nums[i]);
        // 2、跳不过0值的时候不能达到最后一个下标
        if (fartherest <= i) {
            return false;
        }
    }
    return true;
}

跳跃游戏II

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

dp数组解法

int jump(vector<int>& nums) {
    int n = nums.size();
    // dp数组：从0跳到i的最少步数为dp[i]
    vector<int> dp(n, n);
    dp[0] = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            // 当前位置超过i的位置时才更新dp数组
            if (j + nums[j] >= i)
                dp[i] = min(dp[i], dp[j] + 1);
        }
    }

    return dp[n - 1];
}

dp函数解法

vector<int> memo;
int jump(vector<int>& nums) {
    memo.resize(nums.size(), nums.size());
    return dp(nums, 0);
}

int dp(vector<int>& nums, int cur) {
    // base case
    if (cur >= nums.size() - 1)
        return 0;

    // 处理重复子问题
    if (memo[cur] != nums.size())
        return memo[cur];

    int steps = nums[cur];
    for (int i = 1; i <= steps; i++) {
        // 存在更小的跳跃次数则更新
        memo[cur] = min(memo[cur], dp(nums, cur + i) + 1);
    }

    return memo[cur];
}

贪心解法

int jump(vector<int>& nums) {
    int fartherest = 0;
    // 记录这次起跳的右边界，表示起跳点到右边界的任何一点的step都等于1
    int end = 0;
    int step = 0;
    for (int i = 0; i < nums.size() - 1; i++) {
        fartherest = max(fartherest, i + nums[i]);
        // 如果到达右边界，则进行下一次起跳，记录下一次的右边界是多少
        if (i == end) {
            step++;
            end = fartherest;
        }
    }

    return step;
}

JZ71 跳台阶扩展问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。
数据范围：$1≤n≤20$
进阶：空间复杂度 $O(1)$， 时间复杂度$O(1)$
解题关键：每个台阶的方案数是前一个台阶的2倍数。

int jumpFloorII(int number) {
    vector<int> dp(number+1);
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= number; i++) {
        dp[i] = 2 * dp[i-1];
    }
    
    return dp[number];
    
}

JZ19 正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.'：匹配任意单个字符
'*'：匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

输入：s = “aa”, p = “a*”
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

dp数组解法

bool match(string str, string pattern) {
    int n1 = str.size(), n2 = pattern.size();
    vector<vector<bool>> dp(n1+1, vector<bool>(n2+1, false));
    for (int i = 0; i <= n1; i++) {
        for (int j = 0; j <= n2; j++) {
            if (j == 0) {
                dp[i][j] = (i == 0 ? true:false);
            }
            else {
                if (pattern[j-1] != '*') {
                    if (i > 0 && (pattern[j-1] == '.' ||
                     str[i-1] == pattern[j-1])) {
                        dp[i][j] = dp[i-1][j-1];
                    }
                }
                else {
                    if (i > 0 && j >= 2 && 
                    (pattern[j-2] == str[i-1] 
                    || pattern[j-2] == '.')) {
                        dp[i][j] = (dp[i-1][j] || dp[i][j-2]);
                    }
                    else {
                        dp[i][j] = dp[i][j-2];
                    }
                }
            }
        }
    }

    return dp[n1][n2];
}

dp函数解法

int m, n;
map<pair<int, int>, bool> memo;
bool isMatch(string s, string p) {

    m = s.size();
    n = p.size();
    return dp(s, 0, p, 0);
}

bool dp(string s, int i, string p, int j) {
    // base case
    if (j == n)
        return i == m;

    if (i == m) {
        if ((n - j) % 2 == 1)
            return false;

        // 判断模式串是否是a*b*c*的形式
        for (;j + 1 < n; j += 2) {
            if (p[j + 1] != '*')
                return false;
        }
        return true;
    }

    // 消除重叠的子问题
    if (memo.count(make_pair(i, j))) {
        return memo[make_pair(i, j)];
    }

    bool res = false;
    if (s[i] == p[j] || p[j] == '.') {
        if (j < n - 1 && p[j + 1] == '*') {
            // 匹配0个或多个字符串
            res = dp(s, i, p, j + 2) || dp(s, i + 1, p, j);
        }
        else {
            // 两两匹配
            res = dp(s, i + 1, p, j + 1);
        }
    }

    else {
        // *匹配0个字符串
        if (j < n - 1 && p[j + 1] == '*') {
            res = dp(s, i, p, j + 2);
        }
        else {
            res = false;
        }
    }

    memo[make_pair(i, j)] = res;
    return res;

}

最长递增子序列

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
$1 <= nums.length <= 2500$
$-104 <= nums[i] <= 104$

int res;
int lengthOfLIS(vector<int>& nums) {
    // DP数组的物理意义：以num[i]为结尾的子序列的长度
    vector<int> dp(nums.size(), 1);
    for (int i = 0; i < nums.size(); i++) {
        for (int j = 0; j < i; j++) {
            // 状态转移：num[i-1]的子序列的长度计算
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }

        res = max(res, dp[i]);
    }

    return res;
}

最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

说明：每次只能向下或者向右移动一步。
$m == grid.length$
$n == grid[i].length$
$1 <= m, n <= 200$
$0 <= grid[i][j] <= 100$
此题直接用DFS会超时，采用二维DP比较简单。

dp数组解法

明确状态=>DP数组的物理意义=>base case=>状态转移

• 初始化第0行和第0列的某个位置的最短路径；
• 状态dp[i][j]：走到第i行和第j列的最短路径；
• 选择：下一步时选择dp[i-1][j]还是dp[i][j-1]来加上grid[i][j]。

  // dp[][]数组的物理意义：从(0,0)走到位置(i,j)的最短路径
  int minPathSum(vector<vector<int>>& grid) {
      int m = grid.size(), n = grid[0].size();
      vector<vector<int>> dp(m, vector<int>(n));
      dp[0][0] = grid[0][0];
      // base case
      for (int i = 1; i < m; i++) {
          dp[i][0] = dp[i - 1][0] + grid[i][0];
      }
      for (int j = 1; j < n; j++) {
          dp[0][j] = dp[0][j - 1] + grid[0][j];
      }
      // 状态转移
      for (int i = 1; i < m; i++) {
          for (int j = 1; j < n; j++) {
              dp[i][j] = min(dp[i - 1][j], 
              dp[i][j - 1]) + grid[i][j];
          }
      }
  
      return dp[m - 1][n - 1];
  }

自由之路

电子游戏“辐射4”中，任务 “通向自由” 要求玩家到达名为 “Freedom Trail Ring” 的金属表盘，并使用表盘拼写特定关键词才能开门。

给定一个字符串 ring ，表示刻在外环上的编码；给定另一个字符串 key ，表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数。

最初，ring 的第一个字符与 12:00 方向对齐。您需要顺时针或逆时针旋转 ring 以使 key 的一个字符在 12:00 方向对齐，然后按下中心按钮，以此逐个拼写完 key 中的所有字符。

旋转 ring 拼出 key 字符 key[i] 的阶段中：

您可以将 ring 顺时针或逆时针旋转 一个位置 ，计为1步。旋转的最终目的是将字符串 ring 的一个字符与 12:00 方向对齐，并且这个字符必须等于字符 key[i] 。
如果字符 key[i] 已经对齐到12:00方向，您需要按下中心按钮进行拼写，这也将算作 1 步。按完之后，您可以开始拼写 key 的下一个字符（下一阶段）, 直至完成所有拼写。  

输入: ring = “godding”, key = “gd”
输出: 4
解释:
对于 key 的第一个字符 ‘g’，已经在正确的位置, 我们只需要1步来拼写这个字符。
对于 key 的第二个字符 ‘d’，我们需要逆时针旋转 ring “godding” 2步使它变成 “ddinggo”。
当然, 我们还需要1步进行拼写。
因此最终的输出是 4。

vector<vector<int>> memo;
unordered_map<char, vector<int>> s_to_index;
int findRotateSteps(string ring, string key) {
    memo.resize(ring.size(), vector<int>(key.size(), 0));
    for (int i = 0; i < ring.size(); i++) {
        s_to_index[ring[i]].emplace_back(i);
    }

    return dp(ring, 0, key, 0);
}
// 1、状态：圆盘指针所指的位置和当前的输入字符
// 2、dp的物理意义：当圆盘指针指向ring[i]时，
// 输入字符串key[j..]的最少操作数为dp(ring, i, key, j)
// 3、base case
// 4、选择：该往顺时针走还是逆时针走
int dp(string ring, int i, string key, int j) {
    if (j == key.size())    return 0;

    if (memo[i][j] != 0)    return memo[i][j];

    int res = INT_MAX;
    for (auto k: s_to_index[key[j]]) {
        int delta = abs(k - i);
        int n = ring.size();
        // 选择顺时针还是逆时针
        delta = min(delta, n - delta);
        // 将指针拨到ring[k]，继续输入key[j+1...]
        int subProblem = dp(ring, k, key, j+1);
        res = min(res, subProblem + 1 + delta);
    }

    memo[i][j] = res;

    return memo[i][j];
}

BM64 最小花费爬楼梯

给定一个整数数组cost，其中cost[i]是从楼梯第i个台阶向上爬需要支付的费用，下标从0开始。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。
数据范围：数组长度满足$1≤n≤10^5$，数组中的值满足$1≤cost≤10^4$
输入：[2,5,20]
返回值：5
说明：你将从下标为1的台阶开始，支付5 ，向上爬两个台阶，到达楼梯顶部。总花费为5。

int n;
int minCostClimbingStairs(vector<int>& cost) {
    n=cost.size();
    vector<int> dp(n+1);
    dp[0]=0;
    dp[1]=0;
    for (int i=2;i<n+1;i++) {
        // 当前的状态可由上一级走一步或者上两级走两步得到
        dp[i]=min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
    }
    
    return dp[n];
}

数组

BM22 比较版本号

比较规则：
一. 比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较忽略任何前导零后的整数值。比如”0.1”和”0.01”的版本号是相等的
二. 如果版本号没有指定某个下标处的修订号，则该修订号视为0。例如，”1.1”的版本号小于”1.1.1”。因为”1.1”的版本号相当于”1.1.0”，第3位修订号的下标为0，小于1
三. version1>version2 返回1，如果version1<version2返回-1，不然返回0.

数据范围：
1 <= version1.length, version2.length <= 1000
version1和version2的修订号不会超过int的表达范围，即不超过32位整数的范围

int res=0;
int compare(string version1, string version2) {
    int len1=version1.size(), len2=version2.size();
    int i=0, j=0;
    while (i<len1 || j<len2) {
        // 比较小数点之间的数字
        long long num1=0, num2=0;
        while (version1[i]!='.' && i<len1) {
            num1=num1*10 + (version1[i]-'0');
            i++;
        }
        i++;
        
        while (version2[j]!='.' && j<len2) {
            num2=num2*10 +(version2[j]-'0');
            j++;
        }
        j++;
        
        if (num1>num2) {
            return 1;
        }
        else if (num1<num2) {
            return -1;
        }
    }
    
    return 0;
}

滑动窗口问题

最长无重复子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

// 解法：滑动窗口+统计字符个数
int n;
int res=0;
int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> window;
    n=s.size();
    int left=0, right=0;
    while (right < n) {
        char c1=s[right];
        if (!window.count(c1) || window[c1] == 0) {
            window[c1]++;
            right++;
        }
        
        else {
            char c2=s[left];
            window[c2]--;
            left++;
        }

        res = max(res, right-left);
    }

    return res;
}

合并两个有序的数组

给出一个有序的整数数组 A 和有序的整数数组 B ，请将数组 B 合并到数组 A 中，变成一个有序的升序数组
数据范围：$0≤n,m≤100$，$|A_i| <=100，|B_i| <= 100$
​
注意：
1.保证 A 数组有足够的空间存放 B 数组的元素， A 和 B 中初始的元素数目分别为 m 和 n，A的数组空间大小为 m+n
2.不要返回合并的数组，将数组 B 的数据合并到 A 里面就好了，且后台会自动将合并后的数组 A 的内容打印出来，所以也不需要自己打印
3.A 数组在[0,m-1]的范围也是有序的
输入：[4,5,6],[1,2,3]
返回值：[1,2,3,4,5,6]

// 思路：使用3个指针，一个指向A的最大值，一个指向B的最大值，
// 一个指向辅助数组的末尾，从后往前添加
void merge(int A[], int m, int B[], int n) {
    int i=m-1, j=n-1, k=m+n-1;
    while (i>=0 && j>=0) {
        if (A[i] > B[j]) {
            A[k]=A[i];
            i--;
            k--;
        }
        else {
            A[k]=B[j];
            j--;
            k--;
        }
    }
    
    while (j>=0) {
        A[k]=B[j];
        j--;
        k--;
    }
}

两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

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

哈希表解法

时间O(n)，空间O(n)

vector<int> res;
unordered_map<int, int> memo;
vector<int> twoSum(vector<int>& nums, int target) {
    for (int i = 0; i < nums.size(); i++) {
        if (memo.count(nums[i])) {
            res.emplace_back(memo[nums[i]]);
            res.emplace_back(i);
        }
        else {
            memo[target - nums[i]] = i;
        }
    }

    return res;
}

BM53 缺失的第一个正整数

给定一个未排序的整数数组nums，请你找出其中没有出现的最小的正整数
进阶： 空间复杂度$O(1)$，时间复杂度$O(n)$

数据范围:
$-2^31<=nums[i]<=2^31-1$
$0<=len(nums)<=5*10^5$
输入：[-2,3,4,1,5]
返回值：2

int n;
unordered_map<int, int> memo;
int minNumberDisappeared(vector<int>& nums) {
    n=nums.size();
    // 记录当前数组的哈希情况
    for (int i=0;i<n;i++) {
        memo[nums[i]]++;
    }
    
    // 从正整数1开始寻找，直到找不到某个res为止
    int res=1;
    while (memo.find(res)!=memo.end()) {
        res++;
    }
    
    return res;
}

三数之和

排序+双指针法

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

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

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

// 解题思路：
// 1. 三数求和首先讲序列进行排序，然后从第一个数字出发，
// 固定第一个数字，把题目当成两数之和问题进行求解。
vector<vector<int>> res;
vector<vector<int>> threeSum(vector<int>& nums) {
    int n = nums.size();
    sort(nums.begin(), nums.end());


    for (int i = 0; i < n - 1; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;

        int left = i+1;
        int right = n-1;
        while (left < right) {

            if (nums[left] + nums[right] > -nums[i]) {
                right--;
            }
            else if (nums[left] + nums[right] < -nums[i]) {
                left++;
            }
            else {
                res.push_back({nums[i], nums[left], nums[right]});
                left++;
                right--;
                // 避免统计到重复的元素
                while (left < right && nums[left] == nums[left-1])  
                    left++;
                while (left < right && nums[right] == nums[right+1])  
                    right--;

            }
        }
    }

    return res;
}

JZ51 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
数据范围：对于50%的数据, size≤10^4
对于100%的数据, size≤10^5
数组中所有数字的值满足0≤val≤1000000

要求：空间复杂度O(n)，时间复杂度O(nlogn)
输入描述：
题目保证输入的数组中没有的相同的数字

输入：[1,2,3,4,5,6,7,0]
返回值：7

int mod = 1000000007;
int mergeSort(int left, int right, vector<int>& data, vector<int>& temp){
    //停止划分
    if(left >= right)    
        return 0;
    //取中间
    int mid = (left + right) / 2; 
    //左右划分合并
    int res = mergeSort(left, mid, data, temp) + mergeSort(mid + 1, right, data, temp); 
    //防止溢出
    res %= mod;  
    int i = left, j = mid + 1;
    for(int k = left; k <= right; k++)
        temp[k] = data[k];
    for(int k = left; k <= right; k++){
        if(i == mid + 1)
            data[k] = temp[j++];
        else if(j == right + 1 || temp[i] <= temp[j])
            data[k] = temp[i++];
        //左边比右边大，答案增加
        else{ 
            data[k] = temp[j++];
            //统计逆序对
            res += mid - i + 1; 
        }
    }
    return res % mod;
}
int InversePairs(vector<int> data) {
    int n = data.size();
    vector<int> res(n);
    return mergeSort(0, n - 1, data, res);
}

BM97 旋转数组

一个数组A中存有 n 个整数，在不允许使用另外数组的前提下，将每个整数循环向右移$M（ M >=0）$个位置，即将A中的数据由$（A_0 A_1 ……A_{N-1} ）$变换为$（A_{N-M} …… A_{N-1} A_0 A_1 ……A_{N-M-1} ）$（最后 M 个数循环移至最前面的 M 个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？
数据范围：$0<n≤100，0≤m≤1000$
进阶：空间复杂度$O(1)$，时间复杂度$O(n)$
输入：6,2,[1,2,3,4,5,6]
返回值：[5,6,1,2,3,4]

// 思路：3次翻转数组，第一次整体翻转，第二次m部分翻转，第三次n-m部分翻转
vector<int> solve(int n, int m, vector<int>& a) {
    m %= n;
    reverse(a.begin(), a.end()); 
    reverse(a.begin(), a.begin()+m);
    reverse(a.begin()+m, a.end());
    
    return a;
}

字符串

JZ58 左旋字符串

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列 S ，请你把其循环左移 K 位后的序列输出。例如，字符序列 S = ”abcXYZdef” , 要求输出循环左移 3 位后的结果，即 “XYZdefabc”

数据范围：输入的字符串长度满足 0≤len≤100, 0≤n≤100
进阶：空间复杂度O(n) ，时间复杂度O(n)
“abcXYZdef”,3
“XYZdefabc”

string LeftRotateString(string str, int n) {
    if (str == "")    return "";
    int move = n % str.size();
    stringstream ss1, ss2;
    for (int i = 0; i < str.size(); i++) {
        if (i < move) {
            ss1 << str[i];
        }
        else {
            ss2 << str[i];
        }
    }

    return ss2.str() + ss1.str();
}

最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。
输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。

思路：

• 枚举每个字符，以每个字符为中心，或者以该字符和下一个字符为中心，向左右拓展进行长度统计；
• 记录下长的回文子串的长度。

int l, r;
int start=0, end=0;

void expandAroundCenter(string& s, int left, int right) {
    while (left >= 0 && right < s.size() && s[left] == s[right]) {
        left--;
        right++;
    }
    l = left+1;
    r = right-1;

    // 记录下长的回文子串的长度
    if (r - l > end - start) {
        start = l;
        end = r;
    }
}

// 枚举每个字符，以每个字符为中心，
// 或者以该字符和当前的字符为中心，向左右拓展进行长度统计
string longestPalindrome(string s) {
    for (int i=0;i<s.size();i++) {
        expandAroundCenter(s, i, i);
        expandAroundCenter(s, i, i+1);
    } 

    return s.substr(start, end-start+1);
}

链表

JZ6 从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

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

vector<int> res;
vector<int> reversePrint(ListNode* head) {
    if (head == nullptr)    return res;
    reversePrint(head->next);
    res.emplace_back(head->val);

    return res;
}

JZ24 反转链表

迭代法

ListNode* reverseList(ListNode* head) {
       ListNode *pre = nullptr, *cur=head, *next = nullptr;
       while (cur != nullptr) {
           next = cur->next;
           cur->next = pre;
           pre = cur;
           cur = next;
       }

       return pre;
   }

递归法

ListNode* reverseList(ListNode* head) {
    // bad case
    if (head == nullptr || head->next == nullptr)    return head;
    ListNode *last = reverseList(head->next);
    // 第一个元素和后面全部都反转的链表
    head->next->next = head;
    head->next = nullptr;

    return last;
}

BM2 链表内指定区间反转

将一个节点数为size链表m位置到n位置之间的区间反转，要求时间复杂度$O(n)$，空间复杂度$O(1)$。
例如：
给出的链表为1→2→3→4→5→NULL, m=2，n=4
返回1→4→3→2→5→NULL

数据范围： 链表长度0<size≤1000，0<m≤n≤size，链表中每个节点的值满足 |val|≤1000
要求：时间复杂度$O(n)$，空间复杂度$O(n)$
进阶：时间复杂度$O(n)$，空间复杂度$O(1)$

递归法

ListNode* reverseBetween(ListNode* head, int m, int n) {
    if (m == 1) {
        return reverseN(head, n);
    }
    
    head->next = reverseBetween(head->next, m-1, n-1);
    return head;
}

ListNode *successor=nullptr;
ListNode* reverseN(ListNode *head, int n) {
    if (n==1) {
        successor=head->next;
        return head;
    }
    ListNode* last = reverseN(head->next, n-1);
    head->next->next=head;
    head->next=successor;
    
    return last;
}

迭代法

链表排序

升序 排列并返回 排序后的链表。(归并排序的思想)

4->2->1->3 => 1->2->3->4

/**
 * 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* head1 = head;
        ListNode* head2 = split(head);

        head1 = sortList(head1);
        head2 = sortList(head2);

        return merge(head1, head2);
    }

    // 快慢指针返回中间节点
    ListNode* split(ListNode* head) {
        ListNode* slow = head, *fast = head->next;
        while (fast != nullptr && fast-> next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* second = slow->next;
        // 断连接
        slow->next = nullptr;

        return second;

    }

    // 合并两个链表
    ListNode* merge(ListNode*head1, ListNode* head2) {
        ListNode *dummy = new ListNode();
        ListNode* cur = dummy;
        while (head1 != nullptr && head2 != nullptr) {
            if (head1->val > head2->val) {
                cur->next = head2;
                head2 = head2->next;
            }
            else {
                cur->next = head1;
                head1 = head1->next;
            }
            cur = cur->next;
        }
        // 将两个节点连接起来
        cur->next = (head2 == nullptr ? head1 : head2);
        ListNode* ret = dummy->next;
        delete dummy;
        dummy = nullptr;

        return ret;
    }
};

BM3 链表中的节点每k个一组翻转

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。

数据范围：0≤n≤2000，1≤k≤2000 ，链表中每个元素都满足0≤val≤1000
要求空间复杂度$O(1)$，时间复杂度$O(n)$
例如：
给定的链表是1→2→3→4→5
对于k=2, 你应该返回2→1→4→3→5
对于k=3, 你应该返回3→2→1→4→5

思路：

• 按照k进行分组，k个为一组的组内元素反转链表，否则返回表头；
• 将头接到递归的下一组的头上。

ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode *tail=head;
    for (int i=0; i<k; i++) {
        if (tail == nullptr) {
            return head;
        }
        tail=tail->next;
    }
    
    ListNode *temp, *pre=head, *cur=head;
    while (cur != tail) {
        temp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = temp;
    }
    
    head->next = reverseKGroup(tail, k);
    
    return pre;
}

快慢指针

JZ52 两个链表的第一个公共结点

LC160. 相交链表

输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

数据范围：n≤1000
要求：空间复杂度 O(1)，时间复杂度 O(n)
输入：{1},{2,3},{}
返回值：{}

说明：2个链表没有公共节点 ,返回null，后台打印{}

ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
    ListNode *p1 = pHead1, *p2 = pHead2;
	// 遇到空则互换线路，否则继续走
    while (p1 != p2) {
        //             if (p1 == nullptr) {
        //                 p1 = pHead2;
        //             }  
        //             else{
        //                 p1 = p1->next;
        //             }
        //             if (p2 == nullptr) {
        //                 p2 = pHead1;
        //             }
        //             else {
        //                 p2 = p2->next;
        //             }
        //         }
        p1 = (p1 == nullptr)?pHead2:p1->next;
        p2 = (p2 == nullptr)?pHead1:p2->next;
    }
    return p1;
}

环形链表I

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

bool hasCycle(ListNode *head) {
    ListNode *slow = head, *fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
            return true;
    }

    return false;
}

JZ23 链表中环的入口结点

LC142. 环形链表 II

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
数据范围：n≤10000，1<=结点值<=10000
要求：空间复杂度 O(1)，时间复杂度 O(n)

输入描述：输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表
返回值描述：返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。
输入：{1,2},{3,4,5}
返回值：3
说明：返回环形链表入口结点，我们后台程序会打印该环形链表入口结点对应的结点值，即3

ListNode* EntryNodeOfLoop(ListNode* pHead) {
    // 1、双指针从头结点出发
    ListNode *slow=pHead, *fast=pHead;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        // 2、找到第一次相遇的位置
        if (slow == fast) {
            break;
        }
    }

    // 3、判断是否有环
    if (fast == nullptr || fast->next == nullptr)    return nullptr;

    // 4、有环则从原点出发同步走
    fast = pHead;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }

    return slow;
}

JZ22 链表中倒数最后k个结点

输入一个长度为 n 的链表，设链表中的元素的值为 ai，返回该链表中倒数第k个节点。
如果该链表长度小于k，请返回一个长度为 0 的链表。
数据范围：0≤n≤10^5, 0≤ai≤10^9, 0≤k≤10
进阶：空间复杂度 O(1)，时间复杂度 O(n)
输入：{1,2,3,4,5},2
返回值：{4,5}
说明：返回倒数第2个节点4，系统会打印后面所有的节点来比较。

// 快慢指针：快指针先走k步，慢指针才出发，两者同步，当快指针到终点的位置，慢指针的位置就是待求位置
ListNode* FindKthToTail(ListNode* pHead, int k) {
    ListNode *slow=pHead, *fast=pHead;
    for (int i =0; i < k; i++) {
        // 还没走到k步，快指针已经到头了，直接返回空
        if (fast == nullptr)    return nullptr;
        fast = fast->next;

    }

    while (fast != nullptr) {
        fast = fast->next;
        slow = slow->next;
    }

    return slow;
}

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode *dummy = new ListNode(-1), *fast=head, *slow=dummy;
    dummy->next = head;
    for (int i = 0; i < n; i++) {
        fast = fast->next;
    }

    while (fast != nullptr) {
        slow = slow->next;
        fast = fast->next;
    }

    slow->next = slow->next->next;

    return dummy->next;
}

BM14 链表的奇偶重排

给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。
注意是节点的编号而非节点的数值。

数据范围：节点数量满足0≤n≤10^5，节点中的值都满足0≤val≤1000
要求：空间复杂度$O(n)$，时间复杂度$O(n)$

思路：

• 利用odd指针指向奇数位，even指针指向偶数位；
• 两个指针依次走动即可。

ListNode* oddEvenList(ListNode* head) {
    if (head==nullptr) {
        return nullptr;
    }
    ListNode *odd=head, *even=head->next, *evenHead=head->next;
    while (even!=nullptr && even->next!=nullptr) {
        odd->next=even->next;
        odd=odd->next;
        even->next=odd->next;
        even=even->next;
    }
    
    odd->next=evenHead;
    
    return head;
}

JZ35 复杂链表的复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

// 使用哈希表建立原链表和新链表的关系
unordered_map<Node*, Node*> memo;
Node* copyRandomList(Node* head) {
    Node *dummy = new Node(-1), *p=head;
    dummy->next = p;
    while (p != nullptr) {
        memo[p] = new Node(p->val);
        p = p->next;
    }

    p = head;
    while (p != nullptr) {
        memo[p]->next = memo[p->next];
        memo[p]->random = memo[p->random];
        p = p->next;
    }

    return memo[dummy->next];
}

JZ25 合并两个排序的链表

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围：10000≤n≤1000，−1000≤节点值≤1000
要求：空间复杂度 O(1)，时间复杂度 O(n)

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

思路：

• 先定义表头；
• 比较两个链表的值，值小的接到新链表上。

ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
    // 用两个指针指向两个链表遍历即可
    ListNode* dummy = new ListNode(-1), *p1 = pHead1, *p2 = pHead2;
    ListNode *p = dummy;
    while (p1 != nullptr && p2 != nullptr) {
        if (p1->val < p2->val) {
            p->next = p1;
            p1 = p1->next;
        }
        else {
            p->next = p2;
            p2 = p2->next;
        }
        p = p->next;
    }

    if (p1 != nullptr) {
        p->next = p1;
    }
    if (p2 != nullptr) {
        p->next = p2;
    }

    return dummy->next;
}

合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

利用最小堆解决不同数组中链表的排序关系。

struct cmp {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val;
    }
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
    // 1、定义表头
    ListNode *dummy = new ListNode(-1), *p = dummy;
    // 2、定义最小堆
    priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
    // 3、把每个list的头指针入优先队列
    for (auto head : lists) {
        if (head != nullptr)
            pq.push(head);
    }
    // 4、合并有序链表
    while (!pq.empty()) {
        ListNode *node = pq.top();
        pq.pop();
        p->next = node;
        if (node->next != nullptr) {
            pq.push(node->next);
        } 
        p = p->next;
    }
    return dummy->next;
}

JZ76 删除链表中重复的结点

LC82. 删除排序链表中的重复元素 II

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5
数据范围：链表长度满足0≤n≤1000 ，链表中的值满足1≤val≤1000
进阶：空间复杂度 O(n)，时间复杂度 O(n)
输入：{1,2,3,3,4,4,5}
返回值：{1,2,5}

哈希表解法

ListNode* deleteDuplication(ListNode* pHead) {
// 哈希表法：不管有序无序都可以做，记录结点出现的次数，删去次数小于1的结点
ListNode *dummy = new ListNode(-1), *p = pHead;
dummy->next = pHead;
unordered_map<int, int> memo;
while (p != nullptr) {
memo[p->val]++;
p = p->next;
}

p = dummy;
while (p->next != nullptr) {
    if (memo[p->next->val] > 1) {
        p->next = p->next->next;
    }
    else {
        p = p->next;
    }

}

return dummy->next;

}

直接法

// 直接比较相邻的元素是否相等
ListNode* deleteDuplication(ListNode* pHead) {
ListNode *dummy = new ListNode(-1), *p = dummy;
dummy->next = pHead;
while (p->next != nullptr && p->next->next != nullptr) {
if (p->next->val == p->next->next->val) {
int temp = p->next->val;
while (p->next != nullptr && temp == p->next->val) {
p->next = p->next->next;
}
}
else {
p = p->next;
}
}

return dummy->next;

}

JZ18 删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。
1.此题对比原题有改动
2.题目保证链表中节点的值互不相同
3.该题只会输出返回的链表和结果做对比，所以若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点
数据范围:
0<=链表节点值<=10000
0<=链表长度<=10000
输入：{2,5,1,9},5
返回值：{2,1,9}
说明：
给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 2 -> 1 -> 9

ListNode* deleteNode(ListNode* head, int val) {
    ListNode *dummy = new ListNode(-1), *p = dummy;
    dummy->next = head;
    while (p->next != nullptr) {
        if (p->next->val == val) {
            p->next = p->next->next;
        }
        else {
            p = p->next;
        }
    }

    return dummy->next;
}

BM11 链表相加(二)

假设链表中每一个节点的值都在0-9之间，那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。
数据范围：0≤n,m≤1000000，链表任意值0≤val≤9
要求：空间复杂度$O(n)$，时间复杂度$O(n)$

例如：链表1为 9->3->7，链表2为 6->3，最后生成新的结果链表为1->0->0->0。

思路：

• 先反转链表；
• 同时遍历两个链表进行求值和进位数；
• 把值添加入链表。

ListNode* addInList(ListNode* head1, ListNode* head2) {
    ListNode *p1=reverseList(head1), *p2=reverseList(head2);
    ListNode *newHead=new ListNode(-1), *p=newHead;
    int val=0;
    int c_in=0;
    while (p1!=nullptr || p2!=nullptr) {
        val=0;
        if (p1!=nullptr) {
            val+=p1->val;
            p1=p1->next;
        }
        
        if (p2!=nullptr) {
            val+=p2->val;
            p2=p2->next;
        }
        val+=c_in;
        c_in=val / 10;
        ListNode *node=new ListNode(val%10);
        p->next=node;
        p=p->next;
    }
        
    if (c_in != 0) {
        ListNode *node=new ListNode(c_in);
        p->next=node;
        p=p->next;
    }
    
    ListNode *res=reverseList(newHead->next);
    
    return res;
}

ListNode* reverseList(ListNode *head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
    ListNode *last=reverseList(head->next);
    head->next->next=head;
    head->next=nullptr;
    
    return last;
}

BM15 删除有序链表中重复的元素-I

删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次
例如：
给出的链表为1→1→2,返回1→2.
给出的链表为1→1→2→3→3,返回1→2→3.

数据范围：链表长度满足0≤n≤100，链表中任意节点的值满足∣val∣≤100
进阶：空间复杂度$O(1)$，时间复杂度$O(n)$
思路：

• 定义两个指针，一个停留在当前位置，直到下一个值不同的元素才指过去；
• 遇到不一样的值时，更新两个指针的位置；

ListNode* deleteDuplicates(ListNode* head) {
    ListNode *dummy=new ListNode(-1);
    dummy->next=head;
    ListNode *p1=head, *p2=head;
    while (p2!=nullptr) {
        while (p2 != nullptr && p1->val == p2->val) {
            p2=p2->next;
        }
        p1->next=p2;
        p1=p1->next;
    }
    
    return dummy->next;
}

BM16 删除有序链表中重复的元素-II

给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
例如：
给出的链表为1→2→3→3→4→4→5, 返回1→2→5.
给出的链表为1→1→1→2→3, 返回2→3.

数据范围：链表长度0≤n≤10000，链表中的值满足 |val|≤1000
要求：空间复杂度$O(n)$，时间复杂度$O(n)$
进阶：空间复杂度$O(1)$，时间复杂度$O(n)$

ListNode* deleteDuplicates(ListNode* head) {
    ListNode *dummy=new ListNode(-1);
    dummy->next=head;
    ListNode *p2=dummy;
    while (p2->next!=nullptr && p2->next->next!=nullptr) {
        if (p2->next->val == p2->next->next->val) {
            int temp=p2->next->val;
            while (p2->next!=nullptr  && p2->next->val == temp) {
                p2->next=p2->next->next;
            }
        }
        else {
            p2=p2->next;
        }
        
    }
    
    return dummy->next;
}

JZII26 重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：
 L0 → L1 → … → Ln-1 → Ln 
请将其重新排列后变为：
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

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

链表的长度范围为 [1, 5 * 10^4]
1 <= node.val <= 1000

该题由寻找链表的中点，反转链表，合并两个链表三道简单题目组成。

void reorderList(ListNode* head) {
    ListNode *mid = findMid(head);
    ListNode *list1 = head, *list2 = mid->next;
    mid->next = nullptr;

    list2 = reverseList(list2);

    mergeList(list1, list2);

}

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

    return slow;
}

ListNode* reverseList(ListNode *head) {
    if (head == nullptr || head->next == nullptr)    return head;

    ListNode *last = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;

    return last;
}

// 将后半段反转后的链表和前半段链表进行合并
void mergeList(ListNode *list1, ListNode *list2) {
    ListNode *list1_temp, *list2_temp;
    while (list1 != nullptr && list2 != nullptr) {
        list1_temp = list1->next;
        list2_temp = list2->next;

        list1->next = list2;
        list2->next = list1_temp;

        list1 = list1_temp;
        list2 = list2_temp;

    }
}

树

二叉树建树

struct TreeNode {
    TreeNode *left;
    TreeNode *right;
    int val;
    
    TreeNode():val(0), left(nullptr), right(nullptr){}
    TreeNode(int x):val(x){}
    TreeNode(int x, TreeNode *left, TreeNode *right):val(x), left(left), right(right){}
}

二叉树的前序遍历

遍历过程：根->左->右。

递归法

vector<int> res;
vector<int> preorderTraversal(TreeNode* root) {
    preorder(root);
    return res;
}

void preorder(TreeNode *root) {
    if (root == nullptr) 
        return;

    res.emplace_back(root->val);
    preorder(root->left);
    preorder(root->right);
}

非递归法

stack<TreeNode *> s;
vector<int> res;
vector<int> preorderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return res;
    }
    s.push(root);
    // 遍历的顺序和入栈的顺序相反，入栈首先是根进再出栈，
    // 然后再是右节点进，左节点进，再开始出栈。
    while (!s.empty()) {

        TreeNode *node = s.top();
        s.pop();
        res.emplace_back(node->val);

        if (node->right != nullptr) {
            s.push(node->right);
        }
        
        if (node->left != nullptr) {
            s.push(node->left);
        }
    }

    return res;


}

二叉树的中序遍历

遍历过程：左->根->右。

递归法

vector<int> res;
vector<int> inorderTraversal(TreeNode* root) {

    inorder(root);
    return res;
}

void inorder(TreeNode *root) {
    if (root == nullptr) 
        return;

    inorder(root->left);
    res.emplace_back(root->val);
    inorder(root->right);
}

非递归法

vector<int> res;
stack<TreeNode*> s;
vector<int> inorderTraversal(TreeNode* root) {
    while (!s.empty() || root != nullptr) {
        // 1、先往左边走到底
        while (root != nullptr) {
            s.push(root);
            root = root->left;
        }
        // 2、根节点出栈、同时判断右节点下是否有左子树
        TreeNode *node = s.top();
        s.pop();
        res.emplace_back(node->val);
        if (node->right != nullptr) {
            root = node->right;
        }
    }

    return res;
}

二叉树的后序遍历

遍历过程：左->右->根。

递归法

vector<int> res;
vector<int> postorderTraversal(TreeNode* root) {
    postorder(root);
    return res;
}

void postorder(TreeNode *root) {
    if (root == nullptr)
        return;

    postorder(root->left);
    postorder(root->right);
    res.emplace_back(root->val);
}

非递归法

vector<int> res;
vector<int> postorderTraversal(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode *prev = nullptr;
    while (!s.empty() || root != nullptr) {
        while (root != nullptr) {
            s.push(root);
            root = root->left;
        }
        
        TreeNode *node = s.top();
        s.pop();
        // 如果当前根右孩子已经被访问过，就不会再访问了
        if (node->right == nullptr || node->right == prev) {
            res.emplace_back(node->val);
            prev = node;
        }
        else {
            s.push(node);
            root = node->right;
        }
    }
    
    return res;
}

JZ55 二叉树的最大深度

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度，根节点的深度视为 1 。

数据范围：节点的数量满足0≤n≤100 ，节点上的值满足0≤val≤100
进阶：空间复杂度 O(1) ，时间复杂度 O(n)
输入：{1,2,3,4,5,#,6,#,#,7}
返回值：4

递归法

int TreeDepth(TreeNode* pRoot) {
    if (pRoot == nullptr)    return 0;
    return max(TreeDepth(pRoot->left), TreeDepth(pRoot->right)) + 1;

    return depth;   
}

层次遍历法

// 层次遍历写法
int TreeDepth(TreeNode* pRoot) {
    if (pRoot == nullptr)    return 0;
    queue<TreeNode*> q;
    q.push(pRoot);
    int depth = 0;
    while (!q.empty()) {
        int sz = q.size();
        depth++;
        for (int i = 0; i < sz; i++) {
            TreeNode *node = q.front();
            q.pop();
            if (node->left != nullptr)    q.push(node->left);
            if (node->right != nullptr)    q.push(node->right);
        }
    }

    return depth;
}

前缀树

相同前缀的字符串集中在 Trie 树中的一个子树。前缀树一般用来高效操作字符串。Tire树的本质是二叉树衍生出来的多叉树。

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

输入
[“Trie”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”]
[[], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert(“apple”);
trie.search(“apple”); // 返回 True
trie.search(“app”); // 返回 False
trie.startsWith(“app”); // 返回 True
trie.insert(“app”);
trie.search(“app”); // 返回 True

class Trie {
private:
    // 指向子结点的指针数组
    // 该节点是否是字符串的结尾
    vector<Trie*> children;
    bool isEnd;

    // 返回带有前缀树的末端节点
    Trie* searchPrefix(string prefix) {
        Trie* node = this;
        for (char ch:prefix) {
            ch -= 'a';
            if (node->children[ch] == nullptr) {
                return nullptr;
            }
            node = node->children[ch];
        }
        return node;
    }
public:
    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;
    }
    
    bool search(string word) {
        Trie *node = this->searchPrefix(word);
        return node != nullptr && node->isEnd;
    }
    
    bool startsWith(string prefix) {
        Trie *node = this->searchPrefix(prefix);
        return node != nullptr;
    }
};

JZ37 序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。
二叉树的序列化(Serialize)是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#）

二叉树的反序列化(Deserialize)是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
输入：{1,2,3,#,#,6,7}
返回值：{1,2,3,#,#,6,7}

char* Serialize(TreeNode *root) {   
    string res;
    SerializeFunction(root, res);
    char *charRes = new char[res.size() + 1];
    charRes[res.size() - 1] = '\0';
    strcpy(charRes, res.c_str());
    
    return charRes;
}

void SerializeFunction(TreeNode *root, string& res) {
    if (root == nullptr) {
        res += '#';
        return;
    }
    
    res += to_string(root->val) + ',';
    // res += ',';
    SerializeFunction(root->left, res);
    SerializeFunction(root->right, res);
    
    
}

TreeNode *DeserializeFunction(char **str) {
    if (**str == '#') {
        (*str)++;
        return nullptr;
    }
    // 数字转换
    int val = 0;
    while (**str != ',' && **str != '\0') {
        // char只能存一位，所以没遇到","前，按个十百位排
        val = val * 10 + **str - '0';
        (*str)++;
    }
    
    TreeNode *root = new TreeNode(val);
    if (**str == '\0')    return root;
    else    (*str)++;
    
    root->left = DeserializeFunction(str);
    root->right = DeserializeFunction(str);
    
    return root;
}
TreeNode* Deserialize(char *str) {
    if (*str == '#')    return nullptr;
    TreeNode *res = DeserializeFunction(&str);
    
    return res;
}

ZJ82 二叉树中和为某一值的路径(一)

给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。
1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
2.叶子节点是指没有子节点的节点
3.路径只能从父节点到子节点，不能从子节点到父节点
4.总节点数目为n
给出如下的二叉树，sum=22，
返回true，因为存在一条路径25→4→11→2的节点值之和为 22

数据范围：
1.树上的节点数满足0≤n≤10000
2.每 个节点的值都满足 ∣val∣≤1000
要求：空间复杂度 O(n)，时间复杂度 O(n)
进阶：空间复杂度 O(树的高度)，时间复杂度O(n)

递归法

// 递归法
bool hasPathSum(TreeNode* root, int sum) {
    if (root == nullptr)    return false;
    // 查看是否是叶节点
    if (root->left == nullptr && root->right == nullptr && sum - root->val == 0)    return true;

    return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}

JZ34 二叉树中和为某一值的路径(二)

输入一颗二叉树的根节点root和一个整数expectNumber，找出二叉树中结点值的和为expectNumber的所有路径。
1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
2.叶子节点是指没有子节点的节点
3.路径只能从父节点到子节点，不能从子节点到父节点
4.总节点数目为n
如二叉树root为{10,5,12,4,7},expectNumber为22则合法路径有[[10,5,7],[10,12]]

数据范围:
树中节点总数在范围 [0, 5000] 内
-1000 <= 节点值 <= 1000
-1000 <= expectNumber <= 1000

回溯解法

vector<vector<int>> res;
vector<vector<int>> FindPath(TreeNode* root,int expectNumber) {
    vector<int> path;
    backTrack(root, path, expectNumber);

    return res;
}

void backTrack(TreeNode *root, vector<int>& path, int expectNumber) {
    if (root == nullptr)    return;
    if (root->left == nullptr && root->right == nullptr && expectNumber - root->val == 0) {
        path.emplace_back(root->val);
        res.emplace_back(path);
        path.pop_back();
        return;
    }

    path.emplace_back(root->val);
    backTrack(root->left, path, expectNumber - root->val);
    backTrack(root->right, path, expectNumber - root->val);
    path.pop_back();

}

JZ77 按之字形顺序打印二叉树

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
数据范围：0≤n≤1500,树上每个节点的val满足 ∣val∣<=1500
要求：空间复杂度：O(n)，时间复杂度：O(n)
输入：{1,2,3,#,#,4,5}
返回值：[[1],[3,2],[4,5]]

层次遍历

vector<vector<int>> res;
vector<vector<int>> Print(TreeNode* pRoot) {
    if (pRoot == nullptr)    return res;
    queue<TreeNode*> q;
    q.push(pRoot);
    int depth = 1;
    while (!q.empty()) {
        int sz = q.size();
        vector<int> path;
        for (int i = 0; i < sz; i++) {

            TreeNode *node = q.front();
            path.emplace_back(node->val);
            q.pop();
            if (node->left != nullptr) {
                q.push(node->left);
            } 
            if (node->right != nullptr) {
                q.push(node->right);
            }
        }
        if (depth % 2 != 0) {
            res.emplace_back(path);
        }
        else {
            reverse(path.begin(), path.end());
            res.emplace_back(path);
        }
        depth++;
    }


    return res;
}

JZ54 二叉搜索树的第k个节点

给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值。
1.返回第k小的节点值即可
2.不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1
3.保证n个节点的值不一样
数据范围：0≤n≤1000, 0≤k≤1000，树上每个结点的值满足0≤val≤1000
进阶：空间复杂度 O(n)，时间复杂度 O(n)
输入：{5,3,7,2,4,6,8},3
返回值：4

递归做法

vector<int> res;
int KthNode(TreeNode* proot, int k) {
    if (proot == nullptr || k == 0)    return -1;
    inOrder(proot);

    if (k > res.size()) {
        return -1;
    }

    return res[k-1];
}

void inOrder(TreeNode* root) {
    if (root == nullptr)    return;
    inOrder(root->left);
    res.emplace_back(root->val);
    inOrder(root->right);
}

非递归用栈

int KthNode(TreeNode* proot, int k) {
    int cnt = 0;
    stack<TreeNode*> s;
    while (!s.empty() || proot != nullptr) {
        while (proot != nullptr) {
            s.push(proot);
            proot = proot->left;
        }

        cnt++;
        TreeNode *p = s.top();
        if (cnt == k) {
            return p->val;
        }
        s.pop();
        proot = p->right;

    }

    return -1;
}

BM32 合并二叉树

已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。
数据范围：树上节点数量满足$0≤n≤500$，树上节点的值一定在32位整型范围内。
进阶：空间复杂度$O(1)$，时间复杂度$O(n)$
输入：{1,3,2,5},{2,1,3,#,4,#,7}
返回值：{3,4,5,5,4,#,7}

TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
    if (t1==nullptr) {
        return t2;
    }
    
    if (t2==nullptr) {
        return t1;
    }
    
    TreeNode *root=new TreeNode(t1->val+t2->val);
    root->left=mergeTrees(t1->left, t2->left);
    root->right=mergeTrees(t1->right, t2->right);
    
    return root;
}

JZ7 重建二叉树

给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
数据范围：n≤2000，节点的值−10000≤val≤10000
要求：空间复杂度O(n)，时间复杂度O(n)
输入：[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]
返回值：[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]

递归做法

// 根据前序和中序重建二叉树
// 递归做法
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
    // 1、根据前序在中序里面找到根节点的下标
    if (pre.size() == 0 || vin.size() == 0)    return nullptr;
    TreeNode *root = new TreeNode(pre[0]);
    int index = -1;
    for (int i = 0; i < vin.size(); i++) {
        if (vin[i] == root->val){
            index = i;
            break;
        }
    }

    // 2、递归构建左子树
    vector<int> left_new_pre(pre.begin()+1, pre.begin()+1+index);
    vector<int> left_new_vin(vin.begin(), vin.begin()+index);
    root->left = reConstructBinaryTree(left_new_pre, left_new_vin);

    // 3、递归构建右子树
    vector<int> right_new_pre(pre.begin()+index+1, pre.end());
    vector<int> right_new_vin(vin.begin()+index+1, vin.end());
    root->right =reConstructBinaryTree(right_new_pre, right_new_vin);    

    return root;

}

非递归做法

// 栈的做法
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
    if (pre.size() == 0 || vin.size() == 0)    return nullptr;
    stack<TreeNode*> s;
    TreeNode *root = new TreeNode(pre[0]);
    TreeNode *cur = root;
    // 两个指针遍历先序和中序列表
    for (int i=1, j=0; i < pre.size(); i++) {
        // 如果不相等说明左节点还可以添加
        if (cur->val != vin[j]) {
            s.push(cur);
            cur->left = new TreeNode(pre[i]);
            cur = cur->left;
        }
        // 如果相等，说明需要弹出栈顶元素添加右节点
        else {
            j++;
            while (!s.empty() && s.top()->val == vin[j]) {
                cur = s.top();
                s.pop();
                j++;
            }

            cur->right = new TreeNode(pre[i]);
            cur = cur->right;
        }
    }

    return root;
}

JZ26 树的子结构

输入两棵二叉树A，B，判断B是不是A的子结构。（我们约定空树不是任意一个树的子结构）
假如给定A为{8,8,7,9,2,#,#,#,#,4,7}，B为{8,9,2}，2个树的结构如下，可以看出B是A的子结构
数据范围:
0 <= A的节点个数 <= 10000
0 <= B的节点个数 <= 10000
输入：{8,8,7,9,2,#,#,#,#,4,7},{8,9,2}
返回值：true

前序遍历法

bool recur(TreeNode *root1, TreeNode *root2) {
    if (root1 == nullptr && root2 != nullptr)    return false;
    if (root1 == nullptr || root2 == nullptr)    return true;
    if (root1->val != root2->val)    return false;

    return recur(root1->left, root2->left) && recur(root1->right, root2->right);
}
// 前序位置处理逻辑
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
    // bad case
    if (pRoot2 == nullptr)    return false;
    if (pRoot1 == nullptr && pRoot2 != nullptr)    return false;
    if (pRoot1 == nullptr || pRoot2 == nullptr)    return true;

    // 前序位置
    bool flag1 = recur(pRoot1, pRoot2);

    bool flag2 = HasSubtree(pRoot1->left, pRoot2);
    bool flag3 = HasSubtree(pRoot1->right, pRoot2);

    return flag1 || flag2 || flag3;

}

JZ27 二叉树的镜像

操作给定的二叉树，将其变换为源二叉树的镜像。
数据范围：二叉树的节点数0≤n≤1000 ， 二叉树每个节点的值0≤val≤1000
要求： 空间复杂度 O(n)。

后序递归法

TreeNode* Mirror(TreeNode* pRoot) {
    if (pRoot == nullptr)    return nullptr;

    TreeNode *left = Mirror(pRoot->left);
    TreeNode *right = Mirror(pRoot->right);

    // 在后序位置处理递归的逻辑
    pRoot->left = right;
    pRoot->right = left;

    return pRoot;

}

非递归用栈

TreeNode* Mirror(TreeNode* pRoot) {
    if (pRoot == nullptr)    return nullptr;
    stack<TreeNode*> s;
    s.push(pRoot);
    while (!s.empty()) {
        TreeNode *node = s.top();
        s.pop();
        if (node->left != nullptr)    s.push(node->left);
        if (node->right != nullptr)    s.push(node->right);

        TreeNode *temp = node->left;
        node->left = node->right;
        node->right = temp;
    }

    return pRoot;
}

BM31 对称的二叉树

给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）
数据范围：节点数满足0≤n≤1000，节点上的值满足∣val∣≤1000
要求：空间复杂度 O(n)，时间复杂度 O(n)
备注：你可以用递归和迭代两种方法解决这个问题
输入：{1,2,2,3,4,4,3}
返回值：true

如果二叉树是对称的，那么按照”根-左-右”的顺序和按照”根-右-左”的顺序返回的值是一样的。

bool isSymmetrical(TreeNode* pRoot) {
    if (pRoot == nullptr)    return true;

    return recur(pRoot->left, pRoot->right);
}

bool recur(TreeNode *root1, TreeNode *root2) {
    if (root1 == nullptr && root2 == nullptr)    return true;
    if (root1 == nullptr || root2 == nullptr)    return false;
    if (root1->val != root2->val)    return false;


    return recur(root1->left, root2->right) && recur(root1->right, root2->left);

}

JZ32 从上往下打印二叉树

不分行从上往下打印出二叉树的每个节点，同层节点从左至右打印。例如输入{8,6,10,#,#,2,1}，如以下图中的示例二叉树，则依次打印8,6,10,2,1(空节点不打印，跳过)，请你将打印的结果存放到一个数组里面，返回。
数据范围:
0<=节点总数<=1000
-1000<=节点值<=1000
输入：{8,6,10,#,#,2,1}
返回值：[8,6,10,2,1]

vector<int> res;
vector<int> PrintFromTopToBottom(TreeNode* root) {
    if (root == nullptr)    return res;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            TreeNode *node = q.front();
            res.emplace_back(node->val);
            q.pop();
            if (node->left != nullptr)    q.push(node->left);
            if (node->right != nullptr)    q.push(node->right);
        }
    }

    return res;
}

BM34 判断是不是二叉搜索树

给定一个二叉树根节点，请你判断这棵树是不是二叉搜索树。
二叉搜索树满足每个节点的左子树上的所有节点均严格小于当前节点且右子树上的所有节点均严格大于当前节点。
数据范围：节点数量满足$1≤n≤10^4$，节点上的值满足$-2^{31}≤val≤2^31-1$
输入：{2,1,3}
返回值：true

// 中序遍历一遍即可
long pre=INT_MIN;
bool isValidBST(TreeNode* root) {
    if (root==nullptr) {
        return true;
    }
    
    bool left=isValidBST(root->left);
    if (!left) {
        return false;
    }
    if (root->val<=pre) {
        return false;
    }
    pre=root->val;
    
    // 更新最值
    bool right=isValidBST(root->right);
    if (!right) {
        return false;
    }
    
    return true;
}

JZ79 判断是不是平衡二叉树

输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
注：我们约定空树是平衡二叉树。
数据范围：n≤100,树上节点的val值满足0≤n≤1000
要求：空间复杂度O(1)，时间复杂度 O(n)

自顶向下

bool IsBalanced_Solution(TreeNode* pRoot) {
    if (pRoot == nullptr)    return true;
    int left = maxDepth(pRoot->left);
    int right = maxDepth(pRoot->right);
    if (abs(left-right) > 1)    return false;

    return IsBalanced_Solution(pRoot->left) &&
     IsBalanced_Solution(pRoot->right);
}

int maxDepth(TreeNode *root) {
    if (root == nullptr)    return 0;

    return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}

自底向上

// 从最底的叶子结点开始，计算该结点的高度。
// 若该结点不平衡，则直接返回-1，不用继续计算其他结点高度，否则返回其高度；
// 若自底向上的过程中一直都是平衡的，则最终的树是平衡的。
bool IsBalanced_Solution(TreeNode* pRoot) {
    if (pRoot == nullptr)    return true;

    return getDepth(pRoot) >= 0;
}

int getDepth(TreeNode *root) {
    if (root == nullptr)    return 0;
    int left = getDepth(root->left);
    if (left == -1) {
        return -1;
    }
    int right = getDepth(root->right);
    if (right == -1 || abs(left - right) > 1) {
        return -1;
    }


    return max(left, right) + 1;
}

BM35 判断是不是完全二叉树

给定一个二叉树，确定他是否是一个完全二叉树。
完全二叉树的定义：若二叉树的深度为 h，除第 h 层外，其它各层的结点数都达到最大个数，第 h 层所有的叶子结点都连续集中在最左边，这就是完全二叉树。（第 h 层可能包含 [1~2h] 个节点）
数据范围：节点数满足$1≤n≤100$
输入：{1,2,3,4,5,#,6}
返回值：false

// 思路：层次遍历，标记出现空结点的位置即可
bool isCompleteTree(TreeNode* root) {
    queue<TreeNode*> q;
    q.push(root);
    bool flag=true;
    while (!q.empty()) {
        int sz=q.size();
        for (int i=0;i<sz;i++) {
            TreeNode *node=q.front();
            q.pop();
            if (node==nullptr) {
                flag=false;
            }
            else {
                if (!flag) {
                    return false;
                }
                q.push(node->left);
                q.push(node->right);
            }
        }
    }
    
    return true;
}

二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
思路：

• 递归左右子树；
• 两种情况：
  • 1、要么左右子树都包含p和q结点；
  • 2、要么p和q结点只在左子树或只在右子树。

TreeNode *res;
bool dfs(TreeNode *root, TreeNode *p, TreeNode *q) {
    if (root == nullptr) {
        return false;
    }
    // 递归左右子树
    bool lChild = dfs(root->left, p, q);
    bool rChild = dfs(root->right, p, q);

    // 两种情况：
    // 1、要么左右子树都包含p和q结点；
    // 2、要么p和q结点只在左子树或只在右子树。
    if ((lChild && rChild) || 
    ((root->val == p->val || root->val == q->val) 
    && (lChild || rChild))) {
        res = root;
    }
    return lChild || rChild || 
    (root->val == p->val || root->val == q->val);
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, 
                            TreeNode* q) {
    dfs(root, p, q);
    return res;
}

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

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
1.对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q，最近公共祖先LCA(T,p,q)表示一个节点x，满足x是p和q的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先.
2.二叉搜索树是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值
3.所有节点的值都是唯一的。
4.p、q 为不同节点且均存在于给定的二叉搜索树中。
数据范围:
3<=节点总数<=10000
0<=节点值<=10000

输入：{7,1,12,0,4,11,14,#,#,3,5},1,12
返回值：7
说明：节点1 和 节点12的最近公共祖先是7

// 1、从根节点出发，找到p和q两个结点的路径
// 2、遍历两个路径，找到最后一个相同的元素，就是最近的公共祖先结点
vector<int> findPath(TreeNode* root, int val) {
    vector<int> path;
    while (root->val != val) {
        path.emplace_back(root->val);
        if (root->val > val) {
            root = root->left;
        }
        else if (root->val < val) {
            root = root->right;
        }
    }
    path.emplace_back(root->val);

    return path;
}
int lowestCommonAncestor(TreeNode* root, int p, int q) {
    vector<int> path1 = findPath(root, p);
    vector<int> path2 = findPath(root, q);
    int res;

    for (int i = 0; i < path1.size() && i < path2.size(); i++) {
        if (path1[i] == path2[i]) {
            res = path1[i];
        }
        else
            break;
    }

    return res;
}

BM41 输出二叉树的右视图

请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图
数据范围：$0≤n≤10000$
要求： 空间复杂度$O(n)$，时间复杂度$O(n)$

输入：[1,2,4,5,3],[4,2,5,1,3]
返回值：[1,3,5]

// 利用哈希表来记录中序的位置关系，统计长度来建树
unordered_map<int, int> memo;
vector<int> res;
vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
    if (xianxu.size()==0) {
        return res;
    }
    
    for (int i=0; i<zhongxu.size(); i++) {
        memo[zhongxu[i]]=i;
    }
    
    // 建树
    TreeNode *root=buildTree(xianxu, 0, zhongxu.size()-1, zhongxu, 0, zhongxu.size()-1);
    
    // 层次遍历
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int sz=q.size();
        
        for (int i=0;i<sz;i++) {
            TreeNode *node=q.front();
            q.pop();
            if (node->left!=nullptr) {
                q.push(node->left);
            }
            
            if (node->right!=nullptr) {
                q.push(node->right);
            }
            
            if (i==sz-1) {
                res.emplace_back(node->val);
            }
        }
    }
    
    return res;
    
}

TreeNode* buildTree(vector<int>& xianxu, int l1, int r1, vector<int>& zhongxu, int l2, int r2) {
    // bad case
    if (l1>r1 || l2>r2) {
        return nullptr;
    }
    int inIndex=memo[xianxu[l1]];
    int leftsize=inIndex-l2, rightsize=r2-inIndex;
    TreeNode *root=new TreeNode(xianxu[l1]);
    
    root->left=buildTree(xianxu, l1+1, l1+leftsize, zhongxu, l2, inIndex-1);
    root->right=buildTree(xianxu, l1+1+leftsize, r1, zhongxu, inIndex+1, r2);
    
    return root;
    
}

二分搜索

JZ4 二维数组中的查找

在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]
给定 target = 7，返回 true。
给定 target = 3，返回 false。
数据范围：矩阵的长宽满足0≤n,m≤500，矩阵中的值满足0≤val≤10^9
进阶：空间复杂度O(1)，时间复杂度O(n+m)

// 对于矩阵，按副对角线进行二分，从元素左下遍历到右上的位置；
bool Find(int target, vector<vector<int> > array) {
    if (array.size() == 0 || array[0].size() == 0)    return false;
    int m = array.size(), n = array[0].size();
    for (int i = m - 1, j = 0; i >= 0 && j < n;) {
        if (array[i][j] > target)    i--;
        else if (array[i][j] < target) j++;
        else    return true;
    }

    return false;
}

BM19 寻找峰值

给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。
1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
2.假设 nums[-1] = nums[n] = −∞
3.对于所有有效的 i 都有 nums[i] != nums[i + 1]
4.你可以使用O(logN)的时间复杂度实现此问题吗？

数据范围：1≤nums.length≤2×10^5
-2^{31}<= nums[i] <= 2^{31}-1
如输入[2,4,1,2,7,8,4]时，会形成两个山峰，一个是索引为1，峰值为4的山峰，另一个是索引为5，峰值为8的山峰。

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

JZ11 旋转数组的最小数字

有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。

数据范围：1≤n≤10000，数组中任意元素的值:0≤val≤10000
要求：空间复杂度：O(1)，时间复杂度：O(logn)

int minNumberInRotateArray(vector<int> rotateArray) {
    int low = 0, high = rotateArray.size() - 1;
    while (low < high) {
        int mid = (low + high) / 2;
        // 旋转点在[mid+1, high]之间
        if (rotateArray[mid] > rotateArray[high]) {
            low = mid + 1;
        }
        // 旋转点在[low, mid]之间
        else if (rotateArray[mid] < rotateArray[high]) {
            high = mid;
        }
        else {
            high--;
        }
    }

    return rotateArray[low];
}

数学技巧

厄拉多塞筛法

• 如果一个数n是质数，它只需要满足在[2,sqrt(n))的范围内是质数即可。
• 如果一个数x是质数，则对应的2x，3x…必定不是质数。

计数质数

给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

int countPrimes(int n) { 
    // 方法二：改进的厄拉多塞筛法
    vector<int> isPrime(n, 1);
    for (long i = 2; i * i < n; i++) {
        if (isPrime[i]) {
            for (long j = i * i; j < n; j+=i) {
                isPrime[j] = 0;
            }
        }
    }

    int cnt = 0;
    for (int i = 2; i < n; i++) {
        if (isPrime[i])
            cnt++;
    }
    return cnt;
        
}

位操作

// 利用或操作 `|` 和空格将英文字符转换为小写
('a' | ' ') = 'a'
('A' | ' ') = 'a'
// 利用与操作 `&` 和空格将英文字符转换为大写
('b' & '_') = 'B'
('B' & '_') = 'B'
// 利用异或操作 `^` 和空格将英文字符大小写互换
('d' ^ ' ') = 'D'
('D' ^ ' ') = 'd'
// 判断两个数是否异号
int x = -1, y = 2;
bool f = ((x^y) < 0);	// true

int x = 3, y = 2;
bool f = ((x^y) < 0);	// false

n & (n-1)

作用是消除数字 n 的二进制表示中的位置最后的 1。

cout << (4&3);	// 0
cout << (6&5);	// !=0

位1的个数

输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 ‘1’。

int hammingWeight(uint32_t n) {
    // 递归法
    // if (n == 0)  return 0;
    // n = (n&(n - 1));
    // return (hammingWeight(n) + 1);

    // 迭代法 
    int cnt = 0;
    while (n != 0) {
        n = n & (n-1);
        cnt++;
    }

    return cnt;
}

判断一个数是不是 2 的指数

输入：n = 16
输出：true
解释：24 = 16
你能够不使用循环/递归解决此问题吗？

// 如果一个数是2的指数，则它的二进制表示中只有一个1
bool isPowerOfTwo(int n) {
    if (n <= 0) return false;
    return (n & (n - 1)) == 0;
}

a ^ a = 0

一个数和它本身做异或运算结果为 0，即 a ^ a = 0；一个数和 0 做异或运算的结果为它本身，即 a ^ 0 = a。

查找只出现一次的元素

输入: [4,1,2,1,2]
输出: 4

int singleNumber(vector<int>& nums) {
    int res = 0;
    for (int num:nums) {
        res ^= num;
    }

    return res;
}

寻找缺失的元素

只要把所有的元素和索引做异或运算，成对儿的数字都会消为 0，只有这个落单的元素会剩下。

输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

int missingNumber(vector<int>& nums) {
    int n = nums.size();
    int res = 0;
    res ^= n;
    for (int i = 0; i < n; i++) {
        res ^= (nums[i]^i);
    }

    return res;
}

快速乘+快速幂

JZ83 剪绳子II

给你一根长度为 n 的绳子，请把绳子剪成整数长的 m 段（ m 、 n 都是整数， n > 1 并且 m > 1 ， m <= n ），每段绳子的长度记为 k[1],…,k[m] 。请问 k[1]×k[2]×…×k[m] 可能的最大乘积是多少？例如，当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18 。

由于答案过大，请对 998244353 取模。
数据范围：2≤n≤10^14
进阶：空间复杂度 O(1)， 时间复杂度 O(logn)
输入：4
返回值：4
说明：拆分成 2 个长度为 2 的绳子，2×2=4

long long mod = 998244353;
long long fast(long long x, long long y) {
    x %= mod;
    y %= mod;
    long long res = 0;
    while (y != 0) {
        if ((y & 1) != 0) {
            res += x;
            if (res >= mod) {
                res %= mod;
            }
        }
        y = y >> 1;
        x = x << 1;
        if (x >= mod) {
            x %= mod;
        }
    }

    return res;
}

long long Pow(long long x, long long y) {
    long long res = 1;
    while (y != 0) {
        if ((y & 1) != 0) {
            res =fast(res, x);
        }
        x = fast(x, x);
        if (x >= mod) {
            x %= mod;
        }
        y = y >> 1;
    }

    return res;
}
long long cutRope(long long number) {
    if (number <= 3) {
        return number - 1;
    }

    if (number % 3 == 0) {
        return Pow(3, number / 3);
    }
    else if (number % 3 == 1) {
        return fast(4, Pow(3, (number-4)/3));
    }

    return fast(2, Pow(3, (number - 2)/3));
}

阶乘操作

阶乘后的零

给定一个整数 n ，返回 n! 结果中尾随零的数量。
输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0

该题目可以转化为n!中含有多少个5的倍数。

5!<=1, 25!<=5×1+1, 125<=5×(5+1)+1=5×5+5+1

// n!中含有多少个5的倍数
int trailingZeroes(int n) {
    long cnt = 0;
    for (long base = 5; base <=n; base*=5) {
        cnt += n/base;
    }

    return cnt;
}

阶乘后的K个零

二分法+阶乘后的零统计。

输入：k = 0
输出：5
解释：0!, 1!, 2!, 3!, 和 4! 均符合 k = 0 的条件。
0 <= k <= 10^9

int preimageSizeFZF(int k) {

    // cout << findLeft(k) << "  " << findRight(k) << endl;
    return (findRight(k) - findLeft(k));
    return 0;

}

long findLeft(int k) {
    long low = 0, high = LONG_MAX, mid;
    while (low < high) {
        mid = (low + high) / 2;
        if (countZero(mid) < k) {
            low = mid + 1;
        }
        // 这里不减去1因为减去1后可能该处的值属于边界内的
        else if (countZero(mid) > k) {
            high = mid;
        }
        else {
            high = mid;
        }
    }

    return low;
}

long findRight(int k) {
    long low = 0, high = LONG_MAX, mid;
    while (low < high) {
        mid = (low + high) / 2;
        if (countZero(mid) < k) {
            low = mid + 1;
        }
        else if (countZero(mid) > k) {
            high = mid;
        }
        else {
            // 加1是为了寻找右边界
            low = mid + 1;
        }
    }

    return low;
}

long countZero(long n) {
    long cnt = 0;
    for (long base = 5; base <=n; base*=5) {
        cnt += n/base;
    }

    return cnt;
}

水塘抽样

题目特点：给一个未知长度n的序列，如何在其中随机地选择 k 个元素？其中每个样本被选中的概率时一样的。

只选一个元素：当你遇到第 i 个元素时，以 1/i 的概率更新结果就可以保证结果是平均随机。

即第i个元素被选中的概率为1/n。

选k个元素：当你遇到第 i 个元素时，以 k/i 的概率更新结果就可以保证结果是平均随机。

即第i个元素被选中的概率为k/n。

做法：随机选择区间 [0,i) 内的一个整数，如果其等于 0，则将返回值置为该元素。

链表随机节点

给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样。
输入
[“Solution”, “getRandom”, “getRandom”, “getRandom”, “getRandom”, “getRandom”]
[[[1, 2, 3]], [], [], [], [], []]
输出
[null, 1, 3, 2, 2, 3]

解释
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // 返回 1
solution.getRandom(); // 返回 3
solution.getRandom(); // 返回 2
solution.getRandom(); // 返回 2
solution.getRandom(); // 返回 3
// getRandom() 方法应随机返回 1、2、3中的一个，每个元素被返回的概率相等。

Solution(ListNode* head) {
    this->head = head;
}

int getRandom() {
    ListNode *p = this->head;
    int i = 0;
    int res;
    while (p != nullptr) {
        i++;
        // 可以理解成随机生成[0, i)之间的数，数字是0的概率是1/i
         int j = rand() % i;
        if (j == 0) {
            res = p->val;
        }  

        p = p->next;
    }

    return res;
}

随机数索引

给你一个可能含有 重复元素 的整数数组 nums ，请你随机输出给定的目标数字 target 的索引。你可以假设给定的数字一定存在于数组中。
输入
[“Solution”, “pick”, “pick”, “pick”]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
输出
[null, 4, 0, 2]

private:
    vector<int> nums;

public:
Solution(vector<int>& nums): nums(nums) {
}

int pick(int target) {
    int cnt = 0;
    int res;
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] == target) {
            cnt++;
            int j = rand()%cnt;
            if (j == 0) {
                res = i;
            }
        }
    }

    return res;
}

博弈论

巴什博奕：n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。

结论：如果 n 是（m+1）的倍数，那么 先手者就必输。证明如下。

令$n=k(m+1)+x$，只要先手者每次保持物品数量是(m+1)的整数倍，最后造成的局面一定是对于后手者，只剩下m+1个物品，此时无论后手者怎么选，先手者都能赢。

Nim游戏

你和你的朋友，两个人一起玩 Nim 游戏：

桌子上有一堆石头。
你们轮流进行自己的回合， 你作为先手 。
每一回合，轮到的人拿掉 1 - 3 块石头。
拿掉最后一块石头的人就是获胜者。
假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。
你和你的朋友，两个人一起玩 Nim 游戏：
输入：n = 4
输出：false

bool canWinNim(int n) {
       // 巴什博弈的结论：只要物品数n是(m+1)的整数倍，那么先手者必输。
       return (n%4 != 0);
   }

脑筋急转弯

灯泡开关

初始时有 n 个灯泡处于关闭状态。第一轮，你将会打开所有灯泡。接下来的第二轮，你将会每两个灯泡关闭第二个。
第三轮，你每三个灯泡就切换第三个灯泡的开关（即，打开变关闭，关闭变打开）。第 i 轮，你每 i 个灯泡就切换第 i 个灯泡的开关。直到第 n 轮，你只需要切换最后一个灯泡的开关。
找出并返回 n 轮后有多少个亮着的灯泡

输入：n = 3
输出：1
解释：
初始时, 灯泡状态 [关闭, 关闭, 关闭].
第一轮后, 灯泡状态 [开启, 开启, 开启].
第二轮后, 灯泡状态 [开启, 关闭, 开启].
第三轮后, 灯泡状态 [开启, 关闭, 关闭].

int bulbSwitch(int n) {
     // 亮着的灯泡数必定是奇数的反转次数
	// 第i个灯泡的反转次数等于它所有因子的数量
    return (int) sqrt(n);
}

约瑟夫环问题

JZ62 孩子们的游戏(圆圈中最后剩下的数)

有个游戏是这样的：首先，让 n 个小朋友们围成一个大圈，小朋友们的编号是0~n-1。然后，随机指定一个数 m ，让编号为0的小朋友开始报数。每次喊到 m-1 的那个小朋友要出列唱首歌，然后可以在礼品箱中任意的挑选礼物，并且不再回到圈中，从他的下一个小朋友开始，继续0… m-1报数….这样下去….直到剩下最后一个小朋友，可以不用表演，并且拿到牛客礼品，请你试着想下，哪个小朋友会得到这份礼品呢?
数据范围：1≤n≤5000，1≤m≤10000
要求：空间复杂度 O(1)，时间复杂度 O(n)
输入：5,3
返回值：3

递归方法

int LastRemaining_Solution(int n, int m) {
    if (n == 1)
        return 0;

    // 上一个被抬走的人的编号是
    int x = LastRemaining_Solution(n - 1, m);

    return (x + m) % n;
}

迭代方法

int LastRemaining_Solution(int n, int m) {
    int x = 0;
    for (int i = 2; i <= n; i++) {
        x = (x+m) % i;
    }

    return x;
}

特殊数据结构

最大栈

// 对于pair, tuple这样的数据类型。
// 1.pair:
// 大根堆：
priority_queue<pair<int, int>> pq0;
// 小根堆：按照pair的first排序，再按照second排序
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq1;

// 2.tuple:
// 默认是使用大根堆
priority_queue<tuple<int,int,int>> tp0;
// 小根堆，按照tuple的0元素排，再按照1元素排，最后按2元素排
priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<tuple<int,int,int>>> tp1;
// 大根堆
priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,less<tuple<int,int,int>>> tp2;

最大频率栈

设计一个类似堆栈的数据结构，将元素推入堆栈，并从堆栈中弹出出现频率最高的元素。

实现 FreqStack 类:
FreqStack() 构造一个空的堆栈。
void push(int val) 将一个整数 val 压入栈顶。
int pop() 删除并返回堆栈中出现频率最高的元素。
如果出现频率最高的元素不只一个，则移除并返回最接近栈顶的元素。

输入：
[“FreqStack”,”push”,”push”,”push”,”push”,”push”,”push”,”pop”,”pop”,”pop”,”pop”],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
输出：[null,null,null,null,null,null,null,5,7,5,4]
解释：
FreqStack = new FreqStack();
freqStack.push (5);//堆栈为 [5]
freqStack.push (7);//堆栈是 [5,7]
freqStack.push (5);//堆栈是 [5,7,5]
freqStack.push (7);//堆栈是 [5,7,5,7]
freqStack.push (4);//堆栈是 [5,7,5,7,4]
freqStack.push (5);//堆栈是 [5,7,5,7,4,5]
freqStack.pop ();//返回 5 ，因为 5 出现频率最高。堆栈变成 [5,7,5,7,4]。
freqStack.pop ();//返回 7 ，因为 5 和 7 出现频率最高，但7最接近顶部。堆栈变成 [5,7,5,4]。
freqStack.pop ();//返回 5 ，因为 5 出现频率最高。堆栈变成 [5,7,4]。
freqStack.pop ();//返回 4 ，因为 4, 5 和 7 出现频率最高，但 4 是最接近顶部的。堆栈变成 [5,7]。

0 <= val <= 109
push 和 pop 的操作数不大于 2 * 104。
输入保证在调用 pop 之前堆栈中至少有一个元素。

优先队列+哈希表

优先队列C++默认是大顶堆。

// 方法一：优先队列+哈希表
// 优先队列控制栈内元素有序
// 哈希表控制频率最高的元素优先输出
// tuple: freq, index, val
// tuple解释：先按照出现的频率排序，再按照出现的先后索引排序，最后才是进栈的值
priority_queue<tuple<int, int, int>> pq;   
unordered_map<int, int> val2freq;

int index;
FreqStack():index(0) {
}

void push(int val) {
    int freq = val2freq[val]++;
    index++;
    pq.emplace(tuple(freq, index, val));
}

int pop() {
    // 队头元素出栈
    int val = get<2>(pq.top());
    pq.pop();
    val2freq[val]--;

    return val;
}

两个哈希表

// 第二种解法：两个哈希表
// 哈希表1：记录出现值和出现的频率
// 哈希表2：记录当前频率和该频率下的栈
unordered_map<int, int> val2freq;
unordered_map<int, stack<int>> freq2val;
int maxFreq = -1;
FreqStack() {

}

void push(int val) {
    int freq = val2freq[val]++;
    freq2val[freq].push(val);
    maxFreq = max(maxFreq, freq);

}

int pop() {
    int val = freq2val[maxFreq].top();
    freq2val[maxFreq].pop();
    val2freq[val]--;

    if (freq2val[maxFreq].empty()) {
        maxFreq--;
    }

    return val;
}

JZ49 丑数

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第 n个丑数。
数据范围：0≤n≤2000
要求：空间复杂度 O(n)， 时间复杂度 O(n)

输入：7
返回值：8

利用最小堆记录每个丑数，利用哈希表来防止有重复的丑数入最小堆。

int GetUglyNumber_Solution(int index) {
    if (index == 0)    return 0;
    vector<long> f = {2, 3, 5};
    unordered_map<long, int> memo;
    priority_queue<long, vector<long>, greater<long>> pq;
    memo[1]++;
    pq.emplace(1);

    int res;
    while (index > 0) {
        res = pq.top();
        pq.pop();
        index--;

        for (int j = 0; j < 3; j++) {
            if (!memo.count(res*f[j])) {
                memo[res*f[j]]++;
                pq.emplace(res*f[j]);
            }
        }
    }

    return res;

}

BM48 数据流中的中位数

输入：[5,2,3,4,1,6,7,0,8]
返回值：”5.00 3.50 3.00 3.50 3.00 3.50 4.00 3.50 4.00 “
说明：
数据流里面不断吐出的是5,2,3…,则得到的平均数分别为5,(5+2)/2,3…

// 默认是大顶堆，存着值较小的值
priority_queue<int> max_pq;
// 小顶堆，存着值大于大顶堆的值
priority_queue<int, vector<int>,greater<int>> min_pq;
void Insert(int num) {
    min_pq.push(num);
    max_pq.push(min_pq.top());
    min_pq.pop();
    
    if (max_pq.size() > min_pq.size()) {
        min_pq.push(max_pq.top());
        max_pq.pop();
        
    }
}

double GetMedian() { 
    if (max_pq.size() == min_pq.size()) {
        return (float)(max_pq.top()+min_pq.top())/2;
    }
    
    return max_pq.size()>min_pq.size()?max_pq.top():min_pq.top();

}

单调栈

每次新元素入栈后，栈内的元素都保持有序（单调递增或单调递减）。

vector<int> nextGreaterElement(vector<int>& nums) {
    vector<int> res(nums.size()); // 存放答案的数组
    stack<int> s;
    // 倒着往栈里放
    for (int i = nums.size() - 1; i >= 0; i--) {
        // 判定个子高矮
        while (!s.empty() && s.top() <= nums[i]) {
            // 矮个起开，反正也被挡着了。。。
            s.pop();
        }
        // nums[i] 身后的 next great number
        res[i] = s.empty() ? -1 : s.top();
        s.push(nums[i]);
    }
    return res;
}

步骤：

• 从后往前处理；
• 什么时候出栈；
• 什么时候入栈。

下一个更大的元素I

nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：

• 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
• 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
• 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。

解法：单调栈+哈希表 => 时间：O(n+m)

vector<int> res;
unordered_map<int, int> m;
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
    stack<int> s;
    res.resize(nums1.size());
    for (int i = 0; i < nums1.size(); i++) {
        m[nums1[i]] = i;
    }

    for (int i = nums2.size() - 1; i >= 0; i--) {
        while (!s.empty() && s.top() <= nums2[i]) {
            s.pop();
        }
        if (m.count(nums2[i])) {
            res[m[nums2[i]]] = s.empty()?-1:s.top();
        }
        s.push(nums2[i]);
    }

    return res;
}

下一个更大的元素II

输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

vector<int> res;
vector<int> nextGreaterElements(vector<int>& nums) {
    res.resize(nums.size());
    stack<int> s;
    // 假设把数组翻倍，再取余即可
    for (int i = 2 * nums.size() - 1; i >= 0; i--) {
        while (!s.empty() && s.top() <= nums[i % nums.size()])   
            s.pop();
        // if (i < nums.size())
        //     res[i] = s.empty()?-1:s.top();
        res[i % nums.size()] = s.empty()?-1:s.top();
        s.push(nums[i % nums.size()]);
    }

    return res;
}

每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指在第 i 天之后，才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

vector<int> res;
vector<int> dailyTemperatures(vector<int>& temperatures) {
    res.resize(temperatures.size());
    stack<int> s;
    for (int i = temperatures.size() - 1; i >= 0; i--) {
        while (!s.empty() && temperatures[i] >= temperatures[s.top()]) {
            s.pop();
        }
        res[i] = s.empty()?0:s.top() - i;
        s.push(i);

    }

    return res;
}

移掉 K 位数字

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
输入：num = “10200”, k = 1
输出：”200”
解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

讲解

// 单调栈
// 1、当前的元素比前一个小，前一个元素则丢弃，k--;
// 2、若遍历到最后k!=0，说明该序列是由小到大递增的，所以丢弃后k位。
vector<char> s;
string removeKdigits(string num, int k) {
    for (char& ch:num) {
        while (!s.empty() && s.back() > ch && k != 0) {
                s.pop_back();
                k--;
        }

        s.emplace_back(ch);
    }
	
    // 遍历到最后k>0，则丢弃后k位
    while (k > 0) {
        s.pop_back();
        k--;
    }


    // 排除第一个数字是0（前导零）
  	string res;
    bool isLeadingZero = true;
    for (auto &ch:s) {
        if (ch != '0') {
            isLeadingZero = false;
        }
        if (isLeadingZero == false)
            res += ch;
    }

    return res == "" ? "0" : res;

}    

去除重复字母（不同字符的最小子序列）

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
输入：s = “cbacdcbc”
输出：”acdb”
1 <= s.length <= 104
s 由小写英文字母组成

// 哈希表+单调栈
// 时间：O(N)
// 空间：O(N) 
// 1、一个哈希表记录元素待删除的个数
unordered_map<char, int> val2freq;
string removeDuplicateLetters(string s) {
    for (char &ch:s) {
        val2freq[ch]++;
    }
    // 2、利用单调栈控制对字符的删除，当栈顶元素的使用次数为0时，该元素不能出栈
    vector<char> stack;
    unordered_set<char> visit;

    for (char &ch:s) {
        // 当前栈中有元素和ch一样则跳过
        if (!visit.count(ch)) {
            while (!stack.empty() && stack.back() > ch && val2freq[stack.back()] != 0) {
                visit.erase(stack.back());
                stack.pop_back();
            }

            stack.emplace_back(ch);
            visit.emplace(ch);
        }
        val2freq[ch]--;
    }

    string res;
    for (char& ch:stack) {
        res += ch;
    }

    return res;
}

JZ33 二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。
数据范围：节点数量0≤n≤1000 ，节点上的值满足 1≤val≤10^5，保证节点上的值各不相同
要求：空间复杂度 O(n)，时间时间复杂度 O(n^2)

输入：[5,7,6,9,11,10,8]
返回值：true

判断数组中部分元素是否恒大于或者恒小于某一部分的值，考虑单调栈。

// 单调栈的解法
bool VerifySquenceOfBST(vector<int> sequence) {
    // bad case
    if (sequence.size() == 0)    return false;
    stack<int> s;
    int root = INT_MAX;
    // 按照根-右子树-左子树的顺序访问 
    for (int i = sequence.size() - 1; i >= 0; i--) {
        // 查看右子树后面的左子树元素是否大于root
        if (sequence[i] > root)    return false;
        while (!s.empty() && s.top() > sequence[i]) {
            root = s.top();
            s.pop();
        }
        s.push(sequence[i]);
    }

    return true;
}

单调队列

队列中的元素会保持单调递增或单调递减的顺序。C++一般使用双向队列deque来实现。deque的API如下。

class deque {
    // 在队头插入元素 n
    void push_front(int n);
    // 在队尾插入元素 n
    void push_back(int n);
    // 在队头删除元素
    void pop_front();
    // 在队尾删除元素
    void pop_back();
    // 返回队头元素
    int front();
    // 返回队尾元素
    int back();
}

滑动窗口的最大值

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

---

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

class MonotonicQueue {
    private:
    	deque<int> q;
    public:
    	// 尾部小于n的给出队
    	void push(int n) {
            while (!q.empty() && q.back() < n) 
                q.pop_back();
            q.push_back(n);
		}
    	
    	// 队头元素是最大值
    	int max() {
            return q.front();
		}
    	
    	// 待出队元素是否还在队列中
    	void pop(int n) {
			if (!q.empty() && q.front() == n)
                q.pop_front();
        }
};

vector<int> res;
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    MonotonicQueue window;
    for (int i = 0; i < nums.size(); i++) {
        if (i < k - 1) {
            window.push(nums[i]);
        }
        else {
            window.push(nums[i]);
            res.emplace_back(window.max());
            window.pop(nums[i - k + 1]);
        }
    }

    return res;
}

队列和栈互转

用栈实现队列

[JZ9 用两个栈实现队列]

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
输入：
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

class MyQueue {
private:
    stack<int> s1;
    stack<int> s2;
public:
    MyQueue() {

    }
    
    void push(int x) {
        s1.push(x);
    }
    
    int pop() {
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
        int val = s2.top();
        s2.pop();

        return val;

    }
    
    int peek() {
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
        
        return s2.top();
    }
    
    bool empty() {
        return s1.empty() && s2.empty();
    }
};

用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
输入：
[“MyStack”, “push”, “push”, “top”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

思想：把值往后接上，保持一个队列为空，交换两个队列。

class MyStack {
private:
    queue<int> q1;
    queue<int> q2;
public:
    MyStack() {

    }
    
    void push(int x) {
        q1.push(x);
        while (!q2.empty()) {
            q1.push(q2.front());
            q2.pop();
       }

       queue<int> temp = q1;
       q1 = q2;
       q2 = temp;

    }
    
    int pop() {
        int val = q2.front();
        q2.pop();
        return val;
    }
    
    int top() {
        return q2.front();
    }
    
    bool empty() {
        return q2.empty();
    }
};

最小栈

JZ30 包含min函数的栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
输入：
[“MinStack”,”push”,”push”,”push”,”getMin”,”pop”,”top”,”getMin”]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); –> 返回 -3.
minStack.pop();
minStack.top(); –> 返回 0.
minStack.getMin(); –> 返回 -2.

思路：用一个新的栈存放小于第一个元素的最小值即可。

class MinStack {
private:
    stack<int> s;
    stack<int> s_min;
public:
    MinStack() {

    }
    
    void push(int val) {
        s.push(val);
        if (s_min.empty() || (s_min.top() >= val)) {
            s_min.push(val);
        }
    }
    
    void pop() {
        if (s.top() == s_min.top())
            s_min.pop();
        s.pop();
    }
    
    int top() {
        return s.top();
    }
    
    int getMin() {
        return s_min.top();
    }
};

JZ 31栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
说明：
1、0<=pushV.length == popV.length <=1000
2、 -1000<=pushV[i]<=1000
3、pushV 的所有数字均不相同

输入：[1,2,3,4,5],[4,3,5,1,2]
返回值：false

 // 辅助栈
stack<int> s;
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
    int i = 0, j = 0;
    while(i < pushV.size() && j < popV.size() && (s.empty() || s.top() != popV[j])) {

        s.push(pushV[i]);
        i++;

        while (!s.empty() && s.top() == popV[j]) {
            // cout << s.top() << " ";
            s.pop();
            j++;
        }

    }

    if (!s.empty())    return false;

    return true;


}

回溯法（DFS）

岛屿问题

飞地的数量

给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。
返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

输入：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出：3
解释：有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。

思路：

• 题目的本质是回溯边界的岛屿；
• 淹没岛屿；
• 统计剩余的岛屿个数。

int dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int m, n;
int res = 0;
int numEnclaves(vector<vector<int>>& grid) {
    m = grid.size();
    n = grid[0].size();
    for (int i = 0; i < m; i++) {
        dfs(grid, i, 0);
        dfs(grid, i, n - 1);
    }
    for (int j = 0; j < n; j++) {
        dfs(grid, 0, j);
        dfs(grid, m-1, j);
    }

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1)
                res++;
        }
    }

    return res;
}

void dfs(vector<vector<int>>& grid, int i, int j) {
    if (i < 0 || j < 0 || i >= m || j >=n)  return;
    if (grid[i][j] != 1)
        return;
    
    grid[i][j] = 0;
    for (auto &dir:dirs) {
        int next_i = i + dir[0];
        int next_j = j + dir[1];
        dfs(grid, next_i, next_j);
    }
}

统计封闭岛屿的数目

二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。
请返回 封闭岛屿 的数目。

输入：grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
输出：2
解释：灰色区域的岛屿是封闭岛屿，因为这座岛屿完全被水域包围（即被 1 区域包围）。

int dirs[4][2] = {{0,-1},{0,1},{-1,0},{1,0}};
int m, n;
int res=0;
int closedIsland(vector<vector<int>>& grid) {
    m = grid.size();
    n = grid[0].size();
    for (int i = 0; i < m; i++) {
        dfs(grid, i, 0);
        dfs(grid, i, n-1);
    }

    for (int j = 0; j < n; j++) {
        dfs(grid, 0, j);
        dfs(grid, m-1, j);
    }

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 0) {
                dfs(grid, i, j);
                res++;
            }
        }
    }

    return res;
}

void dfs(vector<vector<int>>& grid, int i, int j) {
    if (i<0 || j<0 || i>=m || j>=n)
        return;
    if (grid[i][j] == 1)
        return;
    grid[i][j] = 1;
    for (auto &dir:dirs) {
        int next_i = i + dir[0];
        int next_j = j + dir[1];
        dfs(grid, next_i, next_j);
    }
        

JZII105 岛屿的最大面积

给定一个由 0 和 1 组成的非空二维数组 grid ，用来表示海洋岛屿地图。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

输入：[[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]
输出：4

int dirs[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};
int m, n;
int res=0;
int cnt=0;
int maxAreaOfIsland(vector<vector<int>>& grid) {
    m = grid.size();
    n = grid[0].size();
    for (int i=0; i<m; i++) {
        for (int j=0; j<n;j++) {
            if (grid[i][j] == 1) {
                cnt=0;
                dfs(grid, i, j);
                res = max(cnt, res);
            }
        }
    }
    
    return res;
}

void dfs(vector<vector<int>>& grid, int i, int j) {
    if (i<0 || j<0 || i>=m || j>=n) {
        return;
    }
    if (grid[i][j] == 0) {
        return;
    }
    cnt++;
    grid[i][j] = 0;
    for (auto &dir:dirs) {
        int next_i = i+dir[0];
        int next_j = j+dir[1];
        dfs(grid, next_i, next_j);
    }
}

统计子岛屿

给你两个m x n的二进制矩阵grid1和grid2，它们只包含0（表示水域）和1（表示陆地）。一个岛屿是由四个方向（水平或者竖直）上相邻的1组成的区域。任何矩阵以外的区域都视为水域。
如果grid2的一个岛屿，被grid1的一个岛屿完全包含，也就是说grid2中该岛屿的每一个格子都被grid1中同一个岛屿完全包含，那么我们称grid2中的这个岛屿为子岛屿。

请你返回grid2中子岛屿的数目。

输入：grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
输出：3
解释：如上图所示，左边为 grid1 ，右边为 grid2 。
grid2 中标红的 1 区域是子岛屿，总共有 3 个子岛屿。

int dirs[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
int m, n;
int res=0;
int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
    m = grid2.size();
    n = grid2[0].size();
    // 把2中是陆地但是1中是海水的岛屿淹没掉
    for (int i=0; i<m; i++) {
        for (int j=0; j<n; j++) {
            if (grid2[i][j] == 1 && grid1[i][j] == 0) {
                dfs(grid2, i, j);
            }
            
        }
    }
    // 剩下变成了统计子岛屿的数量问题
    for (int i=0; i<m; i++) {
        for (int j=0; j<n; j++) {
            if (grid2[i][j] == 1) {
                dfs(grid2, i, j);
                res++;
            }
            
        }
    }

    return res;
}

void dfs(vector<vector<int>>& grid2, int i, int j) {
    if (i<0 || j<0 || i>=m || j>=n)
        return;
    if (grid2[i][j] == 0)
        return;

    grid2[i][j] = 0;
    for (auto &dir:dirs) {
        int next_i = i+dir[0];
        int next_j = j+dir[1];
        dfs(grid2, next_i, next_j);
    }
}

岛屿数量

给你一个由'1'（陆地）和'0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

输入：grid = [
[“1”,”1”,”1”,”1”,”0”],
[“1”,”1”,”0”,”1”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”0”,”0”,”0”]
]
输出：1

int dirs[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
int m, n;
int res=0;
int numIslands(vector<vector<char>>& grid) {
    m=grid.size();
    n=grid[0].size();
    for (int i=0; i<m; i++) {
        for (int j=0; j<n; j++) {
            if (grid[i][j] == '1') {
                dfs(grid, i, j);
                res++;
            }
        }
    }

    return res;
}

void dfs(vector<vector<char>>& grid, int i, int j) {
    if (i<0 || j<0 || i>=m || j>=n)
        return;
    if (grid[i][j] == '0')
        return;
    grid[i][j]='0';
    for (auto &dir:dirs) {
        int next_i = i+dir[0];
        int next_j = j+dir[1];
        dfs(grid, next_i, next_j);
    }
}

JZ12 矩阵中的路径

请设计一个函数，用来判断在一个n乘m的矩阵中是否存在一条包含某长度为len的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。
数据范围：0≤n,m≤20,1≤len≤25
输入：[[a,b,c,e],[s,f,c,s],[a,d,e,e]],”abcced”
返回值：true

vector<vector<int>> visit;
int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool res = false;
bool hasPath(vector<vector<char> >& matrix, string word) {
    visit.resize(matrix.size(), vector<int>(matrix[0].size()));
    for (int i = 0; i < matrix.size(); i++) {
        for (int j = 0; j < matrix[0].size(); j++) {
            if (res) {
                return res;
            }
            dfs(matrix, word, i, j, 0);

        }

    }
    return res;
}

void dfs(vector<vector<char>>& matrix, string word, 
        int i, int j, int index) {

    if (i < 0 || i >= matrix.size() || j < 0 || j >= matrix[0].size())
        return;
    f (visit[i][j] || matrix[i][j] != word[index])
        return;

    visit[i][j] = 1;

    // cout << index << " " << i << " " << j << endl;
    if (index == word.size() - 1) {
        res = true;
        return;
    }

    for (auto &dir:dirs) {
        int next_i = i + dir[0];
        int next_j = j + dir[1];
        dfs(matrix, word, next_i, next_j, index+1);
    }
    visit[i][j] = 0;

}

括号生成

思路：

• 该问题是利用两次回溯进行括号匹配；
• 剪枝方法是右括号的个数要不大于左括号个数；
• 终止条件是path里左右括号的数量相同。

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

vector<string> res;
  vector<string> generateParenthesis(int n) {

      int left = n, right = n;
      string path;
      backTrack(left, right, n, path);

      return res;
  }

  void backTrack(int left, int right, int n, string& path) {
      // 结束条件
      // 1、左括号的数量<=右括号的数量
      // 2、左右的剩余括号必须大于0
      if (left > right || left < 0 || right < 0)    return;

      if (path.size() == 2*n) {
          res.emplace_back(path);
          return;
      }

      // 做出选择
      // 选择左括号
      path += "(";
      backTrack(left - 1, right, n, path);
      path.pop_back();

      // 选择右括号
      path += ")";
      backTrack(left, right - 1, n, path);
      path.pop_back();
  }

vector<string> res;
vector<string> generateParenthesis(int n) {
    string path;
    backTrack(path, 0, 0, n);

    return res;
}

void backTrack(string& path, int left, int right, int n) {

    if (left == n && right == n) {
        res.emplace_back(path);
    }
    if (left > n || right > n)  return;

    if (right > left) {
        return;
    }
    path += '(';
    backTrack(path, left + 1, right, n);
    path.pop_back();
    path += ')';
    backTrack(path, left, right + 1, n);
    path.pop_back();
}

子集/排列/组合问题

1、穷举元素时，元素不能回头访问，即num[i]之后的元素不出现num[i]左边的元素，用depth深度进行递归；

2、穷举元素时，元素可以回头访问，num[i]之后的元素出现在num[i]左边的元素，用访问数组进行递归。

元素不可复选

子集(数组中无重复)

无重复元素，且元素不能回头访问。

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

vector<vector<int>> res;
vector<vector<int>> subsets(vector<int>& nums) {
    vector<int> path;
    backTrack(nums, path, 0);

    return res;
}

void backTrack(vector<int>& nums, vector<int>& path, int depth) {
    // 结束条件
    if (depth > nums.size())    return;
    res.emplace_back(path);

    // 选择列表
    for (int i = depth; i < nums.size(); i++) {
        // 做选择
        path.emplace_back(nums[i]);
        backTrack(nums, path, i + 1);
        // 撤销选择
        path.pop_back();
    }

}

子集(数组中有重复)

有重复元素，且元素不能回头访问。

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

// 基于子集I进行修改
   // 添加了排序和剪枝的逻辑
   vector<vector<int>> res;
   vector<vector<int>> subsetsWithDup(vector<int>& nums) {
       // 对于含重复元素的要进行排序
       sort(nums.begin(), nums.end());
       vector<int> path;
       backTrack(nums, path, 0);

       return res;
   }

   void backTrack(vector<int>& nums, vector<int>& path, int depth) {
       // 结束条件
       if (depth > nums.size())    return;
       res.emplace_back(path);

       for (int i = depth; i < nums.size(); i++) {
           // 排除非法选择
           if (i > depth && nums[i] == nums[i-1])
               continue;
           // 做出选择
           path.emplace_back(nums[i]);
           backTrack(nums, path, i + 1);
           // 撤销选择
           path.pop_back();
       }
   }

全排列(数组中无重复)

思路：

• 该问题是无重复元素，且元素可以回头访问；
• 需要访问数组防止当前元素重复访问；
• 终止条件是path里面的个数和数组长度相等。

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

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

// 元素无重复，不可多次选择
int visit[7];
vector<vector<int>> res;
vector<vector<int>> permute(vector<int>& nums) {
    vector<int> path;
    backTrack(nums, path);

    return res;
}

void backTrack(vector<int>& nums, vector<int>& path) {
    // 终止条件
    if (path.size() == nums.size()) {
        res.emplace_back(path);
        return;
    }

    // 选择列表
    for (int i = 0; i < nums.size(); i++) {
        // 是否进行选择
        if (visit[i])
            continue;

        // 做出选择
        visit[i] = 1;
        path.emplace_back(nums[i]);
        backTrack(nums, path);
        // 撤销选择
        visit[i] = 0;
        path.pop_back();
    }
}

全排列(数组中有重复)

思路：

• 该问题是有重复元素，且元素可以回头访问；
• 需要访问数组防止当前元素重复访问，此外当前元素等于前一个元素并且前一个元素没有被访问时也不能访问该元素；
• 终止条件是path里面的个数和数组长度相等。

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

1 <= nums.length <= 8
-10 <= nums[i] <= 10

int visit[9];
vector<vector<int>> res;
vector<vector<int>> permuteUnique(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<int> path;
    backTrack(nums, path);

    return res;
}

void backTrack(vector<int>& nums, vector<int>& path) {
    // 结束条件
    if (path.size() == nums.size()) {
        res.emplace_back(path);
        return;
    }

    // 选择列表
    for (int i = 0; i < nums.size(); i++) {
        // 排除非法选择
        if (visit[i])
            continue;

        // 新增加选择条件，固定相同元素在排列中的相对位置
        if (i > 0 && (nums[i] == nums[i - 1]) && !visit[i - 1]) 
            continue;
        
		// 做出选择
        path.emplace_back(nums[i]);
        visit[i] = 1;
        backTrack(nums, path);
        // 撤销选择
        path.pop_back();
        visit[i] = 0;
    }
}

组合

无重复元素，且元素不能回头访问。

输入：n = 4, k = 2
输出：
[[2,4], [3,4], [2,3], [1,2], [1,3], [1,4],]
1 <= n <= 20
1 <= k <= n

vector<vector<int>> res;
vector<vector<int>> combine(int n, int k) {
    vector<int> nums(n);
    for (int i = 1; i < n + 1; i++) {
        nums[i - 1]=i;
    }
    vector<int> path;
    backTrack(nums, path, k, 0);

    return res;
}

void backTrack(vector<int>& nums, vector<int>& path, int k, int depth) {
    // 终止条件
    if (path.size() == k) {
        res.emplace_back(path);
        return;
    }

    // 选择列表
    for (int i = depth; i < nums.size(); i++) {

        // 做选择
        path.emplace_back(nums[i]);
        backTrack(nums, path, k, i + 1);
        // 撤销选择
        path.pop_back();

    }
}

元素可重复选

组合的和(数组中无重复)

无重复元素，且元素不可回头访问。

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都 互不相同
1 <= target <= 500

 // 元素无重复但是可以重复选择
vector<vector<int>> res;
int pathSum = 0;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<int> path;
    backTrack(candidates, path, target, 0);

    return res;
}

void backTrack(vector<int>& candidates, vector<int>& path, int target, int depth) {
    // 终止条件
    if (pathSum > target)   return;
    if (pathSum == target) {
        res.emplace_back(path);
        return;
    }

    // 选择列表
    for (int i = depth; i < candidates.size(); i++) {

        // 做选择
        path.emplace_back(candidates[i]);
        pathSum += candidates[i];
        backTrack(candidates, path, target, i);
        // 撤销选择
        path.pop_back();
        pathSum -= candidates[i];
        
    }
}

组合的和(数组中有重复)

有重复元素，且元素不可回头访问。

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[[1,1,6], [1,2,5], [1,7], [2,6]]
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

// 元素有重复且不能重选
// 不能往前选，并且要去掉由于相同元素导致的重复解
vector<vector<int>> res;
int pathSum = 0;
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    vector<int> path;
    sort(candidates.begin(), candidates.end());
    backTrack(candidates, path, target, 0);

    return res;
}

void backTrack(vector<int>& candidates, vector<int>& path, int target, int depth) {
    if (pathSum > target)   return;
    // 终止条件
    if (pathSum == target) {
        res.emplace_back(path);
        return;
    }

    // 选择列表
    for (int i = depth; i < candidates.size(); i++) {
        // 排除非法选择
        if (i > depth && candidates[i] == candidates[i - 1])
            continue;
        // 做出选择
        path.emplace_back(candidates[i]);
        pathSum += candidates[i];
        backTrack(candidates, path, target, i + 1);
        // 撤销选择
        path.pop_back();
        pathSum -= candidates[i];
    }
}

组合的和III

无重复元素，且元素不可回头访问。

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。
2 <= k <= 9
1 <= n <= 60

vector<vector<int>> res;
int pathSum = 0;
vector<vector<int>> combinationSum3(int k, int n) {
    vector<int> path;
    vector<int> nums(9);
    for (int i = 1; i < 10; i++) {
        nums[i - 1] = i;
    }
    backTrack(nums, path, k, n, 0);

    return res;
}

void backTrack(vector<int>& nums, vector<int>& path, int k, int n, int depth) {
    // 结束条件
    if (depth > nums.size())    return;
    if (pathSum == n && path.size() == k) {
        res.emplace_back(path);
        return;
    }

    // 选择条件
    for (int i = depth; i < nums.size(); i++) {
        // 做出选择
        path.emplace_back(nums[i]);
        pathSum += nums[i];
        backTrack(nums, path, k, n, i + 1);
        // 撤销选择
        pathSum -= nums[i];
        path.pop_back();

    }
}

BFS

问题抽象成图，从一个点开始，向四周开始扩散。一般来说，写 BFS 算法都是用「队列」这种数据结构，每次将一个节点周围的所有节点加入队列。BFS解决问题的本质就是让你在一幅「图」中找到从起点 start 到终点 target 的最近距离。

二叉树的最小深度

给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

int minDepth(TreeNode* root) {
    if (root == nullptr)    return 0;
    // 1、定义队列
    queue<TreeNode*> q;
    q.push(root);
    int res = 0;
    while (!q.empty()) {
       // 2、取出长度
        int sz = q.size();
        res++;
        for (int i = 0; i < sz; i++) {
            TreeNode *cur = q.front();
            q.pop();
            // 3、判断是否到达终点
            if (cur->left == nullptr && cur->right == nullptr) {
                return res;
            }
            // 4、相邻节点加入队列
            if (cur->left != nullptr)   q.push(cur->left);
            if (cur->right != nullptr)   q.push(cur->right);
        }
    }

    return res;
}

depth 每增加一次，队列中的所有节点都向前迈一步，这保证了第一次到达终点的时候，走的步数是最少的。

如何把数字变成字符串？

char(i + ‘0’)即可。

课程表（拓扑排序）

输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

private:
// 1、建立邻接表
vector<vector<int>> edges;
// 2、统计入度
vector<int> indegrees;
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    edges.resize(numCourses);
    indegrees.resize(numCourses);
    for (const auto & info : prerequisites) {
        edges[info[1]].emplace_back(info[0]);
        indegrees[info[0]]++;
    }

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

    // 3、BFS实现拓扑排序
    int visited = 0;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        visited++;

        for (const auto & v:edges[cur]) {
            indegrees[v]--;
            if (indegrees[v] == 0) {
                q.push(v);
            }
        }
    }

    return visited == numCourses;
}

字典序

字典序排数

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

dfs遍历

 // 多叉树的遍历——使用dfs
vector<int> res;
vector<int> lexicalOrder(int n) {
    for (int i = 1; i < 10; i++) {
        dfs(i, n);
    }

    return res;
}

void dfs(int num, int n) {
    // 当前数小于n则添加入res
    if (num > n)    return;

    res.emplace_back(num);
    // 遍历选择条件
    for (int i = num*10; i < (num*10+10) && (i <= n); i++) {
        dfs(i, n);
    }
}
   

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

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

迭代法

vector<int> res;
vector<int> lexicalOrder(int n) {

    // 迭代法，如果大于n或者遇到9为结尾，则返回上一个序，如14>n，返回2，1999>n，返回2
    int num = 1;
    while (res.size() < n) {
        // 先把1，10，100，1000全入答案
        while (num <= n) {
            res.emplace_back(num);
            num *= 10;
        }

        // 遇到19，1999或19999要返回2
        while (num > n || num % 10 == 9) {
            num /= 10;
        }
        num++;
    }

    return res;
}

字典序的第K小数字

输入: n = 13, k = 2
输出: 10
解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。

$1 <= k <= n <= 10^9$

int findKthNumber(int n, int k) {
    long predix = 1;
    // 2、指定当前的位置
    long p = 1;
    while (p < k) {
        long count = getCount(n, predix);
        // cout << "count = " << count << endl;
        // 3、如果k在当前前缀的范围内
        if (p + count > k) {
            predix *= 10;
            p++;
        }
        // 4、如果k不在当前前缀的范围内，举例n=13, k=10
        else {
            predix++;
            p += count;
        }
    }

    return predix;
}

// 1、求出指定前缀下所有的节点数
int getCount(long n, long predix) {
    long next = predix + 1;
    long count = 0;
    while (predix <= n) {
        count += (min(n+1, next) - predix);
        predix *= 10;
        next *= 10;
    }

    return count;
}

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

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

高频系列

分治算法

本质就是二叉树的后序遍历。思想是把复杂的问题变成若干个小的子问题，递归求解子问题，再通过子问题的结果合并成原问题。

为运算符表达式设置优先级

给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。
输入：expression = “2-1-1”
输出：[0,2]
解释：
((2-1)-1) = 0
(2-(1-1)) = 2

// 记录重复子问题
unordered_map<string, vector<int>> memo;
vector<int> diffWaysToCompute(string expression) {

    if (memo.count(expression)) {
        return memo[expression];
    }
    vector<int> res;
    for (int i = 0; i < expression.size(); i++) {
        if (expression[i] == '+' || expression[i] == '-' || expression[i] == '*') {
            vector<int> left = diffWaysToCompute(expression.substr(0, i));
            vector<int> right = diffWaysToCompute(expression.substr(i + 1, expression.size() - 1));

            // 后序位置开始治
            for (int l:left) {
                for (int r:right) {
                    if (expression[i] == '+') {
                        res.emplace_back(l + r);
                    }
                    else if (expression[i] == '-') {
                        res.emplace_back(l - r);
                    }
                    else if (expression[i] == '*') {
                        res.emplace_back(l * r);
                    }
                }
            }

        }
    }

    // 递归结束条件
    int num;
    stringstream ss;
    ss << expression;
    ss >> num;
    if (res.empty()) {
        res.emplace_back(num);
    }

    memo[expression] = res;

    return res;
}

斗地主凑顺子

分割数组为连续的子序列

给你一个按升序排序的整数数组 num（可能包含重复数字），请你将它们分割成一个或多个长度至少为 3 的子序列，其中每个子序列都由连续整数组成。

如果可以完成上述分割，则返回 true ；否则，返回 false 。

输入: [1,2,3,3,4,5]
输出: True
解释:
你可以分割出这样两个连续子序列 :
1, 2, 3
3, 4, 5

class Solution {
public:
    // 对于每一张牌。只有两种情况：
    // 1、从自身出发可以形成连续的3个子序列；
    // 2、接到上一张排的后面。
    // unordered_map<int, int> freq, need;
    unordered_map<int, int> freq;
    unordered_map<int, vector<vector<int>>> need;
    // vector<vector<int>> res;
    vector<int> seq;
    bool isPossible(vector<int>& nums) {
        for (int &num:nums) {
            freq[num]++;
        }

        for (int &num:nums) {
            if (freq[num] == 0) continue;
            if (need.count(num) && need[num].size() > 0) {
                freq[num]--;
                // need[num]--;
                // need[num+1]++;
                vector<int> seq = need[num].back();
                need[num].pop_back();
                seq.emplace_back(num);
                need[num+1].emplace_back(seq);
                
            }
            
            else if (freq[num] > 0 && freq[num+1] > 0 && freq[num+2] > 0) {
                // need[num+3]++;
                freq[num]--;
                freq[num+1]--;
                freq[num+2]--;
                
                // 构建顺子序列
                vector<int> seq{num, num+1, num+2};
                need[num+3].emplace_back(seq);
            }

            else {
                return false;
            }
        }

        for (auto &kv:need) {
            for (auto &seq:kv.second) {
                for (auto &num:seq) {
                    cout << num << ", ";
                }
                cout << endl;
            }
        }

        return true;
    }
};

网易吃葡萄

有三种葡萄，每种分别有 a, b, c 颗，现在有三个人，第一个人只吃第一种和第二种葡萄，第二个人只吃第二种和第三种葡萄，第三个人只吃第一种和第三种葡萄。

现在给你输入 a, b, c 三个值，请你适当安排，让三个人吃完所有的葡萄，算法返回吃的最多的人最少要吃多少颗葡萄。

第一行数字T，表示数据组数。
接下来T行，每行三个数a,b,c
1≤a,b,c≤10^18 1≤T≤10

输入
2
1 2 3
1 2 6
输出
2
3

吃的最多的人是指当然可以把所吃的两种葡萄全部吃完，比如说第一个人全部吃完a+b，第二个人吃完c，最后一个人不吃，假设a+b>c，此时第一个人吃的最多，但是还有个条件这个人最少要吃多少颗，就是说这个人吃的还是比别人多，但是可能就比别人多一颗或者几颗或者0颗，上述安排方式显然不能满足，此时，如果安排三个人尽量平均地吃，再把葡萄数向上取整(m/n是向下取整，改为(m+n-1)/n则是向上取整)，那么就能满足上述条件。

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

long eatGrapes(long a, long b, long c) {
    vector<long> nums{a, b, c};
    sort(nums.begin(), nums.end());
    long sum = accumulate(nums.begin(), nums.end(), 0);
    // 如果能构成三角形
    if (a + b > c) {
        return (sum+2) / 3;
    }
    // 如果不能构成三角形并且长边大于两倍的短边之和，那么平分长边
    if ((2*(a+b) < c)) {
        return (nums[2]+1) / 2;
    }

    return (sum+2) / 3;

}

int main() {

    int T;
    cin >> T;
    vector<long> res;
    long a, b, c;
    for (int i =0; i < T; i++) {
        cin >> a >> b >> c;
        long r = eatGrapes(a, b, c);
        res.emplace_back(r);
    }

    for (auto &num:res) {
        cout << num << endl;
    }
    
    return 0;
}

汉诺塔问题

煎饼排序

给你一个整数数组 arr ，请使用 煎饼翻转 完成对数组的排序。
一次煎饼翻转的执行过程如下：

选择一个整数 k ，1 <= k <= arr.length
反转子数组 arr[0…k-1]（下标从 0 开始）
例如，arr = [3,2,1,4] ，选择 k = 3 进行一次煎饼翻转，反转子数组 [3,2,1] ，得到 arr = [1,2,3,4] 。
以数组形式返回能使 arr 有序的煎饼翻转操作所对应的 k 值序列。任何将数组排序且翻转次数在 10 * arr.length 范围内的有效答案都将被判断为正确。

输入：[3,2,4,1]
输出：[4,2,4,3]
解释：
我们执行 4 次煎饼翻转，k 值分别为 4，2，4，和 3。
初始状态 arr = [3, 2, 4, 1]
第一次翻转后（k = 4）：arr = [1, 4, 2, 3]
第二次翻转后（k = 2）：arr = [4, 1, 2, 3]
第三次翻转后（k = 4）：arr = [3, 2, 1, 4]
第四次翻转后（k = 3）：arr = [1, 2, 3, 4]，此时已完成排序。

// 煎饼排序——递归思路
// 1、当序列长度为`n`时，找到`0~n-1`序列长度的最大值`maxValue`以及其下标`maxIndex`；
// 2、翻转`0~maxIndex`的序列，把最大值翻到第一个位置；
// 3、再翻转`0~n`的序列，把最大值翻到第`n`个位置；
// 4、此时已得到一个最大值在序列的末尾；
// 5、令`n`减1再递归上述过程，得到有序序列。

vector<int> res;
vector<int> pancakeSort(vector<int>& arr) {
    onceSort(arr, arr.size());

    return res;
}

void onceSort(vector<int>& arr, int n) {
    if (n == 1) return;
    int maxIndex = -1;
    int maxValue = INT_MIN;
    for (int i = 0; i < n; i++) {
        if (arr[i] > maxValue) {
            maxValue = arr[i];
            maxIndex = i;
        }
    }
    reverse(arr, 0, maxIndex);
    res.emplace_back(maxIndex + 1);
    
    reverse(arr, 0, n - 1);
    res.emplace_back(n);

    onceSort(arr, n - 1);
}
void reverse(vector<int>& arr, int i, int j) {
    while (i < j) {
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
        i++;
        j--;
    }
}

字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

输入: num1 = “123”, num2 = “456”
输出: “56088”

string multiply(string num1, string num2) {
    int m = num1.size(), n = num2.size();
    vector<int> res(m + n, 0);
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            int mul = (num1[j] - '0') * (num2[i] - '0');
            int sum = mul + res[i + j + 1];
            res[i + j + 1] = sum % 10;
            res[i + j] += sum / 10;
        }
    }

    int start = 0;
    while (start < res.size() && res[start] == 0) {
        start++;
    }

    string res_final;
    for (int i = start; i < res.size(); i++) {
        res_final += (res[i] + '0');
    }

    return res_final.size() == 0 ? "0":res_final;
}

接雨水

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

备忘录法

记录每个位置i的能接的雨水=之前的最高柱子高度-当前柱子高度

int ans = 0;
// 定义备忘录
vector<int> l_max;
vector<int> r_max;

int trap(vector<int>& height) {

    int len = height.size();
    if (len == 1)   return 0;
    l_max.resize(len);
    r_max.resize(len);
    l_max[0] = height[0];
    r_max[len - 1] = height[len - 1];

    // 初始化备忘录
    for (int i = 1; i < len; i++) {
        l_max[i] = max(l_max[i - 1], height[i]);
    }
    for (int i = len - 2; i >= 0; i--) {
        r_max[i] = max(r_max[i + 1], height[i]);
    }

    for (int i = 0; i < len; i++) {
        ans += (min(l_max[i], r_max[i]) - height[i]);
    }

    return ans;
}

双指针法

l_max代表height[0...left]的最高柱子，r_max代表height[right...end]的最高柱子，只要l_max < r_max，就能以l_max为主接雨水了，否则以r_max为主接雨水。

int ans = 0;
int trap(vector<int>& height) {
    // 一开始确定左右边界，遇到更高的更新边界，遇到更矮的求和
    int left = 0, right = height.size() - 1;
    int l_max = 0, r_max = 0;

    while (left < right) {
        l_max = max(l_max, height[left]);
        r_max = max(r_max, height[right]);

        if (l_max < r_max) {
            ans += (l_max - height[left]);
            left++;
        }
        else {
            ans += (r_max - height[right]);
            right--;
        }
    }

    return ans;
}

交叉应用

BFS+DP

最小跳跃次数

为了给刷题的同学一些奖励，力扣团队引入了一个弹簧游戏机。游戏机由 N 个特殊弹簧排成一排，编号为 0 到 N-1。初始有一个小球在编号 0 的弹簧处。若小球在编号为 i 的弹簧处，通过按动弹簧，可以选择把小球向右弹射 jump[i] 的距离，或者向左弹射到任意左侧弹簧的位置。也就是说，在编号为 i 弹簧处按动弹簧，小球可以弹向 0 到 i-1 中任意弹簧或者 i+jump[i] 的弹簧（若 i+jump[i]>=N ，则表示小球弹出了机器）。小球位于编号 0 处的弹簧时不能再向左弹。
为了获得奖励，你需要将小球弹出机器。请求出最少需要按动多少次弹簧，可以将小球从编号 0 弹簧弹出整个机器，即向右越过编号 N-1 的弹簧。

示例 1：
输入：jump = [2, 5, 1, 1, 1, 1]
输出：3
解释：小 Z 最少需要按动 3 次弹簧，小球依次到达的顺序为 0 -> 2 -> 1 -> 6，最终小球弹出了机器。

限制：
1 <= jump.length <= 10^6
1 <= jump[i] <= 10000

int minJump(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, INT_MAX);
    queue<int> q;
    dp[0] = 0;
    q.push(dp[0]);
    int left = 0;

    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        // 1、到达终点
        if (cur + nums[cur] >= n) {
            return dp[cur] + 1;
        }
		
        // 2、小球第一次到达右边
        else if (dp[cur + nums[cur]] == INT_MAX) {
            q.push(cur + nums[cur]);
            dp[cur + nums[cur]] = dp[cur] + 1;
        }
        
	   // 3、小球往左边走，每次从left出发则不会超时
        while (left < cur) {
            if (dp[left] == INT_MAX) {
                dp[left] = dp[cur] + 1;
                q.push(left);
            }
            left++;
        }
    }

    return -1;

排序算法

冒泡排序

#include<bits/stdc++.h>
using namespace std;


void printArr(int a[], int len) {
    for (int i=0; i<len; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
}

void bubbleSort(int a[], int len) {
    for (int i=0; i < len; i++) {
        for (int j=len-2; j>=i; j--) {
            if (a[j]<a[j+1]) {
                int temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
}

int main() {
    int arr[]={0,12,34,21,566,2,9};
    int n=sizeof(arr) / sizeof(arr[0]);
    printArr(arr, n);
    bubbleSort(arr, n);
    printArr(arr, n);

    return 0;
}

快速排序

#include <bits/stdc++.h>
using namespace std;


int partition(int *arr, int low, int high) {
    swap(arr[low], arr[low + rand()%(high-low+1)]);
    int v=arr[low];
    int i=low+1, j=high;
    while (true) {
        while (i<=high && arr[i]<v) {
            i++;
        }
        while (j>=low+1 && arr[j]>v) {
            j--;
        }
        if (i>j) {
            break;
        }

        swap(arr[i], arr[j]);
        i++;
        j--;
    }
    swap(arr[low], arr[j]);

    return j;
}

void quickSort(int *arr, int low, int high) {
    if (low < high) {
        int pivot=partition(arr, low, high);
        quickSort(arr, low, pivot-1);
        quickSort(arr, pivot+1, high);
    }
}

int main() {
    int arr[] = {10, 10, 3, 4, 7, 7, 9, 3, 10};
    int N = sizeof(arr)/sizeof(arr[0]);

    quickSort(arr, 0, N-1);

    for (int i=0;i<N;i++) {
        printf("%d ", arr[i]);
    }

    return 0;

}

堆排序

# include<cstdio>

void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

void heapAdjust(int arr[], int i, int len) {
    // 1) 取出待调整的结点i元素
    int temp = arr[i];
    for (int k = 2*i+1; k < len; k++) {
        // 2) 找到左孩子(2*i+1)和右孩子(2*i+2)中最大记录的下标；
        if ((k + 1 < len) && (arr[k] < arr[k + 1])) {
            k++;
        }
        // 3) 若孩子结点最大记录大于i结点的元素，将两者值进行交换。完成一次非叶结点堆的调整
        if (arr[k] > temp) {
            arr[i] = arr[k];
            i = k;
        }
        else {
            break;
        }
    }
    // 4) 最后给待调整元素赋值
    arr[i] = temp;
}

void heapSort(int arr[], int len) {
    // 1、构建堆
    for (int i = len / 2; i >= 0; i--) {
        heapAdjust(arr, i, len);
    }

    // 2、调整堆
    for (int i = len - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        heapAdjust(arr, 0, i);
    }
}

void printArr(int *arr, int len) {
    for (int i = 0; i < len; i++) {
        printf("%d ", *arr);
        arr++;
    }
    printf("\n");
    
}


int main() {

    int arr[] = {9, 1, 5, 8, 3, 7, 4, 6, 2};
    int len = sizeof(arr) / sizeof(arr[0]);
    printArr(arr, len);
    heapSort(arr, len);
    printArr(arr, len);
   
    return 0;
}

简单选择排序

# include<cstdio>
# include<cstdlib>
# include<ctime>

void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

void printArr(int *arr, int len) {
    for (int i = 0; i < len; i++) {
        printf("%d ", *arr);
        arr++;
    }
    printf("\n");
    
}

void simple_selection_sort(int *arr, int len) {
    for (int i = 0; i < len - 1; i++) {
        int min = i;
        for (int j = i + 1; j < len; j++) {
            if (arr[j] < arr[min])    min = j;
        }
        if (i != min)
            swap(arr[i], arr[min]);
    }
    
}

int main() {
    int arr[] = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
    int len = sizeof(arr) / sizeof(arr[0]);
    printArr(arr, len);

    simple_selection_sort(arr, len);
    printArr(arr, len);
    
    return 0;
}

直接插入排序

#include<cstdio>

void straightInsertionSort(int *arr, int len) {
    for (int i = 1; i < len; i++) {
        int j;
        if (arr[i] < arr[i - 1]) {
            int temp = arr[i];
            for (j = i - 1; (j >= 0) && (arr[j] > temp); j--) {
                arr[j + 1] = arr[j];
                }
            arr[j + 1] = temp;
        }
    }
}


void printArr(int *arr, int len) {
    for (int i = 0; i < len; i++) {
        printf("%d ", *arr);
        arr++;
    }
    printf("\n");
    
}


int main() {
    int arr[9] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
    int len = sizeof(arr) / sizeof(arr[0]);
    printArr(arr, len);
    straightInsertionSort(arr, len);
    printArr(arr, len);

    return 0;
}

希尔排序

#include <cstdio>

void shell_sort(int *arr, int len) {
    // 1、初始化增量为gap，每次循环增量gap减小为原来的一半；
    for (int gap = len / 2; gap > 0; gap /= 2) {
        // 2、从第gap个元素开始，分组中待插入的元素和距离为前一个gap的元素进行比较，看是否需要插入
        for (int i = gap; i < len; i++) {
            if (arr[gap] < arr[i - gap]) {
                // 3、带插入的元素称为哨兵，将哨兵从后往前，按照gap的距离，依次和顺序表的元素进行比较
                int temp = arr[i];
                int j;
                // 4、比哨兵大则往后挪一位，循环结束时在相应位置插入哨兵
                for (j = i - gap; j >=0 && arr[j] > temp; j-= gap) {
                    arr[j + gap] = arr[j];
                }
                arr[j + gap] = temp;
            }
        }
    }
}




void printArr(int *arr, int len) {
    for (int i = 0; i < len; i++) {
        printf("%d ", *arr);
        arr++;
    }
    printf("\n");
}
int main() {

    int arr[10] = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
    int len = sizeof(arr) / sizeof(arr[0]);
    printArr(arr, len);
    shell_sort(arr, len);
    printArr(arr, len);
    return 0;
}

归并排序

#include<bits/stdc++.h>
using namespace std;

void merge(int *arr, int left, int middle, int right) {
    int help[right - left + 1];
    int p1 = left, p2 = middle + 1, i = 0;
    while (p1 <= middle && p2 <= right) {
        if (arr[p1] <= arr[p2]) {
            help[i]=arr[p1];
            p1++;
        }
        else {
            help[i]=arr[p2];
            p2++;
        }
        i++;
    }

    while (p1 <= middle) {
        help[i] = arr[p1];
        p1++;
        i++;
    } 

    while (p2 <= right) {
        help[i] = arr[p2]; 
        p2++;
        i++;
    }

    for (int j = 0; j < i; j++) {
        arr[left + j] = help[j]; 
    } 
}

void mergeSort(int *arr, int left, int right) {
    if (left >= right) return;
    int middle = left +((right - left) / 2);
    mergeSort(arr, left, middle);
    mergeSort(arr, middle + 1, right);

    merge(arr, left, middle, right);
}

void printArr(int a[], int len) {
    for (int i=0; i<len; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
}


int main() {
    int arr[]={0,12,34,21,566,2,9};
    int n=sizeof(arr) / sizeof(arr[0]);
    printArr(arr, n);
    mergeSort(arr, 0, n - 1);
    printArr(arr, n);
    
    return 0;
}

BM47 寻找第K大

有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。
给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。
数据范围：$0≤n≤10^5, 1≤K≤n$，数组中每个元素满足$0≤val≤10^9$
输入：[1,3,5,2,2],5,3
返回值：2

int partition(vector<int>& a, int low, int high, int K) {
    swap(a[low], a[low + (rand()%(high-low+1))]);
    int v=a[low];
    int i=low+1;
    int j=high;
    while (true) {
        while (j>=low+1 && a[j]<v)
            j--;
        while (i<=high && a[i]>v)
            i++;
        if (i>j) {
            break;
        }
        swap(a[i], a[j]);

        i++;
        j--;
    }
    swap(a[low], a[j]);
    
    // j是从0开始的
    if (K == j+1)
        return a[j];
    // j+1小，说明第K大值在右边
    else if (K > j+1) {
        return partition(a, j+1, high, K);
    }
    
    // j+1大，说明第K大值在左边
    else {
        return partition(a, low, j-1, K);
    }
}
int findKth(vector<int> a, int n, int K) {
    return partition(a, 0, n-1, K);
}

C++把输入转为字符串

#include <bits/stdc++.h>
using namespace std;
string s;
int main() {

    while (1) {
        char c = cin.get();
        if (c == '\n') {
            break;
        }
        else {
            s += c;
        }
    }

    cout << "s->" << s << endl;
    return 0;
}

C++把字符串处理成数组

#include <bits/stdc++.h>
using namespace std;

// 关于C++处理输入处理成数组，小记一手
vector<int> dealInput(const string &s) {
    int n=s.size();
    vector<int> nums;
    string cur="";
    for (int i=0;i<=n;i++) {
        if (s[i]==',' || i==n) {
            nums.push_back(stoi(cur));
            cur="";
        }
        else {
            cur.push_back(s[i]);
        }
    }

    return nums;
}

void printArr(vector<int>& nums) {
    for (auto &num:nums) {
        cout << num << " ";
    }
    cout << endl;
}

/*test
-1,2,-3,4,-5
6

*/

int main() {

    string s;
    int target;
    getline(cin, s);
    vector<int> nums = dealInput(s);
    cin >> target;
    printArr(nums);
   
    return 0;
}