41.缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

这个题的难点就是空间还要常数级，所以我们可以就地哈希，把正数x调整到nums[x-1]这个地方。
但是如果while条件中是nums[i]!=i+1，会出现死循环，比如[1,1]，对于nums[1]=1!=2,那么就互换nums[1],nums[0]，
但是数组还是[1,1]，这不就死循环了。
所以要换一种写法，nums[i]!=nums[nums[i]-1],只需要保证0位置上确实有个1即可。class Solution {
public:int firstMissingPositive(vector<int>& nums) {int sz=nums.size();for(int i=0;i<sz;i++){while(nums[i]>0&&nums[i]<=sz&&nums[i]!=nums[nums[i]-1]){swap(nums[i],nums[nums[i]-1]);}}for(int i=0;i<sz;i++){if(nums[i]!=i+1) return i+1;}return sz+1;}
};

42.接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

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

采用双指针的方法，维护两个指针left和right，两个指针在移动的过程中维护leftmax和rightmax，leftmax是从左到右，
rightmax是从右到左，如果height[left]<height[right],下标 left 处能接的雨水量等于leftmax-height[left]，
将下标left 处能接的雨水量加到能接的雨水总量，然后将 left向右移动一位）；
如果height[left]≥height[right]，下标right处能接的雨水量等于rightmax-height[right]，将下标right处能接的
雨水量加到接的雨水总量，然后将right左移。总而言之，这个leftmax和rightmax的理解很重要！！！class Solution {
public:int trap(vector<int>& height) {int left=0,right=height.size()-1;int leftmax=0,rightmax=0,res=0;while(left<right){leftmax=max(leftmax,height[left]);rightmax=max(rightmax,height[right]);if(height[left]<height[right]){res+=leftmax-height[left]; left++;}else{res+=rightmax-height[right]; right--;}}return res;}
};2.采用单调栈 经典结构——单调栈
维护一个单调栈，单调栈存储的是下标，满足从栈底到栈顶的下标对应的数组height 中的元素递减。从左到右遍历数组，遍历到下标 i 时，
如果栈内至少有两个元素，记栈顶元素为top，top 的下面一个元素是left，则一定有height[left]≥height[top。
如果eight[i]>height[top]，则得到一个可以接雨水的区域，该区域的宽度是i−left−1，
高度是 min(height[left],height[i])−height[top]，根据宽度和高度即可计算得到该区域能接的雨水量。为了得到 left，需要将 top 出栈。在对 top 计算能接的雨水量之后，left 变成新的top，重复上述操作，直到栈变为空，
或者栈顶下标对应的 height 中的元素大于或等于height[i].class Solution {
public:int trap(vector<int>& height) {stack<int> sta;int res=0;for(int i=0;i<height.size();i++){while(!sta.empty()&&height[i]>height[sta.top()]){//维护一个单调递减栈int lowheight=height[sta.top()];sta.pop();if(sta.empty()) break;int left=sta.top();int curwidth=i-left-1;int curheight=min(height[i],height[left])-lowheight;res+=curheight*curwidth;}sta.push(i);}return res;}
};

43.字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例：
输入: num1 = "123", num2 = "456"
输出: "56088"```

说明：
num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

处理思路： num1存放长的数，num2存放短的数，如果
比如561x21,那么str[]={1,6,5}  {0,2,2,1,1},（num1和num2每位相乘的结果进行逆序存储，还要补0 哦）计算的时候1 6 5
+ 0 2 2 1 1
————————————1 8 7 1 1  计算也是从左到右计算啊，进位也是向右进位
之后再翻转得最终结果为11781999x9991 9 9 8
+  0 1 9 9 8
+  0 0 1 9 9 8
——————————————————1 0 0 8 9 9  计算是从左到右计算的！ 进位也是向右进位！    class Solution {
public:string multiply(string num1, string num2) {vector<vector<int>> str(110);int cnt=0,flag=0,maxsz=0,tmp=0,up=0,val=0;if(num2.size()>num1.size()) swap(num1,num2);//num1存长的，num2存短的if(num2=="0"||num1=="0") return "0";//是0直接返回for(int i=num2.size()-1;i>=0;i--){for(int k=0;k<flag;k++) str[cnt].push_back(0);//num2因数位置越高，越需要补充更多的0up=0;tmp=0;for(int j=num1.size()-1;j>=0;j--){tmp=(int)(num2[i]-'0')*(int)(num1[j]-'0')+up;up=tmp/10;val=tmp%10;str[cnt].push_back(val);}if(up) str[cnt].push_back(up);int sz=str[cnt].size();maxsz=max(maxsz,sz);//记录num1和num2每位相乘后的所有结果中的最长长度cnt++;flag++;}string res;tmp=0,up=0;//列式相加，同一列的相加for(int i=0;i<maxsz;i++){for(int j=0;j<num2.size();j++){if(i<str[j].size())  tmp+=str[j][i];   }up=tmp/10;val=tmp%10;char c=val+'0';res.push_back((char)(val+'0'));tmp=up;}if(up) res.push_back((char)(up+'0'));//前面的计算其实都是基于逆序计算的，现在计算出来的结果也是逆序存储的，所以最后需要调换顺序。int left=0,right=res.size()-1;while(left<right){swap(res[left],res[right]);left++;right--;}return res;}
};

44.通配符匹配

给定一个字符串 (s) 和一个字符模式 § ，实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。

'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。

两个字符串完全匹配才算匹配成功。
说明：

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".s = ""
p = "********"
输出: true

自己用递归做，真是太伤脑筋了，debug了好久都只是通过了1200+个测试点，真的累了！下面这是官方题解做法。
dp[i][j]表示s的前i个字符和前j个字符匹配成功了！
如果p[j]是问号，那么对s[i]没有任何要求，状态转移方程为：dp[i][j]=dp[i-1][j-1];
如果p[j]是星号，那么对s[i]没有任何要求，星号可以匹配零或任意多个小写字母，因此状态转移方程分为两种情况，就是使用这个星号dp[i][j-1]或不使用这个星号dp[i-1][j]

当然也有更加便于理解的动态规划表格描述：
https://leetcode-cn.com/problems/wildcard-matching/solution/yi-ge-qi-pan-kan-dong-dong-tai-gui-hua-dpsi-lu-by-/

class Solution {
public:bool isMatch(string s, string p) {int m=s.size(),n=p.size();vector<vector<int>> dp(m+1,vector<int>(n+1,0));//dp[i][j]:s中前i个和p中前j个匹配//dp[i][0]恒为0，恒为假dp[0][0]=1;for(int i=1;i<=n;i++){if(p[i-1]=='*') dp[0][i]=1;//else break;}for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(p[j-1]=='*') dp[i][j]=dp[i][j-1]|dp[i-1][j];else if(p[j-1]=='?'||s[i-1]==p[j-1]) dp[i][j]=dp[i-1][j-1];}}return dp[m][n];}};

45.跳跃游戏 II （贪心）

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

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

贪心策略1：O(n^2)   比较好理解，但是复杂度过高
我们先找到能抵达数组最后一个位置的最后一步的起点，然后再找倒数第二步，倒数第三步，，，
如果有多个位置通过跳跃都能抵达同一目的，那么我们就选择距离目的最远的位置，也就是对应下标最小的那个位置。
因此，我们可以从左到右遍历数组，选择第一个满足要求的位置。找到最后一步跳跃前所在的位置之后，我们继续贪心
地寻找倒数第二步跳跃前所在的位置，以此类推，直到找到数组的开始位置。
class Solution {
public:int jump(vector<int>& nums) {int nowpos=nums.size()-1,res=0;;while(nowpos>0){for(int i=0;i<nums.size();i++){if(nums[i]+i>=nowpos){nowpos=i;res++;break;}}}return res;}
};贪心策略2：（不太好理解！ 真是绕不明白，交给时间吧） 前面方法中是从左到右找到倒数步骤的位置，先找倒数第一个位置，
然后倒数第二个，倒数第三个，倒数第四个等等。这里也是贪心，本质上是策略1的一个升级，这里直接正向找，找到当前位置
能去的所有下一个位置中能抵达最远的作为下一个位置，定义一个maxpos记录当前位置能抵达最远的下标位置，记为边界，我
们从左到右遍历数组，到达边界时，更新边界并将跳跃次数增加1，注意哦！ 我们不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后
一个位置了。如果访问最后一个元素，在边界正好为最后一个位置的情况下，我们会增加一次「不必要的跳跃次数」，因此我们不必访
问最后一个元素。图解见下图：class Solution {
public:int jump(vector<int>& nums) {int maxpos=0,end=0,res=0;for(int i=0;i<nums.size()-1;i++){maxpos=max(maxpos,i+nums[i]);//目前能跳到的最远位置if(i==end){//跳到上次跳跃能到达的右边界了end=maxpos; res++;//目前能跳到的最远位置就变成了下次起跳的起始位置，进入下一次跳跃res++;}}return res;}
};

46.全排列（两种模板）

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

输入：nums = [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>> res;permuteDo(res,nums,0,nums.size());return res;}void permuteDo(vector<vector<int>>&res,vector<int>nums,int k,int m){if(k==m){res.push_back(nums);return;}for(int i=k;i<m;i++){swap(nums[i],nums[k]);permuteDo(res,nums,k+1,m);swap(nums[i],nums[k]);}}
};上面的写法是我数据结构课本上教的，但是这种写法只适合纯全排列的，一旦有一些附属条件比如去重的全排列，就不太方便了，
因为它改了原nums，关于全排列，还有一种写法，这种写法更适合剪枝，适合剪枝这个在下一题尤其能体现。class Solution {
public:vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> res;vector<int> tmp;vector<int> vis(nums.size(),0);//vis标记nums该索引位置的值是否已被选中了permuteDo(res,nums,tmp,vis,0);//这个0表示我们在处理第0个位置return res;}void permuteDo(vector<vector<int>>&res,vector<int>nums,vector<int>&tmp,vector<int>&vis,int k){if(k==nums.size()){res.push_back(tmp);return;}for(int i=0;i<nums.size();i++){if(vis[i]) continue;//这个值已被选中，不再处理tmp.push_back(nums[i]);//假如选中这个，那么就push并vis标记vis[i]=1;permuteDo(res,nums,tmp,vis,k+1);//再处理下一个位置vis[i]=0;//假如不选中这个，那么pop出去并vis标记tmp.pop_back();}}
};

47.全排列 II（序列不重模板）

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

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

这种求全排列写法，我在上面已经提道了，理解起来不会很麻烦，这道题相对于上道题其实就是要先排序再加一个if语句进
行剪枝就好，排序的目的就是让重复值出现在相邻位置
if(vis[i]||(i>0&&nums[i]==nums[i-1]&&vis[i-1])) continue;
如果当前nums[i] i 这个位置的值已经被访问过，那么就不会再选这个值，如果这个值和前一个值相等且前一个值已经被访
问了，那么也不会再选这个值。通过剪枝实现去重是可以优先考虑的算法，不建议把所有的排列求出来然后去整体去重。class Solution {
public:vector<vector<int>> permuteUnique(vector<int>& nums) {vector<vector<int>> res;vector<int> tmp;vector<int> vis(nums.size()+1,0);sort(nums.begin(),nums.end());permuteDo(res,nums,tmp,vis,0,nums.size());return res;}void permuteDo(vector<vector<int>>&res,vector<int>nums,vector<int>& tmp,vector<int> vis,int k,int m){if(k==m){res.push_back(tmp);return;}for(int i=0;i<m;i++){if(vis[i]||(i>0&&nums[i]==nums[i-1]&&vis[i-1])) continue;//这个值被访问过或者相邻相等的值之前已经有被选择了的tmp.push_back(nums[i]);vis[i]=1;permuteDo(res,nums,tmp,vis,k+1,m);vis[i]=0;tmp.pop_back();}}
};

48.旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

解析：[i,j]位置应该旋转至[n-1-j,i]，但是如果每次只调换两个数字的位置，明显是不对的，这里我们考虑四个单位一起换！！！ 这是我以前没有遇到的。四个位置一起换位置，就能轻松解决问题，唯一需要注意的是，由于我们每次处理会导致矩阵中四个位置都处理完毕，所以我们不能对矩阵中每个数字都去遍历处理。

class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n=matrix.size();for(int i=0;i<n/2;i++){for(int j=0;j<(n+1)/2;j++){int tmp=matrix[i][j];matrix[i][j]=matrix[n-1-j][i];matrix[n-1-j][i]=matrix[n-1-i][n-1-j];matrix[n-1-i][n-1-j]=matrix[j][n-1-i];matrix[j][n-1-i]=tmp;}}}
};

解析2：还有一种方法，这种就主要是规律，先以行为单位进行调整，将行从原顺序调整至倒序，然后按照主对角线交换两边的元素，也要注意不要每个数字都遍历处理

class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n=matrix.size();for(int i=0;i<n/2;i++){for(int j=0;j<n;j++){int tmp=matrix[i][j];matrix[i][j]=matrix[n-1-i][j];matrix[n-1-i][j]=tmp;}}for(int i=0;i<n;i++){for(int j=i+1;j<n;j++) {int tmp=matrix[i][j];matrix[i][j]=matrix[j][i];matrix[j][i]=tmp;}}}
};

49. 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母都恰好只用一次。

示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

多个字符串如果经过排序后相等，说明这些字符串就可以归为一组。
但是注意要定义一个临时变量复制原变量，然后对临时变量去排序！不要把原字符串给改了。。
class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string,vector<string>> mp;vector<vector<string>> ans;for(const string & str:strs){string tmp=str;sort(tmp.begin(),tmp.end());mp[tmp].push_back(str);}for(auto it=mp.begin();it!=mp.end();it++)  ans.push_back(it->second);return ans;}
};还有一种方法是字符计数

50.pow(x,n) （快速幂）

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，x^n）。

示例1：
输入：x = 2.00000, n = 10
输出：1024.00000

借助整数的二进制拆分，就可以得到迭代计算的方法，一般地，如果整数 n 的二进制拆分为
$n=2^{i_0}+2^{i_1}+2^{i_2}+...+2^{i_k}$,
那么$x^n=x^{2^{i_0}}\times x^{2^{i_1}}\times x^{2^{i_2}}\times ...\times x^{2^{i_k}}$

class Solution {
public:double myPow(double x, int n) {if(n==0) return 1.0;if(n==INT_MIN) return 1.0/(x*quickMul(x,INT_MAX));//这个问题特殊考虑，因为INT_MIN相反数会溢出else if(n<0) return 1.0/quickMul(x,0-n);return quickMul(x,n);}double quickMul(double x,int n){double res=1.0,step=x;//step表示贡献值，该位为1时候就乘上while(n>0){if(n%2) res*=step;step*=step;//这里初做时竟然不理解，但是后来在纸上演算就明白了，其实就是在获取贡献值n=n/2;}return res;}
};

53.最大子序和

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

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

不解释了，这题都做了多少遍了，要是还不懂，简直无药可救。
想复习的话可以去剑指offer复习。hahahahaha...class Solution {
public:int maxSubArray(vector<int>& nums) {int sum=0,maxAns=INT_MIN;for(int i=0;i<nums.size();i++){sum+=nums[i];if(sum<nums[i]) sum=nums[i];maxAns=max(sum,maxAns);}return maxAns;}
};

54.螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

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

这道题之前也做过，其实很简单，细致一点就ok，下面是我的方法，看了力扣题解，大概也差不多，复杂度是O(mn)
class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {int row=matrix.size(),col=matrix[0].size();int ibegin=0,jbegin=0,iend=row-1,jend=col-1,cnt=0;vector<int> res;while(cnt<row*col){for(int j=jbegin;j<=jend;j++) {res.push_back(matrix[ibegin][j]); cnt++;}//圈中第一行for(int i=ibegin+1;i<=iend;i++) {res.push_back(matrix[i][jend]);cnt++;}if(iend!=ibegin){for(int j=jend-1;j>=jbegin;j--) {res.push_back(matrix[iend][j]);cnt++;}}if(jend!=jbegin){for(int i=iend-1;i>ibegin;i--) {res.push_back(matrix[i][jbegin]);cnt++;}}ibegin++;iend--;jbegin++;jend--;}return res;}
};

55.跳跃游戏

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

解析：这道题和45题有些相似，但这道题难度降低了，可以比对着去理解题意。

class Solution {
public:bool canJump(vector<int>& nums) {int end=0,maxDis=0;for(int i=0;i<nums.size();i++){  //这里不再是<nums.size()-1了哈，前面万一数组是[0]呢？，如果数组只有一个值，那么只需要跳0步，也是true的，上面45题之所以要<nums.size()-1，是因为如果数组中只有一个值，那么就直接返回res=0,如果<nums.size()，那么就要对res平白加1了。if(i<=maxDis) maxDis=max(maxDis,nums[i]+i);if(maxDis>=nums.size()-1) return 1;}return 0;}
};

56.合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

这道题以前学习程序设计的时候接触过，思路就是排序，先按左边值升序排序，如果左边值相等，就按照右边值降序排序。class Solution {
public:static bool cmp(vector<int> num1,vector<int> num2){if(num1[0]<num2[0]) return 1;if(num1[0]==num2[0]) return num1[1]>num2[1];return 0;}vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> res;sort(intervals.begin(),intervals.end(),cmp);int start=intervals[0][0],end=intervals[0][1];for(int i=1;i<intervals.size();i++){if(intervals[i][0]>=start&&intervals[i][0]<=end&&intervals[i][1]>end) end=intervals[i][1];if(intervals[i][0]>end){res.push_back({start,end});start=intervals[i][0]; end=intervals[i][1];}}res.push_back({start,end});return res;}
};

57.插入区间

给你一个 无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

class Solution {
public:vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {vector<vector<int>> res;int left=newInterval[0],right=newInterval[1];for(int i=0;i<intervals.size();i++)   {//找到插入newInterval后区间合并的新区间if(newInterval[0]>=intervals[i][0]&&newInterval[0]<=intervals[i][1]) left=intervals[i][0];if(newInterval[1]>=intervals[i][0]&&newInterval[1]<=intervals[i][1]) right=intervals[i][1];}int flag=-1;for(int i=0;i<intervals.size()&&intervals[i][1]<left;i++){//插入[left,right]左边的区间res.push_back(intervals[i]); flag=i;}res.push_back({left,right});//插入[left,right]for(int i=flag+1;i<intervals.size();i++){//插入[left,right]右边的区间if(intervals[i][0]<=right) continue;res.push_back(intervals[i]);}return res;}
};

58.最后一个单词的长度

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中最后一个单词的长度。
单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

示例1：
输入：s = "   fly me   to   the moon  "
输出：4

class Solution {
public:int lengthOfLastWord(string s) {int i=0,cnt=0;for(i=s.size()-1;i>=0&&s[i]==' ';i--);for(int j=i;j>=0&&s[j]!=' ';j--) cnt++;return cnt;}
};

61.旋转链表

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

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

输入：head = [0,1,2], k = 4
输出：[2,0,1]

思路：闭合为环，之后找到新的头结点，让头结点的前驱节点指向空（环由此断开）。注意k可能很大，要旋转好几个圈，所以k对
链表长度求余。
class Solution {
public:ListNode* rotateRight(ListNode* head, int k) {if(head==NULL||head->next==NULL||k==0) return head;ListNode*cur=head,*par=NULL;int LenOfList=1;while(cur->next!=NULL) {LenOfList++; cur=cur->next;}cur->next=head;//闭合为环k=k%LenOfList;if(k==0) {cur->next=NULL;return head;}//注意这里返回的时候要把环断开cur=head;for(int i=0;i<LenOfList-k;i++) {par=cur;cur=cur->next;}//找新的头节点par->next=NULL;//断开环return cur;}
};

62.不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m,vector<int>(n,0));for(int i=0;i<m;i++) dp[i][0]=1;for(int j=0;j<n;j++) dp[0][j]=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

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m=obstacleGrid.size(),n=obstacleGrid[0].size();vector<vector<int>> dp(m,vector<int>(n,0));if(!obstacleGrid[0][0]) dp[0][0]=1;for(int i=1;i<m;i++) if(!obstacleGrid[i][0]&&dp[i-1][0]) dp[i][0]=1;//这里边界值和上一题不一致的，上一题的边界都是1，但是这里可能出现障碍，可能导致[i,j]这个位置根本无法抵达。for(int j=1;j<n;j++) if(!obstacleGrid[0][j]&&dp[0][j-1]) dp[0][j]=1;for(int i=1;i<m;i++){for(int j=1;j<n;j++) {if(obstacleGrid[i][j]) dp[i][j]=0;//多了一步判断是否是阻碍的语句else dp[i][j]=dp[i-1][j]+dp[i][j-1];}}return dp[m-1][n-1];}
};

64.最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m=grid.size(),n=grid[0].size();vector<vector<int>> dp(m,vector<int>(n,0));dp[0][0]=grid[0][0];for(int i=1;i<m;i++) dp[i][0]=dp[i-1][0]+grid[i][0];for(int j=1;j<n;j++) dp[0][j]=dp[0][j-1]+grid[0][j];for(int i=1;i<m;i++){for(int j=1;j<n;j++){dp[i][j]=grid[i][j]+min(dp[i-1][j],dp[i][j-1]);}}return dp[m-1][n-1];}
};但是但是但是！ 其实不用额外申请一个dp，直接在grid上进行处理即可 ！！ ~~~
class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m=grid.size(),n=grid[0].size();for(int i=1;i<m;i++) grid[i][0]=grid[i-1][0]+grid[i][0];for(int j=1;j<n;j++) grid[0][j]=grid[0][j-1]+grid[0][j];for(int i=1;i<m;i++){for(int j=1;j<n;j++){grid[i][j]+=min(grid[i-1][j],grid[i][j-1]);}}return grid[m-1][n-1];}
};

66.加一（找最长后缀9）

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。

先奉上我的笨蛋方法，这可以说是毫无算法思维可言，就是刻板思维，硬解
class Solution {
public:vector<int> plusOne(vector<int>& digits) {int idx=digits.size()-1;int tmp=(digits[idx]+1)%10;int up=(digits[idx]+1)/10;digits[idx]=tmp;idx--; while(up>0&&idx>=0){tmp=(digits[idx]+up)%10;up=(digits[idx]+up)/10;digits[idx]=tmp;idx--;}if(up){digits.push_back(0);for(int i=digits.size()-2;i>=0;i--)  digits[i+1]=digits[i];digits[0]=up;}return digits;}
};找最长后缀9即从后往前找到第一个不是9的数字 ，比如[2,3,4,9,9,9]，找到4，对4加1，然后其后全部置0
class Solution {
public:vector<int> plusOne(vector<int>& digits) {int sz=digits.size();for(int i=sz-1;i>=0;i--){if(digits[i]!=9){ digits[i]++;//加1for(int j=i+1;j<sz;j++) digits[j]=0;//后面置0return digits;}}//能走到这里，说明是一串全9vector<int> res(sz+1,0);res[0]=1;return res;}
};

67.二进制求和

给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为 非空 字符串且只包含数字 1 和 0。

我的思路如下，就还是硬解。先把字符串倒置，再从头处理到尾，就相当于从低位处理到高位，但这样有必要吗？？ 没必要！
这个算法可以说是很笨了，但是还是有借鉴的地方，比如我发现进位值up=up&num_a|up&num_b|num_a&num_b，哈哈哈哈，不过
好似没什么作用？？？
进位值可以参考剑指offer下第48题，可以知道。
answer = x ^ y
carry = (x & y) << 1另外就是可以不用位运算，而是对和除以2存下除数和余数，除数即为进位，余数即为该位相加后的值。class Solution {
public:string addBinary(string a, string b) {Reverse(a);Reverse(b);string res;int up=0,tmp=0,sz_a=a.size(),sz_b=b.size();for(int i=0;i<min(sz_a,sz_b);i++){int num_a=a[i]-'0',num_b=b[i]-'0';tmp=up^num_a^num_b;up=up&num_a|up&num_b|num_a&num_b;res.push_back(char(tmp+'0'));}for(int i=min(sz_a,sz_b);i<sz_a;i++){int num_a=a[i]-'0';tmp=up^num_a;up=up&num_a;res.push_back(char(tmp+'0'));}for(int i=min(sz_a,sz_b);i<sz_b;i++){int num_b=b[i]-'0';tmp=up^num_b;up=up&num_b;res.push_back(char(tmp+'0'));}if(up) res.push_back(char(up+'0'));Reverse(res);return res;}void Reverse(string &a){int left=0,right=a.size()-1;while(left<right){swap(a[left],a[right]);left++;right--;}}
};

69.Sqrt(x) （二分模板3&2）

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

之前是用的模板2，然后惊奇地发现，long long mid=(l+r+1)/2，这里竟然死活报错，大概是因为如果r=INT_MAX，
那么+1就会出错，也有解决办法，比如1存成long long,见第二份题解。class Solution {
public:int mySqrt(int x) {int left=0,right=x,res=0;while(left<=right){//要取等的哈 ！int mid=left+ (right-left) / 2;if((long long)mid*mid<=x) res=mid,left=mid+1;else right=mid-1;}return res;}
};class Solution {
public:int mySqrt(int x) {int left=0,right=x;long long one=1;while(left<right){long long  mid=(left+right+one) / 2;if(mid*mid<x) left=mid;else if(mid*mid>x) right=mid-1;else return mid;} return left;}
};

70.爬楼梯

略，这题做多少次了。。。

71.简化路径（getline切割）

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 ‘/’ 开头），请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （…） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，’//’）都被视为单个斜杠 ‘/’ 。 对于此问题，任何其他格式的点（例如，’…’）均被视为文件/目录名称。

请注意，返回的 规范路径 必须遵循下述格式：
1).始终以斜杠 ‘/’ 开头。
2).两个目录名之间必须只有一个斜杠 ‘/’ 。
3).最后一个目录名（如果存在）不能 以 ‘/’ 结尾。
此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 ‘.’ 或 ‘…’）
返回简化后得到的规范路径。

输入：path = "/a/./b/../../c/"
输出："/c"

其实很简单的思路，可不要想什么建立树啊啥的，duck不必，按照'/'切割，切割后路径名的就存入数组，是'.'的就省略不管，
是'..'的就返回上一级即删除数组最后一个路径名。最后这个数组就是我们要的路径了，另外就是要注意特殊情况"/../"以及
最后结果记得加上"/"class Solution {
public:string simplifyPath(string path) {vector<string> sta;stringstream ss;ss<<path;string easyPath;while(getline(ss,easyPath,'/')){//这个知识点掌握一下，切割！if(easyPath!=""&&easyPath!=".."&&easyPath!=".") sta.push_back(easyPath);if(!sta.empty()&&easyPath=="..") sta.pop_back();}string res="";if(sta.empty()) return "/";for(auto it:sta) res=res+"/"+it;return res;}
};

72.编辑距离

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
——插入一个字符
——删除一个字符
——替换一个字符

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

本质不同的操作实际上只有三种：
在单词 A 中插入一个字符（等价在B中删除一个字符）；
在单词 B 中插入一个字符（等价在A中删除一个字符）；
修改单词 A 的一个字符（等价在B中修改一个字符）。
定理一：如果其中一个字符串是空串，那么编辑距离是另一个字符串的长度。
定理二：当i>0,j>0时（即两个串都不空时）dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+
(word1[i-1]==word2[j-1]?0:1))。dp[i-1][j-1]这里比较的是word1[i-1]和word2[j-1]，而不是
word1[i]和word2[j]。class Solution {
public:int minDistance(string word1, string word2) {int m=word1.size(),n=word2.size();vector<vector<int> > dp(m+1,vector<int>(n+1,0));for(int i=0;i<=n;i++) dp[0][i]=i;for(int i=0;i<=m;i++) dp[i][0]=i;for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)dp[i][j]=min(min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+(word1[i-1]==word2[j-1]?0:1));return dp[m][n];}
};

73.矩阵置0

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

进阶：
一个直观的解决方案是使用  O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个仅使用常量空间的解决方案吗？

空间复杂度O(M+N) 使用set,记录下来原本有0的行，原本有0的列，然后对这行里所有的数字置为0，对这列的所有数字置为0
class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {int m=matrix.size(),n=matrix[0].size();set<int> row,col;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(!matrix[i][j]) {row.insert(i);col.insert(j);}}}for(auto cur:col)for(int i=0;i<m;i++) matrix[i][cur]=0;for(auto cur:row)for(int i=0;i<n;i++) matrix[cur][i]=0;}
};空间复杂度O(1)
思路就是用两个标记变量来记录第0行的数据和第0列的数据原本有没有1，有1的话就进行标记，在最后要对第0行和第0列进行置0的
之后根据第m行第n列（m>0,n>0）来进行标杆初始化，其实就相当于把第0行和第0列作为标杆了，把matrix[i][j]平移至matrix[i][0]和
matrix[0][j]处理。
之后再根据标杆即第0行和第0列的数据来对m行n列（m>0,n>0）进行置0。
最后那两个标记量的作用就体现了，如果第0行的数据中/第0列的数据中存在0，那么整个第0行/第0列的数据就都要置为0.
class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {int m=matrix.size(),n=matrix[0].size();int flagRow0=0,flagCol0=0;for(int i=0;i<m;i++)if(!matrix[i][0]) flagCol0=1;//第0列是否有0for(int i=0;i<n;i++)if(!matrix[0][i]) flagRow0=1;//第0行是否有0for(int i=1;i<m;i++){for(int j=1;j<n;j++){if(!matrix[i][j]) matrix[i][0]=matrix[0][j]=0;//第0行的数据，第0列的数据作为标杆}}for(int i=1;i<m;i++){for(int j=1;j<n;j++){if(!matrix[i][0]||!matrix[0][j]) matrix[i][j]=0;//用标杆来决定其他是否要赋值为0 }}if(flagRow0){for(int i=0;i<n;i++) matrix[0][i]=0;}if(flagCol0){for(int i=0;i<m;i++) matrix[i][0]=0;}}
};

74.搜索二维矩阵

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

1. 每行中的整数从左到右按升序排列。
2. 每行的第一个整数大于前一行的最后一个整数。

示例1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

我自己做只知道用二分，也不错了，是一大进步！数组每行每列都是升序，先二分查找第0列，找到目的数所在行，然后再对这一行进行二分查找。
复杂度O(logM+logN)
但其实这个方法没有使用到题目中的这个条件“每行的第一个整数大于前一行的最后一个整数”，其实数组每行拼接起来就是一个大的升序，直接对
这一个升序进行二分即可。
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m=matrix.size(),n=matrix[0].size(),flagRow=-1;int top=m-1,low=0;while(low<top){//二分模板2int mid=(low+top+1)/2;if(matrix[mid][0]>target) top=mid-1;else if(matrix[mid][0]<target) low=mid;else{ flagRow=mid;break;}}if(flagRow==-1){if(matrix[low][0]<target) flagRow=low;if(matrix[low][0]==target) return true;}cout<<"flagRow:"<<flagRow<<"\n";if(flagRow==-1) return false;top=n-1,low=0;//对flagRow行进行二分查找while(low<=top){//二分模板3int mid=low+(top-low)/2;if(matrix[flagRow][mid]<target) low=mid+1;else if(matrix[flagRow][mid]>target) top=mid-1;else return true;}return false;}
};方法2：拼接成一个升序，再进行二分，不会傻到再去开一个数组专门存储拼接好后的数组吧，不会吧不会吧！！！ 
使空间复杂度O(1)是基本哈！  如何根据mid在原二维数组matrix中找到对应数字呢，使用：
int x = matrix[mid / n][mid % n];class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size(), n = matrix[0].size();int low = 0, high = m * n - 1;while (low <= high) {int mid = (high - low) / 2 + low;int x = matrix[mid / n][mid % n]; //这一步！！ 要好好学习！if (x < target)   low = mid + 1;else if (x > target)   high = mid - 1;else  return true;}return false;}
};

75.颜色分类

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
你可以不使用代码库中的排序函数来解决这道题吗？
你能想出一个仅使用常数空间的一趟扫描算法吗？

示例1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

如果不要求只遍历一趟，那我其实可以先把0调到前面，第二次遍历把1调到0后面，但是这遍历了两遍，与题意不符。

照例还是先摆出我自己的垃圾代码，平心而论，代码虽然很烂，但是我觉得进步了，题目要求原地重排、使用常数空间以及一趟扫描，
我这份代码都满足这些要求，但是时间上只击败了40%+，所以真的还是有很大进步空间。下面还是讲讲我这份代码的思路。
我选择只处理0，1，把0往数组头调，把2往数组尾调，那么最后，1自然就被弄到中间去了。
代码第一步：过滤数组首部0，尾部2，之后只处理被掐去首位的数组。
代码第二步：tailIndx0实时标记当前数组中从头到尾第一个不为0的位置，fronIdx2实时记录当前数组中从尾到头第一个不为2的位置。
所以每次数组中遇到0就把它与tailIdx0位置交换，遇到2就与frontIdx2位置交换。数组实时变化就是0,0...0,xxxx,2...2细节注意1：交换之后要对i--，因为从frontIdx2/tailIdx0位置来的数字还需要同样的调换，而for中自动就++了，如果不用i--，新
调换来的数字就可能漏处理。
细节处理2：交换0时，要判断i!=tailIdx0,如果i=taiIdx0了，我们对其交换无意义并且此时tailIdx0值应该不变不能进行++。
class Solution {//双指针
public:void sortColors(vector<int>& nums) {if(nums.size()==1) return;int tailIdx0=0,frontIdx2=nums.size()-1;for(tailIdx0=0;tailIdx0<nums.size()&&nums[tailIdx0]==0;tailIdx0++);//过滤前导0for(frontIdx2=nums.size()-1;frontIdx2>=0&&nums[frontIdx2]==2;frontIdx2--);//过滤尾部2int begin=tailIdx0,end=frontIdx2;for(int i=begin;i<=frontIdx2;i++){//处理中间部分if(nums[i]==2) {swap(nums[i],nums[frontIdx2--]);i--;}else if(nums[i]==0&&i!=tailIdx0) {swap(nums[i],nums[tailIdx0++]);i--;}}}
};但其实真的需要那么复杂吗？？ 大多数题解跟我的思路差不多，都是用双指针，但是可以有更简洁易懂的方法，如下：
class Solution {
public:void sortColors(vector<int>& nums) {int sz=nums.size();int p=0,q=sz-1;//头尾指针for(int i=0;i<=q;i++){//是小于等于q,不是nums.size,否则可能把尾的2又调回去了if(nums[i]==0) swap(nums[i],nums[p++]);//把0调到前面if(nums[i]==2){//把2调到后面，注意这里没有else,相当于第一个if进行调换后，如果调来的新数字等2，那么就进入这个循环swap(nums[i],nums[q--]);if(nums[i]!=1) i--;//如果新来的数字是0或者2，那么这个数字肯定还得进行上述相同处理，为了以防for中i++将其跳过导致漏处理，这里要i--去抵消i++}}}
};

77.组合（模板：注意剪枝）

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。

示例1：
输入：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) {combination(1,n,k);return res;}void combination(int num,int n,int cnt){if(cnt==0){res.push_back(tmp); return;}if(num>n) return;tmp.push_back(num);combination(num+1,n,cnt-1);tmp.pop_back();combination(num+1,n,cnt);}
private:vector<vector<int>> res;vector<int> tmp;
};题解剪枝代码：
class Solution {
public:vector<vector<int>> combine(int n, int k) {combination(1,n,k);return res;}void combination(int num,int n,int cnt){       if(tmp.size()==cnt){res.push_back(tmp); return;}if(tmp.size()+n-num+1<cnt) return;  //如果余下可选的数字个数不够，那么完全就可以终止了,这里是n-num+1哈，别忘了加1，因为在判断这个的时候，num这个数字还未push到tmp中，所以应该是n-(num-1)//if(num>n) return;  //上面那个if判断其实可以覆盖这里这个条件，所以这个剪枝可以省略tmp.push_back(num);combination(num+1,n,cnt);tmp.pop_back();combination(num+1,n,cnt);}
private:vector<vector<int>> res;vector<int> tmp;
};

78.子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

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

class Solution {
public:vector<vector<int>> subsets(vector<int>& nums) {for(int i=0;i<=nums.size();i++){combination(nums,0,i);}return res;}void combination(vector<int>nums,int idx,int cnt){if(tmp.size()==cnt) {res.push_back(tmp);return;}if(tmp.size()+nums.size()-idx<cnt) return;tmp.push_back(nums[idx]);combination(nums,idx+1,cnt);tmp.pop_back();combination(nums,idx+1,cnt); }
private:vector<vector<int> >res;vector<int> tmp;
};

79.单词搜索（目前还是超时）

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

救那个大命了，没有pass，超时了！！
这里做个笔记，类似于这种dfs要进行返回值时，我都会被返回值绕晕，返回再返回，我得到了正确值要用return结束函数了，结果又返回到
原断点处，直接绕晕。之后看了别人的代码后，学到了一个小技巧，下面这种写法间接易理解，尤其是下面这句话：
bool res=dfs(board,word,i+1,j,k+1)||dfs(board,word,i-1,j,k+1)||dfs(board,word,i,j-1,k+1)||dfs(board,word,i,j+1,k+1);
按照我之前的写法如下，这个返回值是真的特别令人头疼，怪我学艺不精，基础都不扎实
for(int k=0;k<4;k++){int x=i+dx[k],y=j+dy[k];if(x..||y..||..||..||) dfs(x,y)
}但是下面这份代码，我自认为没问题了，但是超时，这道题我耗费太多时间了，不想再卡这里了，以后再说吧。
class Solution {
public:bool exist(vector<vector<char>>& board, string word) {for(int i=0;i<board.size();i++){//找到等于word[0]的，然后以此为起点进行dfsfor(int j=0;j<board[0].size();j++){if(board[i][j]==word[0])  {if(dfs(board,word,i,j,0))  return 1;}}}return 0;}bool dfs(vector<vector<char>>board,string word,int i,int j,int k){if(k==word.size()) return 1;if(i<0||j<0||i>=board.size()||j>=board[0].size()) return 0;if(word[k]!=board[i][j]) return 0;//返回原断点char tmp=board[i][j];board[i][j]='0';bool res=dfs(board,word,i+1,j,k+1)||dfs(board,word,i-1,j,k+1)||dfs(board,word,i,j-1,k+1)||dfs(board,word,i,j+1,k+1);board[i][j]=tmp;//恢复这个值，便于exist函数中，下一个起点的dfsreturn res;}
};

80.删除有序数组中的重复项II

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素。

有进步啊！ 写得可以！
class Solution {
public:int removeDuplicates(vector<int>& nums) {int idx=1,flag=nums[0],cnt=1;for(int i=1;i<nums.size();i++){if(nums[i]!=flag){ flag=nums[i];cnt=1;}else cnt++;if(cnt>=3) {continue;}nums[idx++]=nums[i];}return idx;}
};