leetcode(力扣）刷题笔记（c ）【中】(力扣怎么刷java题)-pg电子平台

大家好！今天让小编来大家介绍下关于leetcode(力扣）刷题笔记（c ）【中】的问题，以下是酷知号的小编对此问题的归纳整理，让我们一起来看看吧。

文章预览：

• 回溯算法
• • 77. 组合
  • 216.组合总和iii
  • 17.电话号码的字母组合
  • 39. 组合总和
  • 40.组合总和ii
  • 131.分割回文串
  • 93.复原ip地址
  • 78. 子集
  • 90.子集ii
  • 491.递增子序列
  • 46.全排列
  • 47. 全排列 ii
  • 332.重新安排行程
  • 第51题. n皇后
  • 37. 解数独
• 贪心算法
• • 455. 分发饼干
  • 376. 摆动序列
  • 53. 最大子和
  • 122. 买卖股票的最佳时机 ii
  • 55. 跳跃游戏
  • 45. 跳跃游戏 ii
  • 1005. k 次取反后最大化的数组和
  • 134. 加油站
  • 135. 分发糖果
  • 860.柠檬水找零
  • 406.根据身高重建队列
  • 452. 用最少数量的箭引爆气球
  • 435. 无重叠区间
  • 763.划分字母区间
  • 56. 合并区间
  • 738. 单调递增的数字
  • 714. 买卖股票的最佳时机含手续费
  • 968.监控二叉树
• 动态规划
• • 509. 斐波那契数
  • 70. 爬楼梯
  • 746. 使用最小花费爬楼梯
  • 62.不同路径
  • 63. 不同路径 ii
  • 343. 整数拆分
  • 96.不同的二叉搜索树
  • 0-1背包理论基础
  • 416. 分割等和子集
  • 1049. 最后一块石头的重量 ii
  • 494. 目标和
  • 474.一和零
  • 518. 零钱兑换 ii
  • 377. 组合总和 ⅳ
  • 322. 零钱兑换
  • 279.完全平方数
  • 139. 单词拆分
  • 198. 打家劫舍
  • 213. 打家劫舍 ii
  • 337. 打家劫舍 iii
  • 121. 买卖股票的最佳时机
  • 122.买卖股票的最佳时机ii
  • 123.买卖股票的最佳时机iii
  • 188.买卖股票的最佳时机iv
  • 309.最佳买卖股票时机含冷冻期
  • 714.买卖股票的最佳时机含手续费
  • 300.最长递增子序列
  • 674. 最长连续递增序列
  • 718. 最长重复子数组
  • 1143.最长公共子序列
  • 1035.不相交的线
  • 53. 最大子数组和
  • 392. 判断子序列
  • 115. 不同的子序列
  • 583. 两个字符串的删除操作
  • 72. 编辑距离
  • 编辑距离总结篇
  • 647. 回文子串
  • 516.最长回文子序列

参考刷题链接代码随想录

77. 组合

c
法一：回溯

class solution {
public:vector<vector<int>> result;vector<int> temp;void backtracking(int max,int min,int k,int depth){if(depth==k){result.push_back(temp);return;}depth;//当前为第几层，树的深度for(int i=min;i<=max;i){temp.push_back(i);backtracking(max,i1,k,depth);temp.pop_back();//回溯}}vector<vector<int>> combine(int n, int k) {//k为树的深度，n为第一层的宽度backtracking(n,1,k,0);return result;}
};

剪枝优化
这种写法和代码随想录的写法不一样，但是思路一致

class solution {
public:vector<vector<int>> result;vector<int> temp;void backtracking(int max,int min,int k,int depth){if(max-min1depth<k) return;//剪枝优化，如果可以访问到的元素不够k个数则返回，不进行循环if(depth==k){result.push_back(temp);return;}depth;//当前为第几层，树的深度，相当于已经选择的元素个数for(int i=min;i<=max;i){temp.push_back(i);backtracking(max,i1,k,depth);temp.pop_back();//回溯}}vector<vector<int>> combine(int n, int k) {//k为树的深度，n为第一层的宽度backtracking(n,1,k,0);return result;}
};

216.组合总和iii

c
法一：回溯

class solution {
public:vector<vector<int>> result;vector<int> temp;//存放路径值int s=0;//和void backtracking(int max,int min,int s,int k,int n){if(s==n&&temp.size()==k){//相加之和为n且为k个数result.push_back(temp);return;}for(int i=min;i<=max;i){temp.push_back(i);s =i;backtracking(max,i1,s,k,n);s-=i;temp.pop_back();}}vector<vector<int>> combinationsum3(int k, int n) {int max=9;int min=1;backtracking(max,min,s,k,n);return result;}
};

剪枝优化

class solution {
public:vector<vector<int>> result;vector<int> temp;int s=0;void backtracking(int max,int min,int s,int k,int n){if(max-min1temp.size()<k||s>n) return;//剪枝优化,个数不足或者超过了目标值均返回if(temp.size()==k){//且为k个数if(s==n) result.push_back(temp);//相加之和为nreturn;//访问了k个数就返回}for(int i=min;i<=max;i){temp.push_back(i);s =i;backtracking(max,i1,s,k,n);s-=i;temp.pop_back();}}vector<vector<int>> combinationsum3(int k, int n) {int max=9;int min=1;backtracking(max,min,s,k,n);return result;}
};

17.电话号码的字母组合

c
法一：回溯
注意需要按照给出电话按键的顺序进行字母的组合
如果在现场面试的时候，一定要注意各种输入异常的情况，例如本题输入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:vector<string> result;string temp;void backtracking(string &digits,int index){if(index==digits.size()){result.push_back(temp);return;}int k=digits[index]-'0';//取digits的第index个值index;string letter=lettermap[k];for(int i=0;i<letter.size();i){temp.push_back(letter[i]);backtracking(digits,index);temp.pop_back();}}vector<string> lettercombinations(string digits) {if(digits.size()==0) return result;backtracking(digits,0);return result;}
};

39. 组合总和

c
法一：回溯

class solution {
public:vector<vector<int>> result;vector<int> temp;int s=0;void backtracking(vector<int>& candidates,int target,int index){if(s>target) return;if(s==target){result.push_back(temp);return;}for(int i=index;i<candidates.size();i){//注意每次开始的下标不是0temp.push_back(candidates[i]);s =candidates[i];backtracking(candidates,target,i);s-=candidates[i];temp.pop_back();}}vector<vector<int>> combinationsum(vector<int>& candidates, int target) {//每一层的元素都相同backtracking(candidates,target,0);return result;}
};

剪枝优化：如果已经知道下一层的sum会大于target，就没有必要进入下一层递归了。

class solution {
public:vector<vector<int>> result;vector<int> temp;int s=0;void backtracking(vector<int>& candidates,int target,int index){if(s>target) return;if(s==target){result.push_back(temp);return;}for(int i=index;i<candidates.size()&&s<=target;i){//条件判断里加了剪枝优化temp.push_back(candidates[i]);s =candidates[i];backtracking(candidates,target,i);s-=candidates[i];temp.pop_back();}}vector<vector<int>> combinationsum(vector<int>& candidates, int target) {//每一层的元素都相同backtracking(candidates,target,0);return result;}
};

40.组合总和ii

c
法一：回溯，在插入路径时利用find函数进行去重，但是超时了，代码如下

class solution {
public: vector<vector<int>> result;vector<int> temp;int s=0;void backtracking(vector<int>& candidates, int target,int index){if(s>target) return;if(s==target){vector<vector<int>>::iterator it=find(result.begin(),result.end(),temp);if(it==result.end()) result.push_back(temp);return;}for(int i=index;i<candidates.size();i){s =candidates[i];temp.push_back(candidates[i]);backtracking(candidates,target,i1);s-=candidates[i];temp.pop_back();}}vector<vector<int>> combinationsum2(vector<int>& candidates, int target) {sort(candidates.begin(),candidates.end());backtracking(candidates,target,0);return result;}
};

优化：如果同一树层中遇到了重复元素就跳过，因为前面的重复元素和后面元素的组合一定会重复。注意if条件中i>index必须写在&&的前面，不然会报错。

class solution {
public: vector<vector<int>> result;vector<int> temp;int s=0;void backtracking(vector<int>& candidates, int target,int index){if(s>target) return;if(s==target){result.push_back(temp);return;}for(int i=index;i<candidates.size();i){if(i>index&&candidates[i]==candidates[i-1]) continue;//去重步骤，同一层的节点值不能重复s =candidates[i];temp.push_back(candidates[i]);backtracking(candidates,target,i1);s-=candidates[i];temp.pop_back();}}vector<vector<int>> combinationsum2(vector<int>& candidates, int target) {sort(candidates.begin(),candidates.end());backtracking(candidates,target,0);return result;}
};

131.分割回文串

c
法一：回溯。
每层按照1~s.size()的大小依次进行截取

class solution {
public:vector<vector<string>> result;vector<string> temp;bool ispalindrome(const string &s,int start,int end){//这里必须要加const，因为回溯函数中加了//双指针判断是否为回文串for(int i=start,j=end;i<j;i,j--){if(s[i]!=s[j]) return false;}return true;}void backtracking(const string &s,int start_index){if(start_index >= s.size()){//分割结束result.push_back(temp);return;}for(int i=start_index;i<s.size();i){if(ispalindrome(s,start_index,i)) {//是回文串string str=s.substr(start_index,i-start_index1);//start_index位置开始的子串temp.push_back(str);}else continue;//不是回文串就跳过backtracking(s,i1);temp.pop_back();}}vector<vector<string>> partition(string s) {backtracking(s,0);return result;}
};

93.复原ip地址

c
法一：回溯
先分割三次，就会形成四段字符串，循环里每次都会对前三段字符串是否有效进行判断，结束条件里面会对第四段进行判断，但是都不能忘记path需要回溯

class solution {
public:vector<string> result;string path;bool isvalid(const string &s,int start,int end){//判断字符串是否有效if(start>end) return false;if(s[start]=='0'&&start!=end) return false;int num=0;for(int i=start;i<=end;i){num = num * 10  (s[i] - '0');if(num>255) return false;}return true;}void backtracking(const string &s,int index,int depth){if(depth==3){//分割三次后就进行处理判断剩下的字符串是否符合要求if(isvalid(s,index,s.size()-1)){string str=s.substr(index,s.size()-index);path =str;result.push_back(path);for(int j=0;j<str.size();j)path.pop_back();//这里也需要回溯}return;}for(int i=index;i<s.size();i){string str=s.substr(index,i-index1);//[index,i]之间的字符串if(isvalid(s,index,i)){//字符串符合要求path =str; depth;if(depth<4) path ="."; backtracking(s,i1,depth);for(int j=0;j<str.size();j)path.pop_back();//这样写每次只会弹出一个字符，但是str不止一个字符,所以需要加循环处理if(depth<4) path.pop_back();depth--;}else break;}}vector<string> restoreipaddresses(string s) {//树的深度为四层，if (s.size() < 4 || s.size() > 12) return result; // 算是剪枝了backtracking(s,0,0);return result;}
};

78. 子集

c
法一：回溯

class solution {
public:vector<vector<int>> result;vector<int> temp;void backtracking(vector<int>& nums,int index){if(true){//每种分割的结果都放进去result.push_back(temp);//后面就不要再加上return了}for(int i=index;i<nums.size();i){temp.push_back(nums[i]);backtracking(nums,i1);temp.pop_back();}}vector<vector<int>> subsets(vector<int>& nums) {backtracking(nums,0);return result;}
};

90.子集ii

c
法一：回溯
注意：去重必须要先对数组进行排序！

class solution {
public:vector<vector<int>> result;vector<int> temp;void backtracking(vector<int>& nums,int index){result.push_back(temp);for(int i=index;i<nums.size();i){if(i>index&&nums[i]==nums[i-1]){continue;}else{temp.push_back(nums[i]);backtracking(nums,i1);temp.pop_back();                }}}vector<vector<int>> subsetswithdup(vector<int>& nums) {sort(nums.begin(),nums.end());backtracking(nums,0);return result;}
};

491.递增子序列

c
法一：回溯
踩坑记录：采用和上一题90题类似的去重写法，但是这样做只能去除前后出现的重复数字，如果后面又出现了重复数字就去重不了，比如数组[1,2,2,7,5,7]

class solution {
public:vector<vector<int>> result;vector<int> temp;void backtracjing(vector<int>& nums,int index){if(temp.size()>1) result.push_back(temp);for(int i=index;i<nums.size();i){if(i>index&&nums[i]==nums[i-1]){//因为并不是有序数组，所以这样做只能去除前后出现的重复数字，如果后面又出现了重复数字就去重不了continue;}if(temp.size()>0&&nums[i]<temp.back()) continue;temp.push_back(nums[i]);backtracjing(nums,i1);temp.pop_back();}}vector<vector<int>> findsubsequences(vector<int>& nums) {backtracjing(nums,0);return result;}
};

改进后：需要直到同一层中哪些数字用过了，一个for循环就代表横向树的一层，所以在for循环上面添加一个unordered_set容器（该容器底层为哈希表，且不会自动排序，这道题并不需要对元素进行排序），unordered_set中不允许有重复的元素。同一层的元素会出现在路径容器的同一个位置，所以不能出现重复值，回溯代码最后不需要对unordered_set删除nums[i]这个元素，因为unordered_set只记录同一层的元素哪些用过了

class solution {
public:vector<vector<int>> result;vector<int> temp;  void backtracjing(vector<int>& nums,int index){if(temp.size()>1) result.push_back(temp);unordered_set<int> use_num;//这里也可以用数组，耗时更少for(int i=index;i<nums.size();i){if(use_num.find(nums[i])!=use_num.end()){continue;}use_num.insert(nums[i]);//注意后面不需要再删除这个元素if(temp.size()>0&&nums[i]<temp.back()) continue;//保持递增顺序temp.push_back(nums[i]);backtracjing(nums,i1);temp.pop_back();}}vector<vector<int>> findsubsequences(vector<int>& nums) {backtracjing(nums,0);return result;}
};

46.全排列

c
法一：回溯
需要查找temp里面已经用过的元素，如果用过了就不能再用了，且每次循环都是从0开始

class solution {
public:vector<vector<int>> result;vector<int> temp;  void backtracjing(vector<int>& nums,int index){if(temp.size()>1) result.push_back(temp);unordered_set<int> use_num;for(int i=index;i<nums.size();i){if(use_num.find(nums[i])!=use_num.end()){continue;}use_num.insert(nums[i]);//注意后面不需要再删除这个元素if(temp.size()>0&&nums[i]<temp.back()) continue;//保持递增顺序temp.push_back(nums[i]);backtracjing(nums,i1);temp.pop_back();}}vector<vector<int>> findsubsequences(vector<int>& nums) {backtracjing(nums,0);return result;}
};

47. 全排列 ii

c
法一：回溯
也可以使用unordered_set来记录同一层的元素使用情况，利用find函数来进行去重
需要注意的是：使用set去重的版本相对于数组的版本效率都要低很多

class solution {
public:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums,int* use_num){if(path.size()==nums.size()) {result.push_back(path);return;}for(int i=0;i<nums.size();i){//use_num[i-1]==0：同层use_num[i-1]使用过//use_num[i-1]==1：同一树枝use_num[i-1]使用过if(i>0&&nums[i]==nums[i-1]&&use_num[i-1]==0) continue;//对同一层进行去重效率更高if(use_num[i]==1) continue;//跳过本身use_num[i]=1;//1代表用过了path.push_back(nums[i]);backtracking(nums,use_num);path.pop_back();use_num[i]=0;}}vector<vector<int>> permuteunique(vector<int>& nums) {int size=nums.size();int use_num[size];//记录路径元素是否用过，默认初始化为0sort(nums.begin(),nums.end());backtracking(nums,use_num);return result;}
};

332.重新安排行程

c
法一：回溯
踩坑记录：先找出第一个机票再做回溯的做法是不对的，因为找出的最小排序不一定能把所有的机票用完
正确做法： 利用unordered_map<出发机场, map<到达机场, 航班次数>> targets来储存所有的行程中相同出发地的行程，通过判断航班次数来判断该行程是否已经用过。map中所有元素都是pair

class solution {
public:vector<string> result;// unordered_map<出发机场, map<到达机场, 航班次数>> targetsunordered_map<string, map<string, int>> targets;bool backtracking(vector<vector<string>>& tickets){if(result.size()==(1tickets.size())){return true;}for(pair<const string,int>& temp:targets[result[result.size()-1]]){//找出result的最后一个地点，也就是下一个行程的出发地点if(temp.second>0){//说明还没用过result.push_back(temp.first);//只需要放入到达机场temp.second--;if(backtracking(tickets)) return true;//result.pop_back();temp.second;}}return false;//如果没找到行程就会返回false}vector<string> finditinerary(vector<vector<string>>& tickets) {for(vector<string> &temp:tickets){targets[temp[0]][temp[1]];//targets[temp[0]]相当于是key=temp[0]对应的map容器，targets[temp[0]][temp[1]]相当于是对map容器中key=temp[1]进行赋值}result.push_back("jfk");//初始机场backtracking(tickets);return result;}
};

第51题. n皇后

c
法一：回溯
思路：通过used_column来记录用过的列，通过use_loc来记录皇后位置和会被攻击的地方，只需要将下面每一层的对角线的位置标记就可以了，但是n=6时报错了，出现皇后放在了对角线的位置。

class solution {
public:vector<vector<string>> result;vector<string> conver(vector<vector<int>>& use_loc,int n){vector<string> temp;for(int i=0;i<n;i){string str="";for(int j=0;j<n;j){if(use_loc[i][j]==2){str ="q";}else str =".";}temp.push_back(str);}return temp;}void backtracking(int n,vector<vector<int>>& use_loc,int depth,vector<bool>& used_column){if(depth==n){vector<string> temp;temp=conver(use_loc,n);result.push_back(temp);return;}for(int i=0;i<n;i){if(used_column[i]) continue;//跳过用过的列if(use_loc[depth][i]==1) continue;//跳过会被攻击的地方use_loc[depth][i]=2;//皇后//下面每一层的对角线for(int j=depth1,k=i-1;j<n && k>=0;j,k--){use_loc[j][k]=1;}for(int j=depth1,k=i1;j<n && k<n;j,k){use_loc[j][k]=1;}used_column[i]=true;depth;backtracking(n,use_loc,depth,used_column);depth--;use_loc[depth][i]=0;for(int j=depth1,k=i-1;j<n && k>=0;j,k--){use_loc[j][k]=0;}for(int j=depth1,k=i1;j<n && k<n;j,k){use_loc[j][k]=0;}used_column[i]=false;}}vector<vector<string>> solvenqueens(int n) {vector<vector<int>> use_loc(n,vector<int>(n,0));//全部初始化为0vector<bool> used_column(n,false);//用过的列backtracking(n,use_loc,0,used_column);return result;}
};

后来找出了错误，因为有些皇后的攻击的位置会有交叉，在回溯的时候将一些攻击位置置0后是不对的，该位置有可能是上层皇后的攻击位置，所以不能简单的置0和置1，应该每个位置的数值是被攻击的次数，这样回溯时才不会出错

class solution {
public:vector<vector<string>> result;vector<string> conver(vector<vector<int>>& use_loc,int n){vector<string> temp;for(int i=0;i<n;i){string str="";for(int j=0;j<n;j){if(use_loc[i][j]==-1){str ="q";}else str =".";}temp.push_back(str);}return temp;}void backtracking(int n,vector<vector<int>>& use_loc,int depth,vector<bool>& used_column){if(depth==n){vector<string> temp;temp=conver(use_loc,n);result.push_back(temp);return;}for(int i=0;i<n;i){if(used_column[i]) continue;//跳过用过的列if(use_loc[depth][i]>0) continue;//跳过会被攻击的地方use_loc[depth][i]=-1;//皇后//下面每一层的对角线for(int j=depth1,k=i-1;j<n && k>=0;j,k--){use_loc[j][k];}for(int j=depth1,k=i1;j<n && k<n;j,k){use_loc[j][k];}used_column[i]=true;depth;backtracking(n,use_loc,depth,used_column);depth--;use_loc[depth][i]=0;for(int j=depth1,k=i-1;j<n && k>=0;j,k--){use_loc[j][k]--;}for(int j=depth1,k=i1;j<n && k<n;j,k){use_loc[j][k]--;}used_column[i]=false;}}vector<vector<string>> solvenqueens(int n) {vector<vector<int>> use_loc(n,vector<int>(n,0));//全部初始化为0vector<bool> used_column(n,false);//用过的列backtracking(n,use_loc,0,used_column);return result;}
};

法二：改成下面这种判断上面的对角线中是否有皇后就会通过

class solution {
public:vector<vector<string>> result;vector<vector<int>> use_loc;vector<string> conver(vector<vector<int>>& use_loc,int n){vector<string> temp;for(int i=0;i<n;i){string str="";for(int j=0;j<n;j){if(use_loc[i][j]==2){str ="q";}else str =".";}temp.push_back(str);}return temp;}void backtracking(int n,vector<vector<int>>& use_loc,int depth,vector<bool>& used_column){if(depth==n){vector<string> temp;temp=conver(use_loc,n);result.push_back(temp);return;}for(int i=0;i<n;i){//i控制列if(used_column[i]) continue;//跳过用过的列if(use_loc[depth][i]==1) continue;//跳过会被攻击的地方//下面每一层的对角线bool r=false;for(int j=depth-1,k=i1;j>=0 && k<n;j--,k){if(use_loc[j][k]==2) r=true;}if(r) continue;r=false;for(int j=depth-1,k=i-1;j>=0 && k>=0;j--,k--){if(use_loc[j][k]==2) r=true;}if(r) continue;use_loc[depth][i]=2;//皇后used_column[i]=true;depth;backtracking(n,use_loc,depth,used_column);//回溯depth--;use_loc[depth][i]=0;// for(int j=depth 1,k=i-1;j=0;j  ,k--){//     use_loc[j][k]=0;// }// for(int j=depth 1,k=i 1;j//     use_loc[j][k]=0;// }used_column[i]=false;}}vector<vector<string>> solvenqueens(int n) {vector<vector<int>> t(n,vector<int>(n,0));//全部初始化为0use_loc=t;vector<bool> used_column(n,false);//用过的列backtracking(n,use_loc,0,used_column);return result;}
};

37. 解数独

c
法一：回溯
踩坑记录：字符里面没有’10’，最高就是’9’

class solution {
public:bool isvalid(int row,int col,char val,vector<vector<char>>& board){for(int i=0;i<9;i){//行if(board[row][i]==val) return false;}for(int i=0;i<9;i){if(board[i][col]==val) return false;}int startrow=(row/3)*3;int startcol=(col/3)*3;for(int i=startrow;i<startrow3;i){for(int j=startcol;j<startcol3;j){if(board[i][j]==val)return false;}}return true;}bool backtracking(vector<vector<char>>& board){for(int i=0;i<board.size();i){for(int j=0;j<board[0].size();j){if(board[i][j]=='.') {for(char k='1';k<='9';k){//注意这里是<='9'，不能写<'10'，没有10这个字符if(isvalid(i,j,k,board)){board[i][j]=k;if(backtracking(board)) return true;board[i][j]='.';                            }}return false;//9个数都不对，返回false                    }}}return true;}void solvesudoku(vector<vector<char>>& board) {backtracking(board);}
};

455. 分发饼干

c
法一：小饼干先喂饱小胃口

class solution {
public:int findcontentchildren(vector<int>& g, vector<int>& s) {sort(g.begin(),g.end());sort(s.begin(),s.end());int sum=0;vector<bool> uset(s.size(),false);for(int i=0;i<g.size();i){if(s.size()>0&&s.back()<g[i]) break;//如果s的最大值都小于孩子的胃口值，那直接退出循环for(int j=0;j<s.size();j){if(uset[j]) continue;if(s[j]>=g[i]){sum;uset[j]=true;break;}}}return sum;}
};

376. 摆动序列

c
法一：贪心算法。对于连续增长或连续递减的节点们应该怎么删除？保持这两个区间的端点，删掉其他的节点就可，所以只需要记录峰值个数就可以，但是需要处理最左边和最右边的节点。
保持区间波动，只需要把单调区间上的元素移除就可以了。

class solution {
public:int wigglemaxlength(vector<int>& nums) {if(nums.size()<=1) return nums.size();int prediff=0;//把第一个节点的差值设为0int curdiff=0;//当前节点和前一个节点的差值int result=1;//包含了第一个节点for(int i=1;i<nums.size();i){curdiff=nums[i]-nums[i-1];if((curdiff>0&&prediff<=0)||(curdiff<0&&prediff>=0)){result;prediff=curdiff;}}return result;}
};

53. 最大子数组和

c
法一：暴力解法。设置两层循环，但是超过了时间限制

class solution {
public:int maxsubarray(vector<int>& nums) {int result = int32_min;int count = 0;for (int i = 0; i < nums.size(); i) { // 设置起始位置count = 0;for (int j = i; j < nums.size(); j) { // 每次从起始位置i开始遍历寻找最大值count  = nums[j];result = count > result ? count : result;}}return result;}
};

法二：贪心算法。当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。从而推出全局最优：选取最大“连续和”
其关键在于：不能让“连续和”为负数的时候加上下一个元素，而不是 不让“连续和”加上一个负数。

class solution {
public:int maxsubarray(vector<int>& nums) {int result=int_min;int cout=0;//区间连续和for(int i=0;i<nums.size();i){cout =nums[i];if(cout>result) result=cout;//取出最大连续和，不断调整终止位置if(cout<0) cout=0;//如果出现负数,连续和清零，相当于不断调整区间起始位置}return result;}
};

122. 买卖股票的最佳时机 ii

c
法一：贪心算法

class solution {
public:int maxprofit(vector<int>& prices) {int result=0;for(int i=0;i<prices.size();i){if(i>0&&prices[i]>prices[i-1]){//今天大于前一天就卖出result =(prices[i]-prices[i-1]);}}return result;}
};

55. 跳跃游戏

c
法一：贪心

class solution {
public:bool canjump(vector<int>& nums) {//能走到的位置处判断：当前位置元素值 当前位置下标值>=终点下标值int cover=0;//能走到的覆盖范围for(int i=0;i<=cover;i){cover=max(inums[i],cover);//及时更新覆盖范围if(nums[i]i1>=nums.size()){return true;}}return false;}
};

45. 跳跃游戏 ii

c
法一：贪心。在当前覆盖范围内的点：寻找下一个覆盖的更远的点

class solution {
public:int jump(vector<int>& nums) {//当前覆盖范围内的点：寻找下一个覆盖的更远的点int result=0;//跳跃次数int curcover=0;//当前覆盖范围int nextcover;//下一个点的覆盖范围int index;if(nums.size()==1) return 0;//特殊情况for(int i=0;i<nums.size();){curcover=nums[i];nextcover=0;result;//不管当前点的覆盖范围有没有包含终点，步数都需要加一，所以nums的大小至少为2if(curcoveri1>=nums.size()){//说明当前覆盖范围已经到达终点break;}//当前覆盖范围未到达终点for(int j=1;j<=curcover;j){//判断下一步的下标和覆盖范围if(nextcover<nums[ij]ij){nextcover=nums[ij]ij;index=ij;}}i=index;//下一步的下标}return result;}
};

1005. k 次取反后最大化的数组和

法一：贪心算法
写法一：使用for循环，但是这种写法容易漏掉nums.size()

class solution {
public:int largestsumafterknegations(vector<int>& nums, int k) {//负数个数>k:找出最小的k个负数变成正数//负数个数n//所以不管k-n为奇数还是偶数都可以选择最小的正数进行处理int sum=0;sort(nums.begin(),nums.end());int index=0;for(int i=0;i<nums.size()&&k>0;i){if(nums[i]<0){k--;nums[i]=-nums[i];}else{if(k%2==0) break;else{sort(nums.begin(),nums.end());nums[0]=-nums[0];k--;break;}}}//对nums.size()if(k>0&&k%2==1){sort(nums.begin(),nums.end());nums[0]=-nums[0];}for(int i=0;i<nums.size();i){sum =nums[i];}return sum;}
};

134. 加油站

法一：贪心
写法一：超出了时间限制

class solution {
public:int cancompletecircuit(vector<int>& gas, vector<int>& cost) {//从第 i 个加油站开往第 i 1 个加油站需要消耗汽油 cost[i] 升//第 i 1 个加油站有汽油 gas[i 1] 升//净含量=gas[i]-cost[i]>0的点才可以作为出发点vector<int> temp;vector<int> start_index;//出发点if(gas.size()==1){if(gas[0]-cost[0]>=0) return 0;else return -1;}//不能组成环路for(int i=0;i<gas.size();i){if(gas[i]-cost[i]>0){start_index.push_back(i);}temp.push_back(gas[i]-cost[i]);}if(start_index.size()==0) return -1;//没找到出发点int sum=0;int result;for(int i=0;i<start_index.size();i){//循环检查每个出发点sum=0;//检查是否能走完全程for(int j=start_index[i];j<temp.size()start_index[i];j){if(j<temp.size()) sum =temp[j];else sum =temp[j-temp.size()];if(sum<0) break;//小于零说明到不了下一个加油站}if(sum>=0) result=start_index[i];}return result;}
};

写法二：对写法一进行改进
利用cur来计算区间的净含量，如果一旦小于0，说明这个区间都不能作为出发点

class solution {
public:int cancompletecircuit(vector<int>& gas, vector<int>& cost) {//从第 i 个加油站开往第 i 1 个加油站需要消耗汽油 cost[i] 升//第 i 1 个加油站有汽油 gas[i 1] 升//净含量=gas[i]-cost[i]>0的点才可以作为出发点int cur=0;int res_total=0;int result=0;//这里必须初始化,如果cur一直大于0，那0号位置就是出发点for(int i=0;i<gas.size();i){cur =gas[i]-cost[i];res_total =(gas[i]-cost[i]);if(cur<0){result=i1;cur=0;}}if(res_total<0) return -1;return result;//净含量总量大于等于0，说明找到的出发点是能跑完全程的}
};

135. 分发糖果

法一：贪心算法

class solution {
public:int candy(vector<int>& ratings) {int result=0;vector<int> candynum(ratings.size(),1);//先给每个孩子都分配一个糖果if(ratings.size()==1) return 1;//从前往后判断，遇到更高评分的就加一个糖果for(int i=1;i<ratings.size();i){if(ratings[i]>ratings[i-1]){candynum[i]=candynum[i-1]1;}}//从后往前进行判断for(int i=ratings.size()-2;i>=0;i--){if(ratings[i]>ratings[i1]){if(candynum[i]<=candynum[i1])//判断糖果数是否满足要求candynum[i]=candynum[i1]1;}}//汇总for(int i=0;i<candynum.size();i){result =candynum[i];}return result;}
};

860.柠檬水找零

c
法一：贪心

class solution {
public:bool lemonadechange(vector<int>& bills) {unordered_map<int,int> money{{5,0},{10,0},{20,0}};//第一位是钱的金额，第二位是钱的数量for(int i=0;i<bills.size();i){if(bills[i]==5){money[5];}if(bills[i]==10){if(money[5]==0) return false;else{money[5]--;money[10];}}if(bills[i]==20){if(money[10]>0&&money[5]>0){//优先消耗一个10和一个5，如果不够，再消耗三个5money[5]--;money[10]--;   money[20];                }else if(money[10]==0&&money[5]>=3){money[5]=money[5]-3;money[20]; }else return false;}}return true;}
};

406.根据身高重建队列

法一：贪心
注意：类内sort自定义排序函数需定义为static否则报错。具体可见下面链接
类内sort自定义排序函数需定义为static否则报错
版本一：使用vector

class solution {
public:static bool cmp(vector<int>& a,vector<int>& b){if(a[0]==b[0]) return a[1]<b[1];//身高相同则k小的排前面else return a[0]>b[0];//从高到矮进行排序}vector<vector<int>> reconstructqueue(vector<vector<int>>& people) {//身高矮的插在身高高的前面不会有影响//所以先按照身高高矮进行排队，身高相同则k小的排前面sort(people.begin(),people.end(),cmp);vector<vector<int>> que;//按照k进行插入，k就相当于要插入的下标for(int i=0;i<people.size();i){int index=people[i][1];que.insert(que.begin()index,people[i]);}return que;}
};

版本二：使用list，耗时更短
注意：使用list时，不能直接用迭代器 几个的写法，因为链表里面的地址不是连续的

// 版本二
class solution {
public:// 身高从大到小排（身高相同k小的站前面）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) {sort (people.begin(), people.end(), cmp);list<vector<int>> que; // list底层是链表实现，插入效率比vector高的多for (int i = 0; i < people.size(); i) {int position = people[i][1]; // 插入到下标为position的位置std::list<vector<int>>::iterator it = que.begin();while (position--) { // 寻找在插入位置it;}que.insert(it, people[i]);}return vector<vector<int>>(que.begin(), que.end());}
};

452. 用最少数量的箭引爆气球

法一：贪心。先将气球直径按照开始的x坐标进行排序，再判断哪些气球具有交集，没有交集就更新新的开始直径范围，并且不断更新右边界

class solution {
public:static bool cmp(vector<int>& a,vector<int>& b){return a[0]<b[0];}int findminarrowshots(vector<vector<int>>& points) {//算交集sort(points.begin(),points.end(),cmp);int result=points.size();//假设所有气球都没有交集vector<int> start=points[0];for(int i=1;i<points.size();i){if(points[i][0]>start[1]){//没有交集start=points[i];}else{//有交集start[1]=start[1]>points[i][1]?points[i][1]:start[1];//更新直径共同范围的end,取二者最小值result--;};}return result;}
};

435. 无重叠区间

法一：贪心。先按照左边界从小到大进行排序

class solution {
public:static bool cmp(vector<int>& a,vector<int>& b){return a[0]<b[0];}int eraseoverlapintervals(vector<vector<int>>& intervals) {//后边界和前边界重叠不算重叠//选定start后将和start有重叠的区间全算作一整块，看一共有多少块就是最小数量//因为只要这些区间划分为一块了，那么这一块的区间只能留一个区间下来了sort(intervals.begin(),intervals.end(),cmp);int result=0;vector<int> start=intervals[0];for(int i=1;i<intervals.size();i){if(intervals[i][0]>=start[1]){//第i个区间至少和前面界定的重叠区间内的区间内的一个区间（具有最小右边界的区间）不重叠start=intervals[i];}else{//有重叠start[1]=min(start[1],intervals[i][1]);//更新最小右边界result;//移除区间的数量}}return result;}
};

763.划分字母区间

法一：和代码随想录一样
区间内的字符出现最远下标就是最终的右边界了，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
注意：string里面的单个字符是用单引号表示

class solution {
public:vector<int> partitionlabels(string s) {vector<int> result;int farthest_pos[26]={0};//每个字母在s中出现的最远位置int right=0;int left=0;for(int i=0;i<s.size();i){farthest_pos[s[i]-'a']=i;}for(int i=0;i<s.size();i){right=max(right,farthest_pos[s[i]-'a']);if(right==i){result.push_back(right-left1);left=i1;}}return result;       }
};

56. 合并区间

法一：贪心

class solution {
public:static bool cmp(vector<int>& a,vector<int>& b){return a[0]<b[0];}vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(),intervals.end(),cmp);//按开始坐标从小到大进行排序vector<vector<int>> result;if(intervals.size()==0) return result;result.push_back(intervals[0]);for(int i=1;i<intervals.size();i){if(intervals[i][0]<=result[result.size()-1][1]){//有重叠//每次合并都取最大的右边界!而不是取新区间的右边界//排序只是按照左边界进行排序的，右边界不一定result[result.size()-1][1]=max(result[result.size()-1][1],intervals[i][1]);}else{//没有重叠result.push_back(intervals[i]);}}return result;}
};

738. 单调递增的数字

法一：暴力算法，超时

class solution {
public:bool isvalid(int n){vector<int> num;while(n){if(num.size()>0&&(n%10>num.back())) return false;num.push_back(n%10);//放入最后一位数字n=n/10;}return true;}int monotoneincreasingdigits(int n) {while(n){if(isvalid(n)) return n;n--;}return n;}
};

法二：贪心算法

class solution {
public:int monotoneincreasingdigits(int n) {string strnum = to_string(n);int index;//开始赋'9'的下标起始位置for(int i=strnum.size()-1;i>0;i--){if(strnum[i]<strnum[i-1]){index=i;strnum[i-1]--;}}for(int i=index;i<strnum.size();i){strnum[i]='9';}return stoi(strnum);}
};

714. 买卖股票的最佳时机含手续费

法一：贪心。这道题不是很好理解，需要多思考思考

class solution {
public:int maxprofit(vector<int>& prices, int fee) {int result = 0;int minprice = prices[0]; // 记录最低价格for (int i = 1; i < prices.size(); i) {//prices[i]   fee相当于是股票的成本价格// 情况二：相当于买入//经过情况一的minprice = prices[i] - fee操作后，这里的判断条件相当于是prices[i] fee<之前的prices，相当于此时卖出会亏，买也很便宜，所以适合买入。算上手续费已经不盈利了，所以适合在此时的点买入if (prices[i] < minprice) minprice = prices[i];//此时相当于下一轮买入了// 情况三：保持原有状态（因为此时买则不便宜，卖则亏本）if (prices[i] >= minprice && prices[i] <= minprice  fee) {continue;}// 计算利润，可能有多次计算利润，最后一次计算利润才是真正意义的卖出//必须要大于买入价格 手续才能有正利润if (prices[i] > minprice  fee) {//因为后面minprice= prices[i] - fee，所以这里需要加上fee进行对比，相当于和原始prices进行对比result  = prices[i] - minprice - fee;minprice = prices[i] - fee; // 情况一，这一步很关键。避免多减去手续费}}return result;}
};

968.监控二叉树

法一：贪心。大体思路就是从低到上，先给叶子节点的父节点放个摄像头，然后隔两个节点放一个摄像头，直至到二叉树头结点。

class solution {
public:
int result=0;int tranversel(treenode* cur){//0:无覆盖//1：摄像头//2：有覆盖if(cur==null) return 2;//空节点设为有覆盖的状态，因为叶子节点不放摄像头int left=tranversel(cur->left);int right=tranversel(cur->right);if(left==2&&right==2) return 0;if(left==0||right==0){//左右节点至少有一个未覆盖的情况result;return 1;//安装摄像头}if(left==1||right==1) return 2;return -1;}int mincameracover(treenode* root) {if(tranversel(root)==0) result;return result;}
};

509. 斐波那契数

法一：使用递归

class solution {
public:int add_recur(int n){if(n==0) return 0;if(n==1) return 1;return add_recur(n-1)add_recur(n-2);}int fib(int n) {return add_recur(n);}
};

法二：动态规划

class solution {
public:int fib(int n) {if(n<=1) return n;//注意必须加上这个vector<int> dp(n1);dp[0]=0;dp[1]=1;for(int i=2;i<n1;i){dp[i]=dp[i-1]dp[i-2];}return dp[n];}
};

70. 爬楼梯

法一：动态规划

class solution {
public:int climbstairs(int n) {if (n <= 1) return n; // 因为下面直接对dp[2]操作了，防止空指针vector<int> dp(n  1);dp[1] = 1;dp[2] = 2;for (int i = 3; i <= n; i) { // 注意i是从3开始的dp[i] = dp[i - 1]  dp[i - 2];}return dp[n];}
};

法二：动态规划完全背包

class solution {
public:int climbstairs(int n) {vector<int> dp(n1,0);dp[0]=1;for(int j=1;j<=n;j){for(int i=1;i<3;i){if(j>=i) dp[j] =dp[j-i];}}return dp.back();}
};

746. 使用最小花费爬楼梯

法一：动态规划

class solution {
public:int mincostclimbingstairs(vector<int>& cost) {vector<int> dp(cost.size()1);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.back();}
};

62.不同路径

法一：动态规划

class solution {
public:int uniquepaths(int m, int n) {//当前位置路径总和=左边方块的路径数 上面方块的路径数//第1行和第1列只有左边或者上面的路径数// if(m==1||n==1) return 1;//下面的初始化已经考虑到这种情况了int dp[m][n];dp[0][0]=0;for(int i=0;i<m;i) dp[i][0]=1;for(int i=0;i<n;i) dp[0][i]=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];}
};

63. 不同路径 ii

法一：动态规划
有障碍的话，其实就是标记对应的dp table（dp数组）保持初始值(0)就可以了。

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]==1) break;//遇到了障碍物，退出循环dp[i][0]=1;}for(int i=0;i<n;i){if(obstaclegrid[0][i]==1) break;dp[0][i]=1;}for(int i=1;i<m;i){for(int j=1;j<n;j){if(obstaclegrid[i][j]==1) continue;//遇到障碍物，继续下一个位置dp[i][j]=dp[i-1][j]dp[i][j-1];}}return dp[m-1][n-1];}
};

343. 整数拆分

法一：动态规划。
dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。

class solution {
public:int integerbreak(int n) {//dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。vector<int> dp(n1,1);for(int i=3;i<=n;i){for(int j=1;j<=i/2;j){dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));//记得和dp[i]进行对比，因为这是循环，前面也找过拆分i的最大值，所以需要全局对比}}return dp[n];}
};

96.不同的二叉搜索树

法一：动态规划
实际上就是求不同搜索树的数量，不用把具体的节点值都列出来

class solution {
public:int numtrees(int n) {//i个不同元素节点组成的二叉搜索树的个数为dp[i]vector<int> dp(n1);dp[0]=1;for(int i=1;i<=n;i){for(int j=1;j<=i;j){//j-1相当于是左子树节点树，i-1-（j-1）=右子树节点//左子树和右子树分别有多少个节点dp[i] =dp[j-1]*dp[i-j];//i为根节点，还剩下i-1个节点}}return dp.back();}
};

0-1背包理论基础

一维数组：每次循环在用下一个物品时使用的一维数组的各个值，就相当于二维数组时上一层的一行值，这里只是换成了一维数组，在遍历不同物品时不停地覆盖更改值

void test_1_wei_bag_problem() {vector<int> weight = {1, 3, 4};vector<int> value = {15, 20, 30};int bagweight = 4;// 初始化vector<int> dp(bagweight  1, 0);for(int i = 0; i < weight.size(); i) { // 遍历物品for(int j = bagweight; j >= weight[i]; j--) { // 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]]  value[i]);}}cout << dp[bagweight] << endl;
}int main() {test_1_wei_bag_problem();
}

416. 分割等和子集

法一：动态规划一维数组，target为数组总和的一半，只要能找出子集和等于target的就符合要求

class solution {
public:bool canpartition(vector<int>& nums) {int sum=0;vector<int> dp(10001,0);for(int i=0;i<nums.size();i){sum =nums[i];}if (sum%2==1) return false;int 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]);}}if(dp[target]==target) return true;return false;}
};

1049. 最后一块石头的重量 ii

法一：动态规划。
本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。

class solution {
public:int laststoneweightii(vector<int>& stones) {vector<int> dp(1501,0);int target=0;int sum=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];       }
};

494. 目标和

法一：动态规划。
dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法
dp[j] = dp[j – nums[i]]
dp[j]=不需要num[i]就能够凑出j的情况(nums[i-1]对应的dp[j]) 需要num[i]凑出j空间的情况
第一个循环在遍历物品，前面已经遍历过的物品都可以放入背包中，在不同的背包容量下，方法各是多少种

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((targetsum)%2==1) return 0;int bagsize=(targetsum)/2;vector<int> dp(bagsize1,0);dp[0]=1;for(int i=0;i<nums.size();i){for(int j=bagsize;j>=nums[i];j--){dp[j] =dp[j-nums[i]];}}return dp.back();}
};