Pulp Compilation 从零开始的刷题之路

• 1. 数学
• 2. 数组
• 3. 链表
• 4. 哈希散列
• 5. 栈与队列
• 6. 类与OOP应用
• 7. 二叉树
• 8. 回溯
• 9. 贪心
• 10. 动态规划

1. 数学

1.1 基础

有一天, 小明收到一张奇怪的信, 信上要小明计算出给定数各个位上数字为偶数的和。
例如：5548，结果为12，等于 4 + 8 。
小明很苦恼，想请你帮忙解决这个问题

#include <iostream>
using namespace std;
int main(){
    int n, sum = 0;
    //input 
    while(cin >> n){
        // calculation
        while (n != 0){
        int res = 0;
        res = n % 10;
        if ((res % 2) == 0) sum += res;
        n = (n - res) / 10;
        }
    cout << sum << endl;
    cout << endl;
    sum = 0;
    }
    return 0;
}

1.2 计数质数

给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。

枚举法

考虑质数的定义：在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。因此对于每个数 x，我们可以从小到大枚举 [2,x−1] 中的每个数 y，判断 y 是否为 x 的因数。但这样判断一个数是否为质数的时间复杂度最差情况下会到 O(n)，无法通过所有测试数据。

根据数学特性更改枚举范围，可以一定程度上降低时间复杂度，不过依旧超时

class Solution {
public:
    int judge(int x){
        for (int i = 2; i * i <= x; i++){
            if (x % i == 0) return 0;
        }
        return 1;
    }
    int countPrimes(int n) {

        int result = 0;

        if (n == 0 || n == 1) result = 0;
        else{
            for (int i = 2 ; i < n; i++){
                result += judge(i);
            }
        }
        return result;
    }
};

埃氏筛

leetcode官方题解：

枚举没有考虑到数与数的关联性，因此难以再继续优化时间复杂度。接下来我们介绍一个常见的算法，该算法由希腊数学家厄拉多塞（Eratosthenes）提出，称为厄拉多塞筛法，简称埃氏筛。

我们考虑这样一个事实：如果 x 是质数，那么大于 x 的 x 的倍数 2x,3x,… 一定不是质数，因此我们可以从这里入手。

我们设 isPrime[i] 表示数 i 是不是质数，如果是质数则为 1，否则为 0。从小到大遍历每个数，如果这个数为质数，则将其所有的倍数都标记为合数（除了该质数本身），即 0，这样在运行结束的时候我们即能知道质数的个数。

这种方法的正确性是比较显然的：这种方法显然不会将质数标记成合数；另一方面，当从小到大遍历到数 x 时，倘若它是合数，则它一定是某个小于 x 的质数 y 的整数倍，故根据此方法的步骤，我们在遍历到 y 时，就一定会在此时将 x 标记为 isPrime[x]=0。因此，这种方法也不会将合数标记为质数。

当然这里还可以继续优化，对于一个质数 x，如果按上文说的我们从 2x 开始标记其实是冗余的，应该直接从 x⋅x 开始标记，因为 2x,3x,… 这些数一定在 x 之前就被其他数的倍数标记过了，例如 2 的所有倍数，3 的所有倍数等。

链接：https://leetcode.cn/problems/count-primes/solutions/507273/ji-shu-zhi-shu-by-leetcode-solution/

class Solution {
public:
    int countPrimes(int n) {
        vector<int> isPrime(n, 1);
        int ans = 0;
        for (int i = 2; i < n; i++) {
            if (isPrime[i]) {
                ans += 1;
                if ((long long)i * i < n) {
                    for (int j = i * i; j < n; j += i) {
                        isPrime[j] = 0;
                    }
                }
            }
        }
        return ans;
    }
};

 

2. 数组

2.1 基础1

编写一个程序，模拟打印一个正方形的框。程序应该接受用户输入的正整数作为正方形的边长，并打印相应大小的正方形框。 请注意，内部为空白，外部是由 “*” 字符组成的框。

#include <iostream>
using namespace std;
int main(){    
    //input
    int n;
    cin >> n;
    int num = n;
    do{
        if( (num == 1) || (num == n) ) {
            for (int i = 0; i < n; i++){
                cout << '*';
            }
            cout << endl;
        }
        else {
            for (int i = 0; i <= n; i++){
                if ((i == 0) || (i == (n-1))) cout << '*';
                else
                cout << ' ';
            }
             cout << endl;
        }
    num --;
    } while (num) ; 
}

2.2 基础2

给定一个整数数组，编写一个程序实现以下功能：

1. 将输入的整数数组倒序输出，每个数之间用空格分隔。
2. 从正序数组中，每隔一个单位（即索引为奇数的元素），输出其值，同样用空格分隔。

/*
理解错了，我以为是排序，实际上是按输入顺序逆序
*/
#include <iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    if ((n>=1) && ( n<=1000)){
        int origin[n];
        for (int i = 0; i < n; i++){
            cin >> origin[i];
        }
        //reverse
        int max = 0;
        for (int i = 0; i < n; i++){
            for (int j = i + 1 ; j < n; j++){
                if (origin[j] > origin[i]){
                    max = origin[j];
                    origin[j] = origin[i];
                    origin[i] = max;
                }
            }
        }
        //output
        for (int i = 0; i < n; i++){
            cout << origin[i] << ' ';
        }
        cout << endl;
        //reverse
        int min = 0;
        for (int i = 0; i < n; i++){
            for (int j = i + 1 ; j < n; j++){
                if (origin[j] < origin[i]){
                    min = origin[j];
                    origin[j] = origin[i];
                    origin[i] = min;
                }
            }
        }
        //step output
        for (int i = 0; i < n; i++){
            if((i % 2) == 0) cout << origin[i] << ' ';
        }
    }
}

2.3 基础3

给定一个整数数组，编写一个程序实现以下功能：

1. 将输入的整数数组倒序输出，每个数之间用空格分隔。
2. 从正序数组中，每隔一个单位（即索引为奇数的元素），输出其值，同样用空格分隔。

//我的程序
#include <iostream>

using namespace std;

int main(){

    int n;
    cin >> n;
    if ((n>=1) && ( n<=1000)){
        int origin[n];
        for (int i = 0; i < n; i++){
            cin >> origin[i];
        }

        for (int i = n-1; i >= 0; i--){
            cout << origin[i] << ' ';
        }
        
        cout << endl;

        for (int i = 0; i < n; i++){
            if ((i % 2) == 0) cout << origin[i] <<' ' ;
        }
  
    }
}



//题解
//vector(被称为容器)，做为C++ 标准库中的一个容器类，表示对象的集合，它可以动态地存储一组元素，所以可以根据需要轻松地调整 vector 的大小。
#include <iostream>
#include <vector>

using namespace std;
int solution(){
    vector<int> origin;
    int n, num;
    cin >> n;
    if ((n>=1) && ( n<=1000)){
        for (int i = 0; i < n; i++){ // 这里的长度不能用origin.size()
            cin >> num;
            origin.push_back(num);
        }
        for (int i = origin.size()-1; i >= 0; i--){
            cout << origin[i] << ' ';
        }
        cout << endl;
        for (int i = 0; i < origin.size(); i++){
            if ((i % 2) == 0) cout << origin[i] <<' ' ;
        }
    }

    return 0;
}

2.4 基础4

小明很喜欢玩积木。一天，他把许多积木块组成了好多高度不同的堆，每一堆都是一个摞一个的形式。
然而此时，他又想把这些积木堆变成高度相同的。
但是他很懒，他想移动最少的积木块来实现这一目标，你能帮助他吗？

/*
算法非常简单，求均值偏移数
注意计数后的清零，非常重要
*/
#include <iostream>
#include <vector>
using namespace std;

int main(){

    int n, num, sum = 0, steps = 0;
    while (cin >> n){
        if (n == 0) break;
        // input & sum
        vector<int> nums;
        for (int i = 0; i < n; i++){
            cin >> num;
            nums.push_back(num);
            sum += nums[i];
        }
        int average = sum / n;
        sum = 0;
        steps = 0;
        //step calculation:  
        for (int i = 0; i < n; i++){
            if (nums[i] > average) steps += (-average + nums[i]);
        }
        cout << steps << endl;

        cout << endl;

    }
    return 0;
}

2.5 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果 target 存在返回下标，否则返回 -1。

你必须编写一个具有 O(log n) 时间复杂度的算法。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        
        int left = 0;
        int right = nums.size() - 1;
        int middle = left + (right - left) / 2 ;

        while (left <= right){
            if (target > nums[middle]){
                left = middle+1;
                middle = left + (right - left) / 2 ;
            }
            else if (target < nums[middle]){

                right = middle-1;
                middle = left + (right - left) / 2 ;
            }
            else  return middle;
        }
        return -1;
    }
};

2.6 移除元素

双指针法

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

• 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
• 返回 k。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slowindex = 0;
        for (int fastindex = 0; fastindex < nums.size(); fastindex++) {
            if (nums[fastindex] != val) {
                nums[slowindex] = nums[fastindex];
                slowindex++;
            }
        }
        return slowindex;
    }
};

2.7 有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

暴力：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++){
            nums[i] *= nums[i]; 
        }
        sort(nums.begin(),nums.end());
        return nums;
        
    }
};

双指针：

//时间复杂度为O(n)
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {

        int length = nums.size();
        int left = 0;
        int right = length - 1;

        vector<int> result(nums.size(), 0);
        int index = length-1;

        while(left <= right){

            if (nums[left] * nums[left]  <= nums[right] * nums[right]){
                result[index] = nums[right] * nums[right];
                index --;
                right -= 1;
            }

            else if (nums[left] * nums[left]  >= nums[right] * nums[right]){
                result[index] = nums[left] * nums[left];
                index --;
                left += 1;
            }
        }

        return result;
    }
};

2.8 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

滑动窗口：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {

        int left = 0;
        int sum = 0;
        int length = 0;
        // 初始化为极大值，确保第一次比较时 length 会被选中
        int result = INT32_MAX;

        for (int right = 0; right < nums.size(); right++){
            sum += nums[right];
            while (sum >= target){
                length = right - left + 1;
                result = result < length ? result : length;
                sum -= nums[left++];
            }
        }
         return result == INT32_MAX ? 0 : result;
    }
};

2.9 螺旋数组

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {

        int mid = n/2 ;
        int num = 1;
        int loop = n/2;

        int start_x = 0;
        int end_x = n-start_x - 1;
        int start_y = 0;
        int end_y = n-start_y - 1;
        // vector 构建二维数组
        vector<vector<int>> result(n, vector <int>(n, 0));
        
        while (loop -- ){

            for (int i = start_x,  j = start_y; i < end_x; i++){
                result[j][i] = num;
                num ++;
            }

            for (int i = start_y, j = end_x; i < end_y; i++){
                result[i][j] = num;
                num ++;
            }

            for (int i = end_y, j = end_x; j > start_x; j--){
                result[i][j] = num;
                num ++;
            }

            for (int i = end_y, j = start_x; i > start_y; i--){
                result[i][j] = num;
                num ++;
            }

            start_x +=1;
            start_y +=1;

            end_x -= 1;
            end_y -=1;
        }
        if (n % 2 == 1){
            result[mid][mid] = n*n;
        }
        return result;
        
    }
};

2.10 区间和

给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。

输入描述

第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间，直至文件结束。

输出描述

输出每个指定区间内元素的总和。

/*
卡暴力，使用前缀和，即数列和的差值
*/
#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n;
    int num;
    int start = 0, end = 0;
    int result = 0;

    int pre_sum = 0;
    vector<int> pre(n,0);

    cin >> n;
    int i = 0;
	// calculate 前缀和
    while (n--){
        cin >> num;

        pre_sum += num;
        pre[i] = pre_sum;

        i++;
    }

    while(cin >> start >> end){
        result = pre[end] - pre[start-1];
        cout << result << endl;
    }
}

2.11 字符串基础

每门课的成绩分为A、B、C、D、F五个等级，为了计算平均绩点，规定A、B、C、D、F分别代表4分、3分、2分、1分、0分。
有多组测试样例。每组输入数据占一行，由一个或多个大写字母组成，字母之间由空格分隔。
每组输出结果占一行。如果输入的大写字母都在集合｛A,B,C,D,F｝中，则输出对应的平均绩点，结果保留两位小数。
否则，输出“Unknown”。

 
//1. string处理， C++的字符串操作，头文件string， 长度 .size， 访问字符 []
//   判断是否为空 .empty()，输入输出可以用标准库中的iostream
//   cin >> word 读取到空格就会停止
//   getline(cin , word) 读取一行直到换行符或者文件结束符停止


//2. <iomanip> 对标准输出进行格式化处理 比如此题中的 cout << fixed << setprecision(2); 设置精度为2位小数


//注意点：
//getline(cin, grades) 会读取整行输入，包括空格，
//所以当输入包含空格时，default 分支会被触发，导致输出 Unknown 错误产生


#include <iostream>
#include <string>
#include <iomanip>
using namespace std;
int main(){
string grades;
while (getline(cin,grades)){
    bool flag = 0;
    float total = 0;
    int count = 0;
    for (int i = 0; i < grades.size(); i++)
    {
        if (grades[i] == ' ') continue;
        switch(grades[i]){
            case 'A':
                total += 4.0;
                count += 1;
                break;
            case 'B':
                total += 3.0;
                count += 1;
                break;
            case 'C':
                total += 2.0;
                count += 1;
                break;
            case 'D':
                total += 1.0;
                count += 1;
                break;
            case 'F':
                total += 0.0;
                count += 1;
                break;  
            default:
                flag = 1;
                break;       
            }
    }
    if (flag == 0){
            float final = 0.0;

            final = total / count;

            cout << fixed << setprecision(2);

            cout << final << endl;
    }
    else{

        cout << "Unknown " << endl;
    }
}
    return 0;
}

2.12 大写组合

输出一个词组中每个单词的首字母的大写组合。
输入的第一行是一个整数n，表示一共有n组测试数据。（输入只有一个n，没有多组n的输入）
接下来有n行，每组测试数据占一行，每行有一个词组，每个词组由一个或多个单词组成；每组的单词个数不超过10个，每个单词有一个或多个大写或小写字母组成；
单词长度不超过10，由一个或多个空格分隔这些单词

//注意这里使用了 getchar() 函数来吸收一个回车符，因为在输入 n 之后通常需要输入回车符才会输入下一行。

/*
cin >> n 会留下换行符 \n 在缓冲区
当输入 n 的值（比如 2）并按回车后，缓冲区的内容是："2\n"。
cin >> n 只读取 2，剩下的 \n 仍然在缓冲区。
getline(cin, line) 会读取缓冲区中剩余的 \n
getline 遇到 \n 时会直接读取并返回空字符串 ""，导致 line 为空，因此 for 循环不会执行。
*/
#include <iostream>
#include <string>
using namespace std;
char upper(char a){
    char upper;
      if ((a >= 'a') && (a <= 'z'))
        cout << char(a + 'A' - 'a');

      else if ((a >= 'A') && (a <= 'Z'))
        cout << char(a);
    return upper;
}


int main() {
  string line;

  int n;

  cin >> n;
  getchar();

  while (n--) {

    getline(cin, line);

    if (line[0] != ' ') {
      if ((line[0] >= 'a') && (line[0] <= 'z'))
        cout << char(line[0] + 'A' - 'a');

      else if ((line[0] >= 'A') && (line[0] <= 'Z'))
        cout << char(line[0]);
    }
/*
    if (line[0] != ' ') {
        upper(line[0]);
    }

*/
    for (int i = 1; i < line.size(); i++) {

      if ((line[i] != ' ') && (line[i - 1] == ' ')) {

        if ((line[i] >= 'a') && (line[i] <= 'z'))
          cout << char(line[i] + 'A' - 'a');

        else if ((line[i] >= 'A') && (line[i] <= 'Z'))
          cout << char(line[i]);
      }
    }
/*
    for (int i = 1; i < line.size(); i++) {

      if ((line[i] != ' ') && (line[i - 1] == ' ')) {
        upper(line[i]);
      }
    }

*/
    cout << endl;
  }

  return 0;
}

2.13 字符串奇偶位翻转

给定一个长度为偶数位的字符串，请编程实现字符串的奇偶位互换。输入包含多组测试数据。
输入的第一行是一个整数n，表示有测试数据。（整个输入中，只有一个n）
接下来是n组测试数据，保证串长为偶数位(串长<=50)。

//题解使用了自定义的交换函数，其中用了变量引用， which is C++的特性

/*
// 不返回(return)结果，所以返回类型为void， 函数名称为swap
// 传入的参数为两个字符，所以类型为char, 参数名称为a 和 b
void swap(char &a, char &b) { // 交换两个字符串, a和b的内容需要改变，所以需要传递引用
  // 定义第三个字符，并将字符a的内容赋值给第三个字符
    char tmp = a;
  // 将字符a的内容修改为字符b的内容
    a = b;
  // 将字符b的内容修改为第三个字符的内容，也就是字符a的内容，a和b之间完成替换
    b = tmp;
}
*/

#include <iostream>
#include <string>

using namespace std;

int main(){

    string line;
    int n;

    cin >> n;
    getchar();

    while(n--){
        getline(cin,line);
        char c;
        for (int i = 0;  i < line.size()-1; i++){
            if((i)%2 == 0){
                c = line[i];
                line[i] = line[i+1];
                line[i+1] = c; 
            }
        }
        cout << line << endl;
    }

    return 0;
}

2.14 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

暴力：

class Solution {
public:
    void reverseString(vector<char>& s) {

        int n = s.size();

        vector<int> restore(n);

        for(int i = 0 ; i < n; i++){
            restore[i] = s[i] -'a';
        }

        for (int i = n - 1; i >= 0; i-- ){

            s[n-i-1] = restore[i] + 'a';
        }
        
    }
};

双指针：

class Solution {
public:
    void reverseString(vector<char>& s) {

        int n = s.size();
        int left = 0;
        int right = n-1;

        while (left < right){
            swap(s[left], s[right]);

            left ++;
            right --;
        }        
    }
};

2.15 反转字符串Ⅱ

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

• 如果剩余字符少于 k 个，则将剩余字符全部反转。
• 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

class Solution {
public:
    string reverseStr(string s, int k) {

        int n = s.size();

        int roll1 = n / (2*k);

        int roll2 = n % (2*k);

        int start = 0;

        while (roll1 --){

            int left = start;
            int right = start + k -1;
            while (left < right){
                swap(s[left] , s[right]);
                left ++;
                right --;
            }

            start += 2 * k;
        }

        roll1 = n / (2*k);

        if (roll2 < k){

            int start = 2 * k * roll1;

            int left = start;
            int right = start + roll2 - 1;

            while (left < right){
                swap(s[left] , s[right]);
                left ++;
                right --;
            }
        }

        else if (roll2 >= k && roll2 < 2 * k){

            int start = 2 * k * roll1;

            int left = start;
            int right = start + k - 1;

            while (left < right){
                swap(s[left] , s[right]);
                left ++;
                right --;
            }

        }

        return s;
    }
};

2.16 替换数字

给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。 例如，对于输入字符串 “a1b2c3”，函数应该将其转换为 “anumberbnumbercnumber”。

#include <iostream>
#include <string>

using namespace std;

int main(){

    string input;

    cin >> input;

    int total = 0;

    for (auto &s : input){
        if (s >= '0' && s <= '9')
        total ++;
    }

    int space = input.size() + total * 5;

    char output[space + 1];

    int start = input.size() - 1;
    /*
    在 C/C++ 中，字符数组（char[]）用于表示字符串时，必须以 '\0'（空字符，ASCII 码为 0）结尾。
    如果缺少这个终止符，cout 或其他字符串处理函数（如 strlen、strcpy）可能会读取越界，
    导致未定义行为（Undefined Behavior, UB），常见表现包括：
    	1. 输出乱码
    	2. 程序崩溃
    	3. 无限循环（如果内存中碰巧有非零数据）
    */
    output[space] = '\0';   // Ensure null-termination
    int end = space - 1;

    while (start >= 0){

        if (input[start] >= '0' && input[start] <= '9'){
            output[end] = 'r';
            end --;
            output[end] = 'e';
            end --;
            output[end] = 'b';
            end --;
            output[end] = 'm';
            end --;
            output[end] = 'u';
            end --;
            output[end] = 'n';
            end --;
        }
        else{
            output[end] = input[start];
            end --;
        }

        start --;
    }

    cout << output << endl;

    return 0;
}

2.17 找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

暴力（伪双指针）：

class Solution {
public:
    int strStr(string haystack, string needle) {

      int n1 = needle.size();
      int n2 = haystack.size();

      int left1 = 0;
      int left2 = 0;
      int right1 = n1 - 1;
      int right2 = n1 - 1;

      int flag = 1;

      while(right2 < n2){

        if(haystack[left2] == needle[left1] && haystack[right2] == needle[right1]){

          flag = 1;
          int restore = left2;
          for (int i = left2, j = left1; i < right2, j < right1; i++, j++){
            if(haystack[i] != needle[j]) {
              flag = 0;
              break;
            }
          }
          if (flag == 1){
            return restore;
          }
        }
          left2++;
          right2++;
      }
      return -1;
    }
};

KMP：字符串匹配算法，值得理解

class Solution {
public:

    void getprefix(const string &s, int *prefix){
    int fend = 0;
    prefix[0] = 0;

    for (int bend = 1; bend < s.size();  bend++){

        while (fend > 0 && s[fend] != s[bend]){
            fend = prefix[fend - 1];
        }

        if (s[bend] == s[fend]) fend++;
        prefix[bend] = fend;
    }


    }
    int strStr(string haystack, string needle) {

        if (needle.size() == 0) return 0;

        if (needle.size() > haystack.size()) return -1;

        vector<int> prefix(needle.size());

        getprefix(needle, &prefix[0]);

        int index = 0;

        for (int i = 0; i < haystack.size() ; i++){
            

            while (index > 0 && haystack[i] != needle[index]) {
                index = prefix[index - 1];
            }

            if (haystack[i] == needle[index]) index++;

            if (index == needle.size()) return (i - index + 1);
        }

        return -1;
    }

};

2.18 翻转字符串里的单词

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

class Solution {
public:

    void removeextra(string &s){
        int slow = 0;
        for (int fast = 0; fast < s.size(); fast ++){
            if (s[fast] != ' '){
                if (slow > 0) s[slow++] = ' ';
                while (fast < s.size() && s[fast] != ' '){
                    s[slow++] = s[fast++];
                }
            }
        }
        s.resize(slow);
    }

    void reverse(string &s, int left, int right){

        for (int i = left, j = right; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }

    string reverseWords(string s) {

        removeextra(s);
        reverse(s, 0, s.size()-1);

        int start = 0;

        for (int end = 1; end < s.size(); end++){
            if(s[end] == ' '){
                reverse(s, start , end-1);
                start = end + 1;
            }

            else if (end == s.size() - 1){
                reverse(s, start , end);
            }
        }
        return s;
    }
};

2.19 右旋字符串

字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。

例如，对于输入字符串 “abcdefg” 和整数 2，函数应该将其转换为 “fgabcde”。

#include <iostream>
#include <string>

using namespace std;

int main() {

  int n;
  string s;
  cin >> n;
  cin >> s;

  int left0 = 0;
  int right0 = s.length() - 1;
  //全部翻转1
  while (left0 < right0) {
    swap(s[left0], s[right0]);
    left0++;
    right0--;
  }
  //局部翻转1
  left0 = 0;
  right0 = n - 1;
  while (left0 < right0) {
    swap(s[left0], s[right0]);
    left0++;
    right0--;
  }
  //局部翻转2
  left0 = n;
  right0 = s.length() - 1;
  while (left0 < right0) {
    swap(s[left0], s[right0]);
    left0++;
    right0--;
  }

  cout << s;
}

2.20 重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

class Solution {
public:
    bool repeatedSubstringPattern(string s) {

        vector<int> prefix(s.size());

        prefix[0] = 0;

        int j = 0;

        for (int i = 1; i < s.size(); i++){
            while (j > 0 && s[i] != s[j]){
                j = prefix[j- 1];
            }

            if (s[i] == s[j]) j++;

            prefix[i] = j;
        }

        printf("%d\r\n", prefix[s.size()-1]);

        if (s.size() == 2){
            if (prefix[s.size()-1] == 1) return true;
        }

        if (s.size() > 2){
        if (prefix[s.size()-1] != 0 && s.size() % (s.size()-(prefix[s.size() - 1]) )== 0) return true;
        }

        return false;
        
    }
};

 

3. 链表

3.1 基础1

构建一个单向链表，链表中包含一组整数数据。输出链表中的所有元素。

要求：

1. 使用自定义的链表数据结构
2. 提供一个 linkedList 类来管理链表，包含构建链表和输出链表元素的方法
3. 在 main 函数中，创建一个包含一组整数数据的链表，然后调用链表的输出方法将所有元素打印出来

// 0. 构造函数：ListNode(int x) : val(x), next(nullptr) {}
// 这里的ListNode(int x)表示定义一个接收整数参数 x的名称为ListNode的构造函数（名称和结构体相同），:表示初始化列表的开始，val(x)表示链表数据域的值被初始化为传递的参数 x ，next(nullptr)则表示next指针被初始化为nullptr，表示没有下一个节点。


/*
这里有两个新的语法：new运算符和箭头语法->

1. new是一个运算符，它的作用就是在堆内存中动态分配内存空间，并返回分配内存的地址，使用方式一般为：
指针变量 = new 数据类型, 比如下面的代码：

int *arr = new int[5]; 
// 分配一个包含5个整数的数组的内存空间，并返回一个地址，指针arr指向这个地址

2. 箭头语法（->）：用于通过指针访问指针所指向的对象的成员，cur 是一个指向 ListNode 结构体对象的指针，而 next 是 ListNode 结构体内部的一个成员变量（指向下一个节点的指针）。使用 cur->next 表示访问 cur 所指向的节点的 next 成员变量。
*/

#include <iostream>
using namespace std;

struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x) : val(x) , next(nullptr){}
};
int main(){
    // 指针变量 = new 数据类型
    // 建立一个虚拟头节点
    ListNode *dummyhead = new ListNode(0);
    int m, n;
    while (cin >> n){
        ListNode *cur = dummyhead;
        while(n--){
            cin >> m;
            ListNode *newnode = new ListNode(m);
            cur-> next = newnode;
            cur = cur -> next;
        }
        cur = dummyhead;
        while (cur->next != NULL){
            cout << cur->next->val << ' ';
            cur = cur->next;
        }
        cout << endl;
    }
}

3.2 基础2

请编写一个程序，实现以下操作：

构建一个单向链表，链表中包含一组整数数据，输出链表中的第 m 个元素（m 从 1 开始计数）。
要求：

1. 使用自定义的链表数据结构
2. 提供一个 linkedList 类来管理链表，包含构建链表、输出链表元素以及输出第 m 个元素的方法
3. 在 main 函数中，创建一个包含一组整数数据的链表，然后输入 m，调用链表的方法输出第 m 个元素

 
输入描述：

第一行包含两个整数 n 和 k，n 表示需要构建的链表的长度，k 代表输入的 m 的个数。
接下来一行包含 n 个整数，表示链表中的元素。
接下来一行包含 k 个整数，表示输出链表中的第 m 个元素。

 
输出描述
测试数据输出占 k 行。
每行输出链表中的第 m 个元素。如果 m 位置不合法，则输出“Output position out of bounds.”。

#include <iostream>
using namespace std;

struct linknode{
    int val;
    linknode* next;
    linknode(int x): val(x), next(nullptr) {}
};


int main(){
    int n, k;
    int num;
    cin >> n >> k ;

    linknode* dummynode = new linknode(0);
    linknode* cur;

    cur = dummynode;

    // creat linklist
    while (n--){
        cin >> num;
        linknode *newnode =new linknode(num);
        cur->next = newnode;
        cur = cur -> next;
    }

    // output
    while (k--){
        cin >> num;
        cur = dummynode;
        // judge range
        for (int i = 0; i < num; i++){
        // if exceed, break
           if (cur != NULL)
            cur = cur->next ;

           else break;
        }
        // cur == NULL : exceed
        // cur == dummyHead : m = 0
        if (cur == NULL || cur == dummynode) {
        cout << "Output position out of bounds." << endl;
        } 
        else {
        cout << cur->val << endl;
        }
    }

    return 0;
}

3.3 基础3

请编写一个程序，实现以下链表操作：构建一个单向链表，链表中包含一组整数数据。

1. 实现在链表的第 n 个位置插入一个元素，输出整个链表的所有元素。
2. 实现删除链表的第 m 个位置的元素，输出整个链表的所有元素。

要求：

1. 使用自定义的链表数据结构。
2. 提供一个 linkedList 类来管理链表，包含构建链表、插入元素、删除元素和输出链表元素的方法。
3. 在 main 函数中，创建一个包含一组整数数据的链表，然后根据输入的 n 和 m，调用链表的方法插入和删除元素，并输出整个链表的所有元素。
    

输入描述:

每次输出只有一组测试数据。

每组的第一行包含一个整数 k，表示需要构建的链表的长度。

第二行包含 k 个整数，表示链表中的元素。

第三行包含一个整数 S，表示后续会有 S 行输入，每行两个整数，第一个整数为 n，第二个整数为 x ，代表在链表的第 n 个位置插入 x。

S 行输入…

在 S 行输入后，后续会输入一个整数 L，表示后续会有 L 行输入，每行一个整数 m，代表删除链表中的第 m 个元素。

L 行输入…
 

输出描述:

包含多组输出。

每组第一行输出构建的链表，链表元素中用空格隔开，最后一个元素后没有空格。

然后是 S 行输出，每次插入一个元素之后都将链表输出一次，元素之间用空格隔开，最后一个元素后没有空格；

如果插入位置不合法，则输出“Insertion position is invalid.”。

然后是 L 行输出，每次删除一个元素之后都将链表输出一次，元素之间用空格隔开，最后一个元素后没有空格；如果删除元素后链表的长度为0，则不打印链表。

如果删除位置不合法，则输出“Deletion position is invalid.”。

如果链表已经为空，执行删除操作时不需要打印任何数据。

#include <iostream>
using namespace std;

struct linknode {
  int val;
  linknode *next;
  linknode(int x) : val(x), next(nullptr) {}
};

// function for print the linklist
void printlinklist(linknode *listhead) {
  linknode *cur = listhead;
  while (cur->next != NULL) {
    cout << cur->next->val << ' ';
    cur = cur->next;
  }
  cout << endl;
}

int main() {

  int k, s, l;
  int num;
  int place, var;
  int deleteplace;
  bool flag = 0;
  linknode *dummyhead = new linknode(0);
  linknode *cur;

  cin >> k;
  // linklist create
  cur = dummyhead;
  // linklist length
  int listLen = k;
  while (k--) {
    cin >> num;
    cur->next = new linknode(num);
    cur = cur->next;
  }

  // insert
  cin >> s;
  while (s--) {
    cur = dummyhead;
    cin >> place >> var;
    if ((place > listLen) || (place <= 0)) {
      cout << "Insertion position is invalid." << endl;
      continue;
    } 
      else {
      for (int i = 1; i < place; i++) {
        cur = cur->next;
      }
      linknode *insertnode = new linknode(var);
      insertnode->next = cur->next;
      cur->next = insertnode;
      // add length
      listLen++;
    }
    // output
    printlinklist(dummyhead);
  }

  // delete
  cin >> l;
  while (l--) {
    cin >> deleteplace;
    if ((deleteplace > listLen) || (deleteplace <= 0)) {
      cout << "Deletion position is invalid." << endl;
      continue;
    } 
      else {
      cur = dummyhead;
      for (int i = 1; i < deleteplace; i++) {
        cur = cur->next;
      }
      cur->next = cur->next->next;
      listLen--;
    }
    if (listLen)
      printlinklist(dummyhead);
  }
  return 0;
}

3.4 设计链表

你可以选择使用单链表或者双链表，设计并实现自己的链表。（这里使用单链表）

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

• MyLinkedList() 初始化 MyLinkedList 对象。

• int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。

• void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。

• void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。

• void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。

• void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

class MyLinkedList {
public:
    struct LinkNode{
        int val;
        LinkNode* next;
        LinkNode(int val): val(val), next(nullptr){}
    };
    // 初始化
    MyLinkedList() {

        dummyhead = new LinkNode(0);
        size = 0;
        
    }
    int get(int index) {
        
        if ( index < 0 || index > (size - 1)) return -1;

        LinkNode* cur = dummyhead -> next;
        while (index --){
            cur = cur -> next;
        }
        
        
        return cur ->val;
    }
    
    void addAtHead(int val) {
        LinkNode* newhead = new LinkNode(val);
        newhead->next = dummyhead ->next;
        dummyhead ->next = newhead;
        
        size ++;
    }
    
    void addAtTail(int val) {
        LinkNode* newtail = new LinkNode(val);
        LinkNode* cur = dummyhead;
        

        while (cur -> next != NULL){
            cur = cur -> next;
        }

        cur -> next = newtail;

        size ++;
    }
    
    void addAtIndex(int index, int val) {
        LinkNode* newinsert = new LinkNode(val);

        if (index < 0 || index > size) return;
        LinkNode*  cur = dummyhead;

        while (index --){
            cur = cur-> next;
        }

        newinsert -> next = cur -> next;
        cur -> next = newinsert;


        size ++;
        
    }
    
    void deleteAtIndex(int index) {

        LinkNode* cur = dummyhead;
        if (index < 0 || index >= size) return ;

        while (index --){
            cur = cur->next;
        }
        cur ->next = cur->next->next;

        size --;
    }

private:

    LinkNode* dummyhead;
    int size = 0;
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

3.5 反转链表

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {

        ListNode* pre = NULL;

        ListNode* cur = head ;

        ListNode* temp;
//注意临界条件
        while (cur != NULL){
            temp = cur->next;
            cur->next = pre;

            pre = cur;
            cur = temp;
        }
        return pre;
        
    }
};

3.6 两两交换链表中的节点

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {

    ListNode* dummyhead = new ListNode(0);
    dummyhead->next = head;

    ListNode* cur = dummyhead;

    while (cur->next != nullptr && cur->next->next != nullptr){
        ListNode* temp = cur->next;
        ListNode* temp_1 = cur->next->next->next;

        cur->next = cur->next->next;
        cur->next->next = temp;
        cur->next->next->next = temp_1;

        cur = temp;
    }

    return dummyhead->next;
    }
};

3.7 删除链表的倒数第N个节点

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

暴力：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {

        ListNode* dummyhead = new ListNode(0);

        dummyhead->next = head;
        ListNode* cur = dummyhead;

        int count = 0;

        while (cur->next != NULL){

            cur = cur->next;
            count ++;
        }

        int count_reverse = count - n ;

        // cout << count << endl;

        cur = dummyhead;

       for (int i = 0; i < count_reverse ; i++){
            cur = cur->next; 
        }

        // cout << cur->val << endl;

        if (cur->next != NULL)
        cur->next = cur->next->next;

        return dummyhead->next;
    }
};

双指针：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {


        ListNode* dummy = new ListNode(0);
        dummy->next = head;

        ListNode* fast = dummy;
        

        while (n--){
           fast =  fast->next;
        }
        ListNode* slow = dummy;

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

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

        return dummy->next;
    }
};

3.8 链表相交

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

暴力：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* dummyA = new ListNode(0);
        ListNode* dummyB = new ListNode(0);
        dummyA->next = headA;
        dummyB->next = headB;
        ListNode* curA = dummyA;        
        ListNode* curB = dummyB;

        while(curA->next != NULL){

            curA = curA->next;

            while (curB-> next != NULL){

                curB = curB ->next;

                if (curB == curA)
                return curA;
            }

            curB = dummyB;
        }

        return NULL;
    }
};

暴力2：

两链表尾端对齐后，两遍历节点同时取短链表head，向后移动并检查

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curA = headA;
        ListNode* curB = headB;
        int lenA = 0, lenB = 0;
        while (curA != NULL) { // 求链表A的长度
            lenA++;
            curA = curA->next;
        }
        while (curB != NULL) { // 求链表B的长度
            lenB++;
            curB = curB->next;
        }
        curA = headA;
        curB = headB;
        // 让curA为最长链表的头，lenA为其长度
        if (lenB > lenA) {
            swap (lenA, lenB);
            swap (curA, curB);
        }
        // 求长度差
        int gap = lenA - lenB;
        // 让curA和curB在同一起点上（末尾位置对齐）
        while (gap--) {
            curA = curA->next;
        }
        // 遍历curA 和 curB，遇到相同则直接返回
        while (curA != NULL) {
            if (curA == curB) {
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }
        return NULL;
    }
};

3.9 环形链表

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

暴力哈希：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {

        unordered_set<ListNode*> store;

        ListNode* dummy = new ListNode(0);
        dummy->next = head;

        ListNode* cur = dummy;

        while (cur->next != NULL){

            store.insert(cur->next);
            cur = cur->next;
            //if (store.count(cur->next)) 也行
            if (store.find(cur->next) != store.end())
            return cur->next;

        }

        return NULL;

        
    }
};

双指针：fast是走两步，slow是走一步，其实相对于slow来说，fast是一个节点一个节点的靠近slow的，所以fast一定可以和slow重合。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
            // 快慢指针相遇，此时从head和相遇点，同时查找直至相遇
            if (slow == fast) {
                ListNode* index1 = fast;
                ListNode* index2 = head;
                while (index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index2; // 返回环的入口
            }
        }
        return NULL;
    }
};

 

4. 哈希散列

4.1 基础：数组

给定一个只包含小写字母的字符串，统计字符串中每个字母出现的频率，并找出出现频率最高的字母，如果最高频率的字母有多个，输出字典序靠前的那个字母。

包含多组测试数据，每组测试数据占一行。

有多组输出，每组输出占一行。

#include <iostream>
#include <string>
using namespace std;

int main() {

  int n;
  string s;
  while (cin >> n) {
    while (n--) {
      cin >> s;
      int count[26] = {0};
      int max = 0;
      int max_flag = 0;
      // hash
      for (int i = 0; i < s.size(); i++) {
        count[s[i] - 'a']++;
      }
      // select max
      for (int j = 0; j < 26; j++) {
        if (count[j] > max) {
          max = count[j];
          max_flag = j;
        }
      }
      char result;
      result = max_flag + 'a';
      cout << result;
      cout << endl;
    }
  }
  return 0;
}

4.2 基础：set

编写一个程序，判断给定的整数 n 是否存在于给定的集合中。

有多组测试数据，第一行有一个整数 k，代表有 k 组测试数据。

每组数据第一行首先是一个正整数 m，表示集合中元素的数量（1 <= m <= 1000）。

接下来一行包含 m 个整数，表示集合中的元素。

最后一行包含一个整数 n，表示需要进行判断的目标整数。

包含多组输出，每组输出占一行。

如果集合中存在 m，输出“YES”，否则输出“NO”。

// set 集合
#include <iostream>
#include <unordered_set>
using namespace std;

int main() {
  int m, n, l;
  int test;
  cin >> m;
  while (m--) {
    cin >> n;
    unordered_set<int> uset;

    while (n--) {
      cin >> l;
      // set insert
      uset.insert(l);
    }
    //test
    cin >> test;
    if (uset.find(test) != uset.end()) // check iterator
      cout << "YES" << endl;
    else
      cout << "NO" << endl;
  }
}

4.3 基础：map

假设你手里有一串钥匙，这串钥匙上每把钥匙都有一个编号，对应着一个房门的编号。现给你一个房门编号，你需要判断是否能够打开该房门。

测试数据共有多组。

第一行为一个整数 s，表示共有多少组测试数据。

每组第一行有一个整数 n，表示钥匙串上有多少把钥匙。

后面共有 n 行输入，每行两个整数，第一个整数 k 表示钥匙编号，第二个整数 d 表示房门编号。

最后一行有一个整数 x，表示需要打开的房门编号。

输出多组，每组占一行。 如果能打开，则输出钥匙编号，不能打开则输出“Can’t open the door.”。

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
  int n, m;
  cin >> n;
  int key_num;
  int door_num;
  int x;
  while (n--) {
    cin >> m;
    unordered_map<int, int> umap;
    while (m--) {
      cin >> key_num >> door_num;
      umap[key_num] = door_num;
    }
    cin >> x;
    bool flag = 0;
    int answer = 0;

    for (const pair<int,int> &kv : umap) {
      if (kv.second == x) {
        flag = 1;
        answer = kv.first;
        break;
      }
    }
    if (flag == 1) {
      cout << answer << endl;
    } else
      cout << "Can't open the door." << endl;
  }
}

4.4 存在重复元素

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {

        unordered_set<int> res;
        for (int num: nums){
            if (res.contains(num)) return true;
            else res.insert(num);
        }
        return false;
    }
};

4.5 只出现一次的数字

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int , int > count;
        for (int num: nums){
            count[num] ++;
        }
        for (int num : nums){
            if (count[num]  == 1){
                return num;
            }
        }  
        return -1;
    }
};

4.6 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的 字母异位词。

• s 和 t 仅包含小写字母

class Solution {
public:
    bool isAnagram(string s, string t) {
        vector<int> table(26.0);
        //长度不同必定false
        if (s.length() != t.length()) return false;

        for (char &ch : s){
            table[ch - 'a'] ++;
        }

        for (char &ch : t){

            table[ch - 'a']--;
            if (table[ch- 'a'] < 0) return false;
        }
        return true;
        
    }
};

4.7 两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {

        unordered_set<int> result, restore;

        for (auto &num : nums1){
            if(!restore.count(num)) restore.insert(num);
        }

        for (auto &num : nums2){

            if (restore.count(num))
            result.insert(num);
        }
        //vector<int> a(begin_iterator, end_iterator);：使用范围构造函数，用迭代器指定的范围来初始化向量。
        return vector<int>(result.begin(), result.end());
        
    }
};

4.8 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

class Solution {
public:
    bool isHappy(int n) {

        unordered_set <int> sum;
        int result = n;

        while (sumsquare(result) != 1 ){

            result = sumsquare(result);
            if (sum.count(result))
            return false;
            sum.insert(result);
        }

        return true;         
    }

    int sumsquare(int x){
        int sum = 0;
        int j = 0;
        while (x > 0){
            j = x % 10;
            // x = (x - j) / 10;
            x /= 10;

            sum  += j * j;
        }

        return sum;
    }
};

4.9 两数之和

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

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

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

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {

        
        unordered_map<int,int> pair;

        for (int i = 0 ; i< nums.size(); i++){
            
            
            if (pair.count(target-nums[i]))
            return {pair[target- nums[i]], i};

            pair[nums[i]] = i;
        
        }

        return {};
        
    }
};

4.10 四数相加Ⅱ

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        int count = 0;
        int n = nums1.size();
        int sum = 0;
        unordered_map<int, int> result;

        for (int i = 0 ; i < n ; i++ ){
            for (int j = 0; j < n ; j++){
                sum = nums1[i] + nums2[j];
                result[sum] += 1;
            }
        }

        for (int i = 0 ; i < n ; i++ ){
            for (int j = 0; j < n ; j++){
                sum = nums3[i] + nums4[j];
                if(result.find(-sum) != result.end())
                count += result[-sum];
            }
        }
        return count;
        
    }
};

4.11 赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {

        unordered_map<int, int> uptime;

        for (auto &ch : magazine){
            uptime[ch-'a']++;
        }
        for (auto &ch : ransomNote){
            if (uptime[ch - 'a'] == 0){
                return false;
            }
            uptime[ch - 'a'] --;
        }
        return true;
        
    }
};

4.12 三数之和：双指针

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

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

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(),nums.end());

        //本题为防止重复元素出现，需要对内外层去重

        for (int a = 0; a < nums.size(); a++)
        {

            if (nums[a] > 0) {
                return result;
            }

            //对a去重
            if (a > 0 && nums[a] == nums[a - 1]) {
                continue;
            }
            int left = a + 1;
            int right = nums.size()-1;

            while (left < right){
                if (nums[a] + nums[left] + nums[right] < 0) left ++;
                else if (nums[a] + nums[left] + nums[right] > 0) right --;
                else {
                    result.push_back(vector<int>{nums[a], nums[left], nums[right]});
                    // 去重逻辑应该放在找到一个三元组之后，对b和c去重
                    while (right > left && nums[right] == nums[right - 1]) {right--};
                    while (right > left && nums[left] == nums[left + 1]) {left++};

                    // 找到答案时，双指针同时收缩
                    right--;
                    left++;
                }
                }
            }
            return result;
        }
};

4.13 四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

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

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {

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

        vector<vector<int>> result;

        for(int a = 0; a < nums.size(); a++){
			// 去重
            if (a > 0 && nums[a] == nums[a - 1]) {
                continue;
            }
            // 剪枝
            if (nums[a]  > target && nums[a] >= 0) {
                break;
            }

            for (int b = a + 1; b < nums.size(); b++){
			// 去重
            if (b > a + 1 && nums[b] == nums[b - 1]) {
                continue;
            }
			// 剪枝
            if (nums[a] + nums[b] > target && nums[b] >= 0) {
                break;
            }

                int left = b + 1;
                int right = nums.size() - 1;

                while (left < right){
                    
                    if ((long)nums[a] + nums[b] + nums[left] + nums[right] < target)
                    left ++;

                    else if ((long)nums[a] + nums[b] + nums[left] + nums[right] > target)
                    right --;

                    else {
                        result.push_back(vector<int>{nums[a], nums[b], nums[left], nums[right]});
                        while (right > left && nums[left+1] == nums[left]) left ++;
                        while (right > left && nums[right] == nums[right - 1]) right --;
                        left ++;
                        right --;
                    }
                }
            }
        }

        return result;
        
    }
};

 

5. 栈与队列

5.1 基础：栈

在餐厅里，洗盘子的工作需要使用到栈这种数据结构。

假设你手里有一个盘子堆放区。现在需要模拟洗盘子的过程，每个盘子都有一个编号。

盘子堆放区操作说明：

1. 当操作为 1 时，表示从盘子堆放区拿走顶部的盘子清洗。
2. 当操作为 2 时，表示有未洗的盘子放入盘子堆放区。

在一系列操作之后，你需要回答：下一个清洗的盘子编号？

第一行有一个整数 n，代表初始盘子堆放区中盘子的数量为 n。

第二行有 n 个整数，代表了盘子的编号，同时整数之间的顺序也代表了未洗盘子加入盘子堆放区的顺序。

第三行为一个整数 m，代表接下来将会有 m 次操作。

接下来一共有 m 行，代表共有 m 次操作。

如果是操作 1，那么该行只会有一个数字 1，代表有一个盘子被拿走清洗。

如果是操作 2，那么该行有两个数字，第一个数字 2 表示有未洗的盘子加入，第二个数字代表未洗的盘子编号。

输出共一行，为下一个该清洗的盘子编号。 如果没有下一个该清洗的盘子，那么请输出 “All the dishes have been washed.”

#include <iostream>
#include <stack>

using namespace std;

int main(){
    int num, dish_num, oper_num;
    int wash_flag;
    cin >> num;

    stack <int> dishes;
    // enter
    while (num -- ){
        cin >> dish_num;
        dishes.push(dish_num);
    }

    //operate
    cin >> oper_num;
    while ( oper_num --){
        cin >> wash_flag;
        if (wash_flag == 1 && !dishes.empty()) dishes.pop();
        if (wash_flag == 2){
            cin >> dish_num;
            dishes.push(dish_num);
        }
    }

    // judge
    if (dishes.empty()) cout << "All the dishes have been washed." << endl; 
    else cout << dishes.top() << endl;

}

5.2 基础：队列

假设有一家奶茶店，现在有一些人在排队等待取奶茶，同时也有人在取奶茶。 请你设计一个程序模拟这种情况下的奶茶队列管理。

假设每个人取奶茶的时间非常短，可以忽略不计，只需要考虑队列中的操作。

队列操作说明：

1. 当操作为 1 时，表示有人已经取走奶茶，从队列中删除该人的信息。
2. 当操作为 2 时，表示有新人加入排队，将该人的信息加入队列。

在一系列操作之后，你需要回答：下一个取奶茶的人是谁？

第一行有一个整数 n，代表初始队列有 n 个人。

第二行有 n 个字符串，代表当前奶茶队列中的人。

第三行为一个整数 m，代表接下来将会有 m 次操作。

接下来一共有 m 行，代表共有 m 次操作。

如果是操作 1，那么该行只会有一个数字，代表有人取走了奶茶。
如果是操作 2，那么该行有一个数字和一个字符串，第一个数字 2 表示有人加入了奶茶队列，第二个字符串代表新加入的奶茶队列的人。

输出只有一行，为下一个取奶茶的人。 如果已经没有去奶茶的人了，输出“There are no more people in the queue.”。

#include <iostream>
#include <queue>
#include <string>

using namespace std;

int main(){
    int origin_num;
    cin >> origin_num;

    // queue setup
    string name;
    queue <string> milktea_queue;
    while (origin_num --){
        cin >> name;
        milktea_queue.push(name);
    }

    // queue operation
    int opera_num, operation;
    cin >> opera_num;
    while(opera_num --){

        cin >> operation;
        if (operation == 1 && !milktea_queue.empty())
        milktea_queue.pop();
        if (operation == 2)
        {
            cin >> name;
            milktea_queue.push(name);
        }
    }
    // output
    if(milktea_queue.empty()) 
    cout << "There are no more people in the queue." << endl;
    else cout << milktea_queue.front() << endl;
}

5.3 有效的括号

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

class Solution {
public:
    bool isValid(string s) {

        stack<char> left;

        for (char item : s){

            if (item == '(' || item == '[' || item == '{'){
                left.push(item);
            }
            else if (!left.empty() && left.top() == leftreturn(item)){
                left.pop();
            }
            else return false;
        }

        return left.empty();
    }
    char leftreturn (char right){
        if(right == ')') return '(';
        
        if(right == '}') return '{';
        
        if(right == ']') return '[';
        
        return false;
    }
};

5.4 买票需要的时间

有 n 个人前来排队买票，其中第 0 人站在队伍 最前方 ，第 (n - 1) 人站在队伍 最后方 。

给你一个下标从 0 开始的整数数组 tickets ，数组长度为 n ，其中第 i 人想要购买的票数为 tickets[i] 。

每个人买票都需要用掉 恰好 1 秒 。一个人 一次只能买一张票 ，如果需要购买更多票，他必须走到 队尾 重新排队（瞬间 发生，不计时间）。如果一个人没有剩下需要买的票，那他将会 离开 队伍。

返回位于位置 k（下标从 0 开始）的人完成买票需要的时间（以秒为单位）。

class Solution {
public:
    int timeRequiredToBuy(vector<int>& tickets, int k) {
        int n = tickets.size();
        vector<int> time(n);
        
        queue<int> line;
        int timecost = 0;
        // 初始化队列，存储每个人的编号 id
        for(int i = 0; i < n; i++){
            line.push(i);
        }
        while(line.size()){
            if (tickets[line.front()] > 1){
                timecost ++;
                tickets[line.front()]--;
                line.push(line.front());
                line.pop();
            }
            else if (tickets[line.front()] == 1){
                timecost ++;
                time[line.front()] = timecost;
                line.pop();
            }
        }
        return time[k];
        
    }
};

5.5 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

• 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

class MyQueue {
private:
        stack<int> input;
        stack<int> output;
public:
    MyQueue() {
        
    }
    
    void push(int x) {
        input.push(x);
    }
    
    int pop() {
        int temp;
        if(output.empty()){
            while (!input.empty()){
                temp = input.top();
                input.pop();
                output.push(temp);
            }
        }
        int result;
        result = output.top();
        output.pop();
        return result;
    }
    
    int peek() {
        int temp;
        if(output.empty()){
            while (!input.empty()){
                temp = input.top();
                input.pop();
                output.push(temp);
            }
        }
        int result;
        result = output.top();
        return result;
    }
    
    bool empty() {
        return input.empty() && output.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

5.6 用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

class MyStack {
public:

    queue<int> input;
    queue<int> output;

    MyStack() {
        
    }
    
    void push(int x) {
        input.push(x);
    }
    
    int pop() {
        
        while(input.size() > 1){
            output.push(input.front());
            input.pop();
        }

        int result = input.front();
        input.pop();

        while(!output.empty()){
            input.push(output.front());
            output.pop();
        }
        return result;
    }
    
    int top() {
        int temp = this->pop();
        input.push(temp);

        return temp;
        
    }
    
    bool empty() {
        return input.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

5.7 删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 s 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

class Solution {
public:
    string removeDuplicates(string s) {

        stack<char> lowercase;

        for (int i = 0; i < s.size(); i++){
            if (i == 0) lowercase.push(s[i]);
            else{
                if ((!lowercase.empty() && s[i] != lowercase.top()) || lowercase.empty()) lowercase.push(s[i]);
                else lowercase.pop();
            }
        }

        string result = "";
        while (!lowercase.empty()) { 
            result += lowercase.top();// 将栈中元素放到result字符串汇总
            lowercase.pop();
        }
        reverse (result.begin(), result.end()); // 字符串需要反转一下
        return result;
    }
};

5.8 逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

• 有效的算符为 '+'、'-'、'*' 和 '/' 。
• 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
• 两个整数之间的除法总是 向零截断 。
• 表达式中不含除零运算。
• 输入是一个根据逆波兰表示法表示的算术表达式。
• 答案及所有中间计算结果可以用 32 位 整数表示。

class Solution {
public:
    int evalRPN(vector<string>& tokens) {

        stack<int> rpn;

        for(auto &ch : tokens){
            if (ch == "+" || ch == "-" || ch == "*" || ch == "/") {
                // 确保栈中至少有2个元素才能进行运算
                if (rpn.size() < 2) return 0; 
                
                int temp = rpn.top();
                rpn.pop();
                int first = rpn.top();
                rpn.pop();
                
                if (ch == "+") {
                    rpn.push(first + temp);
                } else if (ch == "-") {
                    rpn.push(first - temp);
                } else if (ch == "*") {
                    rpn.push(first * temp);
                } else if (ch == "/") {
                    rpn.push(first / temp);
                }
            } else {
                // 将字符串转换为整数压入栈
                rpn.push(stoi(ch));
            }
        }

        return rpn.top();
    }
};

5.9 滑动窗口最大值

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

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

暴力（力扣超时）：

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {

        int size = nums.size() - k + 1;
        if (size <= 0) {
            vector<int> result;
            return result;
        }
        else {
            vector<int> result;
            vector<int> compare(k);

            for (int i = 0; i < size; i++){
                for(int j = i; j < i + k; j++){
                    compare[j - i] = nums[j];
                }
                sort(compare.begin(), compare.end(),[](const int &a, const int &b){
                    return a < b;
                });
                result.push_back(compare[k-1]);
            }
            return result;
        }
    }
};

queue单向队列做（力扣超时）：

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {

        int size = nums.size() - k + 1;
        int max = nums[0];

        queue<int> Max;
        vector<int> result;

        for (int i = 0 ; i < size; i++){
            int window = i + k;
            int i0 = i;

            if (Max.empty()) Max.push(nums[0]);

            if (i > 0 && nums[i - 1] == Max.front()){
                Max.pop();
            }

            while (i0 < window){
                if (nums[i0] >= Max.front()){
                    while (!Max.empty()){
                        Max.pop();
                    }
                    Max.push(nums[i0]);
                }
                else Max.push(nums[i0]);
                i0++;
            }
            result.push_back(Max.front());

        }
        return result;        
    }
};

deque双向队列：可从末尾删除，想法上也更合理

#include <vector>
#include <deque>

using namespace std;

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> result;
        deque<int> dq; // 存储索引

        for (int i = 0; i < nums.size(); ++i) {
            // 移除离开窗口的元素
            while (!dq.empty() && dq.front() <= i - k) {
                dq.pop_front();
            }

            // 从队尾移除比当前小的元素
            while (!dq.empty() && nums[dq.back()] < nums[i]) {
                dq.pop_back();
            }

            // 加入当前元素索引
            dq.push_back(i);

            // 窗口形成后记录最大值
            if (i >= k - 1) {
                result.push_back(nums[dq.front()]);
            }
        }
        return result;
    }
};

5.10 前K个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {

        unordered_map<int,int> count(0);

        for (int i = 0; i < nums.size(); i++){
            count[nums[i]] ++;
        }
        // 转换为vector
        vector<pair<int, int>> freqVec(count.begin(), count.end());
        //lambda表达式
        sort(freqVec.begin(), freqVec.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
            return a.second > b.second; 
        });
        // 提取前 k 个高频元素
        vector<int> result;
        for (int i = 0; i < k && i < freqVec.size(); i++) {
            result.push_back(freqVec[i].first);
        }
        return result;

    }
};

 

6. 类与OOP应用

6.1 图形面积

考虑一个简单的图形类层次结构，包括基类 Shape 和两个派生类 Rectangle 和 Circle。每个类都有一个用于计算面积的方法。你的任务是编写一个程序，根据输入数据创建一个图形对象，然后计算并输出其面积。

输入包括多行，每行包含一个图形的描述。 描述的第一个单词是图形类型（”rectangle”或”circle”），然后是与该图形相关的参数。 对于矩形，参数是宽度和高度，对于圆形，参数是半径。输入以单词”end”结束。

对于每个图形描述，输出其类型和面积。使用两位小数点精度输出面积。

#include <iomanip>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Shape {
public:
  // virtual function
  virtual double getArea() const = 0;
  virtual string getType() const = 0;
};

// Class Circle
class Circle : public Shape {
public:
  Circle(int r) : radius(r) {}
  // f1
  string getType() const override { return "Circle"; }

  // f2
  double getArea() const override { return 3.14 * radius * radius; }

private:
  int radius;
};

// Class Rectangle
class Rectangle : public Shape {
public:
  Rectangle(int w, int h) : width(w), height(h) {}

  // f1
  string getType() const override { return "Rectangle"; }

  // f2
  double getArea() const override {
    return static_cast<double>(width * height);
  }

private:
  int width;
  int height;
};

int main() {
  vector<Shape *> shapes;

  while (true) {
    string type;

    cin >> type;

    if (type == "end")
      break;

    if (type == "circle") {

      int radius;

      cin >> radius;

      shapes.push_back(new Circle(radius));
    }

    else if (type == "rectangle") {

      int width, height;

      cin >> width >> height;

      shapes.push_back(new Rectangle(width, height));
    }
  }

  for (const Shape *shape : shapes) {
    cout << shape->getType() << " area: " << fixed << setprecision(2)
         << shape->getArea() << endl;
  }
  return 0;
}

 

7. 二叉树

7.1 二叉树的递归遍历

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

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //前序遍历
    void presearch(TreeNode* cur, vector<int> &val){
        if (cur == NULL) return;
        val.push_back(cur->val);
        presearch(cur->left,val);
        presearch(cur->right,val);
    }
	//中序遍历
    void middlesearch(TreeNode *cur, vector<int> &val){
        if (cur == NULL) return;

        middlesearch(cur->left, val);
        val.push_back(cur->val);
        middlesearch(cur->right, val);
    }
    //后序遍历
    void backsearch(TreeNode *cur, vector<int> &val){
        if (cur == NULL) return;
        
        backsearch(cur->left, val);
        backsearch(cur->right,val);

        val.push_back(cur->val);
    }
    
    vector<int> inorderTraversal(TreeNode* root) {

        vector<int> result;
        middlesearch(root, result);

        return result;
        
    }
};

7.2 二叉树的迭代遍历

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

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

 	//前序遍历
   void presearch(TreeNode* root, vector<int> &val){
        stack<TreeNode*> st;
        if (root == NULL) return;
        st.push(root);
        while (!st.empty()){
            TreeNode* head = st.top();
            st.pop();
            val.push_back(head->val);
            if (head->right) st.push(head->right);
            if (head->left) st.push(head->left);
        }
    }
    
    //中序遍历
    void middlesearch(TreeNode* root, vector<int> &val){
        stack<TreeNode*> st;
        if (root == NULL) return;
        TreeNode* cur = root;
        while ( !st.empty() || cur != NULL){
            if (cur != NULL) {
                st.push(cur);
                cur = cur->left;
            }
            else {
                cur = st.top();
                st.pop();
                val.push_back(cur->val);
                cur = cur->right;
            }
        }
    }
    
    //后序遍历
    void backsearch(TreeNode *head, vector<int> &val){
        stack<TreeNode*> st;
        if (head == NULL) return;
        // 如果始终没有打印过节点，head就一直是头节点
        // 一旦打印过节点，head就变成打印节点
        // 之后head：上一次打印完的节点
        st.push(head);
        TreeNode* cur;
        while ( !st.empty()){
            cur = st.top();
            //有左树 且左树没处理过
            if (cur->left != NULL && head != cur->left && head != cur->right){
                st.push(cur->left);
            }
            //有右树 且右树没处理过
            else if (cur->right != NULL && head != cur->right){
                st.push(cur->right);
            }
            //左树 右树 都为NULL 或都处理过了
            else {
                head = st.top();
                val.push_back(st.top()->val);
                st.pop();
            }
        }
    }

    vector<int> preorderTraversal(TreeNode* root) {

        vector<int> result;
        presearch(root , result);

        return result;
        
    }
};

7.3 二叉树的层序遍历

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

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {

        vector<vector<int>> result;
        queue<TreeNode*> que;
        if (root) que.push(root);

        while (!que.empty()){
            int size = que.size();
            vector<int> layer;
            for (int i = 0; i < size; i++){
                TreeNode* cur = que.front();
                que.pop();
                layer.push_back(cur->val);
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
            result.push_back(layer);
        }
        // 如果要从底层开始，翻转一下就行
        // reverse(result.begin(), result.end());
        return result;
    }
};

7.4 二叉树的右视图

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

*即进行层序遍历时判断当前是否为该层最后一个元素

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        TreeNode* cur = root;
        vector<int> result;
        queue<TreeNode*> que;
        if (root) que.push(root);

        while (!que.empty()){
            int size = que.size();
            for (int i = 0; i < size; i++){
                cur = que.front();
                que.pop();
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
                if (i == (size - 1)) result.push_back(cur->val);
            }
        }
        return result;
    }
};

7.5 二叉树的层平均值

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {

        vector<double> result;
        
        queue<TreeNode*> que;

        if (root) que.push(root);

        while (!que.empty()){
            int size = que.size();
            int count = 0;
            double sum = 0;
            for (int i = 0; i < size; i++){

                TreeNode* cur = que.front();
                que.pop();
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
                sum += cur->val;
                count++;
            }
            result.push_back(sum/count);
        }
        return result;
    }
};

7.6 N叉树的层序遍历

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔。

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
    vector<vector<int>> result;
    queue<Node*> que;
    if (root) que.push(root);
    while (!que.empty()){
        int size = que.size();
        vector<int> local;
        for (int i = 0; i < size; i++){
            Node* cur = que.front();
            for (auto &ch : cur->children){
                if (ch){
                    que.push(ch);
                }
            }
            que.pop();
            local.push_back(cur->val);
        }
        result.push_back(local);
    }
    return result;
    }
};

7.7 在每个树行中找最大值

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {

        vector<int> max;
        queue<TreeNode*> que;
        if (root) que.push(root);
        while (!que.empty()){
        int max_num = INT_MIN;
        int size = que.size();
        for(int i = 0; i < size; i++){
            TreeNode* cur = que.front();
            que.pop();
            if (cur->left) que.push(cur->left);
            if (cur->right) que.push(cur->right);
            if (cur->val >= max_num) max_num = cur->val;
        }
        max.push_back(max_num);
        }
        return max;
    }
};

7.8 填充每个节点的下一个右侧节点指针

给定一个二叉树：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。

初始状态下，所有 next 指针都被设置为 NULL 。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {

    queue<Node*> que;
    if (root) que.push(root);
    while (!que.empty()){
        int size = que.size();
        for (int i = 0; i < size; i++){
            Node* cur = que.front();
            que.pop();

            if (i == size-1) cur->next = NULL;
            else cur->next = que.front();

            if(cur->left) que.push(cur->left);
            if(cur->right) que.push(cur->right);
        }
    }
    return root; 
    }
};

7.9 二叉树的最大深度

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

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

迭代写法：

class Solution {
public:
    int maxDepth(TreeNode* root) {
        int depth = 0;
        queue<TreeNode*> que;
        if (root) que.push(root);
        while (!que.empty()){
            int size = que.size();
            for (int i = 0 ; i < size; i++){
                TreeNode* cur = que.front();
                que.pop();

                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
                
            }
            depth++;
        }
        return depth;
    }
};

递归写法：

class Solution {
public:

    int checkdepth(TreeNode* root){
        if (root == NULL){
            return 0;
        }
        else{
        int leftdepth = 0;
        int rightdepth = 0;
        if (root->left != NULL)  leftdepth = checkdepth(root->left) + 1;
        if (root->right != NULL) rightdepth = checkdepth(root->right) + 1;
        if (root->left == NULL && root->right == NULL) return 1;
        return max(leftdepth, rightdepth);
        }
    }
    int maxDepth(TreeNode* root) {
        int depth = 0;
        depth = checkdepth(root);
        return depth;
    }
};

7.10 二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

迭代写法：

class Solution {
public:
    int minDepth(TreeNode* root) {
        int depth = 0;

        queue<TreeNode*> que;

        if (root) que.push(root);

        while (!que.empty()){
            int size = que.size();
            for (int i = 0 ; i < size; i++){
                TreeNode* cur = que.front();
                que.pop();
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
                if (!cur->left && !cur->right){
                    depth++;
                    return depth;
                } 
            }
            depth++;
        }
        return depth;
    }
};

递归写法：

class Solution {
public:
    int checkdepth(TreeNode* root){
        if (root == NULL){
            return 0;
        }
        else{

        if (root->left == NULL && root->right == NULL) return 1;
        
        int leftdepth = INT_MAX;
        int rightdepth = INT_MAX;
        if (root->left != NULL )  leftdepth = checkdepth(root->left) + 1;
        if (root->right != NULL) rightdepth = checkdepth(root->right) + 1;
        
        return min(leftdepth, rightdepth);
        }
    }

    int minDepth(TreeNode* root) {
        int depth = 0;
        depth = checkdepth(root);
        return depth;
    }
};

7.11 翻转二叉树

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

class Solution {
public:

    void reverstreenode (TreeNode* cur){
        if (cur == NULL) return;
        reverstreenode(cur->left);
        reverstreenode(cur->right);

        TreeNode* temp;
        temp = cur->right;
        cur->right = cur->left;
        cur->left = temp;
    }
    TreeNode* invertTree(TreeNode* root) {
        

        reverstreenode(root);
        return root;
    }
};

7.12 对称二叉树

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

递归写法：

class Solution {
public:

    bool check(TreeNode* branch1, TreeNode* branch2){

        if (branch1 == NULL && branch2 == NULL) return true; // 递归退出条件
        else if (branch1 != NULL && branch2 == NULL) return false;
        else if (branch1 == NULL && branch2 != NULL) return false;
        else if (branch1 != NULL && branch2 != NULL) {
            if (branch1->val != branch2->val)
            return false;
        }
        return (check(branch1->left, branch2->right) && (check(branch1->right, branch2->left)));
    
    }
    bool isSymmetric(TreeNode* root) {

        if (root == NULL) return false;
        return check(root->left, root->right);
        
    }
};

迭代写法：

class Solution {
public:

    bool isSymmetric(TreeNode* root) {
        stack<TreeNode*> st;
        if (root == NULL) return false;
        else if (root->left == NULL && root->right == NULL) return true;
        else if (root->left != NULL && root->right == NULL) return false;
        else if (root->left == NULL && root->right != NULL) return false;
        else {
            st.push(root->left);
            st.push(root->right);
        }

        while (!st.empty()){
            TreeNode* cur1 = st.top();
            st.pop();
            TreeNode* cur2 = st.top();
            st.pop();

            if (cur1->left == NULL && cur2->right != NULL) return false;
            if (cur1->left != NULL && cur2->right == NULL) return false;
            if (cur1->right == NULL && cur2->left != NULL) return false;
            if (cur1->right != NULL && cur2->left == NULL) return false;

            if (cur1->val != cur2->val) {
                return false;
            }
            if (cur1->left) st.push(cur1->left);
            if (cur2->right) st.push(cur2->right);
            if (cur1->right) st.push(cur1->right);
            if (cur2->left) st.push(cur2->left);
        }
        return true;
    }
};

7.13 完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（从第 0 层开始），则该层包含 1~ 2h 个节点。

class Solution {
public:
    int countNodes(TreeNode* root) {

        int count = 0;
        if (root == NULL) return 0;

        queue<TreeNode*> que;
        que.push(root);

        while (!que.empty()){

            int size = que.size();
            TreeNode* cur;
            for (int i = 0; i < size; i++){
                cur = que.front();
                que.pop();
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
                count++;
            }
        }
        return count;
    }
};

7.14 平衡二叉树

给定一个二叉树，判断它是否是 平衡二叉树 （ 是指该树所有节点的左右子树的高度相差不超过 1。）

class Solution {
public:
    int height (TreeNode* root){
        int count = 0;
        if (root == NULL) return 0;
        else {
            int leftdepth = 0;
            int rightdepth = 0;
            if (root->left != NULL) leftdepth = height(root->left);
            if (root->right != NULL) rightdepth = height(root->right);

            if (root->left == NULL && root->right == NULL) return 1;
            return max(leftdepth, rightdepth) + 1;
        }
    }

    bool isBalanced(TreeNode* root) {

        if (root == NULL) return true;
        queue<TreeNode*> que;
        que.push(root);
        while (!que.empty()){
            int size = que.size();
            TreeNode* cur;
            for (int i = 0; i < size; i++){
                cur = que.front();
                que.pop();
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);

                if (height(cur->left) > height(cur->right)){
                    if (height(cur->left) - height(cur->right) > 1) return false;
                }

                if (height(cur->left) < height(cur->right)){
                    if (height(cur->right) - height(cur->left) > 1) return false;
                }
            }
        }
    return true;
    }
};

7.15 左叶子之和

给定二叉树的根节点 root ，返回所有左叶子之和。

class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == NULL) return 0;
        int sum = 0;
        queue<TreeNode*> que;
        que.push(root);
        while (!que.empty()){
            int size = que.size();
            TreeNode* cur;
            for (int i = 0; i < size; i++){

                cur = que.front();
                que.pop();

                if (cur->left) {
                    if (cur->left->left == NULL && cur->left->right == NULL)
                    sum += cur->left->val;
                    que.push(cur->left);
                }
                if (cur->right) que.push(cur->right);
            }
        }
        return sum;
    }
};

7.16 二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

*回溯思想

class Solution {
public:

    void travelback(TreeNode* root, vector<int> &path, vector<string> &result){
        path.push_back(root->val);
        //终止条件
        if (root->left == NULL && root->right == NULL){
            string str;
            for (auto ch : path){
                str +=  to_string(ch);
                str += "->";
            }
            str.pop_back();
            str.pop_back();
            result.push_back(str);
            return;
        }
        if (root->left != NULL){
            travelback(root->left, path, result);
            path.pop_back(); // 回溯
        }
        if (root->right != NULL){
            travelback(root->right, path, result);
            path.pop_back(); // 回溯
        }

    }
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        vector<int> path;
        if (root == NULL) return result;
        travelback(root, path, result);
        return result;
    }
};

7.17 找树左下角的值

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {

        int result = 0;

        queue<TreeNode*> que;

        // if (root == NULL) return -1;
        que.push(root);
        while (!que.empty()){

            int size = que.size();
            TreeNode* cur;

            for (int i = 0; i < size; i++){
                cur = que.front();
                que.pop();
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
                if ( i == 0) result = cur->val;
            }
        }
        return result;
    }
};

7.18 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点 是指没有子节点的节点。

class Solution {
public:

    void sumcheck(TreeNode* root , int &sum, int &result, int &calculate){

        calculate += root->val;

        if (root ->left == NULL && root->right == NULL){
            if (calculate == sum)
            result += 1;
        }

        if (root->left != NULL){
            sumcheck(root->left, sum, result,calculate);
            calculate -= root->left->val;
        }

        if (root->right != NULL){
            sumcheck(root->right, sum, result,calculate);
            calculate -= root->right->val;
        }
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        int result = 0;
        int calculate = 0;
        if (root == NULL) return false;
        sumcheck(root, targetSum, result, calculate);

        if (result) return true;
        else return false;
        
    }
};

7.19 从中序和后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

*递归

//选择用索引应该会更好
class Solution {
public:
    TreeNode* rebuild(vector<int>& inorder, vector<int>& postorder){

        if (postorder.size() == 0) return NULL;

        int rootvalue = postorder[postorder.size()-1];

        TreeNode* root = new TreeNode(rootvalue);

        if (postorder.size() == 1) return root;

        vector<int> newleftmiddle;
        vector<int> newrightmiddle;
        vector<int> newleftback;
        vector<int> newrightback;

        int flag = 0;
        // 左递归处理
        for (auto &ch : inorder){
            if (ch != rootvalue && flag == 0)
            newleftmiddle.push_back(ch);
            else if (ch == rootvalue && flag == 0){
                flag = 1;
            }
            else
            newrightmiddle.push_back(ch);
        }

        // 右递归处理
        for (int i = 0; i < newleftmiddle.size(); i++){
            newleftback.push_back(postorder[i]);
        }
        for (int i = newleftmiddle.size(); i < postorder.size()-1; i++){
            newrightback.push_back(postorder[i]);
        }

        root->left = rebuild(newleftmiddle, newleftback);

        root->right = rebuild(newrightmiddle, newrightback);

        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {

        return rebuild(inorder,postorder);
        
    }
};

7.20 最大二叉树

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

1. 创建一个根节点，其值为 nums 中的最大值。
2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树\ 。

class Solution {
public:

    TreeNode* rebuild(vector<int> &nums){
        
        if (nums.size() == 0) return NULL;
        int max = INT_MIN;
        int maxindex = 0;
        for (int i = 0; i < nums.size(); i++){
            if (nums[i] > max) {
                max = nums[i];
                maxindex = i;
            }
        }

        TreeNode* root = new TreeNode(max);

        vector<int> leftnew(nums.begin(), nums.begin()+maxindex);
        vector<int> rightnew(nums.begin()+maxindex+1, nums.end());

        root->left = rebuild(leftnew);
        root->right = rebuild(rightnew);

        return root;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return rebuild(nums);
    }
};

7.21 合并二叉树

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {

        if (root1 == NULL && root2 == NULL) return NULL;
        if (root1 == NULL && root2 != NULL) return root2;
        if (root1 != NULL && root2 == NULL) return root1;

        queue<TreeNode*> que;
        que.push(root1);
        que.push(root2);
        while(!que.empty()){
            TreeNode* cur1;
            TreeNode* cur2;

            cur1 = que.front();
            que.pop();

            cur2 = que.front();
            que.pop();

            cur1->val += cur2->val;

            if (cur1->left && cur2->left) {
                que.push(cur1->left);
                que.push(cur2->left);
            }

            if (cur1->right && cur2->right) {
                que.push(cur1->right);
                que.push(cur2->right);
            }

            if (!cur1->left && cur2->left) {
                cur1->left = cur2->left;
            }

            if (!cur1->right && cur2->right) {
                cur1->right = cur2->right;
            }

        }

        return root1;
    }
};

7.22 二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

二叉搜索树是一个有序树：

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉搜索树

// 写复杂了，其实不需要队列
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {

        if (root == NULL) return NULL;
        queue<TreeNode*> que;
        que.push(root);

        TreeNode* resultnode;

        while (!que.empty()){
            TreeNode* cur = que.front();
            que.pop();

            if (cur->val > val){
                if (cur->left) que.push(cur->left);
                else return NULL;
            }
            else if (cur->val < val){
                if (cur->right) que.push(cur->right);
                else return NULL;
            }
            else {
                resultnode = cur;
                break;
            }
        }
        return resultnode;
    }
};

7.23 验证二叉搜索树

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

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

• 节点的左子树只包含 严格小于 当前节点的数。
• 节点的右子树只包含 严格大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

// 只需要利用这个特性：二叉搜索树的中序遍历是递增数列
class Solution {
public:
    bool isValidBST(TreeNode* root) {
       stack<TreeNode*> st;
        if (root == NULL) return true;
        TreeNode* cur = root;
        TreeNode* pre = NULL; 

        while ( !st.empty() || cur != NULL){
            if (cur != NULL) {
                st.push(cur);
                cur = cur->left;
            }
            else {
                cur = st.top();
                st.pop();
                if (pre != NULL && cur->val <= pre->val)
                return false;

                pre = cur; //保存前一个访问的结点
                cur = cur->right;
            }
        }
        return true;
    }
};

7.24 二叉搜索树的最小绝对差

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

// 中序遍历 递增
class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        // if (root == NULL) return 0;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        TreeNode* pre = NULL;
        int min = INT_MAX;
        while ( !st.empty() || cur != NULL){

            if (cur){
                st.push(cur);
                cur = cur->left;
            }
            else {
                cur = st.top();
                st.pop();

                //处理
                if(pre != NULL){
                    if ((cur->val) - (pre->val) < min)
                    min = (cur->val) - (pre->val);
                }

                pre = cur;
                cur = cur ->right;
            }
        }

        return min;
        
    }
};

7.25 二叉搜索树中的众数

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的众数，即出现频率最高的元素。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

• 结点左子树中所含节点的值 小于等于 当前节点的值
• 结点右子树中所含节点的值 大于等于 当前节点的值
• 左子树和右子树都是二叉搜索树

class Solution {
private:
    void searchBST(TreeNode* root, vector<int> &result) {
        if (root == NULL) return;
        stack<TreeNode*> st;
        int maxcount = 0;
        int count = 0;
        TreeNode* cur = root;
        TreeNode* pre = NULL;

        while (!st.empty() || cur != NULL){

            if (cur){
                st.push(cur);
                cur = cur->left;
            }

            else{
                cur = st.top();
                st.pop();
               
                // 重复处理逻辑
                if (pre == NULL) count = 1;
                else {
                    if (pre->val == cur->val){
                        count ++;
                    }
                    else count = 1;
                }
                if (count == maxcount)
                    result.push_back(cur->val);
                if (count > maxcount){
                    maxcount = count;
                    result.clear();
                    result.push_back(cur->val);
                }
                pre = cur;
                cur = cur->right;
                
            }
        }  
    }

public:
    vector<int> findMode(TreeNode* root) {

        vector<int> result;
        searchBST(root, result);
        return result;
    }
};

7.26 二叉树的最近公共祖先

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

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

// 有点难度
class Solution {
public:

    TreeNode* ancestorbackforth(TreeNode* root, TreeNode* p, TreeNode* q){
        if (root == NULL) return NULL;
        if (root == p || root == q) return root;

        TreeNode* left = ancestorbackforth(root->left, p , q);
        TreeNode* right = ancestorbackforth(root->right, p, q);

        if (left && right) return root;
        else if (!left && right) return right;
        else if (left && !right) return left;
        else return NULL;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return ancestorbackforth(root, p, q);
    }
};

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

相比上一题难度降低很多，利用有序性就行

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

        if (root == NULL) return NULL;
        TreeNode* cur = root;
        while (cur){
            if (cur->val > p->val && cur->val > q->val) cur = cur->left;
            if (cur->val < p->val && cur->val < q->val) cur = cur->right;
            else return cur;
        }
        return NULL;
    }
};

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

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。（指该树所有节点的左右子树的高度相差不超过 1。）

class Solution {
public:

    TreeNode* BSTbuild(vector<int> &nums){
    TreeNode* root = new TreeNode(0);
    int middleindex = 0;
    vector<int> newleft;
    vector<int> newright;

    if (nums.size() == 0) return NULL;

    else if (nums.size() % 2 == 1){
        middleindex = nums.size() / 2;
        root->val = nums[middleindex];
        for (int i = 0; i < middleindex; i++){
            newleft.push_back(nums[i]);
        }
        for (int i = middleindex + 1; i < nums.size(); i++){
            newright.push_back(nums[i]);
        }
    }
    else if (nums.size() % 2 == 0){
        middleindex = nums.size() / 2;
        root->val = nums[middleindex];
        for (int i = 0; i < middleindex; i++){
            newleft.push_back(nums[i]);
        }
        for (int i = middleindex + 1; i < nums.size(); i++){
            newright.push_back(nums[i]);
        }
    }

    root->left = BSTbuild(newleft);
    root->right = BSTbuild(newright);

    return root;

    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
    // 题目可以转换为：知道二叉搜索树的中序遍历，还原树
    // 很容易想到递归
    return BSTbuild(nums);

    }
};

7.29 二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        TreeNode* cur = new TreeNode(val);
        if (root == NULL) {
            root = cur;
            return root;
        }
        TreeNode* cur1 = root;
        TreeNode* pre = new TreeNode(0);
        while (cur1){
            if (cur1->val > val) {
                pre = cur1;
                cur1 = cur1->left;
            }

            else if (cur1->val < val) {
                pre = cur1;
                cur1 = cur1->right;
            }
        }

        if (pre->val < val) pre->right = cur;
        if (pre->val > val) pre->left = cur;
        return root;
    }
};

7.30 修剪二叉搜索树

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int L, int R) {
        if (!root) return nullptr;

        // 处理头结点，让root移动到[L, R] 范围内，注意是左闭右闭
        while (root != nullptr && (root->val < L || root->val > R)) {
            if (root->val < L) root = root->right; // 小于L往右走
            else root = root->left; // 大于R往左走
        }
        TreeNode *cur = root;
        // 左侧修剪拼接
        while (cur != nullptr) {
            while (cur->left && cur->left->val < L) {
                cur->left = cur->left->right;
            }
            cur = cur->left;
        }
        cur = root;
        // 右侧修剪拼接
        while (cur != nullptr) {
            while (cur->right && cur->right->val > R) {
                cur->right = cur->right->left;
            }
            cur = cur->right;
        }
        return root;
    }
};

7.31 删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

1. 首先找到需要删除的节点；
2. 如果找到了，删除它。

// 没有想象中简单，需要把边界条件理清楚
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {

        if (root == NULL) return NULL;
        TreeNode* cur = root;
        TreeNode* pre = root;
        while (cur){

            if (cur->val > key) {
                pre = cur;
                cur = cur -> left;
            }
            else if (cur->val < key) {
                pre = cur;
                cur = cur -> right;
            }
            else break;
            
        }

        if (cur == NULL) return root;
        else {
            if (key < pre->val){
                if (cur -> right) {
                    TreeNode* newleft = cur ->right;
                    while (newleft -> left){
                        newleft = newleft ->left;
                    }
                    newleft -> left = cur ->left;
                    pre ->left = cur->right;
                }
                else if (cur->left) pre ->left = cur->left;
                else pre->left = NULL;
            }

            if (key > pre->val){
                if (cur -> left){
                    TreeNode* newright = cur ->left;
                    while (newright -> right){
                        newright = newright ->right;
                    }
                    newright->right = cur->right;
                    pre ->right = cur->left;
                } 
                else if (cur->right) pre ->right = cur->right;
                else pre->right = NULL;
            }

            if (key == pre->val){

                if (cur->left){
                    TreeNode* newright = cur ->left;
                    while (newright -> right){
                        newright = newright ->right;
                    }
                    newright->right = cur->right;
                    root = cur->left;
                }
                else if (cur->right) root = pre ->right;
                else {
                    root = NULL;
                }
            }
        }
        return root;
        
    }
};

7.32 把二叉搜索树转换为累加树

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

• 节点的左子树仅包含键 小于 节点键的节点。
• 节点的右子树仅包含键 大于 节点键的节点。
• 左右子树也必须是二叉搜索树。

class Solution {
public:
    //思路：首先遍历一下取得所有节点和，然后中序遍历依次把值换成总和减去前一个节点值

    int getsum(TreeNode* root){
        if (root == NULL) return 0;

        int val1 = getsum(root -> left);
        int val2 = getsum(root -> right);

        return root->val + (val1 + val2);
    }
    TreeNode* convertBST(TreeNode* root) {

        int sum = getsum(root);
        if (root == NULL) return NULL;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        int presum = 0;

        while (!st.empty() || cur != NULL){
            if (cur){
                st.push(cur);
                cur = cur->left;
            }
            else {
            cur = st.top();
            st.pop();

            //计算
            presum += cur->val;
            cur ->val = sum -presum + cur->val;
            cur = cur ->right;
            }
        }
    return root;
        
    }
};

 

8. 回溯

8.0 回溯法模板

剪枝时注意递归循环中的起始位置

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

8.1 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

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

class Solution {
public:

    vector<vector<int>> result;
    vector<int> path;

    void backtraval(int n, int k , int startindex){
        // 返回条件
        if (path.size() == k){
            result.push_back(path);
            return;
        }

        // 递归过程
        for (int i = startindex; i <= n; i++){
            path.push_back(i);
            backtraval(n,k,i+1);
            // 回溯
            path.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        backtraval(n,k,1);
        return result;
    }
};

8.2 组合总和Ⅲ

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9
• 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

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

    void backtrack(int n, int k, int startindex){
        if (path.size() == k && sum == n){
            result.push_back(path);
            return;
        }

        for (int i = startindex; i <= 9; i++){
            path.push_back(i);
            sum += i;
            // 剪枝
            if (sum > n) { 
                sum -= i; 
                path.pop_back(); 
                return;
            }
            backtrack(n,k,i+1);

            path.pop_back();
            sum -= i;
        }

    }
    vector<vector<int>> combinationSum3(int k, int n) {
        backtrack(n,k,1);
        return result;
    }
};

8.3 电话号码的字母组合

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

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

class Solution {
private:
    const string letterMap[10] = {
        "", // 0
        "", // 1
        "abc", // 2
        "def", // 3
        "ghi", // 4
        "jkl", // 5
        "mno", // 6
        "pqrs", // 7
        "tuv", // 8
        "wxyz", // 9
    };
public:
    string path;
    vector<string> result;
    
    void backtrack(string digits, int length, int startindex){
        if (path.size() == length){
            result.push_back(path);
            return;
        }

        for (int j = startindex; j < digits.size() ; j++){
            int num = digits[j] - '0';
            if (num != 7 && num!= 9){
                for (int i = 0; i <= 2; i++){
                    path.push_back(letterMap[num][i]);
                    backtrack(digits, length, j+1);
                    path.pop_back();
                }
            }
            else {
                for (int i = 0; i <= 3; i++){
                    path.push_back(letterMap[num][i]);
                    backtrack(digits, length, j+1);
                    path.pop_back();
                }
            }
        }
    }
    vector<string> letterCombinations(string digits) {
        if (digits == "") return result;
        int length = digits.size();
        backtrack(digits,length,0);
        return result;
    }
};

8.4 组合总和

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

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

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

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

    void backtrack(vector<int> &candidates, int target, int startindex){

        if (sum == target){
            result.push_back(path);
            return;
        }
        // 必要剪枝，避免无限递归导致栈溢出
        if (sum > target){
            return;
        }

        for (int i = startindex; i <candidates.size(); i++){
            path.push_back(candidates[i]);
            sum+= candidates[i];

            backtrack(candidates, target, i);

            sum-= candidates[i];
            path.pop_back();
        }
    }
    
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backtrack(candidates,target,0);
        return result;
    }
};

8.5 组合总和Ⅱ

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

// 此写法必须先进行排序

class Solution {
public:

    vector<vector<int>> result;
    vector<int> path;

    void backtrack(vector<int> &candidates, int target, int startindex, int sum){

        if (sum == target){
            result.push_back(path);
            return;
        }

        if (sum > target) return;

        for (int i = startindex; i < candidates.size(); i++){
            // 不使用重复值（排序后）
            if (i > startindex && candidates[i] == candidates[i-1]) continue;
            
            path.push_back(candidates[i]);
            sum += candidates[i];

            backtrack(candidates, target, i + 1 , sum);

            path.pop_back();
            sum -= candidates[i];
        }

    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        backtrack(candidates, target, 0,0);
        return result;
    }
};

8.6 分割回文串

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

class Solution {
public:

    vector<vector<string>> result;
    vector<string> path;
    int stringcheck(string &s){
        for (int i = 0, j = s.size() - 1; i < j; i++, j--){
            if (s[i] != s[j]){
                return 0;
            }
        }
        return 1;
    }
    void backtrack(string &s, int startindex){
       if (startindex >= s.size()){
            result.push_back(path);
            return ;
       }
       
        for (int i = startindex; i < s.size(); i++){     
            string substr = s.substr(startindex, i - startindex + 1);
            if ( stringcheck(substr) )// 为回文串
            {
                path.push_back(substr);
            }
            else{
                continue;
            }
            backtrack(s, i+1);
            path.pop_back();
        }
    }

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

8.7 复原IP地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

• 例如："0.1.2.201" 和"192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

// 有点难度
class Solution {
public:
    vector<string> result;
    string path;

    void backtrack(string &s, int startindex, int dotCount) {
        if (startindex == s.size() && dotCount == 4) {
            // 去除末尾的'.'
            path.pop_back();
            result.push_back(path);
            return;
        }

        // 剪枝：提前终止条件：剩余字符太多或太少
        if (s.size() - startindex > (4 - dotCount) * 3 || 
            s.size() - startindex < (4 - dotCount)) {
            return;
        }

        for (int i = startindex; i < s.size() && i < startindex + 3; i++) {
            string substr = s.substr(startindex, i - startindex + 1);
            
            if (isValid(substr)) {
                int originalSize = path.size();
                path += substr + ".";
                
                backtrack(s, i + 1, dotCount + 1);
                
                // 回溯
                path.erase(originalSize);
            }
        }
    }

    bool isValid(string &substr) {
        if (substr.size() > 1 && substr[0] == '0') {
            return false; 
        }
        
        int num = stoi(substr);
        return num >= 0 && num <= 255;
    }
    
    vector<string> restoreIpAddresses(string s) {
        if (s.size() < 4 || s.size() > 12) return result;
        backtrack(s, 0, 0);
        return result;
    }
};

8.8 子集

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

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

// 想复杂了，本质上不需要条件直接返回就行
class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;

    void backtrack(vector<int> &nums, int startindex , int length){
        // condition
        if (path.size() == length){
            result.push_back(path);
            return;
        }
        for (int i = startindex; i < nums.size(); i++ ){
            path.push_back(nums[i]);

            backtrack(nums, i+1, length);
            path.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        for (int i = 0; i <= nums.size(); i++){
           backtrack(nums,0,i); 
        }
        return result;
    }
};

8.9 子集Ⅱ

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。

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

// 去重也可以用set
class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    void backtrack(vector<int> &nums, int startindex){
        //add to result
        result.push_back(path);

        for (int i = startindex; i < nums.size(); i++){
            //去重
            if (i > startindex && nums[i] == nums[i-1]){
                continue;
            }

            path.push_back(nums[i]);
            backtrack(nums,i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        backtrack(nums, 0);
        return result;
    }
};

8.10 非递减子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

// 这题不能用sort，因此选择用哈希表去重
class Solution {
public:

    vector<vector<int>> result;
    vector<int> path;

    void backtrack(vector<int>& nums, int startindex){
        if (path.size() >= 2 ){
            result.push_back(path);
            // return;
        }
        unordered_set<int> used;
        for (int i = startindex; i < nums.size(); i++){
            if (used.find(nums[i]) != used.end()) continue;
            if (path.size() != 0){
                if (nums[i] >= path.back()){
                    used.insert(nums[i]);
                    path.push_back(nums[i]);
                    backtrack(nums, i+1);
                    path.pop_back();
                }
            }
            else{
                used.insert(nums[i]);
                path.push_back(nums[i]);
                backtrack(nums, i+1);
                path.pop_back();
            }
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtrack(nums, 0);
        return result;
    }
};

8.11 全排列

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

// 经典问题
class Solution {
public:

    vector<vector<int>> result;
    vector<int> path;

    void backtrack(vector<int> &nums, vector<bool> &used){
        if (path.size() == nums.size()){
            result.push_back(path);
            return;
        }
        // 每次回溯均要从0索引开始
        for (int i = 0; i < nums.size(); i++){
            if (used[i] == true) continue;

            path.push_back(nums[i]);
            used[i] = true;

            backtrack(nums,used);

            path.pop_back();
            used[i] = false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> used(nums.size(), false);
        backtrack(nums,used);
        return result;
    }   
};

8.12 全排列Ⅱ

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

class Solution {
public:

    vector<vector<int>> result;
    vector<int> path;

    void backtrack(vector<int> &nums, vector<bool> &used){
        if (path.size() == nums.size()){
            result.push_back(path);
            return;
        }
        // repeat set记录同一层级(深度)的已使用过的元素集，去重
        // 确保在同一层级去重，不影响不同层级选择相同值的元素，同一层级的去重靠used实现
        unordered_set<int> repeat;
        for (int i = 0; i < nums.size(); i++){
            if (repeat.find(nums[i]) != repeat.end()) continue;
            if (used[i] == true) continue;
            used[i] = true;
            path.push_back(nums[i]);

            backtrack(nums, used);

            path.pop_back();
            used[i] = false;
            repeat.insert(nums[i]);
        }
    } 
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<bool> used(nums.size(), false);
        backtrack(nums, used);
        return result;
    }
};

8.13 N皇后

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

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

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

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

// 一开始写有两个问题，一是字符串的处理还不够熟练，二是used3状态索引一开始用的abs(i - j) 其实是错的
class Solution {
public:
    vector<string> path;
    vector<vector<string>> result;
    void backtrack(int n, int i, vector<bool> &used1, vector<bool> &used2, vector<bool> &used3){
        if (i == n){
            result.push_back(path);
            return;
        }

        for (int j = 0; j < n; j++){
            
            if ( used1[j] || used2[i+j] || used3[i - j + n]) continue;

            string s(n, '.');
            s[j] = 'Q';

            used1[j] = true;
            used2[i+j] = true;
            used3[i - j + n] =true;
            path.push_back(s);

            backtrack(n, i + 1, used1, used2, used3);
            
            used1[j] = false;
            used2[i+j] = false;
            used3[i - j + n] =false;

            path.pop_back();
            }
    }
    vector<vector<string>> solveNQueens(int n) {

        vector<bool> used1(n, false);
        vector<bool> used2(n*n, false);
        vector<bool> used3(n*n, false);

        backtrack(n, 0, used1, used2, used3);
        return result;
    }
};

8.14 解数独

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

class Solution {
public:

    bool backtrack(vector<vector<char>>& board){
        for (int row = 0; row < 9; row++){
            for (int col = 0; col < 9; col++){
                if (board[row][col] == '.'){
                    for (char k = '1'; k <= '9'; k++){
                        if (isValid(board, row, col, k)) {
                            board[row][col] = k;
                            if (backtrack(board)) return true; 
                            board[row][col] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true; 
    }

    bool isValid(vector<vector<char>>& board, int row, int col, char k){
        for (int i = 0; i < 9; i++){
            if (board[row][i] == k) return false;
        }

        for (int i = 0; i < 9; i++){
            if (board[i][col] == k) return false;
        }

        int startrow = (row / 3) * 3;
        int startcol = (col / 3) * 3;

        for (int i = startrow; i < startrow + 3; i++){
            for (int j = startcol; j < startcol + 3; j++){
                if (board[i][j] == k) return false;
            }
        }

        return true;
    }
    void solveSudoku(vector<vector<char>>& board) {
        backtrack(board);
    }
};

 

9. 贪心

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

9.1 分发饼干

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是满足尽可能多的孩子，并输出这个最大数值。

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {

        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int count = 0;
        int backindex = s.size() - 1;
        for (int i = g.size() - 1; i >= 0; i--) {
            if (backindex >= 0 && s[backindex] >= g[i] ) {
                backindex--;
                count++;
            }
            if(backindex < 0) break;
        }
        return count;
    }
};

9.2 摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

//注意连续数据相等的情况
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if (nums.size() == 1) return 1;
        
        int count = 1; 
        int prevDiff = 0;

        for (int i = 1; i < nums.size(); i++) {
            int currDiff = nums[i] - nums[i-1];
            
            if (currDiff == 0) continue;
            
            if (prevDiff == 0 || (prevDiff > 0 && currDiff < 0) || (prevDiff < 0 && currDiff > 0)) {
                count++;
                prevDiff = currDiff;
            }
        }

        return count;
    }
};

9.3 最大子数组和

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

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

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int count = 0;
        int maxsum = INT_MIN;

        for (int i = 0; i < nums.size(); i++){
            count += nums[i];
            if (count > maxsum) maxsum = count;
            if (count < 0) count = 0;
        }
        return maxsum;
    }
};

9.4 买卖股票的最佳时机Ⅱ

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profits = 0;
        for (int i = 1; i < prices.size(); i++){
            int curdiff = prices[i] - prices[i - 1];
            if (curdiff > 0){
                profits += curdiff;
            }
        }
        return profits;
    }
};

9.5 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

//写的太复杂了，思路对的，但不需要 跳转 这个操作
class Solution {
public:
    bool canJump(vector<int>& nums) {

        int length = nums.size();
        int startindex = 0;

        if (nums.size() == 0) return false;

        while (startindex < nums.size() - 1){
            int nextrange = nums[startindex];
            if (nextrange == 0) return false;
            int nextmax = INT_MIN;
            if (startindex + nextrange >= nums.size() - 1) return true;
            int recordindex = startindex;
            for (int i = startindex + 1; i <= startindex + nextrange; i++){
                    int opt = i + nums[i];
                    if (opt > nextmax){
                        nextmax = opt;
                        recordindex = i;
                    }
            }
            startindex = recordindex; 
        }
        return true;
    }
};

// 简单解法
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int cover = 0;
        if (nums.size() == 1) return true;
        for (int i = 0; i <= cover; i++) { 
            cover = max(i + nums[i], cover);
            if (cover >= nums.size() - 1) return true; 
        }
        return false;
    }
};

9.6 跳跃游戏Ⅱ

给定一个长度为 n 的 0 索引整数数组 nums。初始位置在下标 0。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：

• 0 <= j <= nums[i] 且
• i + j < n

返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1。

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

        int startindex = 0;
        int count = 0;
        if (nums.size() == 1) return 0;

        while (startindex < nums.size() - 1){
            int nextrange = nums[startindex];
            if (nextrange == 0) {
                return 0;
            }
            int nextmax = INT_MIN;
            if (startindex + nextrange >= nums.size() - 1){
                break;
            } 
            int recordindex = startindex;
            for (int i = startindex + 1; i <= startindex + nextrange; i++){
                    int opt = i + nums[i];
                    if (opt > nextmax){
                        nextmax = opt;
                        recordindex = i;
                    }
            }
            startindex = recordindex; 
            count ++;
        }

        count += 1;
        return count; 
    }
};

9.7 K次取反后最大化的数组和

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

• 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。

重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后，返回数组 可能的最大和 。

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
		// 不需要按绝对值排序
        for (int i = 0; i < k; i++) {
            sort(nums.begin(), nums.end());
            nums[0] = -nums[0];
        }

        int sum = 0;
        for (auto& num : nums) {
            sum += num;
        }

        return sum;
    }
};

9.8 加油站

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        vector<int> diff(gas.size(), 0);
        for (int i = 0; i < gas.size(); i++){
            diff[i] = gas[i] - cost[i];
        }
        int count = 0;
        int totalsum = 0;
        int possum = 0;
        int negasum = 0;

        for (int i = 0; i < diff.size(); i++){
            if (diff[i] < 0) negasum += diff[i];
            if (diff[i] > 0) possum += diff[i]; 
            totalsum += diff[i];
			// 这里是精髓
            if (totalsum < 0){
                count = i + 1;
                totalsum = 0;
            }
        }

        if ((negasum + possum) < 0) return -1;

        else return count;
    }
};

9.9 分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 相邻两个孩子中，评分更高的那个会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

//没想出来
class Solution {
public:
    int candy(vector<int>& ratings) {
        int sum = 0;
        vector<int> candycount(ratings.size(), 1);

        for (int i = 0; i < ratings.size()-1; i++){
        if (ratings[i+1] > ratings[i]) candycount[i+1] = candycount[i] + 1;
        }

        for (int i = ratings.size() - 2; i >= 0; i--){
        if (ratings[i+1] < ratings[i]) {
            //贪心思想在这里
            candycount[i] = max(candycount[i+1] + 1, candycount[i]);
        }
        }
        for (int i = 0; i < candycount.size(); i++){
            sum += candycount[i];
        }

        return sum;
    }
};

9.10 柠檬水找零

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        unordered_map<int,int> cash;
        for (int i = 0; i < bills.size(); i++){
            if(bills[i] == 5) cash[5]++;
            else if (bills[i] == 10) {
                cash[10]++;
                if (cash[5]>0) cash[5]--;
                else return false;
            }
            else{
                 cash[20]++;
                //优先找10块钱的
                 if (cash[5]>0 && cash[10]>0){
                 cash[5]--;
                 cash[10]--;
                 }
                 else if (cash[5]>=3){
                    cash[5] -= 3;
                 }
                 else return false;
            }
        }
        return true;
    }
};

9.11 根据身高重建队列

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。

请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

//两个判断条件，先梳理好一个再考虑另外一个
class Solution {
public:
//类内定义cmp需要使用静态成员函数，防止this指针出现
    static bool cmp(const vector<int>& a, const vector<int>&b){
        if (a[0] == b[0]) return a[1] < b[1];
        return a[0] > b[0];
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        vector<vector<int>> queue;
        sort(people.begin(), people.end(), cmp);
        for (int i = 0; i < people.size(); i++){
            int index = people[i][1];
            queue.insert(queue.begin() + index, people[i]);
        }
        return queue;
    }
};

9.12 用最少数量的箭引爆气球

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

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

给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。

//秒了
class Solution {
public:

    static bool cmp(const vector<int> &a, const vector<int> &b){
        if (a[0] == b[0]) return a[1] < b[1];
        return a[0] < b[0];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(), points.end(), cmp);
        int count = points.size();
        int rightboundary = points[0][1];
        for (int i = 0;  i < points.size() - 1; i++){
            if (points[i+1][0] <= rightboundary){
                rightboundary = min(rightboundary, points[i+1][1]);
                count--;
            }
            else rightboundary = points[i+1][1];
        }
        return count;
    }
};

9.13 无重叠区间

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

注意 只在一点上接触的区间是 不重叠的。例如 [1, 2] 和 [2, 3] 是不重叠的。

//思想同上，边界处理方式不同
class Solution {
public:
    static bool cmp(const vector<int> &a, const vector<int> &b){
        if (a[0] == b[0]) return a[1] < b[1];
        return a[0] < b[0];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int result = 0;
        sort(intervals.begin(), intervals.end(), cmp);
        int right = intervals[0][1];
        for (int i = 0; i < intervals.size()-1; i++){
        if(intervals[i+1][0] < right){
            result++;
            right = min(intervals[i+1][1], right);
        } 
        else {
            right = intervals[i+1][1];
        }
        }
        return result;
    }
};

9.14 划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

// 用哈希表记录每个字符出现的最后位置
// 统计每一个字符最后出现的位置
// 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
class Solution {
public:
    vector<int> partitionLabels(string s) {

        vector<int> hash(27,0);
        for (int i = 0; i < s.size(); i++){
            hash[s[i] - 'a'] = i;
        }

        int maxindex = 0;
        vector<int> result;
        int left = 0;
        for (int right = 0; right < s.size(); right++){
        	maxindex = max(maxindex,  hash[s[right] - 'a']);
        	if (right == maxindex){
                result.push_back(right - left + 1);
                left = right + 1;
        	}
        }
        return result;
    }
};

9.15 合并区间

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

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

        vector<vector<int>> result;
        vector<int> ele(2,0);
        
        sort(intervals.begin(), intervals.end(), cmp);
        int right = intervals[0][1];
        int left = intervals[0][0];

        for (int i = 0; i < intervals.size() - 1; i++){
            if (intervals[i+1][0] <= right){
                right = max(intervals[i+1][1], right);
            }
            else{
                ele[0] = left;
                ele[1] = right;
                result.push_back(ele); 

                left = intervals[i+1][0];
                right = intervals[i+1][1];
            }
        }
        //最后一项也放进去
        ele[0] = left;
        ele[1] = right;
        result.push_back(ele); 

        return result;
        
    }
};

9.16 单调递增的数字

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。

//本题用字符串就不需要考虑数据大小的问题了
class Solution {
public:
    int monotoneIncreasingDigits(int n) {

        if (n == 0) return 0;
        vector<int> nums;
        while (n > 0){
            int num = n % 10;
            n = n / 10;
            nums.push_back(num);
        }
        for (int i = 0; i < nums.size()-1; i++){
            if (nums[i] < nums[i+1]){
                for (int j = 0; j <= i; j++) nums[j] = 9;
                nums[i+1] = nums[i+1] - 1;
            }
        }
        int sum = 0;
        //测试例有较大数据，用long
        long weight = 1;
        for (int i = 0; i < nums.size(); i++){
            sum += nums[i] * weight;
            weight *= 10;
        }
        return sum;
    }
};

9.17 监控二叉树

给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

//难度高
//贪心思想：从叶子节点向上搜索，叶子节点的父节点需要安装，再往上每隔2个节点放一个
//0：该节点无覆盖
//1：本节点有摄像头
//2：本节点有覆盖
class Solution {
private:
    int result;
    int traversal(TreeNode* cur) {

        // 空节点，该节点有覆盖
        if (cur == NULL) return 2;

        int left = traversal(cur->left);    // 左
        int right = traversal(cur->right);  // 右

        // 情况1
        // 左右节点都有覆盖
        if (left == 2 && right == 2) return 0;

        // 情况2
        // left == 0 && right == 0 左右节点无覆盖
        // left == 1 && right == 0 左节点有摄像头，右节点无覆盖
        // left == 0 && right == 1 左节点有无覆盖，右节点摄像头
        // left == 0 && right == 2 左节点无覆盖，右节点覆盖
        // left == 2 && right == 0 左节点覆盖，右节点无覆盖
        if (left == 0 || right == 0) {
            result++;
            return 1;
        }

        // 情况3
        // left == 1 && right == 2 左节点有摄像头，右节点有覆盖
        // left == 2 && right == 1 左节点有覆盖，右节点有摄像头
        // left == 1 && right == 1 左右节点都有摄像头
        // 其他情况前段代码均已覆盖
        if (left == 1 || right == 1) return 2;

        // 这个 return -1 逻辑不会走到这里。
        return -1;
    }

public:
    int minCameraCover(TreeNode* root) {
        result = 0;
        // 情况4
        if (traversal(root) == 0) { // root 无覆盖
            result++;
        }
        return result;
    }
};

10. 动态规划

动态规划中每一个状态一定是由上一个状态推导出来的，这一点区分于贪心，贪心没有状态推导，而是从局部直接选最优的。

10.1 斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

class Solution {
public:
    int fib(int n) {
        if (n == 0 ) return 0;
        if (n == 1 ) return 1;
        return (fib(n-1) + fib(n-2));
    }
};

//dp 形式
class Solution {
public:
    int fib(int n) {
        if (n == 0 ) return 0;
        if (n == 1 ) return 1;
        vector<int> dp(n+1,0);
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};
// 递归比dp效率低，因为很多值被重复计算了多次

10.2 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return n; // 因为下面直接对dp[2]操作了，防止空指针
        vector<int> dp(n+1,0);
        dp[1] = 1;
        dp[2] = 2; 

        for (int i = 3; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }

        return dp[n];
    }
};

10.3 使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
       vector<int> dp(cost.size()+2,0); 
       dp[0] = 0;
       dp[1] = 0;

       for (int i = 2; i <= cost.size(); i++){
        dp[i] = min(dp[i-1] + cost[i-1] , dp[i-2] + cost[i-2]);
       }

       return dp[cost.size()];
    }
};

10.4 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m,vector<int> (n,0));

        for (int i = 0; i < n; i++){
            dp[0][i] = 1;
        }
        for (int i = 0; i < m; i++){
            dp[i][0] = 1;
        }
        for (int i = 1; i < m ; i++){
            for (int j = 1; j < n; j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};

10.5 不同路径Ⅱ

给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。

网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。

返回机器人能够到达右下角的不同路径数量。

测试用例保证答案小于等于 2 * 109。

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int>> dp(m, vector<int>(n,0));
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 0) dp[i][0] = 1;
            if (obstacleGrid[i][0] == 1) {
                for (int j = i; j < m; j++) dp[j][0] = 0;
                break;
            }
        }
        for (int i = 0; i < n; i++) {
            if (obstacleGrid[0][i] == 0) dp[0][i] = 1;
            if (obstacleGrid[0][i] == 1) {
                for (int j = i; j < n; j++) dp[0][j] = 0;
                break;
            }
        }
        for (int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if (obstacleGrid[i][j]){
                    dp[i][j] = 0;
                }
                else dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};

10.6 整数拆分

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

// 拆分成2个数和3个数及以上的情况
class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n+1,0);

        dp[2] = 1;
        dp[1] = 1;

        for (int i = 3; i <= n; i++){
            for (int j = 1; j < i ; j++){
                //首个max():内层遍历  第二个max():比较2个数和多个数大小
                dp[i] = max( dp[i] , max(j*(i-j), j*dp[i-j]));
            }
        }
        return dp[n];
    }
};

10.7 不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+1, 0);
        if (n <= 2) return n;
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++){
            for (int j = 0; j < i; j++){
                dp[i] += dp[j] * dp[i - j - 1];
            }
        } 
        return dp[n];
    }
};

10.8 01背包问题

小明需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。

小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。

输入描述：

第一行包含两个正整数，第一个整数 M 代表研究材料的种类，第二个正整数 N，代表小明的行李空间。

第二行包含 M 个正整数，代表每种研究材料的所占空间。

第三行包含 M 个正整数，代表每种研究材料的价值。

输出整数代表小明能够携带的研究材料的最大价值。

#include <iostream>
#include <vector>

using namespace std;

int main(){

    int type, luggage;
    cin >> type >> luggage;
    vector<int> space(type,0);
    vector<int> value(type,0);
    for (int i = 0; i < type; i++){
       cin >> space[i]; 
    }
    for (int i = 0; i < type; i++){
       cin >> value[i]; 
    }

    vector<vector<int>> dp(type, vector<int>(luggage + 1,0));

    //初始化dp
    //1. dp[i][0] 
    for(int i = 0; i < type; i++){
        dp[i][0] = 0;
    }
    //2. dp[0][j]
    for (int j = space[0]; j < luggage + 1; j++){
        dp[0][j] = value[0];
    }

    //递推,dp[i][j] 表示在j的空间下，在前i种选择里能达到的最大价值
    // 有两种情况，1是取i的物品，2是不取
    for (int i = 1; i < type; i++){
        for (int j = 0; j < luggage+1; j++){
            if (j >= space[i])
            dp[i][j] = max(dp[i-1][j] , dp[i-1][j-space[i]] + value[i]);
            else dp[i][j] = dp[i-1][j];

            //cout << dp[i][j]<< ' ';
        }
    }
    cout << dp[type-1][luggage];
    return 0;

}



// 一维压缩 这里使用递减的原因是二维状态转移时左上方数值需要保留以用来参考，则一维需要保留左侧数值参考
#include <iostream>
#include <vector>

using namespace std;

int main(){

    int type, luggage;
    cin >> type >> luggage;
    vector<int> space(type,0);
    vector<int> value(type,0);
    for (int i = 0; i < type; i++){
       cin >> space[i]; 
    }
    for (int i = 0; i < type; i++){
       cin >> value[i]; 
    }

    //初始化
    vector<int> dp(luggage + 1,0);

    // 新增一层物品状态来源于上一层状态
    for (int i = 0; i < type; i++){
        for (int j = luggage; j >= space[i]; j--){
            dp[j] = max(dp[j] , dp[j-space[i]] + value[i]);
        }
    }

    cout << dp[luggage];

    return 0;

}

10.9 分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        vector<int> dp(10001,0);
        int sum = 0;
        int target = 0;
        for (int i = 0; i < nums.size(); i++){
            sum += nums[i];
        }
        if (sum % 2) return false;
        else  target = sum / 2;
        for (int i = 0; i < nums.size(); i++){
            for (int j = target; j >= nums[i]; j--){
                dp[j] = max(dp[j], dp[j-nums[i]] + nums[i]);
            }
        }
		//判断能否分割，看 sum的一半 背包能否被装满
        if (dp[target] == target) return true;
        return false;
    }
};

10.10 最后一块石头的重量Ⅱ

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

• 如果 x == y，那么两块石头都会被完全粉碎；
• 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        
         vector<int> dp(15001,0);
        int sum = 0;
        int target = 0;
        for (int i = 0; i < stones.size(); i++){
            sum += stones[i];
        } 
        target = sum / 2;
        for (int i = 0; i < stones.size(); i++){
            for (int j = target; j >= stones[i]; j--){
                dp[j] = max(dp[j], dp[j-stones[i]] + stones[i]);
            }
        }
        return (sum - dp[target]) - dp[target];
    }
};

10.11 目标和

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
     int sum = 0;
     for (int i = 0; i < nums.size(); i++){
        sum += nums[i];
     }

     if (abs(target) > sum) return 0;
     if ((sum + target) % 2) return 0; 
     int bagsize = (sum + target) / 2;
     
    vector<int> dp(bagsize+1,0);
    dp[0] = 1;
    for (int i = 0; i < nums.size();i++){
        for (int j = bagsize; j>=nums[i]; j--){
            // 组合问题用二维的方式先思考一遍
            dp[j] = dp[j] + dp[j-nums[i]];
        }
    }

    return dp[bagsize];
    }
};

10.12 一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

//相当于物品有两个维度的重量
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
      
      vector<vector<int>> dp(m+1, vector<int>(n+1,0));
       for (auto &s : strs){
        int zeronum = 0;
        int onenum = 0;

        for (auto &ch : s){
            if (ch == '0') zeronum ++;
            else onenum ++;
        }
		//向后遍历原因：实际上这两层for循环都是在遍历背包，又根据递推式可知后一次遍历的值需要和之前的左上方对比，因此需要从后向前遍历
        for (int i = m; i >= zeronum; i--){
            for(int j = n; j >= onenum; j--){
                dp[i][j] = max(dp[i][j], dp[i-zeronum][j-onenum] + 1);
            }
          }
       } 
       return dp[m][n];
    }
};

10.13 完全背包

小明需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的重量，并且具有不同的价值。

小明的行李箱所能承担的总重量是有限的，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料可以选择无数次，并且可以重复选择。

输入描述

第一行包含两个整数，n，v，分别表示研究材料的种类和行李所能承担的总重量

接下来包含 n 行，每行两个整数 wi 和 vi，代表第 i 种研究材料的重量和价值

// 由于 可以重复取 这一特性，dp初始化与递归式与01背包不同
#include <iostream>
#include <vector>
using namespace std;

int main(){
    
int type, bagsize;
cin >> type >> bagsize;

vector<int> weight(type, 0);
vector<int> value(type, 0);

for (int i = 0; i < type; i++) cin >> weight[i]>> value[i];

vector<vector<int>> dp(type , vector<int>(bagsize + 1, 0));
// 初始化
for (int j = weight[0]; j <= bagsize; j++)
    dp[0][j] = dp[0][j - weight[0]] + value[0];

for (int i = 1; i < type; i++){
    for (int j = 0; j <= bagsize; j++){
        if (j >= weight[i])
            // 这里递归式需要注意也可以取当前行的
            dp[i][j] = max(dp[i-1][j], dp[i][j - weight[i]] + value[i]);
        else 
            dp[i][j] = dp[i-1][j];
    }
}

cout << dp[type - 1][bagsize] << endl;

}

10.14 零钱兑换Ⅱ

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

class Solution {
public:
    int change(int amount, vector<int>& coins) {
      // 用uint64_t 应对最后一个测试用例 
     vector<vector<uint64_t>> dp(coins.size(), vector<uint64_t>(amount + 1,0)); 
     // 初始化
     for (int i = 0; i < coins.size(); i++) dp[i][0] = 1;
     for (int i = 0; i <= amount; i++){
        if (i % coins[0] == 0) dp[0][i] =1;
     }
     // 递推
     for (int i = 1; i < coins.size(); i++){
        for (int j = 0; j <= amount; j++ ){
            if (j >= coins[i]) dp[i][j] = dp[i-1][j] + dp[i][ j - coins[i]];
            else dp[i][j] = dp[i-1][j];
        }
     }  

     return dp[coins.size() - 1][amount];
    }
};

//一维dp
// 可压缩原因：尽管从递推公式上看，dp[i][j]由前一行和本行共同决定，貌似不能压缩，但是其实由于完全背包的特性，只要从前向后遍历，就能保留本行的结果

class Solution {
public:
    int change(int amount, vector<int>& coins) {

     vector<uint64_t> dp(amount + 1,0); 
     // 初始化
     dp[0] = 1;

     // 递推
     for (int i = 0; i < coins.size(); i++){
        for (int j = 0; j <= amount; j++ ){
            if (j >= coins[i]) dp[j] += dp[j - coins[i]];
            else dp[j] = dp[j];
        }
     }  
     return dp[amount];
    }
};
// 一维完全背包dp递推一个重要的性质，将内外循环顺序对换后，是组合与排列的区别
//组合数的递推：
//dp[j] 只依赖于之前已经计算过的组合，不会产生重复的顺序排列

//排列数的递推：
//对于每个金额j，都会考虑所有可能的硬币作为最后一步，从而产生所有可能的排列

10.15 组合问题Ⅳ

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

// 求排列就是求排列，还叫组合问题就不太对了
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {

        vector<uint64_t> dp(target+1, 0);

        dp[0] = 1;

        for (int j = 0; j <= target; j++){
            for (int i = 0; i < nums.size(); i++){
                if (j >= nums[i])
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[target];
    }
};

10.16 爬楼梯进阶

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int n , m;
    cin >> n >> m;

    vector<int> dp(n + 1, 0);
    dp[0] = 1;

    for (int j = 0; j <= n; j++){
        for (int i = 1; i <= m; i++){
            if (j >= i) dp[j] += dp[j - i];
        }
    }
    cout << dp[n];
    return 0;
}

10.17 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<vector<int>> dp(coins.size(), vector<int>(amount+1 , INT_MAX));
        // 初始化
        for (int i = 0; i <= amount; i++){
            if (i % coins[0] == 0) dp[0][i] = i / coins[0];
        }

        for (int i = 0; i < coins.size(); i++){
            dp[i][0] = 0;
        }
        
        // 递推
        for (int i = 1; i < coins.size(); i++){
            for (int j = 0; j <= amount; j++){
                if (j >= coins[i]) {
                    if (dp[i][j - coins[i]] == INT_MAX) dp[i][j] = dp[i-1][j];
                    else dp[i][j] = min(dp[i-1][j], dp[i][j - coins[i]] + 1);
                }   
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }

        if (dp[coins.size() - 1][amount] == INT_MAX) return -1;
        return dp[coins.size() - 1][amount];
    }
};

10.18 完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1);

        dp[0] = 0;
        for (int i = 1; i <= n; i++) dp[i] = i;
        for (int i = 2; i <= sqrt(n); i++){
            for (int j = 0; j <= n; j++){
                if (j >= i*i)
                    dp[j] = min(dp[j], dp[j - i*i] + 1);
            }
        }

        return dp[n];
    }
};

10.19 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

// 想法有点难度 递推公式比较特殊 不能纠结于“背包”概念
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for (int i = 1; i <= s.size(); i++) {   
            for (int j = 0; j < i; j++) {       
                string word = s.substr(j, i - j); //substr(起始位置，截取的个数)
                if (wordSet.find(word) != wordSet.end() && dp[j]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.size()];
    }
};

10.20 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

// dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。
class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        vector<int> dp(nums.size(), 0);

        dp[0] = nums[0];
        dp[1] = max(nums[0] , nums[1]);

        for (int i = 2; i < nums.size(); i++){
            dp[i] = max(dp[i - 2] + nums[i] , dp[i-1]);
        }

        return dp[nums.size() - 1];
    }
};

10.21 打家劫舍Ⅱ

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

//按首尾包含情况分两种讨论
class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        if (nums.size() == 2) return max(nums[0], nums[1]);

        vector<int> dp(nums.size(), 0);

        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        
        for (int i = 2; i < nums.size() - 1; i++){
            dp[i] = max(dp[i-1] , dp[i-2] + nums[i]);
        }

        int result1 = dp[nums.size() - 2];

        dp = vector<int>(nums.size(), 0);
        dp[1] = nums[1];
        dp[2] = max(dp[1], nums[2]);

        for (int i = 3; i < nums.size(); i++){
            dp[i] =  max(dp[i-1] , dp[i-2] + nums[i]);
        }

        int result2 = dp[nums.size() - 1];

        return max(result1, result2);
    }
};

10.22 打家劫舍Ⅲ

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 *在不触动警报的情况下 ，小偷能够盗取的最高金额* 。

// 一开始的错误思路
// 层序遍历后把每层的和作为一次value
// 这样写的问题，漏了一些情况，比如[2,1,3,null,4]
class Solution {
public:
    int rob(TreeNode* root) {
        if (root == NULL) return 0;

        queue<TreeNode*> que;
        int layer = 0;
        que.push(root);
        vector<int> value;

        while (!que.empty()){

            int size = que.size();
            int layervalue = 0;
            for (int i = 0; i < size; i++){
            TreeNode* cur = que.front();
            que.pop();

            layervalue += cur->val;

            if (cur->left) que.push(cur->left);
            if (cur->right) que.push(cur->right);
            }

            value.push_back(layervalue);
            layer++;
        }

        if (layer == 1) return value[0];
        vector<int> dp(layer,0);
        dp[0] = value[0];
        dp[1] = max(value[0], value[1]);

        for (int i = 2; i < layer; i++){
            dp[i] = max(dp[i-2] + value[i], dp[i-1]);
        }

        return dp[layer - 1];
    }
};

// 思路：把dp由一维数组转换成树形结果
class Solution {
public:

    vector<int> robtree(TreeNode* cur){
		// 两种情况，对应不选本节点和选本节点
        //所以dp数组：下标为0记录不选该节点所得到的的最大金钱，下标为1记录选该节点所得到的的最大金钱。
        vector<int> result(2,0);
        if (cur == NULL) return result;

        vector<int> left = robtree(cur->left);
        vector<int> right = robtree(cur->right);

        // 不选本节点
        result[0] = max(left[0], left[1]) + max(right[0], right[1]);
        // 选本节点
        result[1] = cur->val + left[0] + right[0];

        return result;
    }
    int rob(TreeNode* root) {
        vector<int> result = robtree(root);
        return max(result[0], result[1]);
    }
};

10.23 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

// 想法：dp[i][0] 表示第i天持有股票所得最多现金
// dp[i][1] 表示第i天不持有股票所得最多现金
/*
如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来

第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]
那么dp[i][0]应该选所得现金最大的，所以dp[i][0] = max(dp[i - 1][0], -prices[i]);

如果第i天不持有股票即dp[i][1]， 也可以由两个状态推出来

第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：prices[i] + dp[i - 1][0]
同样dp[i][1]取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
*/
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 0) return 0;
        vector<vector<int>> dp(prices.size(), vector<int>(2, 0));

        dp[0][0] = -prices[0];
        dp[0][1] = 0;

        for (int i = 1; i < prices.size(); i++){
            dp[i][0] = max(dp[i-1][0], -prices[i]);
            dp[i][1] = max(dp[i-1][1], prices[i] + dp[i-1][0]);
        }

        return dp[prices.size() - 1][1];
    }
};

10.24 买卖股票的最佳时机Ⅱ（dp写）

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

// 之前用贪心写过， 用dp方法写一下
class Solution {
public:
    int maxProfit(vector<int>& prices) {

        if (prices.size() == 0) return 0;
        vector<vector<int>> dp(prices.size(), vector<int>(2,0));

        dp[0][0] = -prices[0];
        dp[0][1] = 0;

        for (int i = 1; i < prices.size(); i++){
            // 这里是与上一题的区别之处: max中的后一项指第i天持有股票，可以是前一天不持有股票，今天买入后的现金; 上一题由于一共只能买一次，因此买之前一定现金为0
            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[prices.size() - 1][1];
    }
};

10.25 买卖股票的最佳时机Ⅲ

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 0) return 0;

        vector<vector<int>> dp(prices.size(), vector<int>(4,0));

        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = -prices[0];
        dp[0][3] = 0;

        for (int i = 1; i < prices.size(); i++){
            // first hold
            dp[i][0] = max(dp[i-1][0], -prices[i]);
            // first unhold
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);
            // second hold
            dp[i][2] = max(dp[i-1][2], dp[i-1][1] - prices[i]);
            // second unhold
            dp[i][3] = max(dp[i-1][3], dp[i-1][2] + prices[i]);
        }

        // return dp[prices.size() - 1][3]; 这个包含下面的情况
        return max(dp[prices.size() - 1][1], dp[prices.size() - 1][3]);
    }
};

10.26 买卖股票的最佳时机Ⅳ

给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

// 从上一题归纳而来
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if (prices.size() == 0) return 0;

        vector<vector<int>> dp(prices.size(), vector<int>(k*2,0));
        for (int j = 0; j < 2*k; j++){
            if ( j % 2 == 0) dp[0][j] = -prices[0];
            else dp[0][j] = 0;
        }
        for (int i = 1; i < prices.size(); i++){
            dp[i][0] = max(dp[i-1][0], -prices[i]);
            for (int j = 1; j < 2 * k; j++){
                if (j % 2) // unhold
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + prices[i]);
                else // hold
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] - prices[i]);
            }
        }

        return dp[prices.size() - 1][2*k-1]; 
    }
};

10.27 买卖股票的最佳时机含冷冻期

给定一个整数数组prices，其中第 prices[i] 表示第 *i* 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

// 除了基础的状态外增加冷冻期状态和当天卖出状态

/*
持有股票状态（状态一）即：dp[i][0]，有两个操作：
1：前一天就是持有股票状态（状态一），dp[i][0] = dp[i - 1][0]
2：今天买入了，有两种情况
前一天是冷冻期（状态四），dp[i - 1][3] - prices[i]
前一天是保持卖出股票的状态（状态二），dp[i - 1][1] - prices[i]
那么dp[i][0] = max(dp[i - 1][0], dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]);

无股票且不进入冷冻期（当天不卖出）状态（状态二）即：dp[i][1]，有两个具体操作：
操作一：前一天就是状态二
操作二：前一天是冷冻期（状态四）
dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);

无股票且进入冷冻期（当天卖出股票）状态（状态三），即：dp[i][2] ，只有一个操作：
昨天一定是持有股票状态（状态一），今天卖出
即：dp[i][2] = dp[i - 1][0] + prices[i];

冷冻期状态（状态四），即：dp[i][3]，只有一个操作：
昨天卖出了股票（状态三）
dp[i][3] = dp[i - 1][2];
*/
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0;
        vector<vector<int>> dp(n, vector<int>(4, 0));
        dp[0][0] = -prices[0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]));
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
            dp[i][2] = dp[i - 1][0] + prices[i];
            dp[i][3] = dp[i - 1][2];
        }
        return max(dp[n - 1][3], max(dp[n - 1][1], dp[n - 1][2]));
    }
};

10.28 买卖股票的最佳时机含手续费

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        if (prices.size() == 0) return 0;
        vector<vector<int>> dp(prices.size(), vector<int>(2,0));
        dp[0][0] = -prices[0];
        dp[0][1] = 0;

        for (int i = 1; i < prices.size(); 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] - fee);
        }
        return dp[prices.size() - 1][1];
    }
};

10.30 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.size() <= 1) return nums.size();
        // dp[i] : longest subarray end by num[i]
        vector<int> dp(nums.size() , 1);
        int result = 0;
        for (int i = 1; i < nums.size(); i++){
		// search the longest subarray end by element before num[i]
            for (int j = 0; j < i; j++){
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            if (dp[i] > result) result = dp[i];
        }
        return result;
    }
};

10.31 最长连续递增序列

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        if (nums.size() <= 1) return nums.size();

        vector<int> dp(nums.size(), 1);
        int result = 0;
        for (int i = 1; i < nums.size(); i++){
            if (nums[i] > nums[i-1]) dp[i] = dp[i-1] + 1;
            if (dp[i] > result) result = dp[i];
        }
        return result;
    }
};

10.32 最长重复子数组

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

// 想法有点难
// dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。
class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() == 0 || nums2.size() == 0) return 0;

        vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
        int result = 0;
        for (int i = 1; i <= nums1.size(); i++){
            for (int j = 1; j <= nums2.size(); j++){
                if (nums1[i -1] == nums2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
                if ( dp[i][j] > result ) result = dp[i][j];
            }
        }
        return result;

    }
};

10.32 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        if (text1.size() == 0 || text2.size() == 0) return 0;

        vector<vector<int>> dp(text1.size()+1, vector<int>(text2.size()+1,0));

        for (int i = 1; i <= text1.size(); i++){
            for (int j = 1; j <= text2.size(); j++){
                if (text1[i-1] == text2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
            }
        }

        return dp[text1.size()][text2.size()];
    }
};

10.33 不相交的线

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足：

• nums1[i] == nums2[j]
• 且绘制的直线不与任何其他连线（非水平线）相交。

请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。

以这种方法绘制线条，并返回可以绘制的最大连线数。

// 思路最清晰的一集
class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() == 0 || nums2.size() == 0) return 0;

        vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));

        for (int i = 1; i <= nums1.size(); i++){
            for (int j = 1; j <= nums2.size(); j++){
                if (nums1[i-1] == nums2[j-1]){
                    dp[i][j] = max(dp[i-1][j-1] + 1, max(dp[i-1][j], dp[i][j-1]));
                }
                else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[nums1.size()][nums2.size()];
    }
};

10.34 最大子数组和

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

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

// 配合前面的贪心算法食用
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        // dp: subarray's maxsum ended by nums[i]
        vector<int> dp(nums.size(), 0);

        dp[0] = nums[0];
        int result = nums[0];
        for (int i = 1; i < nums.size(); i++){
            dp[i] = max(dp[i-1] + nums[i], nums[i]);
            if (dp[i] > result) result = dp[i];
        }
        return result;
    }
};

10.35 判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

// 按10.33写法可以直接过
class Solution {
public:
    bool isSubsequence(string s, string t) {

        if (s.size() > t.size() ||  t.size() == 0 && s.size()) return false;
        if (s.size() == 0) return true;

        vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));

        for (int i = 1; i <= s.size(); i++){
            for (int j = 1; j <= t.size(); j++){
                if (s[i-1] == t[j-1]){
                    dp[i][j] = max(dp[i-1][j-1] + 1, max(dp[i-1][j], dp[i][j-1]));
                }
                else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return (dp[s.size()][t.size()] == s.size());
    }
};

10.36 不同的子序列

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。

测试用例保证结果在 32 位有符号整数范围内。

class Solution {
public:
    int numDistinct(string s, string t) {
        if (s.size() < t.size()) return 0;

        vector<vector<uint64_t>> dp(s.size()+1, vector<uint64_t>(t.size() + 1,0));
        for (int i = 0; i <= s.size(); i++) dp[i][0] = 1;

        for (int i = 1; i <= s.size(); i++){
            for (int j = 1; j <= t.size(); j++){
                if (s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
                else dp[i][j] = dp[i-1][j];
            }
        }

        return dp[s.size()][t.size()];
    }
};

10.37 两个字符串的删除操作

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。

每步 可以删除任意一个字符串中的一个字符。

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1,0));
        for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
        for (int i = 0; i <= word2.size(); i++) dp[0][i] = i;

        for (int i = 1; i <= word1.size(); i++){
            for (int j = 1; j <= word2.size(); j++){
                if (word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1];
                else dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + 1;
            }
        }

        return dp[word1.size()][word2.size()];
    }
};

10.38 编辑距离

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

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

• 插入一个字符
• 删除一个字符
• 替换一个字符

class Solution {
public:
    int minDistance(string word1, string word2) {

        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));

        for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
        for (int i = 0; i <= word2.size(); i++) dp[0][i] = i;

        for (int i = 1; i <= word1.size(); i++){
            for (int j = 1; j <= word2.size(); j++){
                if (word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1];
                else
                    // 主要要了解替换插入和删除是等价的
                    dp[i][j] = min(dp[i-1][j-1] + 1, min(dp[i][j-1]+1, dp[i-1][j] + 1));
            }
        }

        return dp[word1.size()][word2.size()];
        
    }
};

10.39 回文子串

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

// 可以两层for循环再reverse判断
// dp写法 这里的递推关系和遍历顺序都比较特殊，dp[i][j] 是s的i~j项能否组成回文子串，需要靠内层判断
class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        int result = 0;

        for (int i = s.size() - 1; i >= 0; i--){
            for (int j = i; j < s.size(); j++){
                if (s[i] == s[j]) {
                    if (j - i <= 1){
                        dp[i][j] = true;
                        result++;
                    }  
                    else{
                        if (dp[i][j] = dp[i+1][j-1] & true){
                            dp[i][j] = true;
                            result++;
                        }
                    }
                }
            }
        }

        return result;
    }
};

10.40 最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
        int result = 0;

        for (int i = s.size() - 1; i >= 0; i--){
            for (int j = i; j < s.size(); j++){
                if (s[i] == s[j]) {
                    if (j - i == 0){
                        dp[i][j] += 1;
                    }  
                    else
                        dp[i][j] = dp[i+1][j-1] + 2;
                }
                else dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
            }
        }
        return dp[0][s.size() - 1]; 
    }
};