LEETCODE学习记录(动态规划+回溯+贪婪)

# 4.动态规划(Dynamic Programming)
## 4.1 买卖股票的最佳时机
(Best Time to Buy and Sell Stock)
### I 只能买卖一次:
 - `题目要求`
- 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
- 如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
- 注意：你不能在买入股票前卖出股票。
 - `测试样例`
```
- 输入: [7,1,5,3,6,4]
- 输出: 5
- 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
```
 - `参考代码`
```
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()==0) return 0;
        int profit = 0;
        int min_price = prices[0];
        for(int i = 1;i < prices.size();i++)
        {
            min_price = min(prices[i-1],min_price); //动态规划最低的价格
            profit = max(profit,prices[i] - min_price);
        }
        return profit;
    }
};
```
### II 不限制交易次数：
"有钱就赚",可以交易多次:
```
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        if(len == 0) return 0;
        int profit = 0;
        for(int i = 1;i<len;i++)
        {   //有钱就赚，最终就可以赚最多的钱
            if(prices[i-1] < prices[i])
            {
                profit+= prices[i] - prices[i-1];
            }
        }
        return profit;
    }
};
```
### III 只允许两笔交易:
```
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        if(len == 0) return 0;
        int *lp= new int[len],*minleft = new int[len];  //前i天的最大收益以及前i天的最低价
        int *rp = new int[len],*maxright = new int[len]; //后i天的最大收益 以及最高价
        memset(lp,0,sizeof(int)*len);
        memset(lp,0,sizeof(int)*len);
        minleft[0] = prices[0];
        maxright[len-1] = prices[len - 1];

for(int i = 1;i < len;i++)
        {
            if(prices[i] < minleft[i-1]) minleft[i] = prices[i];  //前i个值的最小值易主
            else minleft[i] = minleft[i-1];
            lp[i] = max(lp[i-1],prices[i]-minleft[i-1]);
        }
        for(int i = len-2;i>=0;i--)
        {
            //最大值易主
            maxright[i] = prices[i] > maxright[i+1]? prices[i]:maxright[i+1];
            rp[i] = max(rp[i+1],maxright[i+1] - prices[i]);
        }
        
        int max_pro = 0;
        for(int i = 0;i<len;i++)
        {
           max_pro = max(max_pro,lp[i] + rp[i]);
        }
        delete []lp;
        delete []rp;
        delete []minleft;
        delete []maxright;
        return max_pro;
    }
};
```
### IV 允许k笔交易:
```
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        /*当k>=数组长度一半时,直接任意交易数均可
        当k<数组长度一半时，
        */
        if(k<=0 || prices.size()<=1) return 0;
        int prof = 0;
        int len = prices.size();
       
        //贪心策略处理
        if(k >= len/2)
        {
            for(int i = 1;i<len;i++)
            {
                prof+=max(0,prices[i] - prices[i-1]);
            }
            return prof;
        }
        //基于状态机的三维动态规划处理,dp[i][j][0 0r 1]代表第i天，在最大允许j笔交易的情况下,不持有或者持有股票的最大收益
        vector<vector<vector<int>>> dp(len+1,vector<vector<int>>(k+1,vector<int>(2,0)));//必须在判断完k以后再定义dp,否则测试样例中k过大而报错
        for(int i = 0;i<len;i++)
        {
            for(int j =0;j<=k;j++)
            {
                /*写法一:买入时允许的最大交易笔数减少1,此时j从1开始,因为j = 0不允许买入，所以不计算dp[i][0][0],使用其默认值0*/
                //这一步很重要,第一天虽然没有正收益,但可以有负收益(纯买入则为负收益)
                if(i == 0){
                    dp[i][j][0] = 0;
                    dp[i][j][1] = -prices[i];
                    continue;
                }
                if(j>0)
                //今天不持有股票，则要么是昨天就不持有，要么昨天持有，今天卖出股票(卖出则允许的最大交易笔数减少1)
                dp[i][j][0] = max(dp[i-1][j][0],dp[i-1][j][1] + prices[i]);
                //今天持有股票，则要么是昨天就持有，要么是昨天没有股票，今天买入股票
                if(j>0)
                dp[i][j][1] = max(dp[i-1][j][1],dp[i-1][j-1][0] - prices[i]);

// /*写法二:卖出时才允许的最大交易笔数减少1，j从0开始，因为j=0时时是允许买入的，所以必须要计算dp[i][0][1],不计算的话值默认为0,是错误的*/   
                // if(i == 0){
                //     dp[i][j][0] = 0;
                //     dp[i][j][1] = -prices[i];
                //     continue;
                // }
                // if(j > 0) dp[i][j][0] = max(dp[i-1][j][0],dp[i-1][j-1][1] + prices[i]);//今天不持有股票，则要么是昨天就不持有，要么昨天持有，今天卖出股票(卖出则允许的最大交易笔数减少1)
                
                // //今天持有股票，则要么是昨天就持有，要么是昨天没有股票，今天买入股票
                // dp[i][j][1] = max(dp[i-1][j][1],dp[i-1][j][0] - prices[i]);
            }
        }
        return dp[len-1][k][0]; //最后一天不持有股票，显然利润更大
    }
};
```
### V 包含冷冻期
即卖出后,不能马上买入,必须过一天才能再买入:
```
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()<=1) return 0;
        int len = prices.size();
        int prof = 0;
        //dp[i][0] 第i天不持有股票的收益 dp[i][j]第i天持有股票的收益
        vector<vector<int>> dp(len+1,vector<int>(2,0));
        for(int i = 0;i<len;++i)
        {
            if(i==0)
            {
                dp[i][0] = 0;
                dp[i][1] = -prices[i];
                continue;
            }
            if(i==1)
            {
                dp[i][0] = max(dp[i-1][0],dp[i-1][1] + prices[i]);
                dp[i][1] = max(dp[i-1][1],-prices[i]);
                continue;
            }
            //有可能昨天就不持有,有可能昨天持有,今天卖了
            dp[i][0] = max(dp[i-1][0],dp[i-1][1] + prices[i]);
            //有可能昨天就已经持有,或者前天就没有,今天刚买的(注意卖出时有冷淡期)
            dp[i][1] = max(dp[i-1][1],dp[i-2][0] - prices[i]);
        }
        return dp[len-1][0];
    }
};
```
### VI 包含手续费:
每次交易需要支付手续费
```
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        /*贪心算法,速度快很多*/
        if(prices.size()<2) return 0;
        int len = prices.size();
        int profit(0);
        // vector<int> minp(len,prices[0]);
        int mini = prices[0];
        for(int i = 1;i<prices.size();++i)
        {
            if(prices[i] < mini)
            {
                mini = prices[i]; //mini已经是免受手续费的了,比mini更低,说明要重新开始了
            }
            else if(prices[i] > mini + fee) //prices[i]只比mini大一点点儿的情况是被忽略了的
            {
                profit+=prices[i] - fee - mini;
                mini = prices[i] - fee; //在此基础上,后面要是再进行交易,相当于是免收手续费的
            }
        }
        return profit;

/*动态规划,状态机通用解法,速度较慢*/
        // if(prices.size()<=1) return 0;
        // int profit = 0;
        // int length = prices.size();
        // vector<vector<int>> dp(length,vector<int>(2,0));
        // for(int i = 0;i<length;++i)
        // {
        //     if(i == 0)
        //     {
        //         dp[i][0] = 0;
        //         dp[i][1] = -prices[i] - fee; //我们在买入时收取手续费,卖出时免手续费
        //     }else
        //     {
        //         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);
        //     }
        // }
        // profit = dp[length-1][0];
        // return profit;

}
};
```
## 4.2 不同路径
### I(Unique Paths):
 -`题目要求`
- 一个机器人位于一个 m x n 网格的左上角。
- 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。
- 问总共有多少条不同的路径？
 -`测试样例`
```
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
```
 -`参考代码`
```

class Solution {
public:
    int uniquePaths(int m, int n) {
        if(m==0 || n==0) return 0;
        //申请内存dp，dp[i][j]表示从(0,0)到(m,n)位置的不同路径数目
        int** dp = new int*[m];
        for(int i=0;i<m;i++){
            dp[i] = new int[n];
            memset(dp[i],0,n*sizeof(int));
        }
        //迭代时计算递推表达式边界初始化
        for(int i = 0;i<m;i++)
        {
            for(int j = 0;j<n;j++)
            {
               if(i==0 || j==0){
                   dp[i][j] = 1;
               }else{
                   dp[i][j] = dp[i-1][j] + dp[i][j-1];
               }
            }
        }
        int res = dp[m-1][n-1];
        //释放内存
        for(int i=0;i<m;i++){
            delete []dp[i];
            dp[i] =NULL;
        }
        delete[] dp;
        dp = NULL;
        return res;
    }
};
```
### II 存在障碍物
与前面要求基本一样,但是网格中存在障碍物(障碍物用1表示,无障碍物则用0表示):
```
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        if(m==0) return 0;
        int n = obstacleGrid[0].size();
        //申请动态规划递推数组内存,使用int中间结果会溢出
        long **dp = new long*[m];
        for(int i=0;i<m;i++){
            dp[i] = new long[n];
            memset(dp[i],0,n*sizeof(long));
        }
        for(int i=0;i<m;i++){
           for(int j=0;j<n;j++)
           {
               //实际上相比于第一题,本题就主要是多了下面这一条约束而已
               if(obstacleGrid[i][j] == 1) dp[i][j] = 0;//存在障碍物的地点则不可达
               else if(i==0)
               {
                    if(j==0) dp[i][j] = 1;
                    else dp[i][j] = dp[i][j-1];
               }else if(i>0)
               {
                    if(j==0) dp[i][j] = dp[i-1][j];
                    else dp[i][j] = (dp[i-1][j]+dp[i][j-1]);
               }
           }
        }

int res = dp[m-1][n-1];
        for(int i=0;i<m;i++){
            delete [] dp[i];
            dp[i] = NULL;  //delete只是清除指针的值，并不删除指针
        }
        delete []dp;
        dp = NULL;
        return res;
    }
};
```
## 4.3 最大子序和(以及积)
 - `题目要求(53. Maximum Subarray)`
- 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 - `测试样例`
```
 输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
```
 - `参考代码`
```
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.empty()) return 0;
        int len = nums.size();
        int sum = nums[0];
        int temp = 0;
        for(int i = 0;i < len;++i)
        {   
            //大于0才对后面的计算有帮助,否则直接从当前开始
            if(temp > 0) temp+=nums[i];
            else temp = nums[i];
            
            sum = max(sum,temp);
        }
        return sum;
    }
};
```
 - `题目要求(152. Maximum Product Subarray)`
- 这道题是求数组中子区间的最大乘积,与前面类似,只不过要注意"负负得正",所以需要同时记录最大值最小值:
```
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int m = nums.size();
        if(m == 0) return 0;
        //maxdp[i]:0到i索引间的最大乘积（注意，一定包含i位置），mindp同理
        int *maxdp = new int[m],*mindp = new int[m];
        //dp[i]则表示0到i之间的最大乘积，不一定包含末尾索引
        int *dp = new int[m];
        int res = nums[0];
        for(int i=0;i<m;i++){
            if(i==0){
                maxdp[i] = nums[i];
                mindp[i] = nums[i];
                //dp[i] = nums[i];
            }else{
                maxdp[i] = max(nums[i],maxdp[i-1]*nums[i],mindp[i-1]*nums[i]);
                mindp[i] = min(nums[i],mindp[i-1]*nums[i],maxdp[i-1]*nums[i]);
                //dp[i] = dp[i-1]>maxdp[i]?dp[i-1]:maxdp[i];
                res = res > maxdp[i] ? res:maxdp[i];
            }
        }
        // res = dp[m-1];
        delete []maxdp;
        delete []mindp;
        delete []dp;
        return res;       
    }
private:
    int max(int a,int b,int c){
        int max_val = a > b? a:b;
        return max_val > c ? max_val:c;
    }
    int min(int a,int b,int c){
        int min_val = a<b?a:b;
        return min_val < c ?min_val:c;
    }

};
```
## 4.4 三角形最小路径和
  - `题目要求(120.Triangle)`
 - 给定一个三角形，找出自顶向下的最小路径和。
 - 每一步只能移动到下一行中相邻的结点上。
  - `测试样例`
```
例如，给定三角形：
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
```
 - `参考代码`
```
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        return func3(triangle);
    }
    //使用O(n^2)空间
    int func1(vector<vector<int>>& triangle){
                int n = triangle.size();
        if(n<1) return 0;
        int **dp = new int*[n];
        for(int i = 0;i<n;i++)
        {
            dp[i] = new int[n];
            //memset函数是以字节为操作单位的，通常只能操作char数组，操作其他数组，只能初始化为0
            memset(dp[i],0,n*sizeof(int));
            //for(int j = 0;j<n;j++) dp[i][j] = 0;
        }
        dp[0][0] = triangle[0][0];
        for(int i = 1;i<n;i++)
        {
            int m = triangle[i].size();
            for(int j=0;j<m;j++)
            {
                 if(j == 0){dp[i][j] = dp[i-1][j] + triangle[i][j];}
                 else if(j == m-1){dp[i][j] = dp[i-1][j-1] + triangle[i][j];}
                 else
                 {
                   dp[i][j] = triangle[i][j] + min(dp[i-1][j],dp[i-1][j-1]);
                 }
                cout <<dp[i][j]<<" ";
            }
            cout<<endl;
        }
        int res =dp[n-1][0];
        for(int i = 0;i<n;i++)
        {
            res = res < dp[n-1][i] ? res:dp[n-1][i];
        }
        for(int i = 0;i<n;i++){
            delete []dp[i];
            dp[i] = NULL;} 
        delete [] dp;
        return res;
    }
    
    //使用O(n)的空间,自顶向下
    int func2(vector<vector<int>> &triangle)
    {
        int n = triangle.size();
        if(n<1) return 0;
        //dp[i]滚动保存每一行的规划值
        int *dp = new int[n],*pdp = new int[n];
        //memset函数是以字节为操作单位的，通常只能操作char数组，操作其他数组，只能初始化为0
        memset(dp,0,n*sizeof(int));
        memset(pdp,0,n*sizeof(int));
        dp[0] = triangle[0][0];
        pdp[0] = dp[0];
        for(int i = 1;i<n;i++)
        {
            cout<<i<<":";
            int m = triangle[i].size();
            for(int j=0;j<m;j++)
            {
                 if(j == 0){
                     dp[j] = pdp[j] + triangle[i][j];
                 }
                 else if(j == m-1){
                     dp[j] = pdp[j-1] + triangle[i][j];
                 }
                 else
                 {
                   dp[j] = triangle[i][j] + min(pdp[j],pdp[j-1]);
                 }
            }
            for(int k =0;k<m;k++) pdp[k] = dp[k];
        }
        int res =dp[0];
        for(int i = 0;i<n;i++)
        {
            res = res < dp[i] ? res:dp[i];
        }
        delete [] dp;
        dp = NULL;
        return res;
    }

//O(n)版本进一步优化，为了避免计算时的覆盖问题，我们改变遍历的反向即可（从左到右，或者从下到上均可），这样不必再开辟pdp内存
    int func3(vector<vector<int>> & triangle)
    {
        int n = triangle.size();
        if(n<1) return 0;
        //dp[i]滚动保存每一行的规划值
        int *dp = new int[n];
        memset(dp,0,n*sizeof(int));
        //dp[0] = triangle[0][0];
        for(int i = 0;i<n;i++)
        {
            //cout<<i<<":";
            int m = triangle[i].size();
            for(int j=m-1;j>=0;j--)
            {
                 if(j == 0){
                     dp[j] = dp[j] + triangle[i][j];
                 }
                 else if(j == m-1){
                     dp[j] = dp[j-1] + triangle[i][j];
                 }
                 else
                 {
                   dp[j] = triangle[i][j] + min(dp[j],dp[j-1]);
                 }
                //cout <<dp[j]<<" ";
            }
            //cout<<endl;
        }
        int res =dp[0];
        for(int i = 0;i<n;i++)
        {
            res = res < dp[i] ? res:dp[i];
        }
        delete [] dp;
        dp = NULL;
        return res;
    }
};
```
## 4.5 不同的二叉搜索树
### `I (96. Unique Binary Search Trees I)`
- 给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
 - `举例`
```
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3
```
 - `参考代码`
实际上既可以递归,也可以动态规划:
```
class Solution {
public:
    int numTrees(int n) {
        if(n<=1) return 1;
        int *dp = new int[n+1];
        memset(dp,0,(n+1)*sizeof(int));
        for(int i = 0;i<n+1;i++)
        {
            if(i<=1) dp[i] = 1;
            else
            {
                for(int j = 1;j<=i;j++)
                {
                    dp[i] += dp[j-1] * dp[i-j];
                }
            }
        }
        int res = dp[n];
        delete []dp;
        dp = NULL;
        return res;
    }
};
```
### `II(95.Unique Binary Search Trees II)`
与前一题几乎一样,只是给定一个整数 n，需要生成所有由 1 ... n 为节点所组成的二叉搜索树。
```
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        vector<TreeNode*> retVec;
        if(n<1) return retVec;
        return genFunc(1,n);
    }
private:
    vector<TreeNode*> genFunc(int low,int high)
    {
        vector<TreeNode*> retVec;
        if(low > high){
            retVec.push_back(NULL);
            return retVec;
        }
        for(int i = low;i <= high;i++)
        {
            vector<TreeNode*> left_nodes = genFunc(low,i-1);
            vector<TreeNode*> right_nodes = genFunc(i+1,high);
            for(TreeNode *left_node:left_nodes){
                for(TreeNode *right_node:right_nodes)
                {
                    TreeNode *t = new TreeNode(i);
                    t->left = left_node;
                    t->right =right_node;
                    retVec.push_back(t);
                }
            }
        }
        return retVec;
    }
};
```
## 4.6 完全平方数
 - `题目要求(279.perfect squares)`
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于
n。你需要让组成和的完全平方数的个数最少。
 - `测试样例`
```
输入: n = 12
输出: 3 
解释: 12 = 4 + 4 + 4.
```
 - `参考代码`
```
class Solution {
public:
    int numSquares(int n) {
        if(n == 1) return 1;
        int *dp = new int[n+1];
        memset(dp,0,n*sizeof(int));
        //显然，dp[0]=0,dp[1] = 1;
        for(int i = 1;i<=n;i++)
        {
            dp[i] = i;
            int k = sqrt(i);
            if(k*k == i){
                dp[i] = 1;
                continue;
            }
            for(int j = k;j>0;j--)
            {    
                dp[i] = min(dp[i],dp[i-j*j]+1);
            }
        }
        int res = dp[n];
        delete []dp;
        dp = NULL;
        return res;
    }
};
```
## 4.7 零钱兑换
### I(322. Coin Change I)
- 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
- 说明:
你可以认为每种硬币的数量是无限的。
- `测试样例`
```
输入: coins = [1, 2, 5], amount = 11
输出: 3 
解释: 11 = 5 + 5 + 1
```
- `参考代码`
```
class Solution {
public:
    unordered_map<int,int> cache;
    int coinChange(vector<int>& coins, int amount) {
        return dynamic(coins,amount);
        //虽然是带备忘录,但是效率还是不高,但是不带备忘录的dfs,就会超时
        //return dfs(coins,amount);
    }
    //动态规划
    int dynamic(vector<int> &coins, int amount)
    {
        if(coins.empty() or amount <= 0) return 0;
        vector<int> dp(amount+1,-1);
        for(int i = 1;i<=amount;++i)
        {
            for(int coin:coins)
            {
                if(i > coin && dp[i-coin] != -1)
                {
                    if(dp[i] == -1) dp[i] = dp[i-coin]+1;
                    else dp[i] = min(dp[i],dp[i-coin]+1);
                }
                else if(i == coin) 
                     dp[i] = 1;
            }
        }
        return dp[amount];
    }

//带备忘录的dfs
    int dfs(vector<int> &coins,int amount)
    {
        if(coins.empty() or amount <= 0) return 0;
        if(cache.count(amount)!=0) return cache[amount];
        int res = -1;
        for(auto coin:coins)
        {
            if(amount == coin) return 1;
            else if(amount > coin)
            {
                int temp = 0;
                if(cache.find(amount-coin)!= cache.end()) temp = cache[amount-coin];
                else temp = dfs(coins,amount-coin);
                //此时说明不需要考虑该硬币,直接跳过
                if(temp == -1) continue;
                
                if(res == -1)  res = 1 + temp;
                else res = min(res,1 + temp);
            }
        }
        cache[amount] = res;
        return res;
    }

};
```
### II(518.Coin Change II)
- 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
- `测试样例`
```
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
```
- `参考代码`
```
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        if(amount == 0) return 1;
        if(coins.empty() || amount<0) return 0;
        vector<int> dp(amount+1,0);
        dp[0] = 1;
        for(int i = 0;i<coins.size();++i)
        {// 记录每添加一种面额的零钱，总金额为j时的零钱兑换方法数量变化
            for(int j = coins[i];j<=amount;++j) //该层循环在外则有序,在内则是组合,即(1,2)和(2,1)是一样的
            {
                //j肯定是大于coins[i]的,if条件是为了防止int溢出
                if(dp[j] < INT_MAX - dp[j - coins[i]]){
                    dp[j] += dp[j - coins[i]];
                }
                
            }
        }
        return dp[amount];
    }
};
//https://leetcode-cn.com/problems/coin-change-2/
```
## 4.8 剪绳子
### `剪绳子I`
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m] 。请问 k[0]*k[1]*...*k[m] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
```
示例 1：
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
```
```
class Solution {
public:
    int cuttingRope(int n) {
        /*写法一*/
        // if(n<=0) return -1;
        // vector<int> dp(n+1,1);
        // int res = 1;
        // //动态规划时, 长度小于n的绳子,可以选择不割
        // for(int i = 1;i<n;++i)
        // {
        //     for(int j = 0;j<i;++j)
        //     {
        //         dp[i] = max(dp[i],max(i,dp[j]*dp[i-j]));
        //     }
        // }
        // //最后求解n长度的绳子时, 则必须至少割一刀
        // for(int i = 1;i<n;++i)
        // {
        //     res = max(res,dp[i]*dp[n-i]);
        // }
        // return res;

/*写法二*/
        if(n<=0) return -1;
        if(n <=2) return 1;//只有在n比较小的时候乘积值才可能较大, 加了这两句判断, 则不需要最后的for循环
        if(n == 3) return 2;
        vector<int> dp(n+1,1);
        int res = 1;
        for(int i = 1;i<=n;++i)
        {
            for(int j = 0;j<i/2+1;++j)
            {
                dp[i] = max(dp[i],max(i,dp[j]*dp[i-j]));
            }
        }
        return dp[n];
    }
};
```
### `剪绳子II`
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m] 。请问 k[0]*k[1]*...*k[m] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
```
示例 1：
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
```
```
class Solution {
public:
    int cuttingRope(int n) {
        //写法一, 会溢出
        // if(n<=0) return 0;
        // if(n ==1 || n==2) return 1;
        // if(n == 3) return 2;
        // vector<int> dp(n+1,1);
        // dp[0] = 1;
        // dp[1] = 1;
        // dp[2] = 2;
        // dp[3] = 3;
        // for(int i = 4;i<=n;++i)
        // {
        //     for(int j = 0;j<i/2+1;++j)
        //     {
        //         dp[i] = max(dp[i],dp[j]*dp[i-j]);
        //     }
        // }
        // return dp[n] % 1000000007;

//写法二,数学上可以证明,应该拆成2和3的组合, 且尽可能多用3,但是n为4的时候,要拆成2*2
        if(n<=0) return 0;
        if(n ==1 || n==2) return 1;
        if(n == 3) return 2;

int mod = 1000000007;
        long res = 1;
        
        while (n > 4) {

res *= 3;
            res %= mod;
            n -= 3;
        }

return (int)(res * n % mod);
    }
};
```
## 4.9 正则表达式匹配
请实现一个函数用来匹配包含`.`和`*`的正则表达式。模式中的字符`.`表示任意一个字符,而`*`表示它前面的字符可以出现任意次（含0次）。在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串`aaa`与模式`a.a`和`ab*ac*a`匹配,但与`aa.a`和`ab*a`均不匹配。
```
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

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

示例 3:
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 4:
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5:
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
```
```
class Solution {
public:
    bool isMatch(string s, string p) {
        //return matchCore(s,p,0,0);
        return matchRegex(s,p);
    }
    //方法一: 递归, 该方法思路应该没问题,只是速度慢,超时了
    bool matchCore(string s,string p,int i, int j)
    {
        if(s.empty() && p.empty()) return true;
        //已经匹配到字符串末尾, 匹配成功
        if(i == s.size() && j == p.size())
            return true;
        //因为""和".*"是匹配的
        if(i!= s.size() && j==p.size())
            return false;
        //p中下一个位置是'*'
        if(p[j+1] == '*')
        {
            //当前位置匹配上
            if(p[j] == s[i] || (p[j] == '.'&& i<s.size()) )
            {
                //i位置存在重复的情况 || i位置不重复了,跳过当前位置i+1,j+2  || 忽略当前模式的位置j 
                return matchCore(s,p,i+1,j) || matchCore(s,p,i+1,j+2) || matchCore(s,p,i,j+2);
            }
            //当前位置没有匹配上, 但是因为其后有'*',所以可以忽略该位置,继续匹配
            else
            {
                return matchCore(s,p,i,j+2);
            }
        }
        //下一个位置不是'*'
        else
        {
            //当前位置已经匹配上,继续匹配下一个位置
            if(s[i] == p[j] ||( p[j] == '.' && i<s.size()))
                return matchCore(s,p,i+1,j+1);
        }
        return false;
    }

//方法二: 动态规划
    bool matchRegex(string s, string p)
    {
         if(s.empty() && p.empty()) return true;
         int l1 = s.size(),l2 = p.size();
         //dp[i][j]表示s中i位置之前,p中j位置之前的匹配情况,不包括i与j(这么设置是为了匹配空字符串)
         vector<vector<bool>> dp(l1+1,vector<bool>(l2+1,false));
         dp[0][0] = true;

for(int i = 0;i<=l1;++i)
            for(int j = 1;j<=l2;++j)
            {
                //边界条件,dp[0][i]表示空字符的匹配情况(即i==0),""可以匹配".*",但不能匹配"."
                if(i == 0)
                {
                    if(j-2>=0 && p[j-1] == '*' && dp[0][j-2])
                    {
                        dp[0][j] = true;
                    }
                }
                //这里才匹配的是非空字符串,因为i>=1
                else
                {
                    //直接匹配上
                    if(p[j-1] == s[i-1] || (p[j-1] == '.'))
                    {
                        dp[i][j] = dp[i-1][j-1];
                    }
                    //间接匹配上
                    if(p[j-1] == '*')
                    {   //*前面一个位置能匹配 
                        if((j-2>=0 && p[j-2] == s[i-1]) || (p[j-2] == '.'))
                        {   //对应5种情况(只是便于理解,虽然后两种重复)，比如Ba,BAa*,变为寻找(1)Ba,BAa (2)B,BAa* (3)Ba,BA (4)B,BA (5)B,BAa的匹配 
                            //dp[i][j] = dp[i][j-1] || dp[i-1][j] || dp[i][j-2] || dp[i-1][j-2] || dp[i-1][j-1];
                            dp[i][j] = dp[i][j-1] || dp[i-1][j] || dp[i][j-2]; //实际上只需要下面这样就够了
                        }
                        else if(j>=2)
                        {//不能匹配 如aba abab*,那么只能将*及*前面的b给抛弃
                            dp[i][j] = dp[i][j-2];
                        }
                    }
                }
            }
        return dp[l1][l2];
    }
};
```
## 4.10 除数博弈
```
爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。

最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：

选出任一 x，满足 0 < x < N 且 N % x == 0 。
用 N - x 替换黑板上的数字 N 。
如果玩家无法执行这些操作，就会输掉游戏。

只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 false。假设两个玩家都以最佳状态参与游戏。
```
```
示例 1：
输入：2
输出：true
解释：爱丽丝选择 1，鲍勃无法进行操作。

示例 2：
输入：3
输出：false
解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。
```
```
class Solution {
public:
    bool divisorGame(int N) {
        if(N <= 1 || N == 3 ) return false;
        if(N == 2 ) return true;

//递归, 但是超时
        // bool winnerIsAlice = false;
        // for(int i = 1;i<N;++i)
        // {
        //     if(N%i==0)
        //     {
        //         winnerIsAlice |= !divisorGame(N - i);
        //     }
        // }
        // return winnerIsAlice;

//动态规划
        vector<bool> dp(N+1,false);
        for(int i = 2;i<=N;++i)
        {
            for(int j = 1;j<(i>>1);++j)
            {
                if(i%j==0)
                {
                    dp[i] = dp[i] || (!dp[i-j]);
                    if(dp[i]) break;
                }
            }
        }
        return dp[N];

//偶数必胜
        //return !(N&0x01);
    }
};
```
## 4.11 最长回文子串
```
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"
```
```
//解法一：扩张法
class Solution {
public:
    //向两边扩张
	int expandAroundCenter(string s, int left, int right)
	{
		int L = left, R = right;
		int ret_len = 0;
		while (L >= 0 && R < s.length() && s[L] == s[R]) {
			ret_len = R - L + 1;
			L--;
			R++;
		}
		return ret_len;
	}
	string longestPalindrome(string s) {
		if (s.length() < 1) return "";
		int max_len=0;
		int start = 0, end = 0;
        //类似于滑动窗口法
		for (int i = 0; i < s.length(); i++) {
			int len1= expandAroundCenter(s, i, i);
			if (len1 > max_len)
			{
				max_len = len1;
				start = i - (max_len - 1) / 2;
			}
		}
		for (int i = 0; i < s.length(); i++) {
			int len2 = expandAroundCenter(s, i, i + 1);
			if (len2 > max_len) {
	            //更新end和start
				max_len = len2;
				start = i - (max_len-2) / 2;
			}
		}
		return s.substr(start, max_len);
	}
};
```

```
//解法二:动态规划
class Solution {
public:
    string longestPalindrome(string s) {
        //考虑动态规划,dp[i][j]表示从i位置到j位置[i,j]是否是回文
        int len = s.size();
        vector<vector<int>> dp(len,vector<int>(len,0));
        //初始化边界
        for(int i = 0;i<len;++i)
        {
            dp[i][i] = 1;
        }
        int max_len = 0;
        int left= 0,right=0;
        for(int i = len-1;i>=0;--i)
        {
            for(int j = i;j<len;++j)
            {
                if(s[i] == s[j] && ((i == j) || (i == j-1) || dp[i+1][j-1] == 1))
                {
                    dp[i][j] = 1;
                    //更新最长回文子串
                    if(max_len < j - i + 1)
                    {
                        max_len = j - i + 1;
                        left = i;
                        right = j;
                    }
                }
            }
        }
        return s.substr(left,max_len);
    }
};
```
## 4.12 最长回文子序列
```
给定一个字符串s，找到其中最长的回文子序列，并返回该序列的长度。可以假设s的最大长度为1000。

示例 1:
输入:
"bbbab"
输出:
4
一个可能的最长回文子序列为 "bbbb"。

示例 2:
输入:
"cbbd"
输出:
2
一个可能的最长回文子序列为 "bb"。
```
```
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        //dp[i][j] 表示[i,j]位置的最长回文子序列的长度
        int len = s.size();
        vector<vector<int>> dp(len,vector<int>(len,0));
        //初始化
        for(int i = 0;i<len;++i)
        {
            dp[i][i] = 1;
        }
        //注意因为推断dp[i][j]需要依赖更大的i,更小的j,因此i要从大到小,j要从小到大
        for(int i = len-1;i>=0;--i)
        {
            for(int j = i+1;j<len;++j)
            {
                if(s[i] == s[j])
                {
                    dp[i][j] = 2 + dp[i+1][j-1];
                }
                else
                {
                    //这里容易错写成dp[i][j] =dp[i+][j-1];这是不对的
                    dp[i][j] = max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][len-1];
    }
};
```

## 4.13 最长不含重复字符的子字符串
```
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

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

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

示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
```
```
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        return func3(s);
    }
    //方法一: 动态规划
    int func1(string s)
    {
        if(s.empty()) return 0;
        int length = s.size();
        vector<int> dp(length,0);  //dp[i]表示以第i个字符结尾的最长无重复子串的长度
        unordered_map<char,int> position; //每个字母上一次出现的位置,不存在则说明从未出现过

int res = 1;
        dp[0] = 1;
        position[s[0]] = 0;
        for(int i = 1;i<length;++i)
        {
            //第i个字符从未出现
            if(position.find(s[i])==position.end())
            {
                dp[i] = dp[i-1] + 1;
            }
            //第i个字符已经出现过
            else
            {
                //出现位置在子串起始点之前, 则不受影响,该子串长度继续增加
                if(position[s[i]] < i - dp[i-1]) dp[i] = dp[i-1] + 1;
                //出现在了子串中间, 则子串起始点改变,从首次出现的位置之后再开始计算
                else dp[i] = i - position[s[i]];
            }       
            res = max(dp[i],res);
            position[s[i]] = i;
        }
        return res;
    }
    //方法二:滑动窗口法,维护一个始终不重复的字符串窗口,C++使用deque双端队列或者set都可以(queue不可以,因为没有迭代器,不能find)
    //可以比较方便的模拟滑动窗口
    int func2(string s)
    {
        if(s.empty()) return 0;
        deque<char> windoww;
        int res = 0;
        for(auto ch:s)
        {   
            //先检查窗口中是否存在与当前ch重复的字符,存在则去除掉重复
            while(std::find(windoww.begin(),windoww.end(),ch)!=windoww.end())
                 windoww.pop_front();
            windoww.push_back(ch);
            //res = res > window.size() ? res:window.size();
            res = std::max(res,(int)windoww.size()); //VS把min和max这两个标识符定义成了宏,必须int强转才行
        }
        return res;
    }
    //方法三: 滑动窗口,使用set容器
    int func3(string s) 
    {
        set<char>t;
        int left = 0, right = 0;
        int sum = 0;
        while(right < s.size()) //右指针移动
        {
            if(t.find(s[right]) == t.end())
            {
                t.insert(s[right++]);
                sum = max(sum,(int)t.size());
            }
            else
            {   //左指针移动
                while(left < right && t.find(s[right])!=t.end())
                {
                    t.erase(s[left++]);
                }
            }
        }
        return sum;
    }
};
```
## 4.14 最长公共(连续)子序列
- 注意,连续和不要求连续是有差别的:
```
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。

示例 1:
输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace"，它的长度为 3。最长公共连续子序列为"a",或者"c",或者"e"

示例 2:
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。最长公共连续子序列为也为"abc"

示例 3:
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0。
```
整体平移一个单位的写法:
```
class Solution {
public:
    int longestCommonSubsequence(string &text1, string &text2) {
        return substr1(text1,text2);
    }
private:
    //求最长公共子序列的长度
    int substr1(string &text1,string &text2)
    {
        int len1 = text1.length();
        int len2 = text2.length();
        vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));
        //这样会有繁琐的边界判断
        // for(int i = 0;i<len1;++i)
        // {
        //     for(int j = 0;j<len2;++j)
        //     {
        //         if(text1[i] == text2[j])
        //         {
        //             if(i==0)
        //             { 
        //                 dp[i][j] = 1;
        //             }
        //             else
        //             {
        //                 if(j>0) dp[i][j] = dp[i-1][j-1] + 1;
        //                 else dp[i][j] = 1;
        //             }
        //         }
        //         else
        //         {
        //             if(i == 0)
        //             {
        //                  if(j==0)  dp[i][j] = 0;
        //                  else dp[i][j] = dp[i][j-1];
        //             }
        //             else
        //             {
        //                 if(j==0) dp[i][j] = dp[i-1][j];
        //                 else dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
        //             }
        //         }
        //     }
        // }
        //return dp[len1-1][len2-1];
        
        //整体平移一个单位,避免边界判断,dp[i][j] 表示text1的前i-1个字符与text2的前j-1个字符匹配情况
        for(int i = 0;i<len1;++i)
        {
            for(int j = 0;j<len2;++j)
            {
                if(text1[i]==text2[j])
                {
                    dp[i+1][j+1] = dp[i][j] + 1;
                }
                else dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j]);
            }
        }
        return dp[len1][len2];
    }
    //拓展:如果是让求两个字符串的最长公共连续子序列(或者叫最长公共子串),这里要求是连续的
    int substr2(string &text1,string &text2)
    {
        int len1 = text1.size();
        int len2 = text2.length();
        int maxLength = 0;
        int maxEnd = 0;
        string resStr;
        //dp[i][j] 表示以text1的第i-1个字符结尾的子串与text2的第j-1个字符结尾的子串匹配情况
        vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));
        for(int i = 0;i<len1;++i)
        {
            for(int j = 0;j<len2;++j)
            {
                //相同才更新,不同则相当于为0
                if(text1[i] == text2[j])
                {
                    dp[i+1][j+1] = dp[i][j] + 1;
                    if(dp[i+1][j+1] > maxLength)
                    {
                        maxLength = dp[i+1][j+1];
                        //记录结果
                        maxEnd = i;
                    }
                }
            }
        }
        resStr = text1.substr(maxEnd - maxLength + 1,maxLength);
        //cout<<resStr<<endl; //resStr即为最终的子串
        return maxLength;
    }
};

```

最长公共子串(即最长公共连续子序列)不整体平移的写法:
```
#include <iostream>
#include <string>
#include<vector>
using namespace std;

string getLCS(string &str1, string &str2) {
	vector<vector<int> > record(str1.length(), vector<int>(str2.length()));
	int maxLen = 0, maxEnd = 0;
	for (int i = 0; i<str1.length(); ++i)
		for (int j = 0; j < str2.length(); ++j) {
			if (str1[i] == str2[j]) {
				if (i == 0 || j == 0) {
					record[i][j] = 1;
				}
				else {
					record[i][j] = record[i - 1][j - 1] + 1;
				}
			}
			else {
				record[i][j] = 0;
			}
			if (record[i][j] > maxLen) {
				maxLen = record[i][j];
				maxEnd = i; //记录i,便于最后获取LCS时取str1的子串
			}
		}
	//如果是求长度,则直接返回maxLen即可
	return str1.substr(maxEnd - maxLen + 1, maxLen);
}

int main()
{
	string str1 = "abcdefg";
	string str2 = "gabcdef";
	cout << substr2(str1, str2) << endl;
	system("pause");
	return 0;
}
//可参考https://blog.csdn.net/qq_25800311/article/details/81607168
```

## 4.15 编辑距离
```
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

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

插入一个字符
删除一个字符
替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
```
```
class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.size();
        int len2 = word2.size();
        //dp[i][j]表示word1的前[0,i)位置的字符和word2的[0,j)位置的字符的编辑距离
        vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));
        for(int i = 0;i<=len1;++i)
        {
            dp[i][0] = i;
        }
        for(int j = 0;j<=len2;++j)
        {
            dp[0][j] = j;
        }
        for(int i = 1;i<=len1;++i)
        {
            for(int j = 1;j<=len2;++j)
            {
                int t = min(dp[i-1][j] + 1,dp[i][j-1] + 1);
                if(word1[i-1] != word2[j-1])
                {
                    dp[i][j] = min(t,dp[i-1][j-1] + 1);
                }
                else
                {
                    dp[i][j] = min(t,dp[i-1][j-1]);
                }
            }
        }
        return dp[len1][len2];
    }
};
```
## 4.16 最长有效括号
```
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
https://leetcode-cn.com/problems/longest-valid-parentheses
```
```
class Solution {
public:
    int longestValidParentheses(string s) {
        if(s.empty()) return 0;
        int res = 0;
        //用于找具体的子串
        //string str;
        //int start = 0;

vector<int> dp(s.size()+1,0); //dp[i]代表以s中第i个字符结束的最长有效括号的长度
        for(int i = 1;i<s.size();i++)
        {
            //只有以')'结尾的才可能大于0
            if(s[i] == ')')
            {
                //前一个位置是有效括号的末尾
                if(dp[i-1]>0)
                {
                    //因为前一个位置末尾是“有效的”，接上,比如(())
                    if(i - 1 - dp[i-1] >= 0 && s[i - 1 - dp[i-1]] == '(')
                    {
                        dp[i] = 2 + dp[i-1];
                    }
                    //接上了之后"(())"前面可能还有一段,比如()(())
                    if(i-dp[i] > 0 && dp[i - dp[i]] > 0)
                    {
                        dp[i] += dp[i - dp[i]];
                    }
                }
                //前一个位置不是有效括号的结尾
                else
                {
                    if(s[i-1] == '(')
                    {
                        dp[i] = 2;
                        //“()”前面还可能有一段
                        if(i-2 >= 0 && dp[i-2]>0) dp[i] += dp[i-2];
                    }
                }
            }
            //记录dp[i]的最大值
            if(dp[i] > res)
            {
                res = dp[i];
                //找具体的子串
                //start = i - dp[i] + 1;
                //str = s.substr(start,dp[i]);
            }
        }
        //cout<<str;
        return res;
    }
};
```
## 4.17 最大正方形
```
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

示例:

输入:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

输出: 4

链接：https://leetcode-cn.com/problems/maximal-square
```
```
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if(matrix.empty()) return 0;
        int max_area = 0;// matrix[0][0] - '0';
        /**dp[i][j]表示以坐标i，j位置的点为正方形左下角度顶点的，最大正方形的边长
        递推式为：dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]);
        **/
        vector<vector<int>> dp(matrix.size(),vector<int>(matrix[0].size(),0));
        for(int i  = 0;i<matrix.size();i++)
        {
            for(int j = 0;j<matrix[i].size();j++)
            {
                //为0的地方dp[i][j] = 0;
                if(matrix[i][j] == '1')
                {
                    if(i == 0)
                    {
                        dp[i][j] = 1;
                    }
                    else
                    {
                        if(j == 0)
                        {
                            dp[i][j] = 1;
                            
                        }
                        else
                        {
                            dp[i][j] = 1 + min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]);
                        }
                    }
                    //记录最大值
                    max_area = max(max_area,dp[i][j]*dp[i][j]);
                }
            }
        }
        return max_area;
    }
};
```
## 4.18 每日温度
```
请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

链接：https://leetcode-cn.com/problems/daily-temperatures
```
```
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        /**
 * 根据题意，从最后一天推到第一天，这样会简单很多。因为最后一天显然不会再有升高的可能，结果直接为0。
 * 再看倒数第二天的温度，如果比倒数第一天低，那么答案显然为1，如果比倒数第一天高，又因为倒数第一天
 * 对应的结果为0，即表示之后不会再升高，所以倒数第二天的结果也应该为0。
 * 自此我们容易观察出规律，要求出第i天对应的结果，只需要知道第i+1天对应的结果就可以：
 * - 若T[i] < T[i+1]，那么res[i]=1；
 * - 若T[i] > T[i+1]
 *   - res[i+1]=0，那么res[i]=0;
 *   - res[i+1]!=0，那就比较T[i]和T[i+1+res[i+1]]（即将第i天的温度与比第i+1天大的那天的温度进行比较）
 */
    vector<int> res(T.size(),0);
    res[T.size() - 1] = 0;
    for (int i = T.size() - 2; i >= 0; i--) {
        for (int j = i + 1; j < T.size(); j += res[j]) {
            if (T[i] < T[j]) {
                res[i] = j - i;
                break;
            } else if (res[j] == 0) {
                res[i] = 0;
                break;
            }
        }
    }
    return res;
    }
};
```
## 4.19 分割等和子集
```
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200

示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.

https://leetcode-cn.com/problems/partition-equal-subset-sum
```
```
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        if(nums.empty()) return false;
        //状态定义：dp[i][j]表示从数组的 [0, i] 这个子区间内挑选一些正整数，每个数只能用一次，使得这些数的和恰好等于j。
        int sum = 0;
        for(int t:nums)
        {
            sum+=t;
        }
        //总和为奇数肯定为false
        if((sum&1) == 1) return false;
        //这里就只需要找是否能组合成target就行了
        int target = sum/2;
        vector<vector<bool>> dp(nums.size(),vector<bool>(target + 1,false));
        dp[0][0] = true;
        for(int i = 1;i < nums.size();++i)
        {
            for(int j = 0;j <= target;++j)
            {
                if(nums[i] <= j)
                {  
                    //前i-1个元素之和可以凑成j或者可以凑成j-nums[i]
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }
                else
                {
                    dp[i][j] = dp[i-1][j];
                }
            }
            if(dp[i][target]) return true;
        }
        return dp[nums.size()-1][target];
    }
};
```
# 5.回溯法(Backtracking)
## 5.1 组合
 - `题目要求(77.combination)`
- 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
 - `测试样例`
```
输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
```
 - `参考代码`
```
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ret;
        vector<int> curr;
        backtrack(ret,curr,n,k,1);
        return ret;
    }
    //DFS+回溯，类似于二叉树求最大路径和
     void backtrack(vector<vector<int>> &ret,vector<int> &curr,int &end,int &k,int start)
    {
         if(curr.size() == k)
         {
             ret.push_back(curr);
             return;
         }

for(int i = start;i<=end;i++)
         {
             curr.push_back(i);
             backtrack(ret,curr,end,k,i+1);
             curr.pop_back();
         }
    }
};
//https://leetcode-cn.com/problems/combinations/
```
## 5.2 组合总和
### `I(39. Combination Sum)`
- 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

- candidates 中的数字可以无限制重复被选取。

- 说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。

- `测试样例`
```
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]
```
 - `参考代码`
```
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
         vector<vector<int>> ret;
         vector<int> curr;
         backTrack(ret,curr,candidates,0,target);
         return ret;
    }
    void backTrack(vector<vector<int>> &ret,vector<int> &curr,vector<int> candidates,int start,int target)
    {
        if(target == 0) //保存结果
        {
            ret.push_back(curr);
            return;
        }else if(target < 0){ //剪枝
            return;
        }
        //深搜+回溯，start表示起始位置，用于去重，保证每次都是“前面的选择后面的，则不会有重复的”
        for(int i =start; i<candidates.size();i++)
        {
            int cand = candidates[i];
            curr.push_back(cand);
            backTrack(ret,curr,candidates,i,target - cand);
            curr.pop_back();
        }
    }
};
```
### `II(40. Combination Sum II)`
- 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

- candidates 中的每个数字在每个组合中只能使用一次。
- 说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。

- `测试样例`
```
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]
```
- `参考代码`
```
class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        vector<int> curr;
        //默认升序排序
        sort(candidates.begin(),candidates.end());
        backTrack(ans,curr,candidates,0,target);
        return ans;
    }

void backTrack(vector<vector<int>> &retans,vector<int> &tpath,vector<int>& candidates,int start,int target)
    {
        if(target == 0)
        {
            retans.push_back(tpath);
            return;
        }else if(target < 0) return;
         //“前面的选择后面的”
         for(int i = start;i<candidates.size();i++)
         {
             tpath.push_back(candidates[i]);
             backTrack(retans,tpath,candidates,i+1,target-candidates[i]);
             tpath.pop_back();
             //去重
             while(i<candidates.size()-1 && candidates[i] == candidates[i+1]) i++;
         }
    }
};
```
### `III(216. Combination Sum III)`
- 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
- 说明：
所有数字都是正整数。
解集不能包含重复的组合。 
- `测试样例`
```
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
```
- `参考代码`
```
class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ans;
        vector<int> curr;
        backTrack(ans,curr,1,k,n);
        return ans;
    }

void backTrack(vector<vector<int>> &ans,vector<int> &curr,int start,int k,int target)
    {
         if(k == 0 && target==0)
         {
             ans.push_back(curr);
             return;
         }else if(k<0 || target<0) return;
         //else if(start>9) return; //不需要
          
          for(int i = start;i<=9;i++)
          {
              curr.push_back(i);
              backTrack(ans,curr,i+1,k-1,target-i);
              curr.pop_back();
          }
    }
};
```
### IV(377. Combination Sum IV)
给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。本题与动态规划中的`零钱兑换`有一定的相似性.

实际上本题,应该属于动态规划的题目.从这里我们可以看出,回溯法一般适用于需要返回`具体组合`的问题,而动态规划则更擅长返回`数字结果`的题目.
- `测试样例`
```
nums = [1, 2, 3]
target = 4

所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

请注意，顺序不同的序列被视作不同的组合。

因此输出为 7。
```
- `参考代码`
```
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        // vector<int> curr;
        // int ans = 0;
        // backTracking(nums,curr,ans,target);
        // return ans;

//return dynamic(nums,target);

unordered_map<int,int> cache;
        return dfs(nums,cache,target);
    }
    
    //当target较小时,回溯法效率还行,target较大时就一定超时,内存也会爆掉
    void backTracking(vector<int> &nums,vector<int> &curr,int &ans,int target)
    {
        if(target == 0)
        {
            ans++;
            return;
        }else if(target < 0) return;

for(auto n:nums)
        {
            curr.push_back(n);
            backTracking(nums,curr,ans,target - n);
            curr.pop_back();
        }
    }

//自底向上动态规划
    int dynamic(vector<int> &nums, int target)
    {
        if(nums.size() == 0 || target < 0) return 0;
        int len = nums.size();
        //vector<unsigned long long> dp(target+1,0); //可避免溢出
        vector<int> dp(target+1,0); //
        dp[0] = 1;
        for(int i = 1;i<=target;++i)
        {
            for(auto num:nums)
            {   //分类思想,dp[i]的数量由可按照最后一个数字的不同而分类
                if(i>=num)
                {
                    //因为返回值为int,超范围的dp[i]都不是递推最终dp[target]需要使用的值
                    //使用减法判断溢出,当然也可以//if(i>=num) dp[i]+=dp[i-num]%INT_MAX;,但此时就不能用int的vector了
                    if(dp[i] > INT_MAX - dp[i-num]){
                        dp[i-num] = 0; 
                        break;
                    }
                    dp[i]+= dp[i-num];
                }
            }
        }
        return dp[target];
    }

//自顶向下的备忘录算法
    int dfs(vector<int> &nums,unordered_map<int,int> &cache,int target)
    {
        if(nums.empty() || target < 0) return 0;
        if(target == 0) return 1;
        //在这里调用缓存也可以,还更简单 if(cache.count(target)!=0) return cache[target];
        int res = 0;
        for(auto num:nums)
        {
            if(num <= target)
            {
                if(cache.find(target - num)!= cache.end())
                  res+= cache[target - num];
                else res+=dfs(nums,cache,target - num);
            }
        }
        cache.insert(make_pair(target,res));
        return res;
    }
};
```
## 5.3 电话号码的字母组合
 - `17. Letter Combinations of a Phone Number`
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

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

- 尽管测试样例中的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
 - `测试样例`
```
 输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
```
 - `参考代码`
```
class Solution {
public:
    vector<string> letterCombinations(string digits) {
          map<char,string> phone = phoneNumber();
          vector<string> retstr;
          string curr;
          backTrack(phone,retstr,curr,digits,0);
          return retstr;
    }
    void backTrack(map<char,string>&phone,vector<string> &retstr,string &temp,string digits,int num)
    {
            if(digits.size() && num == digits.size()) //这里需要判断一下如果digits为空，则不要push一个“”进去，这不符合题意
            {
                retstr.push_back(temp);
                return;
            }
            //回溯的关键关键点在于，前一个回溯函数，要向后一个回溯函数传递可取值的范围
            string phone_number = phone[digits[num]];
            for(int j = 0;j<phone_number.size();++j)
            {
                temp.push_back(phone_number[j]);
                backTrack(phone,retstr,temp,digits,num+1);
                temp.pop_back();
            }
    }
private:
   map<char,string> phoneNumber()
   {
     map<char, string> direct;
     direct.insert( pair<char, string>('2', "abc" ));
     direct.insert( pair<char, string>('3', "def" ));
     direct.insert( make_pair('4', "ghi" ));
     direct.insert( make_pair('5', "jkl" ));
     direct.insert( make_pair('6', "mno" ));
     direct.insert( make_pair('7', "pqrs" ));
     direct.insert( make_pair('8', "tuv" ));
     //direct.insert( make_pair('9', "wxyz" ));
     direct['9'] = "wxyz";

//  typedef map<char, string>::iterator MyIterator;
    //  MyIterator it = direct.begin();
    //  while(it!=direct.end())
    // {
    //     cout<<it->first<<": "<<it->second<<endl;
    //     ++it;
    // }
     return direct;
   }

};
```
## 5.4 子集
### `78.subsets I`
- 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
- 说明：解集不能包含重复的子集。
- `测试样例`
```
输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]
```
 - `参考代码`
```
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ret;
        vector<int> temp;
        //sort(nums.begin(),nums.end());
        backTrack(ret,nums,temp,0);
        return ret;
    }
    void backTrack(vector<vector<int>> &ret,vector<int> &nums,vector<int> &temp,int start)
    {   
        //所有结果均保存
        ret.push_back(temp);
        //继续回溯
        for(int i = start;i<nums.size();i++)
        {
            temp.push_back(nums[i]);
            backTrack(ret,nums,temp,i+1);
            temp.pop_back();
        }
    }
};
```
### `90.subsets II`
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
 - `测试样例`
```
输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]
```
 - `参考代码`
```
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> ret;
        vector<int> temp;
        sort(nums.begin(),nums.end());
        backTrack(ret,nums,temp,0);
        return ret;
    }

void backTrack(vector<vector<int>> &ret,vector<int> &nums,vector<int> &temp,int start)
    {   
        //所有结果均保存
        ret.push_back(temp);
        //继续回溯
        for(int i = start;i<nums.size();i++)
        {
            temp.push_back(nums[i]);
            backTrack(ret,nums,temp,i+1);
            temp.pop_back();
            //这可以理解为,同一层次的元素去重,不同层次的可以重
            while(i < nums.size()-1 && nums[i] == nums[i+1]) i++;
        }
    }
};
```
## 5.5 全排列
### `46. Permutations I`
- 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
- `参考例子`
```
输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]
```
- `参考代码`
```
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ret;
        vector<int> temp;
        vector<int> visited(nums.size(),0);
        backTracking(ret,nums,temp);//,visited);
        return ret;
    }
    //方法一：用时间换空间
    void backTracking(vector<vector<int>> &ret,vector<int>&nums,vector<int>&temp)
    {
        if(temp.size() == nums.size())
        {
            ret.push_back(temp);
            return;
        }

for(int i = 0;i<nums.size();i++)
        {
            //如果nums[i]不在temp中
            if(!isVisited(temp,nums[i])) 
            {
                temp.push_back(nums[i]);
                backTracking(ret,nums,temp);
                temp.pop_back();
            }
        }   
    }

bool isVisited(vector<int> &nums,int cur)
    {
        for(int i = 0;i<nums.size();i++)
        {
            if(nums[i] == cur) return true;
        }
        return false;
    }
    
    //方法二：用空间换时间
    void backTracking2(vector<vector<int>> &ret,vector<int>&nums,vector<int>&temp,vector<int> &visited)
    {
        if(temp.size() == nums.size())
        {
            ret.push_back(temp);
            return;
        }

for(int i = 0;i<nums.size();i++)
        {
            //未访问，即nums[i]不在temp中
            if(visited[i] == 0) 
            {
                temp.push_back(nums[i]);
                visited[i] = 1;
                backTracking(ret,nums,temp);
                temp.pop_back();
                visited[i] = 0;
            }
        }   
    }

};
```
### `47. Permutations II`
给定一个可包含重复数字的序列，返回所有不重复的全排列。与子集问题类似,这道题实际上就是需要去重而已,要注意题目给的数据是否`已经排序`,如果没有,需要自己排下序.
- `测试样例`
```
输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]
```
- `参考代码`
```
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
           vector<vector<int>> ret;
           vector<int> temp;
           vector<int> visited(nums.size(),0);
           sort(nums.begin(),nums.end());
           backTracking(ret,nums,temp,visited);
           return ret;
    }

void backTracking(vector<vector<int>> &ret,vector<int> &nums,vector<int> &temp,vector<int> &visited)
    {
         if(temp.size() == nums.size())
         {
             ret.push_back(temp);
             return;
         }

for(int i = 0;i < nums.size();i++)
         {
             if(visited[i] == 0)
             {
                 temp.push_back(nums[i]);
                 visited[i] = 1; //表示已经访问,即temp中已经存在nums[i]
                 backTracking(ret,nums,temp,visited);
                 temp.pop_back();
                 visited[i] = 0;
                 //同一层的要去重,不同层次的可以重复
                 while(i < nums.size()-1 && nums[i] == nums[i+1]) ++i;
             }
         }
    }
};
```
## 5.6 N皇后
### N皇后I
```
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

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

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
```
```
输入: 4
输出: [
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。
```
```
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> queensPermutation;
        vector<string> queens(n,string(n,'.'));
        dfs(queensPermutation,queens,0);
        return queensPermutation;
    }
private:
    //判断第x行,第y列能否放皇后
    bool checkQueens(vector<string> &queens,int x,int y)
    {
        //如果是只需要求解N皇后问题有几种解法, 则可以用只用数组记录已有皇后的位置
        //如果用queen[j]表示第j行的皇后的列数, 则相应的判断方式类似于 i - j = queen[i] - queens[j]; 
        for(int i = 0;i < x; ++i)
        {
            //检查纵向
            if(queens[i][y]=='Q') 
                return false;
            //检查左侧斜向
            if(y - i - 1 >= 0 && queens[x - i - 1][y - i - 1] == 'Q')
                return false;
            //检查右侧斜向
            if(y + i + 1 < queens[0].size() &&queens[x - i - 1][y + i + 1] == 'Q')
                return false;
        }
        return true;
    }
    void dfs(vector<vector<string>> &queensPermutation,vector<string> &queens,int x)
    {
        for(int i = 0;i<queens.size();++i)
        {
            //第x行,第i列可以放皇后
            if(checkQueens(queens,x,i))
            {
                queens[x][i] = 'Q';
                //最下面一行,保存一下结果
                if(x == queens.size()-1)
                {
                    queensPermutation.push_back(queens);
                }
                else
                {
                    dfs(queensPermutation,queens,x+1);
                }
                //回溯
                queens[x][i] = '.';
            }
        }
    }
};
```
### N皇后II
如果只需要`求N皇后问题一共有多少种解法`,而不必求出每种解法的具体排列,则可以使用两个数组rows和cols来分别记录当前已经存在的皇后的位置,而不是直接使用一个n*n的矩阵来记录, 降低了空间复杂度. 代码如下:
```
class Solution {
public:
    int totalNQueens(int n) {
        if(n <= 0) return 0;
        vector<int> rows,cols;
        int totalCnt = 0;
        dfs(rows,cols,totalCnt,n,0);
        return totalCnt;
    }
private:
    bool checkQueens(vector<int> &rows,vector<int> &cols,int x, int y)
    {
        for(int i = 0;i<rows.size();++i)
        {
            //判断纵向,横向(实际上对于dfs,可以不检查横向))
            if(y == cols[i])// || x == rows[i])
                return false;
            //判断斜方向
            if(x - y == rows[i]-cols[i] || x + y == cols[i] + rows[i])
                return false;
        }
        return true;
    }
    void dfs(vector<int> &rows,vector<int> &cols,int &totalCnt,int n,int x)
    {
        for(int i = 0;i<n;++i)
        {
            if(checkQueens(rows,cols,x,i))
            {
                rows.push_back(x);
                cols.push_back(i);
                if(x == n - 1)
                {
                    ++totalCnt;
                }
                else
                {
                    dfs(rows,cols,totalCnt,n,x+1);
                }
                rows.pop_back();
                cols.pop_back();
            }
        }
        
    }
};
```
## 5.7 生成括号

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

示例：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
```

```
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        if(n<1) return vector<string>();
        vector<string> res;
        string curStr;
        dfs(res,curStr,0,0,n);
        return res;
    }
    void dfs(vector<string> &res,string curStr,int left,int right,int n)
    {
        //已经存在n对括号了，保存结果
        if(left == n && right == n)
        {
            res.push_back(curStr);
            return;
        }
        //左括号小于n个，则还可以再增加左括号
        if(left < n)
        {
            dfs(res,curStr+'(',left+1,right,n);
        }
        //左括号比右括号多，则可以增加右括号
        if(left>right)
        {
            dfs(res,curStr+')',left,right+1,n);
        }
    }
};
```
## 5.8 搜索单词
```
给定一个二维网格和一个单词，找出该单词是否存在于网格中。

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

示例:
board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false

提示：
board 和 word 中只包含大写和小写英文字母。
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3

链接：https://leetcode-cn.com/problems/word-search
```
```
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        vector<vector<bool>> visited(board.size(),vector<bool>(board[0].size(),false));
        bool result = false;
        string curr_str;
        int index = 0;
        for(int i = 0;i<board.size();++i)
        {
            for(int j = 0;j<board[i].size();++j)
            {
                result = result || search(board,word,visited,index,i,j);
                // if(search(board,word,visited,idx,i,j))
                //     return true; 
            }
        }
        return result;
        // return false;
    }
private:
    bool search(vector<vector<char>>& board,string &word,vector<vector<bool>> &visited,int index,int x,int y)
    {
        //适当剪枝
        if(index >= word.size()) return true;
        //越界或者已经访问，或者未访问但不相等，则直接结束
        if(x<0 || x>=board.size() || y<0 || y>= board[x].size() || visited[x][y] || board[x][y]!=word[index])
            return false;

//到这里说明未访问，且相等，则可以继续在(x,y)点周围继续搜索
        //向后搜索前，先将（x,y）点处置为已经访问状态，后面不可再访问
        visited[x][y] = true;            
        if(search(board,word,visited,index+1,x+1,y) || search(board,word,visited,index+1,x,y+1)
        || search(board,word,visited,index+1,x-1,y) || search(board,word,visited,index+1,x,y-1))
            return true;
        //x,y点访问结束，重新置为可访问状态
        visited[x][y] = false;
        return false;
    }
};
```
## 5.9 岛屿数量(DFS和BFS)
```
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

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

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

示例 1:

输入:
[
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
输出: 1
示例 2:

输入:
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

链接：https://leetcode-cn.com/problems/number-of-islands
```
```
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        //return func1(grid);
        return func2(grid);
    }
private:
    //方法一:DFS深度优先搜索
    int func1(vector<vector<char>>& grid) {
        if(grid.empty()) return 0;
        vector<vector<bool>> visited(grid.size(),vector<bool>(grid[0].size(),false));
        int islandCnt = 0;
        for(int i = 0;i<grid.size();++i)
        {
            for(int j = 0;j<grid[i].size();++j)
            {
                //还未访问过的"陆地",其周围的陆地均会变为访问状态(就像被“感染一样”)
                 if(grid[i][j] == '1' && visited[i][j] == false)
                 {
                     infect(grid,visited,i,j);
                     islandCnt++;
                 }
            }
        }
        return islandCnt;
    }
    void infect(vector<vector<char>> &grid,vector<vector<bool>>& visited,int x,int y)
    {
        //如果越界或者已经访问过，或者未访问过，但是不是陆地，直接返回
        if(x<0 || x>=grid.size() || y<0 || y>=grid[x].size() || visited[x][y] || grid[x][y] == '0') return;

//未越界并且未访问
        visited[x][y] = true;
        infect(grid,visited,x+1,y);
        infect(grid,visited,x,y+1);
        infect(grid,visited,x-1,y);
        infect(grid,visited,x,y-1);
    }
    //方法二:BFS广度优先搜索（也是“感染”的一个过程）
    int func2(vector<vector<char>>& grid)
    {
        if(grid.empty()) return 0;
        vector<vector<bool>> visited(grid.size(),vector<bool>(grid[0].size(),false));
        int islandCnt = 0;
        for(int i = 0;i<grid.size();++i)
        {
            for(int j = 0;j<grid[i].size();++j)
            {
                if(grid[i][j] == '1' && visited[i][j] == false)
                {
                    islandCnt++;
                    queue<pair<int,int>> q;
                    visited[i][j] = true;
                    q.push(make_pair(i,j));
                    while(!q.empty())
                    {
                        int nx = q.front().first;
                        int ny = q.front().second;
                        q.pop();
                        if(nx - 1 >=0 && grid[nx-1][ny] == '1' && visited[nx-1][ny] == false)
                        {
                            q.push(make_pair(nx-1,ny));
                            visited[nx - 1][ny] = true;
                        }
                        if(ny - 1 >=0 && grid[nx][ny - 1] == '1' && visited[nx][ny - 1] == false) 
                        {
                            q.push(make_pair(nx,ny - 1));
                            visited[nx][ny - 1] = true;
                        }
                        if(nx + 1 < grid.size() && grid[nx + 1][ny] == '1' && visited[nx + 1][ny] == false)
                        {
                            q.push(make_pair(nx + 1,ny));
                            visited[nx + 1][ny] = true;
                        }
                        if(ny + 1 < grid[nx].size() && grid[nx][ny + 1] == '1' && visited[nx][ny + 1] == false) 
                        {
                            q.push(make_pair(nx,ny + 1));
                            visited[nx][ny + 1] = true;
                        }
                    }
                }
            }
        }
        return islandCnt;
    }
};
```
# 6. 贪婪算法(Greedy)
## 6.1 跳跃游戏
### `55. Jump Game I`
- 给定一个非负整数数组，你最初位于数组的第一个位置。

- 数组中的每个元素代表你在该位置可以跳跃的最大长度。

- 判断你是否能够到达最后一个位置。

```
输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
```
```
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
```
```
class Solution {
public:
    bool canJump(vector<int>& nums) {
         return greedyJump2(nums);    
    }

bool greedyJump(vector<int>& nums)
    {
         int remaining_steps = nums[0];
         for(int i = 1;i<nums.size();i++)
         {
            remaining_steps--;    
            if(remaining_steps < 0) return false;
            if(nums[i] > remaining_steps) remaining_steps = nums[i];
         }
         return true;
    }

//贪婪算法基本思想：每走一步，都考虑怎样才能走得更远,同时更新能走的最远距离
    bool greedyJump2(vector<int> &nums)
    {
         int len = nums.size();
         if(len <=1) return true;
         int furthest = nums[0];
         //最重要的一点是，每一个位置都要找最远距离
         for(int i=1;i<len;i++)
         {
            if(furthest<i) return false;//表示i不可达，可直接得出结果
            else{
                //最远距离更新
                furthest = max(furthest,i+nums[i]);
            }
         }
         return furthest >=len-1;
    }
};
//https://leetcode-cn.com/problems/jump-game/
```
### `45. Jump Game II`
- 给定一个非负整数数组，你最初位于数组的第一个位置。

- 数组中的每个元素代表你在该位置可以跳跃的最大长度。

- 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
- 说明:
假设你总是可以到达数组的最后一个位置。
```
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
```

```
class Solution {
public:
    int jump(vector<int>& nums) {
        return greedy(nums);
        //return dynamic(nums);
    }

//贪婪算法,O(n)
    int greedy(vector<int> &nums)
    {
        //贪心策略,每一步都为下一步做考虑,每一步都使得下一步走的更远
        int res = 0;
        int station = 0;
        int distance = 0;
        for(int i = 0;i<nums.size()-1;i++)
        {
            //在走的过程中,就在不停的寻找下一个中转站
            distance = max(distance,nums[i]+i);
            //到达中转站,则再走一步
            if(i== station){
                //下一个中转站更新
                station = distance;
                //要再走一步
                res++;
            }
        }
        return res;
    }
    //动态规划,O(n^2),代码好像没有问题,不过由于测试样例过于变态,会超时
    int dynamic(vector<int> &nums)
    {
        //if(nums.empty()) return -1;
        int len = nums.size();
        vector<int> dp(len + 1,-1);
        dp[0] = 0;

for(int i = 1;i<len;++i)
        {
            for(int j = 0;j<i;j++)
            {
                if(j+nums[j] >=i){
                    if(dp[i] == -1)
                       dp[i] = 1 + dp[j];
                    else dp[i] = min(dp[i],dp[j] + 1);
                } 
            }
        }
        return dp[len-1];
    }
};
//https://leetcode-cn.com/problems/jump-game-ii/
```
### 快手面试题: 跳跃游戏
- 作者：ergereffo
链接：https://www.nowcoder.com/discuss/496754?type=all&order=time&pos=&page=1&channel=-2&source_id=search_all
来源：牛客网

- 有一个整数数组，里面有正有负，从第一个元素开始遍历，每次碰到一个正数就往数组的尾部跳对应个数(意思是最多跳跃这个对应个数吧？)，碰到负数就往数组头部跳对应个数。问是否能跳出这个数组。比如数组 [1， 2， 0， 2， -5， -1]就可以跳出去。

- 个人代码：
```
#include<iostream>
#include<vector>
using namespace std;
bool  greedyJump(vector<int> & nums)
{
	int len = nums.size();
	if (len <= 1)  return true;
	int furthest = nums[0]; //furthest能到达的最远处坐标
	for (int i = 1; i < len; i++)
	{
		//说明无法向右跳出去，只能考虑向左跳
		if (furthest < i) break;
		else
		{
			//更新最远距离
			if (i + nums[i] > furthest)
				furthest = i + nums[i];
		}
	}
	//注意这里与leetcode55的区别，这里要求跳出去,所以是>= len
	if (furthest >= len)
	{
		//说明能够向右跳出去
		return true;
	}
	else //说明只能考虑向左跳看能否跳出去
	{
		//有可能此时furthest就在0以前,比如{ -1,2,0,2,-5,-1 };
		if (furthest < 0) return true;
		//出发点index选在[0,1,..., furthest]范围内的任意个点，向左跳看能否跳出去
		for (int i = 0; i <= furthest; i++)
		{
			//因为[0,1,..., furthest]范围内的点都是可以到达的
			if (i + nums[i] < 0) return true;
		}
	}
	return false;
}

int main()
{
	vector<int> nums = { 1,-2,0,2,-5,-1 };
	cout << greedyJump(nums)<<endl;
	system("pause");
	return 0;
}

```

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

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

- 如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

- 说明
如果题目有解，该答案即为唯一答案。
输入数组均为非空数组，且长度相同。
输入数组中的元素均为非负数。
```
输入: 
gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]

输出: 3

解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。
```
```
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        return greedy2(gas,cost);
    }
    
    //暴力求解法：显然速度很慢
    int greedy(vector<int> &gas,vector<int> &cost)
    {
        int cnt;
        int len = gas.size();
        if(len==1) return gas[0]>=cost[0]? 0:-1;
        for(int i = 0;i<len;i++)
        {
            //起步时，油必须够
            if(gas[i]>cost[i])
            {
              int curgas=0;
              cnt = 0;
              //循环走
              for(int j = i;j<=len;j++)
              {
                  j = j%len;//取模
                  cnt++;
                  curgas+=gas[j];
                  curgas-=cost[j];
                  if(curgas<0) break;
                  if(cnt == len) return i;
              }
            }
        }
        return -1;
    }
  
    //这是贪婪算法吗,怎么理解??！！！
    int greedy2(vector<int>& gas,vector<int> &cost)
    {   /* 
        如果total<0,那么必不可能跑完
        反之，如果total>=0,那么必可以跑完，只是需要找到对应的出发点
        从i出发到j，暂时油量<0了，那么出发点只可能在j之后，因此i=j+1
        */
        int temp = 0; //暂时的总油量
        int total = 0; //所有环路上，减去耗油量之后的总油量
        int start = 0; //出发地
        for(int i = 0;i<gas.size();i++)
        {
            temp+=gas[i]-cost[i];
            if(temp < 0){
                start = i + 1;
                temp = 0;
            }
            total+=gas[i] - cost[i];
        }
        return total<0?-1:start;
    }

};
```
## 6.3 分发糖果
 - `135.candy`
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

- 你需要按照以下要求，帮助老师给这些孩子分发糖果：

- 每个孩子至少分配到 1 个糖果。
- 相邻的孩子中，评分高的孩子必须获得更多的糖果。
- 那么这样下来，老师至少需要准备多少颗糖果呢？
```
示例 1:
输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
示例 2:

输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这已满足上述两个条件。
```
```
class Solution {
public:
    int candy(vector<int>& ratings) {
        return greedy(ratings);
    }
    /*基本思想：从左向右遍历一次，凡是分数更高的，多加一个糖果，再反过来一次*/
    int greedy(vector<int>& ratings)
    {
        int candy;  //需要的最少糖果数量
        int len = ratings.size();
        if(len<=1){return len;}
        vector<int> candy_vec(len,1);
        
        for(int i = 1;i<len;i++)
        {
           if(ratings[i-1]<ratings[i]){
               candy_vec[i] = candy_vec[i-1]+1;
           };
        }
        //反向遍历时即可开始求和
        candy = candy_vec[len-1];
        for(int i = len-2;i>=0;i--)
        {
            if(ratings[i]>ratings[i+1] && candy_vec[i]<=candy_vec[i+1]) //如果candy_vec[i]本来就更大,则不需要更新
            {
                candy_vec[i] = candy_vec[i+1]+1;
            }
            candy+=candy_vec[i];
        }
        return candy;
    }
};

```
## 6.4 单词拆分
### `139. Word Break`
- 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
- 说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
```
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。
     
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
```
```
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
         int len = s.size();
         //本题实际上是个动态规划的题目
         vector<bool> dp(len+1,false);
         dp[0] = true;
         for(int i=1;i<=len;i++)
         {
            for(int j = i-1;j>=0;j--)
            {
                //if(dp[j] && inDict(s.substr(j,i-j),wordDict))
                //if(dp[j] && std::count(wordDict.begin(),wordDict.end(),s.substr(j,i-j))!= 0)
                if(dp[j] && std::find(wordDict.begin(),wordDict.end(),s.substr(j,i-j))!= wordDict.end())
                {
                    dp[i] = true;
                    break;
                }
            } 
         }
         return dp[len];
    }

//实际上用find函数或者count函数都行,效率还更高
    bool inDict(string s,vector<string> &wordDict)
    {
        for(auto word:wordDict)
        {
            if(s == word) return true;
        }
        return false;
    }
};
```
### `140. Word Break II`
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明：

分隔时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
```
示例 1：
输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
[
  "cats and dog",
  "cat sand dog"
]

示例 2：
输入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
输出:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
解释: 注意你可以重复使用字典中的单词。

示例 3：
输入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
输出:
[]
```
```
class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
          unordered_map<string,vector<string> > m;
          return dfs(m,wordDict,s);
    }
    //更高效的深度优先搜索
    vector<string> dfs(unordered_map<string,vector<string>> &cache,vector<string> &wordDict,string s)
    {
        if(cache.find(s)!=cache.end()) return cache[s];//或者if(cache.count(s)) return cache[s];
        if(s.empty()) return {""};
        vector<string> res;
        for(auto word:wordDict)
        {
            if(s.substr(0,word.size()) == word)
            {
                //substr默认是截取到结尾,所以substr函数的参数(start_pos,num)中num可以省略,或者num可以大于字符串的长度
                vector<string> temp = dfs(cache,wordDict,s.substr(word.size(),s.size()));//-word.size()));
                for(auto item:temp)
                {
                    res.push_back(word + (item.empty()?"":" "+item));
                }
            }
        }
        cache[s] = res;
        return res;
    }

//下面的这种查找方式,效率要低一点(当然也可以用类似于回溯的方式),因为多了很多次无效的查找
    vector<string> dfs2(unordered_map<string,vector<string>> &cache,vector<string> &wordDict,string s)
    {
        if(cache.count(s)) return cache[s];
        if(s.empty()) return {""};
        vector<string> res;
        for(int i = 0;i<s.size();++i)
        {
            if(std::find(wordDict.begin(),wordDict.end(),s.substr(0,i+1)) != wordDict.end())
            {
                vector<string> temp = dfs2(cache,wordDict,s.substr(i+1));
                for(auto item:temp)
                {
                    res.push_back(s.substr(0,i+1) + (item.empty()?"":" "+item));
                }
            }
        }
        cache[s] = res;
        return res;
    }
};
```
## 6.5 分发饼干
```
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

注意：

你可以假设胃口值为正。
一个小朋友最多只能拥有一块饼干。

示例 1:

输入: [1,2,3], [1,1]

输出: 1

解释: 
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
示例 2:

输入: [1,2], [1,2,3]

输出: 2

解释: 
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.
```
```
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        return func1(g,s);
    }
private:
    int func1(vector<int>& g, vector<int>& s)
    {
        //与优先队列的仿函数是相反的，less的在前面
        sort(g.begin(),g.end(),less<int>());
        sort(s.begin(),s.end());
        int result = 0;
        int i = 0,j = 0; 
        for(;i<g.size();++i)
        {
            for(;j < s.size();++j)
            {
                if(g[i] <= s[j])
                {
                    result++;
                    j++;
                    break;
                }
            }
        }
        return result;
    }
    int func2(vector<int>& g, vector<int>& s)
    {
        //贪心: 优先满足满足度最小的孩子，并且使用尺寸最小的饼干
        priority_queue<int,vector<int>,greater<int> > g_queue,s_queue;
        for(auto n:g)
        {
            g_queue.push(n);
        }
        for(auto n:s)
        {
            s_queue.push(n);
        }
        int result = 0;
        int child_appetite = 0;
        int biscuit = 0;
        while(!g_queue.empty())
        {
            //胃口最小的孩子的胃口
            child_appetite = g_queue.top();
            g_queue.pop();
            biscuit = 0;
            if(s_queue.size())
            {
                biscuit = s_queue.top();
                s_queue.pop();
            }
            while(s_queue.size() && biscuit < child_appetite)
            {
                biscuit = s_queue.top();
                s_queue.pop();
            }
            if(biscuit >= child_appetite)
            {
                result++;
            }
            else break;
        }
        return result;
    }
};
```
## 6.6 任务调度器
```
给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。

然而，两个相同种类的任务之间必须有长度为 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。

你需要计算完成所有任务所需要的最短时间。

示例 ：

输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
     在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。

提示：

任务的总个数为 [1, 10000]。
n 的取值范围为 [0, 100]。
链接：https://leetcode-cn.com/problems/task-scheduler
```
```
class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {    
    /**
     * 解题思路：
     * 1、将任务按类型分组，正好A-Z用一个int[26]保存任务类型个数
     * 2、对数组进行排序，优先排列个数（count）最大的任务，
     *      如题得到的时间至少为 retCount =（count-1）* (n+1) + 1 ==> A->X->X->A->X->X->A(X为其他任务或者待命)
     * 3、再排序下一个任务，如果下一个任务B个数和最大任务数一致，
     *      则retCount++ ==> A->B->X->A->B->X->A->B
     * 4、如果空位都插满之后还有任务，那就随便在这些间隔里面插入就可以，因为间隔长度肯定会大于n，在这种情况下就是任务的总数是最小所需时间
     */
        if (tasks.size() <= 1 || n < 1) return tasks.size();
        //步骤1
        int counts[26] = {0};
        for (int i = 0; i < tasks.size(); i++) {
            counts[tasks[i] - 'A']++;
        }
        //步骤2
        sort(counts,counts+26,less<int>());
        int maxCount = counts[25];
        int retCount = (maxCount - 1) * (n + 1) + 1;
        int i = 24;
        //步骤3
        while (i >= 0 && counts[i] == maxCount) {
            retCount++;
            i--;
        }
        //步骤4
        return max(retCount, (int)tasks.size());
    }
};
```
## 6.7 根据身高重建队列
```
假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。
注意：
总人数少于1100人。

示例
输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

链接：https://leetcode-cn.com/problems/queue-reconstruction-by-height
```
```
class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        /*核心思路非常简单：先排身高更高的，这是要防止后排入人员影响先排入人员位置
        每次排入新人员[h,k]时，已处于队列的人身高都>=h，所以新排入位置就是people[k]*/
        //使用list速度快很多,但是占用内存更多
        //vector<vector<int>> res;
        list<vector<int>> res;
        if(people.empty()) return vector<vector<int>>();
        //第一步，按照身高h排序
        sort(people.begin(),people.end(),cmp);
        //第二步，以k作为index插入到前面的队列即可
        res.insert(res.begin(),people[0]);
        for(int i = 1;i < people.size();i++)
        {
            //cout<< people[i][0] << people[i][1] << ' ';
            list<vector<int>>::iterator it = res.begin();
            for(int j = 0;j < people[i][1];j++)
            {
                it++;
            }
            res.insert(it,people[i]);
        }
        return vector<vector<int>>(res.begin(),res.end());
    }
private:
    static bool cmp(vector<int> &lhs,vector<int> &rhs)
    {
        return lhs[0] == rhs[0] ? lhs[1] <= rhs[1] : lhs[0] > rhs[0];
    }
};
```

lee-romantic 's Blog

导航

最近发表

友情链接