# leetcode C++

2020年05月09日 阅读数：707

### 文章目录

C++版的leetcode，从头再来！java

# 1.两数之和(hash)

class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int length = sizeof(nums)/sizeof(nums[0]);
for(int i = 0;i < length;++i)
for(int j = 0; j<length;++i)
if (nums[i] + nums[j] == target)
{

return {nums[i],nums[j]};
}

}
};


class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int length = nums.size();
vector<int> ans;
for(int i = 0;i < length;i++)
for(int j = i + 1; j<length;j++)
if (nums[i] + nums[j] == target)
{
ans.push_back(i);
ans.push_back(j);
return ans;
}
return ans;
}
};


1.一个函数是必须有返回值的，若是只有if里加了return，当出现else的 状况这个函数就没有了，因此要加else，要么最后加return也行；
2.返回一个列表时，能够定义一个容器来装
3.计算数组长度用size（）函数；

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

unordered_map<int,int> m;

for(int i=0;i<nums.size();i++)
m[nums[i]] = i;         //向map中添加元素

for(int i=0;i<nums.size();i++)
{
if(m.find(target-nums[i]) != m.end() && m[target-nums[i]] != i)     //若是m中存在对应的键值，而且不为i，后面这个条件很重要，由于会有重复的元素
return {i , m[target-nums[i]]};
}
return {};
}
};



# 2. 两数相加(链表)

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* temp1 = l1;
int len1 = 0;
while(temp1)
{
temp1 = temp1->next;
len1++;
}
ListNode* temp2 = l2;
int len2 = 0;
while(temp2)
{
temp2 = temp2->next;
len2++;
}
temp1 =l1;
while(temp1->next)
{
temp1 = temp1->next;
}
temp2=l2;
while(temp2->next)
{
temp2=temp2->next;
}
while(len1 <len2)
{
ListNode* zero = new ListNode(0);
temp1->next=zero;
temp1 = zero;
len1++;
}
while(len2<len1)
{
ListNode* zero = new ListNode(0);
temp2->next = zero;
temp2 = zero ;
len2++;
}
temp1=l1;
temp1 = temp1->next;
temp2=l2;
temp2 = temp2->next;
while(len1-1)
{
ListNode* cur = new ListNode(temp1->val+temp2->val);
temp1=temp1->next;
temp2=temp2->next;
temp->next = cur;
temp = cur;
len1--;
}
while(temp->next)
{
if(temp->val>=10)
{
temp->val -=10;
temp->next->val +=1;
}
temp =temp->next;
}
if(temp->val>=10)
{
ListNode* zero = new ListNode(1);
temp->val -=10;
temp->next = zero;
}
}
};


/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int len1=1;//记录l1的长度
int len2=1;//记录l2的长度
ListNode* p=l1;
ListNode* q=l2;
while(p->next!=NULL)//获取l1的长度
{
len1++;
p=p->next;
}
while(q->next!=NULL)//获取l2的长度
{
len2++;
q=q->next;
}
if(len1>len2)//l1较长，在l2末尾补零
{
for(int i=1;i<=len1-len2;i++)
{
q->next=new ListNode(0);
q=q->next;
}
}
else//l2较长，在l1末尾补零
{
for(int i=1;i<=len2-len1;i++)
{
p->next=new ListNode(0);
p=p->next;
}
}
p=l1;
q=l2;
bool count=false;//记录进位
ListNode* l3=new ListNode(-1);//存放结果的链表
ListNode* w=l3;//l3的移动指针
int i=0;//记录相加结果
while(p!=NULL&&q!=NULL)
{
i=count+p->val+q->val;
w->next=new ListNode(i%10);
count=i>=10?true:false;
w=w->next;
p=p->next;
q=q->next;
}
if(count)//若最后还有进位
{
w->next=new ListNode(1);
w=w->next;
}
return l3->next;
}
};



# 3. 无重复字符的最长子串（滑动窗口双指针）

class Solution {
public:
int lengthOfLongestSubstring(string s) {
//遍历确定不行，子串表示要连续
//尝试双指针遍历加剪枝
if(s.empty())return 0;
if(s.size()==1)return 1;
int len = s.size();
int max = 1;
for(int i= 0 ; i<len ; i++)
{
set<int> st;
st.insert(s[i]);
for(int j = i+1; j<len ;j++)
{
int k = st.size();
st.insert(s[j]);
if(st.size()==k) break;
if(st.size()>max)max=st.size();
}
}
return max;
}
};


class Solution
{
public:
int lengthOfLongestSubstring(string s)
{
//s[start,end) 前面包含 后面不包含
int start(0), end(0), length(0), result(0);
int sSize = int(s.size());
unordered_map<char, int> hash;
while (end < sSize)
{
char tmpChar = s[end];
//仅当s[start,end) 中存在s[end]时更新start
if (hash.find(tmpChar) != hash.end() && hash[tmpChar] >= start)
{
start = hash[tmpChar] + 1;
length = end - start;
}
hash[tmpChar] = end;

end++;
length++;
result = max(result, length);
}
return result;
}
};



class Solution
{
public:
// 在左闭右开[left,right)的字符串s中，找字符target对应的下标位置，若未找到，则返回-1
int getThePosOfSame(int left, int right, const string& s, char target) const
{
for (int i = left; i < right; i++)
{
if (s[i] == target)
{
return i;
}
}

return -1;
}

int lengthOfLongestSubstring(string s)
{
const int len = s.length();

int max_len = 0;
int i = 0;
int j = 0;

while (j < len)
{
int pos = getThePosOfSame(i, j, s, s[j]);

if (pos == -1)
{
j++;
}
else
{
max_len = (j - i) > max_len ? (j - i) : max_len;

i = pos + 1;
}
}

max_len = (j - i) > max_len ? (j - i) : max_len;

return max_len;
}
};



class Solution {
public:
int lengthOfLongestSubstring(string s) {
//遍历确定不行，子串表示要连续
//尝试双指针遍历加剪枝
if(s.empty())return 0;
if(s.size()==1)return 1;
int len = s.size();
int max = 1;
int i = 0;
int j = 1;
vector<char> temp;
temp.push_back(s[0]);
while(i<len && j<len)
{
if( find(temp.begin(),temp.end(),s[j])==temp.end() )
{
temp.push_back(s[j]);
j++;
if(temp.size()>max)max =temp.size();
}
else
{
int k = find(temp.begin(),temp.end(),s[j])-temp.begin();
i = i+k+1;
j=i+1;
temp.clear();
temp.push_back(s[i]);
}

}
return max;

}
};


# 6.Z 字形变换

1.每行须要创建一个容器存放值
2.可是因为行数是题目给定的，并非常量，因此只能先创建一个二维矩阵，行数就是题目的行数
3.设置在到达边界是当即返回，这个地方还想的不是很清楚
4.可想而知会很是复杂

class Solution {
public:
string convert(string s, int numRows) {

if (numRows == 1) return s;

vector<string> rows(min(numRows, int(s.size())));
int curRow = 0;
bool goingDown = false;

for (char c : s) {
rows[curRow] += c;
if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
curRow += goingDown ? 1 : -1;
}

string ret;
for (string row : rows) ret += row;
return ret;
}
};



# 7.整数反转

class Solution {
public:
int reverse(int x) {
int p = 10;
int n;
long result = 0;
if(x == INT_MIN)
{
return 0;
}
if (x >= 0)
{

while(x > 0)
{
n = x % p;
x = x / p;
result = result*10 + n;
}
if(result > INT_MAX)
{
return 0;
}
return result;

}
else
{
int y = -x;
while(y > 0)
{
n = y % p;
y = y / p;
result = result*10 + n;
}
if(result > INT_MAX)
{
return 0;
}
return -result;
}
}
};


1.INT_MIN ,INT_MAX第一次见
INT_MAX = 2^31-1
INT_MIN= -2^31

2.反转后不用放到容器里而是分离的时候能够直接构成反转数；
3.遇到正反两种状况时不须要分两大类，而是在开头转换就能够，使用一次递归，以下所示

class Solution
{
public:
int reverse(int x)
{
long result(0); //利用long避免溢出
if (x == INT_MIN)
{
return 0;
}
if (x < 0)
{
return -reverse(-x);//当x小于0，再次调用该函数解出x大于0的状况，结果加负号返回
}

int digit(0);
while (x > 0)
{
digit = x % 10;
x /= 10;
result = result * 10 + digit;//这里能够直接返回
}

if (result > INT_MAX)
{
return 0;
}
return int(result);
}
};


class Solution {
public:
int reverse(int x) {
int rev = 0;
while (x != 0) {
int pop = x % 10;
x /= 10;
if (rev > INT_MAX/10 || (rev == INT_MAX / 10 && pop > 7)) return 0;
if (rev < INT_MIN/10 || (rev == INT_MIN / 10 && pop < -8)) return 0;
rev = rev * 10 + pop;
}
return rev;
}
};



# 9.回文数

class Solution {
public:
bool isPalindrome(int x) {
if(x < 0){return false;}
else
{
long result = 0;
int y = x;
int n = 0;
while(x > 0)
{
n = x % 10;
x = x / 10;
result = result*10 + n;
}
if (result == y){return true;}
else{return false;}
}
}
};


return (x==n) ? true : false;


return (result == y) ? true: false;


# 13.罗马数字转换

#include <map>
#include <iostream>
using namespace std;
class Solution {
public:
int romanToInt(string s) {
int length = s.size();
std::map<string,int> luoma;
luoma.insert(pair<string,int>("I",1));
luoma.insert(pair<string,int>("V",5));
luoma.insert(pair<string,int>("X",10));
luoma.insert(pair<string,int>("L",50));
luoma.insert(pair<string,int>("C",100));
luoma.insert(pair<string,int>("D",500));
luoma.insert(pair<string,int>("M",1000));
long result = 0;
if (length >1)
{
for (int i = 0;i < length-1; i++ )
{
if(luoma[s.substr(i,1)] >= luoma[s.substr(i+1,1)])
{
result = result + luoma[s.substr(i,1)];
}
else
{
result = result - luoma[s.substr(i,1)];
}
}
result = result + luoma[s.substr(length-1,1)];
}
else{
result = luoma[s.substr(0)];
}

return result;

}
};


class Solution {
public:
int romanToInt(string s) {
unordered_map<string, int> m = {{"I", 1}, {"IV", 3}, {"IX", 8}, {"V", 5}, {"X", 10}, {"XL", 30}, {"XC", 80}, {"L", 50}, {"C", 100}, {"CD", 300}, {"CM", 800}, {"D", 500}, {"M", 1000}};
int r = m[s.substr(0, 1)];
for(int i=1; i<s.size(); ++i){
string two = s.substr(i-1, 2);
string one = s.substr(i, 1);
r += m[two] ? m[two] : m[one];
}
return r;
}
};



map：

unordered_map：

# 14.最长公共前缀

1.要注意函数可能没有返回值的状况
2.要求一个公共最小长度，不必定非要建出容器而后求最小值，能够直接在求每一个值的时候顺带求出最小值
3.substr函数仍是很好用的，主要是还能指定输出的个数

class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
int a = strs.size();

if (a == 0)
{
return "";
}
else if (a == 1)
{
return strs[0];
}
else
{
int aamin = strs[0].size();
for(int i = 1; i <a ; i++)
{
if(aamin > strs[i].size()){aamin = strs[i].size();}
}

for (int i = 0; i < aamin; i++ )
{
for (int j = 0; j< a; j++)
{
if (strs[0].substr(i,1) != strs[j].substr(i,1))
{
return strs[0].substr(0,i);
}
}

}
return strs[0].substr(0,aamin);

}
}
};


class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(strs.size()==0)
return "";
string str="";
int min_lenth=strs[0].size();
for(int i=1;i<strs.size();i++)
{
if(min_lenth>=strs[i].size())
min_lenth=strs[i].size();
}
for(int k=0;k<min_lenth;k++)
{
char s=strs[0][k];
for(int j=1;j<strs.size();j++)
{
if(s!=strs[j][k])
return str;
}
str+=s;
}
return str;
}
};


# 15. 三数之和(双指针)

class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
//没有好的办法，双指针不行，矩阵不行，贪心不行
//二维数组

int len = nums.size();
//vector<vector<int> > myvec(len, vector<int>(nums,0));
set<multiset<int> > res;
for (int i = 0; i<len; i++)
{
for(int j= i+1; j<len ; j++)
{
for (int c=j+1 ;c<len; c++)
{
//if (c==i || c==j){continue;}
if ((nums[i]+nums[j]+nums[c])==0)
{
multiset<int> x;
x.insert(nums[i]);
x.insert(nums[j]);
x.insert(nums[c]);
res.insert(x);
}
}
}
}
vector<vector<int> > re;
for(auto i:res)
{
vector<int> x;
for(auto j:i)
{
x.push_back(j);
}
re.push_back(x);
}
//vector<vector<int> > re = res;
return re;

}
};


class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int len = nums.size();
if(len<3)return {};
sort(nums.begin(),nums.end());
int i = 0 ;
int j = 1 ;
int l = 2;

set<vector<int>> res;
for(int i = 0 ; i<len ;i++)
{
if(nums[i]>0) break;//直接中止循环
if(nums[i]+nums[len-2]+nums[len-1]<0)continue;//直接跳过这次循环
for(int j = i+1;j<len ;j++)
{
if(nums[i]+nums[j]+nums[len-1]<0)continue;//跳过这次循环
for(int k = j+1 ; k<len ;k++)
{
if(nums[i]+nums[j]+nums[k]==0)
{
vector<int> temp = {nums[i],nums[j],nums[k]};
res.insert(temp);
//为了防止又相同值这里不能中止
}
if(nums[i]+nums[j]+nums[k]>0) break;//后面的k也都不行了
}
}

}
vector<vector<int>> r(res.begin(),res.end());
return r;

}
};


class Solution
{
public:
vector<vector<int>> threeSum(vector<int> &nums)
{
vector<vector<int>> result;
int vecSize = int(nums.size());
if (vecSize <= 2)
{
return result;
}
int possibleSize = vecSize - 2;
sort(nums.begin(), nums.end());

for (int index = 0; index < possibleSize; index++)
{
int intNow = nums[index];
if(intNow > 0){
break;
}
int negativeNow = 0 - intNow;
int lo = index + 1;
int hi = vecSize - 1;
while (lo < hi)
{
int intLo = nums[lo];
int intHi = nums[hi];

if (intLo + intHi == negativeNow)
{
vector<int> tmpVec{intNow, intLo, intHi};
result.push_back(tmpVec);
//去重
while (lo < hi && nums[lo] == intLo)
{
lo++;
}
while (lo < hi && nums[hi] == intHi)
{
hi--;
}
}
else if (intLo + intHi < negativeNow)
{
lo++;
}
else if (intLo + intHi > negativeNow)
{
hi--;
}
}
//去重
while (index + 1 < possibleSize && nums[index] == nums[index + 1])
{
index++;
}
}

return result;
}
};



class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int len = nums.size();
int k=0, i=1,j = len-1;
sort(nums.begin(),nums.end());
vector<vector<int>> res;
while(k<=len-3)
{
if(nums[k]+nums[k+1]+nums[k+2]>0)break;
if(nums[k]+nums[k+1]+nums[k+2]==0)
{       vector<int> temp={nums[k],nums[k+1],nums[k+2]};
res.push_back(temp);break;};
//if(nums[k]+nums[i]+nums[j]>0){k++;i=k+1;j=len-1;continue;}
if(nums[k]+nums[j-1]+nums[j]<0){k++;i=k+1;j=len-1;continue;}
while(i<j)
{
if(nums[i]+nums[j]==-nums[k])
{
vector<int> temp={nums[k],nums[i],nums[j]};
res.push_back(temp);
i++;j--;
}
else if(nums[i]+nums[j]>-nums[k])
{
j--;
}
else
{
i++;
}
}
k++;
i=k+1;
j=len-1;
}
set<vector<int>> r(res.begin(),res.end());
res.assign(r.begin(),r.end());
return res;
}
};


# 16. 最接近的三数之和

class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int len = nums.size();
int k=0,i=1,j=len-1;
sort(nums.begin(),nums.end());
int res = 1e6;
if(nums[0]+nums[1]+nums[2]>target) return nums[0]+nums[1]+nums[2];
if(nums[len-3]+nums[len-2]+nums[len-1]<target) return nums[len-3]+nums[len-2]+nums[len-1];
while(k<=len-3)
{
if(nums[k]+nums[k+1]+nums[k+2]>target)
return abs(res-target)<abs(nums[k]+nums[k+1]+nums[k+2]-target)?res:nums[k]+nums[k+1]+nums[k+2];
while(i<j)
{
if(nums[k]+nums[i]+nums[j]==target)return target;
else if(nums[k]+nums[i]+nums[j]>target)
{
res = abs(res-target)<abs(nums[k]+nums[i]+nums[j]-target)?res:nums[k]+nums[i]+nums[j];j--;
}
else
{
res =abs(res-target)<abs(nums[k]+nums[i]+nums[j]-target)?res:nums[k]+nums[i]+nums[j];i++;
}
}
k++;
i=k+1;
j=len-1;
}
return res;
}
};


# 17. 电话号码的字母组合

	string str;
str = str + 'm' + "m" + to_string(m)+char(m) + char(m+'0') ;


class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> res;//用于输出向量
map<char, string> m = { {'2',"abc" },{'3',"def"},{'4',"ghi"},{'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"} };//映射map哈希表
int size = digits.size();//输入字符串产长度
queue<string> que;//新建队列

//先将第一个元素对应的码表入队
for (int j = 0; j < m[digits[0]].size(); j++)
{
string str;
str.push_back(m[digits[0]][j]);//char转string
que.push(str);//string入队，分别将'a','b','c'入队列
}
string s;//用于存储队头元素
for (int i = 1; i < size; i++)//对剩下的第二个开始进行遍历，每一都会组成新的字符串放入队列，而后将此弹出
{
int length = que.size();//当前队列长度，这时的队列存放的是上一层全部的字符串，以前的都弹掉了，对于里面的每一个，都须要新的组合进入队尾，再弹出这个
while (length--)//
{
for (int j = 0; j < m[digits[i]].size(); j++)
{
s = que.front();
s = s + m[digits[i]][j];//队头元素加上新元素
que.push(s);//入队
}
que.pop();//队头出队
}
}
while (!que.empty())
{
res.push_back(que.front());//队头元素存储至res
que.pop();//队头出队
}
return res;//返回
}
};



class Solution {
private:
vector<string> res;
string path;
int len;
public:
void dfs(unordered_map<char,string> mymap, int pos, string digits)
{
if(pos == len)
{
res.push_back(path);
}
for(auto i:mymap[digits[pos]])
{
path = path+ i;
dfs(mymap,pos+1,digits);
path.pop_back();
}
}

vector<string> letterCombinations(string digits) {
if(digits.empty())return res;
len = digits.size();
unordered_map<char,string> mymap{{'2',"abc"},{'3',"def"},{'4',"ghi"},{'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}};
dfs(mymap,0,digits);
return res;
}
};


# 18. 四数之和

class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(),nums.end());
int len = nums.size();
int i = 0, j = 1, k1= 2,k2= len-1;
set<vector<int> > res;
while(i< len-3  )
{
while(j<len-2)
{
while( k1<k2)
{
int temp = nums[i]+nums[j]+nums[k1]+nums[k2];
if (temp == target)
{
vector<int> vec ={nums[i], nums[j], nums[k1],nums[k2]};
res.insert(vec);
k1++;
}
else if (temp > target){k2--;}
else {k1++;}
}
j++;
k1 = j+1;
k2 = len-1;
}
i++;
j=i+1;
k1=j+1;
k2=len-1;
}
vector<vector<int> > re;
for (auto i :res)
{
re.push_back(i);
}
return re;
}
};


指针依次是 p,k,i,j，若是 nums[p] + 3 * nums[p + 1] > target，由于 nums 按升序排列，因此以后的数确定都大于 target ，直接 break；



class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int len = nums.size();
int k=0,l=1,i=2,j=len-1;
sort(nums.begin(),nums.end());
set<vector<int>> res;
while(k<=len-4)
{
if(nums[k]+nums[k+1]+nums[k+2]+nums[k+3]>target)break;
if(nums[k]+nums[j-2]+nums[j-1]+nums[j]<target){k++;l=k+1;i=k+2;j=len-1;continue;}
while(l<=len-3)
{
if(nums[k]+nums[l]+nums[l+1]+nums[l+2]>target)break;
if(nums[k]+nums[l]+nums[j-1]+nums[j]<target){l++;i=l+1;j=len-1;continue;}
while(i<j)
{
if(nums[k]+nums[l]+nums[i]+nums[j]==target)
{
vector<int> temp={nums[k],nums[l],nums[i],nums[j]};
res.insert(temp);i++;j--;
}
else if(nums[k]+nums[l]+nums[i]+nums[j]>target)
{
j--;
}
else
{
i++;
}
}
l++;i=l+1;j=len-1;
}
k++;
l=k+1;
i=l+1;
j=len-1;
}
vector<vector<int>> r(res.begin(),res.end());
return r;
}
};


# 19. 删除链表的倒数第N个节点

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {

int len=0;
while(temp!=nullptr)
{
len++;
temp = temp->next;
}
if(len==1){return NULL;}
else
{
for(int i= 0;i<len-n-1;i++)
{
temp=temp->next;
}

temp ->next = temp ->next->next;
}
}
};


/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(NULL);
ListNode* slow=dummy,* fast=dummy;
int distance=0;
while(fast->next){
if(distance<n){
fast=fast->next;
distance++;
}else{
fast=fast->next;
slow=slow->next;
}
}
slow->next=slow->next->next;
return dummy->next;
}
};



# 20.有效的括号（堆栈的运用）

class Solution {
public:
bool isValid(string s) {
int length = s.size();
if (length % 2 == 1)
{
return false;
}
else
{
map <string ,int> fuhao = {{"(",1}, {")",-1}, {"[",2}, {"]",-2}, {"{",3}, {"}",-3}};
while((s.size()) > 0)
{

length = s.size();
for(int i = 0; i < s.size()-1; i++)
{
if ( fuhao[s.substr(i,1)] == - fuhao[s.substr(i+1,1)])
{
s.erase(i,2);
break;
}
}
if(length == 0)
{
return true;
}
else if (length == s.size())
{
return false;
}
else
{
continue;
}

}
return (s.size() == 0) ? (true) : (false);
}
}

};


1.for(auto i : s)遍历s中的全部字符、元素，甚至可使用自动类型推断，一个冒号就解决了，实用性很大！
2.vector.empty()与
if (vector.size() == 0 ){return true}
else {return false} 的效果更简洁，若是要反着来能够在前面加一个！
3.对于s中的每个符号，若是是左半边，就把这个推动容器；若是是右半边，此时若容器为空则说明以前没有左半边入栈，则false，若是容器不为空继续，把容器最后一个左半括号提取出来，若是此右半边和这个括号不匹配，则false，若是匹配则弹出此左半括号，继续下去，所有走完后，直接用空就表明是否所有匹配，一语双关！

class Solution {
public:
bool isValid(string s) {
if(s.size() % 2) return false;
vector<char> vecStack;//字符型的容器
char c;
//对于s中的每个符号，若是是左半边，就把这个推动容器；若是是右半边，此时若容器为空则说明以前没有左半边入栈，则false，若是容器不为空继续，把容器最后一个左半括号提取出来，若是此右半边和这个括号不匹配，则false，若是匹配则弹出此左半括号，继续下去，所有走完后，直接用空就表明是否所有匹配，一语双关！
for(auto i : s) {
if(i == '}' || i == ')' || i== ']') {
if (!vecStack.empty()) c = vecStack[vecStack.size()-1];
else return false;
if(i == '}' && c != '{') return false;
if(i == ')' && c != '(') return false;
if(i == ']' && c != '[') return false;
vecStack.pop_back();
}
else vecStack.push_back(i);
}
return vecStack.empty();
}
};



class Solution {
public:
bool isValid(string s) {
vector <char> kuohao;
if (s.size() % 2 == 1) return false;
for (auto str : s)
{
if ((str == '{') || (str == '[') || (str == '('))
{
kuohao.push_back(str);
}
else
{
if(kuohao.size() == 0) return false;
if (str == '}' && kuohao[kuohao.size()-1] == '{')
{
kuohao.pop_back();
continue;
}
else if (str == ']' && kuohao[kuohao.size()-1] == '[')
{
kuohao.pop_back();
continue;
}
else if (str == ')' && kuohao[kuohao.size()-1] == '(' )
{
kuohao.pop_back();
continue;
}
else
{
return false;
}
}
}
return kuohao.empty();
}
};


char b[5]={‘a’,‘b’,‘c’,‘d’,‘e’};

int a=10;

cout<<“a”;输出为 字符a;这就是上次“s[0]”中不能再编译s[0]的缘由，可是若是是单引号没准能编译

cout<<a;输出为10；

cout<<‘a’ ;输出为65；

# 21.合并链表

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* temp1 = l1;
ListNode* temp2 = l2;
while(temp1!= nullptr && temp2!= nullptr)
{
while (temp1 != nullptr && temp1->val <= temp2->val)
{
ListNode* temp = new ListNode(temp1->val);
res->next = temp;
res = temp;
temp1 = temp1->next;
}
while (temp1 != nullptr&&temp2 != nullptr && temp1->val > temp2->val)
{
ListNode* temp = new ListNode(temp2->val);
res->next = temp;
res = temp;
temp2 = temp2->next;
}
}
while (temp1!=nullptr)
{
ListNode* temp = new ListNode(temp1->val);
res->next = temp;
res= temp;
temp1=temp1->next;
}
while(temp2!=nullptr)
{
ListNode* temp = new ListNode(temp2->val);
res->next =temp;
res= temp;
temp2=temp2->next;
}
}
};

#include <vector>
using namespace std;

/**
*/

struct ListNode//链表的结构体
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};

class Solution
{
public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
{
ListNode *result = new ListNode(-1); //哑节点简化代码
ListNode *workNode = result;
while (l1 != nullptr && l2 != nullptr) //直到有一个为空指针为止
{
if (l1->val <= l2->val) //若是1的值小于2的值，就考察1的下一个值
{
workNode->next = l1;
l1 = l1->next;
}
else//考察2的下一个值
{
workNode->next = l2;
l2 = l2->next;
}
workNode = workNode->next;
}
workNode->next = (l1 != nullptr) ? l1 : l2;//谁不为空就把谁剩下的加进去

return result->next;
}
};



# 22. 括号生成

class Solution {
public:
bool isright(string s)
{
stack<char> st;
for (auto i : s)
{
if (i == '(') { st.push('('); }
else
{
if (!st.empty() && st.top() == '(') { st.pop(); }
else { return false; }
}
}
if (st.empty()) { return true; }
else { return false; }
}

vector<string> generateParenthesis(int n) {
if (n == 0)
{
vector<string> s = { "" };
return s;
}
else
{
string s = "(";
queue<string> res;
res.push(s);
for (int i = 0; i < 2 * (n-1); i++)
{
int j = res.size();
while (j)
{

string s1 = res.front() + "(";
res.push(s1);
string s2 = res.front() + ")";
res.push(s2);
res.pop();
j--;
}
}
vector<string> re;
while (!res.empty())
{
string s3 = res.front() + ")";
if (isright(s3))
{
re.push_back(s3);
res.pop();
}
else { res.pop(); }
}
return re;
}

}
};


class Solution {
public:
vector<string> generateParenthesis(int n) {
if (n == 0)  return{ "" };
if (n == 1)  return{ "()" };
vector<string> ans;
generateParenthesisIter("(", n-1, n, ans);
return ans;
}

void generateParenthesisIter(string valid, int left_num, int right_num, vector<string>& ans){
if (left_num == 0){     //递归终止条件
valid.append(right_num, ')');
ans.push_back(valid);
return;
}
for (int n = left_num; n >= 0; n--){ //本层使用的左括号数量
string str = valid;
if (left_num - n > right_num - 1)//剪枝: 无效的分支
return; //剩余括号中左括号数量大于右括号数量，说明已用的右括号数量大于左括号数量
str.append(n, '(');
str.append(1, ')');
generateParenthesisIter(str, left_num - n, right_num - 1, ans);
}
return;
}
};



…以此类推，前n位数字和均大于等于0.

…依然知足规律。

1.目标为n时，能够转化为n个-1和n个1
2.求这串数字的全部排列
3.知足以上规律的就是有效的括号组合
4.最后一步再将数字组合转化成括号组合

1.求全排列的函数：next_permutation
2.数字转化成括号：容器map

class Solution {
public:
vector<string> generateParenthesis(int n)
{
vector<string> result;
if(n == 0){return result;}
vector<vector<int>> mid;
vector<int> temp;
for(int i = 0 ; i < n ; i ++)
{
temp.push_back(-1); //先放全部的-1
}
for(int i = 0 ; i < n ; i ++)
{
temp.push_back(1);  //再放全部的+1（这样的缘由是由于全排列须要从小到大的顺序）
}
while(next_permutation(temp.begin(),temp.end()))    //求全排列
{
int target = 0;
int judg = 1;
for(auto i:temp)
{
target+=i;
if(target < 0)
{
judg = 0;break; //是否知足前n项之和不小于0
}
}
if(judg == 1){mid.push_back(temp);}//若是不用剪枝，则能够将数组放入mid
}
map<int,string> invert;
invert.insert(map<int,string>::value_type(1,"("));  //1对应左括号
invert.insert(map<int,string>::value_type(-1,")")); //-1对应右括号
for(auto i:mid)
{
string s;
for(auto j:i)
{
s += invert[j]; //数字组合转化成字符串
}
result.push_back(s);
}
return result;
}
};



## 全排列函数next_permutation

 while(next_permutation(temp.begin(),temp.end()))
{}


next_permutation(num,num+n)函数是对数组num中的前n个元素进行全排列，同时并改变num数组的值。

# 23. 合并K个排序链表

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
vector<int> v;
{
{
}

}
sort(v.begin(),v.end());
//int i = v.size();
for(int i = 0 ; i<v.size(); i++)
{
ListNode* temp =new ListNode(v[i]);
res->next = temp;
res = temp;
}
}
};


# 26. 删除排序数组中的重复项

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

int i =1;
int j = 0;
int len = nums.size();
if(len==0)return 0;
for(i=1; i<len;i++)
{
if(nums[i]==nums[j])continue;
else
{
nums[++j] = nums[i];
}
}
return j+1;
}
};


# 27. 移除元素

class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int i = 0 ;
int j = nums.size()-1;
while(i<=j)
{
while(i<=j && nums[i]!=val) i++;
while(i<=j && nums[j]==val)j--;
if(i<=j) swap(nums[i],nums[j]);
}
return i;
}
};


# 31. 下一个排列

class Solution {
public:
void nextPermutation(vector<int>& nums) {
if(next_permutation(nums.begin(),nums.end()))
{
return ;
}
else
{
sort(nums.begin(),nums.end());
return ;
}
}
};


class Solution {
public:

bool is(string s1)
{
if(s1[0]==')')return false;
int len = s1.size();
if(len%2!=0)return false;
stack<char> st;
for(auto i:s1)
{
if(i=='(')
{
st.push(i);
}
else
{
if(!st.empty() && st.top()=='(')
{
st.pop();
}
else
{
return false;
}
}
}
return st.empty();
}

int longestValidParentheses(string s) {
//两种办法，第一种双指针窗口法，当遇到破坏结构时，从中间的地方开始起，可是可能会有一点复杂
//遍历判断法，专门呢写一个函数，第一种的复杂度确定是最低的
if(s.empty())return 0;
int max = 0;
int len = s.size();
if(len==1)return 0;
for(int i = 0 ; i<len ;i++)
{
for(int j = i+1;j<len;j++)
{
string s1=s.substr(i,j-i+1);
if(is(s1) && j-i+1>max)max = j-i+1;
}
}
return max;
}
};


# 33. 搜索旋转排序数组

class Solution {
public:
int search(vector<int>& nums, int target) {
int right = nums.size();
int left = 0;
while(left<right)
{
int mid = left + (right-left)/2;
if(nums[mid]==target){return mid;}
else if (nums[mid]>target)
{
if(target>=nums[0] || nums[mid]<nums[0]){right = mid;}
else{left=mid+1;}
}
else
{
if(nums[mid]>=nums[0] ||target<nums[0]){left=mid+1;}
else{right=mid;}
}
}
return -1;
}
};

class Solution {
public:
int search(vector<int>& nums, int target) {
int lo = 0, hi = nums.size() - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if ((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid]))
lo = mid + 1;
else
hi = mid;
}
return lo == hi && nums[lo] == target ? lo : -1;
}
};



# 34. 在排序数组中查找元素的第一个和最后一个位置

class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int left = 0, right = nums.size();
while(left<right)
{
int mid = left + (right-left)/2;
if(nums[mid]==target)
{
int t1 =mid-1, t2 = mid+1;
while(t1>=0 && nums[t1]==target)t1--;
while(t2<(int)nums.size() && nums[t2]==target)t2++;
return {t1+1,t2-1};
}
else if(nums[mid]<target)
{
left = mid +1;
}
else{right = mid;}
}
return {-1,-1};
}
};


# 35. 搜索插入位置（二分法***************）

class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int len = nums.size();
int left=0,right = len-1;
if(target<=nums[0])return 0;
if(target>nums[len-1])return len;
if(target==nums[len-1])return len-1;
while(left<right)
{
int mid = (left+right)/2;
if(nums[mid]==target)return mid;
else if(nums[mid]>target)
{
right = mid;
}
else
{
left = mid;
}
if(left==right-1 && nums[left]<target && nums[right]>target )return right;
}
return right;
}
};


class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int low = 0, high = nums.size() - 1, mid = 0;
while(low <= high){
mid = low + (high - low) / 2;
if(nums[mid] < target) low = mid + 1;
else if(nums[mid] > target) high = mid - 1;
else return mid;
}
return low;
}
};


class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int len = nums.size();
int left=0,right = len;
while(left<right)
{
int mid = (left+right)/2;
if(nums[mid]==target)return mid;
else if(nums[mid]<target)
{
left = mid+1;
}
else
{
right = mid;
}
}
return left;
}
};


# 36. 有效的数独

class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
//主要考察二维数组用法
//每一列
for(int i= 0 ; i<9 ;i++)
{
set<char> st;
int num = 0;
for(int j = 0 ; j < 9; j++)
{
if(board[i][j]=='.'){continue;}
else{st.insert(board[i][j]);num++;}
}
if(st.size()!=num){return false;}
}
//每行
for(int i= 0 ; i<9 ;i++)
{
set<char> st;
int num = 0;
for(int j = 0 ; j < 9; j++)
{
if(board[j][i]=='.'){continue;}
else{st.insert(board[j][i]);num++;}
}
if(st.size()!=num){return false;}
}

for(int c1 = 0 ; c1<9; c1=c1+3)
{
for(int c2 =0 ; c2<9 ;c2=c2+3)
{
set<char>st;
int num=0;
for(int i=0 ; i<3 ;i++)
{
for(int j = 0; j<3; j++)
{
if(board[c1+i][c2+j]=='.'){continue;}
else{st.insert(board[c1+i][c2+j]);num++;}
}

}
if(st.size()!=num){return false;}
}
}

return true;
}
};


# 36. 有效的数独

class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
vector<int> wow(9,0);
int mux1;
int mux2;
int mux3;
int box_index;

for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
if(board[i][j] == '.'){
continue;
}
mux1 = 0x01 << (board[i][j] - '1');
mux2 = 0x01 << 9 << (board[i][j] - '1');
mux3 = 0x01 << 9 << 9 << (board[i][j] - '1');
box_index = (i/3) * 3 + j/3;
if((wow[i]&mux1) != mux1 && (wow[j]&mux2) != mux2 && (wow[box_index]&mux3) != mux3){
wow[i] = wow[i]|mux1;
wow[j] = wow[j]|mux2;
wow[box_index] = wow[box_index]|mux3;
}
else{
return false;
}
}
}
return true;
}
};


class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
int row[9][10] = {0};// 哈希表存储每一行的每一个数是否出现过，默认初始状况下，每一行每个数都没有出现过
// 整个board有9行，第二维的维数10是为了让下标有9，和数独中的数字9对应。
int col[9][10] = {0};// 存储每一列的每一个数是否出现过，默认初始状况下，每一列的每个数都没有出现过
int box[9][10] = {0};// 存储每个box的每一个数是否出现过，默认初始状况下，在每一个box中，每一个数都没有出现过。整个board有9个box。
for(int i=0; i<9; i++){
for(int j = 0; j<9; j++){
// 遍历到第i行第j列的那个数,咱们要判断这个数在其所在的行有没有出现过，
// 同时判断这个数在其所在的列有没有出现过
// 同时判断这个数在其所在的box中有没有出现过
if(board[i][j] == '.') continue;
int curNumber = board[i][j]-'0';
if(row[i][curNumber]) return false;
if(col[j][curNumber]) return false;
if(box[j/3 + (i/3)*3][curNumber]) return false;

row[i][curNumber] = 1;// 以前都没出现过，如今出现了，就给它置为1，下次再碰见就可以直接返回false了。
col[j][curNumber] = 1;
box[j/3 + (i/3)*3][curNumber] = 1;
}
}
return true;
}
};



class Solution {
public:
int num(vector<vector<char>>& board, int k1, int k2)
{

map<char, int> m = { {'1',0},{'2',0},{'3',0},{'4',0},{'5',0},{'6',0},{'7',0},{'8',0},{'9',0} };
for (int i = 0; i < 9; i++)
{
if (board[k1][i] != '.') { m[board[k1][i]] = 1; }
if (board[i][k2] != '.') { m[board[i][k2]] = 1; }
}
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
if (board[k1 / 3 + i][k2 / 3 + j] != '.') { m[board[k1 / 3 + i][k2 / 3 + j]] = 1; }
}
}
map<char, int>::iterator iter;
int num = 0;
int res = 0;
for (auto iter = m.begin(); iter != m.end(); iter++)
{
//int num = 0;
if (iter->second == 0) { res = iter->second; num++; }

}
if (num == 1) { return res; }
else { return 0; }

}

bool is(vector<vector<char>>& board)
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (board[i][j] == '.') { return false; }

}
}
return true;
}
void solveSudoku(vector<vector<char>>& board) {
//想法使用递归，终止条件是填满了，方法是对空着的位置进行遍历，每个都设置一个哈希，当行列块又出现的设为1，当剩最后一个 了时就返回这个表

for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (board[i][j] == '.')
{
if (num(board, i, j)) { board[i][j] = char(num(board, i, j)+'0' ); }
else { continue; }
}
}
}
while (!is(board)) { solveSudoku(board); }
return;
}
};


# 39. 组合总和

class Solution {
private:
vector<vector<int>> res;
vector<int> path;
int sum = 0;
public:
void dfs(vector<vector<int>>& res,vector<int>& candidates,vector<int>& path, int sum,int target ,int j)
{
if(sum == target)
{
res.push_back(path);return;
}
if(sum>target)return;
for(int i = j; i<(int)candidates.size() ;i++)
{
path.push_back(candidates[i]);
sum +=candidates[i];
dfs(res,  candidates,  path,  sum,  target,i);
path.pop_back();
sum -=candidates[i];
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(),candidates.end());
dfs(res,candidates,path,0,target,0);
return res;
}
};


## （二叉树经常使用算法：回溯、队列、递归、剪枝）

// author:rmokerone
#include <iostream>
#include <vector>

using namespace std;

class Solution {
private://成员变量
vector<int> candidates;
vector<vector<int>> res;
vector<int> path;
public:
void DFS(int start, int target) {
if (target == 0) {  //递归终止条件
res.push_back(path);
return;
}
for (int i = start; i < candidates.size() && target - candidates[i] >= 0; i++) {
path.push_back(candidates[i]);
DFS(i, target - candidates[i]);
path.pop_back();
}
}

vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
std::sort(candidates.begin(), candidates.end());
this->candidates = candidates;
DFS(0, target);

return res;
}

};



1.是用了剪枝是为了提速
2.除此以外，在深度优先搜索的时候能够设置从当前元素开始，由于以前的元素在以前的节点已经用过了因此加了一个start变量用来记录在can容器中的位置
3.像sum这种的不用每次都计算，直接加个参数就好了，注意全局变量的定义位置，由于递归函数要用，因此定义在全局的地方，还能够在外面定义可是在函数中进行计算，好比siz这个变量，更严格点能够定义在private中

class Solution {
public:
vector<int> tmp;
vector<vector<int>> ans;
int siz;

void dfs(int now, int sum, int tar, vector<int>& num)
{
if(sum > tar) return;
if(sum == tar)
{
ans.push_back(tmp);
return;
}
for(int i = now; i < siz; i ++)
{
tmp.push_back(num[i]); //一层一层往下走
dfs(i, sum + num[i], tar, num); //当大于或者等于时都会返回
tmp.pop_back();//回到上一个分叉节点，从整个树的最左边一条开始试
}
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
siz = candidates.size();
dfs(0, 0, target, candidates);
return ans;
}
};



# 41. 缺失的第一个正数

class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
//sort(nums.begin(),nums.end());
for(int i = 1;true;i++)
{
auto temp = find(nums.begin(),nums.end(),i);
if (temp==nums.end()){return i;}
}
}
};


# 42. 接雨水

#include <algorithm>
//返回迭代器
auto max = max_element(v.begin(), v.end());
//获得最大值对应下标
int kk = max-v.begin();


class Solution {
public:
int trap(vector<int>& height) {
if(height.size()<=2){return 0;}
int i = 0;
int j = 1;
int sum = 0;
while (i < height.size() - 2)
{
while (j<height.size() && height[i] > height[j]) { j++; }
if (j == height.size())
{
auto m = max_element(height.begin()+i+1, height.end());
j=m-height.begin();
}
sum = sum + (j - i - 1)*min(height[i], height[j]);
for (int c = i + 1; c < j; c++)
{
sum = sum - height[c];
}
i = j;
j = i + 1;
}
return sum;
}
};


\text{ans}ans 。

\text{height}[current]>\text{height}[st.top()]height[current]>height[st.top()]

\text{distance} = \text{current} - \text{st.top}() -
1distance=current−st.top()−1 找出界定高度 \text{bounded_height} =
\min(\text{height[current]}, \text{height[st.top()]}) -
\text{height[top]}bounded_height=min(height[current],height[st.top()])−height[top]

\text{bounded_height}ans+=distance×bounded_height 将当前索引下标入栈 将
\text{current}current 移动到下个位置

int trap(vector<int>& height)
{
int ans = 0, current = 0;
stack<int> st;
while (current < height.size()) {
while (!st.empty() && height[current] > height[st.top()]) {
int top = st.top();
st.pop();
if (st.empty())
break;
int distance = current - st.top() - 1;
int bounded_height = min(height[current], height[st.top()]) - height[top];
ans += distance * bounded_height;
}
st.push(current++);
}
return ans;
}



# 43. 字符串相乘

class Solution {
public:
string multiply(string num1, string num2) {
int n1=num1.size();
int n2=num2.size();
string res(n1+n2,'0');
for(int i=n2-1;i>=0;i--){
for(int j=n1-1;j>=0;j--){
int temp=(res[i+j+1]-'0')+(num1[j]-'0')*(num2[i]-'0');
res[i+j+1]=temp%10+'0';//当前位
res[i+j]+=temp/10; //前一位加上进位，res[i+j]已经初始化为'0'，加上int类型自动转化为char，因此此处不加'0'
}
}

//去除首位'0'
for(int i=0;i<n1+n2;i++){
if(res[i]!='0')
return res.substr(i);
}
return "0";

}
};



# 44. 通配符匹配

class Solution {
public:
bool isMatch(string s, string p) {
int n = s.size(), m = p.size();
vector< vector<bool> > dp(n+1, vector<bool>(m+1, false)); dp[0][0] = true;

// initialize
for (int i = 1; i <= m; ++ i){
if(p[i - 1] == '*' && dp[0][i - 1]) dp[0][i] = dp[0][i - 1];
}

for (int i = 1; i <= n; ++ i){
for (int j = 1; j <= m; ++ j){
if (s[i - 1] == p[j - 1] || p[j - 1] == '?'){
dp[i][j] = dp[i - 1][j - 1];// ismatch, move on
}else if (p[j - 1] == '*'){
bool zero, mul;// '*' act as zero, '*' act as multiple characters
zero = (j < m && s[i - 1] == p[j] && dp[i - 1][j - 1]) || dp[i][j - 1];
mul = dp[i -1][j];
dp[i][j] = zero || mul;
}
}
}

return dp[n][m];
}
};



# 45. 跳跃游戏 II

class Solution {

public:
int ans=0;

int summm(int start, vector<int> nums)
{
int  temp = max_element(nums.begin() + start +1, nums.begin() + start + nums[start]+1) - nums.begin();

if (start + nums[start] >= temp + nums[temp]) { ans++; return start + nums[start]; }
else { ans++; return temp ; }

}
int jump(vector<int>& nums) {
int len = nums.size();
//int ans = 0;
if (len == 1) { return 0; }
else
{
int start = 0;
//if (start + nums[start] >= len) { return 1; }
while (start<len )
{

if (start + nums[start] >= len-1) { return ans + 1; }
start = summm(start, nums);

}
return ans;

}
}
};


## 贪心算法

int jump(vector<int> &nums)
{
int ans = 0;
int start = 0;
int end = 1;
while (end < nums.size())
{
int maxPos = 0;
for (int i = start; i < end; i++)
{
// 能跳到最远的距离
maxPos = max(maxPos, i + nums[i]); //在遍历的过程当中不断更新这个最大值
}
start = end;      // 下一次起跳点范围开始的格子
end = maxPos + 1; // 下一次起跳点范围结束的格子，加一是由于上面的遍历时左闭右开的
ans++;            // 跳跃次数
}
return ans;
}



# 46. 全排列

1.之气那要排序
2.只要开始全排列，第一个结果是已经改变以后的数组，而不是原来的
3。参数是首末迭代器

class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> > res;
sort(nums.begin(), nums.end());
res.push_back(nums);
while(next_permutation(nums.begin(),nums.end()))
{
res.push_back(nums);
}
return res;

}
};


class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> > res;
if (nums.size()==0 || nums.size()==1)
{
res.push_back(nums);
return res;
}
sort(nums.begin(), nums.end());
queue<vector<int>> q;

for(auto i:nums)
{
vector<int> temp;
temp.push_back(i);
q.push(temp);
}

//int i=nums.size()-1;
while(q.front().size()!=nums.size())
{

for (auto i:nums)
{
vector<int> temp = q.front();
if(find(temp.begin(),temp.end(),i)==temp.end())
{
temp.push_back(i);
q.push(temp);
}
}
q.pop();
}
while(!q.empty())
{
res.push_back(q.front());
q.pop();
}
return res;

}
};


## 回溯问题+决策树

递归{
递归出口；
for(int i = 1;i<=n;i++){
进入递归；
remove(i);
}
}


void backtrack(路径，选择列表)
{
if(终止条件)
{
传出路径结果
return;
}
for i in 选择列表
{
进入该选择
back(路径，选择列表)
退出该选择
}
}


class Solution {
private:
vector<vector<int> > res;
int len;
vector<int> path;
public:
void backtrack(vector<int> &path, vector<int>& nums)
{
set<int> s(path.begin(),path.end());
if(path.size()==len)
{
if (s.size()==len)
{
res.push_back(path);
return;
}
else
{
return;
}
}
for(auto i : nums)
{
path.push_back(i);
backtrack(path,nums);
path.pop_back();
}
}

vector<vector<int>> permute(vector<int>& nums) {
len = nums.size();
if (nums.size()==0 || nums.size()==1)
{
res.push_back(nums);
return res;
}
sort(nums.begin(), nums.end());
backtrack(path,nums);
return res;

}
};


# 48. 旋转图像

class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
int m = matrix[0].size();

// 对于正对角线对称翻转
for (int i = 0; i < n; i++) {
for (int j = i; j < m; j++) {
swap(matrix[i][j], matrix[j][i]);
}
}
// 竖轴镜像操做
for (int i = 0; i < n; i++) {
reverse(matrix[i].begin(), matrix[i].end());
}
}
};



# 49. 字母异位词分组

class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> res;
vector<pair<multiset<char>,vector<string>>> st;
for(auto str:strs)
{
multiset<char> temp(str.begin(),str.end());
bool b = false;
for(int i = 0 ;i<(int)st.size() ;i++)
{

if(st[i].first==temp)
{
st[i].second.push_back(str);
b = true;
break;
}

}
if(!b)
{
st.push_back(pair<multiset<char>,vector<string>>(temp,{str}));
}
}
for(auto i:st)
{
vector<string> temp;
for(auto j:i.second)
{
temp.push_back(j);
}
res.push_back(temp);
}
return res;
}
};


class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> res;
int sub=0;  //结果vector的下标值
string tmp; //临时string
unordered_map<string,int> work; //判断排序后单词是否存在，即字母组成是否一致
for(auto str:strs)
{
tmp=str;
sort(tmp.begin(),tmp.end());
if(work.count(tmp))
{
res[work[tmp]].push_back(str);
}
else
{
vector<string> vec(1,str);
res.push_back(vec);
work[tmp]=sub++;
}
}
return res;
}
};



# 50. Pow(x, n)

class Solution {
public:
double myPow(double x, int n) {
if(x==0)return 0;
if(x==1 || n==0) return 1;
double res=1;
while(n>0)
{
res=res*x;
n--;
}
while(n<0)
{
res = res/x;
n++;
}

return res;

}
};


class Solution {
public:
double myPow(double x, int n) {
if (n == 0) { return 1; }
if (n == 1) { return x; }
if (n == -1) { return 1 / x; }
double half = myPow(x, n / 2);
double rest = myPow(x, n % 2);
return rest * half * half;
}
};



# 51. N皇后（回溯dfs）

class Solution {
vector<vector<string>> res;//存结果
vector<string> tmp;//存棋盘
public:
vector<vector<string>> solveNQueens(int n) {
string line(n,'.');//既然一行一行试，那就一行一行存
solveNQueens(line, 0, n);//从第0行开始
return res;
}

private:
//试某一行
void solveNQueens(string& line, int row, int n)
{
if(tmp.size() == n)//棋盘绘制够n行存进结果，不用继续试了
{
res.push_back(tmp);
return;
}
for(int i = 0; i < n; ++i)//一格一格，每格都要试
{
if(checkAll(row, i, n))     //符合条件了
{
line[i] = 'Q';          //就把当前试的这一格放皇后
tmp.push_back(line);    //而后把这一行绘制进棋盘
line[i] = '.';          //棋盘的下一行应该是没有皇后的
solveNQueens(line, row + 1, n);//去试下一行
tmp.pop_back();         //接下来要去试下一格，刚才绘制进去的那一行删掉
}
}
}

//暴力检查条件
bool checkAll(int row, int col, int n)
{
for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i,--j)//左上方
{
if(tmp[i][j] == 'Q')
return false;
}
for(int i = row - 1; i >= 0; --i)//正上方
{
if(tmp[i][col] == 'Q')
return false;
}
for(int i = row -1, j = col + 1; i >= 0 && j < n; --i, ++j)//右上方
{
if(tmp[i][j] == 'Q')
return false;
}
return true;
}
};



# 53. 最大子序和（贪心）

class Solution
{
public:
int maxSubArray(vector<int> &nums)
{
//相似寻找最大最小值的题目，初始值必定要定义成理论上的最小最大值
int result = INT_MIN;
int numsSize = int(nums.size());
int sum = 0;
for (int i = 0; i < numsSize; i++)
{
sum += nums[i];
result = max(result, sum);
//若是sum < 0，从新开始找子序串
if (sum < 0)
{
sum = 0;
}
}

return result;
}
};



# 55. 跳跃游戏

class Solution {
public:
bool canJump(vector<int>& nums) {
int left = 0;
int len = nums.size();
while(1)
{
if(left>=len-1 || left+nums[left]>=len-1)return true;

int max = 0;
int temp = 0;
for(int i = left ; i<=len-1 &&i<=left+nums[left] ;i++)
{
if(i+nums[i]>max){max = i+nums[i];temp=i;}

}
if(max<len-1&& nums[max]==0)return false;
left = temp;
}
return false;
}
};


1.若是某一个做为 起跳点 的格子能够跳跃的距离是 3，那么表示后面 3 个格子均可以做为 起跳点。
2.能够对每个能做为 起跳点 的格子都尝试跳一次，把 能跳到最远的距离 不断更新。
3.若是能够一直跳到最后，就成功了。

bool canJump(vector<int>& nums)
{
int k = 0;
for (int i = 0; i < nums.size(); i++)
{
if (i > k) return false;//k表示到i的时候，以前全部位置能到达的最大距离，每个都走一下，可是不用考虑怎么走的，当走到一个位置不能再更新了，就会小于下一个i
k = max(k, i + nums[i]);
}
return true;
}



# 56. 合并区间(贪心)

class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> res;
if(intervals.empty())return res;
sort(intervals.begin(),intervals.end());
res.push_back(intervals[0]);
for(int i = 1 ;i< (int)intervals.size() ;i++)
{
if(intervals[i][0]<= res.back()[1])
{
res.back()[1] = max(res.back()[1],intervals[i][1]);
}
else
{
res.push_back(intervals[i]);
}
}
return res;
}
};


class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (!intervals.size()) return {};

//先把区间集合按照左端点从小到大进行排序
sort(intervals.begin(), intervals.end(), less<vector<int>>());
int pos = 0;//pos的值是每一个不重叠的区间
//直接在原区间上作就能够
//从第二个区间开始去比较
for (int i = 1; i < intervals.size(); ++i)
{
//两个区间若能合并，则第一个区间的右端点必定大于等于第二个区间的左端点
//好比[1,3] [2,6]
if (intervals[pos][1] >= intervals[i][0])
{
//第一个区间的尾部须要更新为：两个区间的最大值即[1,6]
intervals[pos][1] = max(intervals[pos][1], intervals[i][1]);
}
else//没有重叠时
{
//[1,6] [2,8]====>区间1就是目前的这个区间
intervals[++pos] = intervals[i];
}
}

intervals.resize(pos + 1);//把最后的不用的弹出
return intervals;
}

};


class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.empty()) {
return intervals;
}
sort(intervals.begin(), intervals.end());
vector<vector<int>> result{ intervals.front() };
for (auto&& interval : intervals) {
if (interval.front() > result.back().back()) {
result.emplace_back(move(interval));
} else {
result.back().back() = max(interval.back(), result.back().back());
}
}
return result;
}
};



# 57. 插入区间

class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
vector<vector<int>> res;
if(newInterval.empty())return intervals;
intervals.push_back(newInterval);
sort(intervals.begin(),intervals.end());
res.push_back(intervals[0]);
for(int i =1; i< (int)intervals.size() ;i++)
{
if(intervals[i][0]<= res.back()[1])
{
res.back()[1] = max(res.back()[1], intervals[i][1]);
}
else
{
res.push_back(intervals[i]);
}
}
return res;

}
};


# 62. 不一样路径(dp)

class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> board(m,vector<int>(n,0));
for(int i = 0 ; i <m ;i++)
{
board[i][0]=1;
}
for(int j = 0; j<n ;j++)
{
board[0][j]=1;
}
for(int i = 1; i<m ;i++)
{
for(int j = 1 ; j<n ;j++)
{
board[i][j] = board[i-1][j] + board[i][j-1];
}
}
return board[m-1][n-1];
}
};


# 64. 最小路径和(dp)

class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if(grid.empty())return 0;
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> board(m,vector<int>(n,0));
board[0][0]=grid[0][0];
for(int i = 1 ; i< n ;i++)
{
board[0][i] = grid[0][i]+board[0][i-1];
}
for(int i = 1 ; i< m ; i++)
{
board[i][0] = grid[i][0]+board[i-1][0];
}
for(int i = 1 ; i < m ;i++)
{
for(int j = 1 ; j< n; j++)
{
board[i][j] = grid[i][j] + min(  board[i-1][j],board[i][j-1]);
}
}
return board[m-1][n-1];
}
};


# 69. x 的平方根(二分法)

1.mid最好设置为两个的和除以2再加1，扩大范围更好，否则可能会chucuo
2.初始值能够设置的更小点
3.最后是left和right的变化问题，最后两个都变化或者至少一个变化，而后返回left就能够，没必要要返回mid

class Solution {
public:
int mySqrt(int x) {
if(x==0)return 0;
long left = 1;
long right = x;
while(left<right)
{
long mid = (left+right)/2+1;
if(mid==x/mid)return mid;
else if(mid>x/mid)
{right = mid-1;}
else
{left = mid;}
}
return left;
}
};


# 70. 爬楼梯（dp）

class Solution {
public:
int climbStairs(int n) {
if(n==0)return 0;
if(n==1)return 1;
if(n==2) return 2;
vector<int> dp(n+1,0);
dp[0]=0;
dp[1]=1;
dp[2]=2;
for(int i = 3 ; i<n+1; i++)
{
dp[i] = dp[i-1]+ dp[i-2];
}
return dp[n];
}
};


# 72. 编辑距离

class Solution {
public:
int minDistance(string word1, string word2) {
int len1 = word1.size();
int len2 = word2.size();
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++)
{
if(word1[i-1]==word2[j-1])
{
dp[i][j] = dp[i-1][j-1] ;
}
else
{
dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
}
}

}
return dp[len1][len2];
}
};


# 73. 矩阵置零

class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
if(matrix.size()==0)return;
vector<int> row;
vector<int> col;
int len1 = matrix.size();
int len2 = matrix[0].size();
for(int i= 0 ;i<len1 ; i++)
{
for(int j = 0 ; j <len2 ;j++)
{
if(matrix[i][j]==0)
{
row.push_back(i);
col.push_back(j);
}
}
}
for(auto i :row)
{
for(int j = 0 ; j<len2 ;j++)
{
matrix[i][j]=0;
}
}
for(auto j:col)
{
for(int i = 0 ; i<len1 ; i++)
{
matrix[i][j] = 0;
}
}
return;
}
};


# 75. 颜色分类（三数快排）

class Solution {
public:
void sortColors(vector<int>& nums) {
int left = 0 , right = nums.size()-1;
for(int i = left ;i<=right ;i++)
{
if(nums[i]==0)swap(nums[left++],nums[i]);
if(nums[i]==2)swap(nums[right--],nums[i--]);

}
return;
}
};


## 快速排序

class Solution {
public:
void quicksort(int left,int right, vector<int>& nums)
{
if(left>=right)return;
int i = left;
int j = right;
while(i<j)
{
while(i<j && nums[j]>=nums[left])j--;
while(i<j && nums[i]<=nums[left])i++;

if(i<j)
{
swap(nums[i],nums[j]);
}

}
swap(nums[left],nums[i]);
quicksort(left,i-1,nums);
quicksort(i+1,right,nums);
}
void sortColors(vector<int>& nums) {
int len = nums.size();
if(len==0 || len==1)return;
quicksort(0,len-1,nums);
return;
}
};


# 74. 搜索二维矩阵

class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.empty())return false;
if(matrix[0].empty())return false;
int len = matrix.size();
int left = 0,right = len;
while(left<right)
{
int mid = (left+right)/2;
if(matrix[mid][0]==target)return true;
else if(matrix[mid][0]<target)
{
left = mid+1;
}
else
{
right = mid;
}
}
int temp = left-1;
if(temp<0)return false;
len = matrix[0].size();
left = 0;right=len;
while(left<right)
{
int mid = (left+right)/2;
if(matrix[temp][mid]==target) return true;
else if(matrix[temp][mid]<target)
{
left=mid+1;
}
else
{
right=mid;
}
}
return false;
}
};


# 77. 组合

class Solution {
private:
vector<vector<int> > res;
vector<int> path;
public:
void dfs(int n,int pos, int k)
{
if (path.size()==k)
{
res.push_back(path);
}
for(int i = pos; i<= n; i++)
{
path.push_back(i);
dfs(n,pos+1,k);
path.pop_back();
pos++;
}
}

vector<vector<int>> combine(int n, int k) {
if(n==0||k==0) return res;
dfs(n,1,k);
return res;
}
};


class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> list;
vector<int> result;
dfs(list,result,n,k,0,-1);
return list;
}
void dfs(vector<vector<int>>& list, vector<int>& result, int n, int k, int pos,int pre){
if(pos == k){
list.push_back(result);
return;
}
if((pos + (n-pre)) <= k)return;//剪枝，添加以后用时节省了2/3
//在当前对不合理的取值进行判断，结束下一层的递归操做。
//若是当前剩余可操做数字的个数即（n-pre）< k-pos+1(即组合中有待赋值的位置个数)，（+1是由于当前pos尚未进行操做），则能够判断该条路径不可能获得正确的解，再也不向下探寻。
for(int i=pre+1; i<n ; i++){
result.push_back(i+1);
pre = i;
dfs(list,result,n,k,pos+1,pre);
result.pop_back();//回溯
}
return;
}
};



# 78. 子集

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


class Solution {
public:
vector<vector<int>> ans;
vector<int> tmp;
void find(int dep, vector<int>& nums)
{
// 已经处理完最后一位，将目前存储的集合存入 ans ，并回溯
if(dep <= 0)
{
ans.push_back(tmp);
return;
}
// 状况一：集合中有该元素
tmp.push_back(nums[dep - 1]);
find(dep - 1, nums);
tmp.pop_back();
// 状况二：集合中无该元素
find(dep - 1, nums);
}

vector<vector<int>> subsets(vector<int>& nums) {
find(nums.size(), nums);
return ans;
}
};



# 79. 单词搜索

class Solution {
private:
string s1;
int h=0;
int l = 0;
public:

//位置必须传递，才能和上次有关联
bool dfs(char s1, string& s, int a , int b , vector<vector<char>>& board)
{
if(a==0)
{
if(b==0)
{
if(board[a+1][b]==s1 || board[a][b+1]==s2){return true;}}
}
if(b==l-1 )
{
if(board[a+1][b]==s1 || board[a][b-1]==s2){return true;}}
}
else
{
if(board[a+1][b]==s1 || board[a][b+1]==s2 || board[a][b-1]==s2){return true;}}
}

for(int j = 0 ; j <b ; j++ )
{
if(board[a+1][j]==s1){return true;}

}
if(a==h-1)
{
for(int j = 0 ; j <b ; j++ )
{
if(board[a-1][j]==s1){return true;}
}
}
if(b==l-1)
{
for(int i = 0 ; i<a; i++)
{
if(board[i][])
}
}

for(auto i :s)
{

dfs(i,s,)

}

}
bool exist(vector<vector<char>>& board, string word) {
h = board.size();
l = board[0].size();
//如何获取第一次的正确位置，或者进行遍历寻找
for(int i = 0 ; i< h;i++ )
{
for(int j = 0; j<l ; j++)
{
if (board[i][j]==word[0])//这里不用判断
{
if(dfs(word[1],word,i,j,board)){return true;}
}
}
}
return false;

}
};

class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
if(board.size() == 0) return false;
for (int i=0;i<board.size();i++){
for(int j=0;j<board[0].size();j++){
if (dfs(board,word,i,j,0)){
return true;
}
}
}
return false;
}

bool dfs(vector<vector<char>>& board, string& word, int i,int j,int length){
if(i>=board.size()||j>=board[0].size()||i<0||j<0||length>=word.size()||word[length]!=board[i][j]){
return false; //出界或者最后一位不相等
}
if(length==word.size()-1&&word[length]==board[i][j]){//word不为空且最后一位和当前位置相等
return true;
}
char temp=board[i][j];
board[i][j]='0';//这个位置
bool flag=dfs(board,word,i,j+1,length+1)||dfs(board,word,i,j-1,length+1)||dfs(board,word,i+1,j,length+1)||dfs(board,word,i-1,j,length+1); //找四边的每个点，若是点
board[i][j]=temp;  // 标记过的点恢复原状，以便进行下一次搜索
return flag;
}
};



dfs（i，j，word， board，len）
{
if（i，j已经出界 || 这个位置和wordlen元素不相等）
{返回false}
if（这个位置和word最后一维相等）
{返回true}

}
exist（）
{
遍历board，并对每个位置执行一次判断//当每一个位置都输入进去，直接进入dfs，判断和第一位是否相等，若是不相等则到下一个位置，若是相等则进入函数主体，判断四周的四个位置都和下一位相等，true的终止条件是到了最后一位并且与此位置相等。里面有一点要注意为了防止出现AEA这种又回去的状况，在这次搜索中已经相等过的要设置为‘0’防止回去
}


1.总结：dfs也能够设置为有类型的，当设置为bool型这种特殊的类型时，要写两个终止条件，一个是true的，一个是false，false能够是每次的回退条件，可是true必定是最终的判断条件，剩下的函数主题就是默认的经过这次验证

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

class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int len = nums.size();
int i = 0, j = 0;
while(i<len)
{
int temp = i;
while(i<len && nums[i]==nums[temp])i++;
if(i-temp==1){nums[j++]=nums[temp];}
else if(i-temp>=2){nums[j++]=nums[temp];nums[j++]=nums[temp];}

}
return j;
}
};


# 81. 搜索旋转排序数组 II

class Solution {
public:
bool search(vector<int>& nums, int target) {
if(nums.empty())return false;
int j = 0;
for(int i =1 ;i<(int)nums.size() ;i++)
{if(nums[i]!=nums[j])nums[++j]=nums[i];}
vector<int> num;
num.assign(nums.begin(),nums.begin()+j+1);
if((int)num.size()>1 && num[j]==num[0]){num.pop_back();}
int right = num.size();
int left = 0;
while(left<right)
{
int mid = left + (right-left)/2;
if(num[mid]==target){return true;}
else if (num[mid]>target)
{
if(target>=num[0] || num[mid]<num[0]){right = mid;}
else{left=mid+1;}
}
else
{
if(num[mid]>=num[0] ||target<num[0]){left=mid+1;}
else{right=mid;}
}
}
return false;
}
};


# 88. 合并两个有序数组

class Solution {
public:
void merge(vector<int>& arr1, int m, vector<int>& arr2, int n) {
//int len1 = arr1.size();
//int len2 = arr2.size();
if(m==0)
{
arr1.assign(arr2.begin(),arr2.end());
return;
}
if(n==0) return;
int i = m - 1;
int j = n - 1;
int k = m + n - 1;
while (i>= 0 && j>= 0)
{
while (i>= 0 && j>=0 && arr1[i] >= arr2[j])
{
arr1[k--] = arr1[i--];
}
while (i >= 0 && j >= 0 && arr1[i] <= arr2[j])
{
arr1[k--] = arr2[j--];
}

}
while (i>=0 )
{
arr1[k--] = arr1[i--];
}
while (j>=0)
{
arr1[k--] = arr2[j--];
}
return ;
}
};


# 91.

## 字符串转数字

atoi(str.c_str());


## 字符转数字

int(char-'0')


# 94. 二叉树的中序遍历

/**
* 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 {
vector<int> res;
public:
void dfs(TreeNode* root)
{
if(!root) return;

dfs(root->left);
res.push_back(root->val);
dfs(root->right);
}

vector<int> inorderTraversal(TreeNode* root) {
if(!root) return res;
dfs(root);
return res;
}
};


# 95. 不一样的二叉搜索树 II

2 做为根节点，[ 1 ] 做为左子树，[ 3…n ] 的全部可能做为右子树。

3 做为根节点，[ 1 2 ] 的全部可能做为左子树，[ 4 … n ] 的全部可能做为右子树，而后左子树和右子树两两组合。

4 做为根节点，[ 1 2 3 ] 的全部可能做为左子树，[ 5 … n ] 的全部可能做为右子树，而后左子树和右子树两两组合。

n 做为根节点，[ 1… n ] 的全部可能做为左子树，[ ] 做为右子树。

class Solution {
public:
vector<TreeNode*> helper(int start,int end){
vector<TreeNode*> ret;
if(start > end)
ret.push_back(nullptr);

for(int i=start;i<=end;i++){
vector<TreeNode*> left = helper(start,i-1);
vector<TreeNode*> right = helper(i+1,end);
for(auto l : left){
for(auto r : right){
TreeNode* root = new TreeNode(i);
root -> left = l;
root -> right = r;
ret.push_back(root);
}
}
}
return ret;
}

vector<TreeNode*> generateTrees(int n) {
vector<TreeNode*> ret;
if(n == 0)
return ret;
ret = helper(1,n);
return ret;
}
};



# 97. 交错字符串

class Solution {
private:
int len1;
int len2;
int len3;
public:
bool dfs(int i, int j, int k, string& s1, string &s2, string &s3)
{
if(i==len1 && j==len2 && k==len3) return true;

if(i<len1 && j<len2)
{
if(s2[j]!=s3[k]&&s1[i]==s3[k])
{
return dfs(i+1,j,k+1,s1,s2,s3);
}
if(s1[i]!=s3[k]&&s2[j]==s3[k])
{
return dfs(i,j+1,k+1,s1,s2,s3);
}
if(s1[i]==s3[k]&&s2[j]==s3[k])
{
return dfs(i+1,j,k+1,s1,s2,s3)||dfs(i,j+1,k+1,s1,s2,s3);
}
if(s1[i]!=s3[k]&&s2[j]!=s3[k])
{
return false;
}
}
if(i==len1 && j<len2)
{
if(s2[j]==s3[k]) return dfs(i,j+1,k+1,s1,s2,s3);
else{return false;}
}
if(i<len1 && j==len2)
{
if(s1[i]==s3[k]) return dfs(i+1,j,k+1,s1,s2,s3);
else{return false;}
}

}

bool isInterleave(string s1, string s2, string s3) {
len1 = s1.size();
len2 = s2.size();
len3 = s3.size();
if(len1+len2 != len3) return false;
if(s1.empty()&&s2.empty()&&s3.empty()) return true;
return dfs(0,0,0,s1,s2,s3);
}
};


# 98. 验证二叉搜索树（dfs）

/**
* 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:

//用来遍历，得到全部节点下的值
void dfs1(TreeNode* root, vector<int>& res)
{
if(!root) return;
res.push_back(root->val);
dfs1(root->left,res);
dfs1(root->right,res);
}

//用来判断每一个节点做为根节点时候是否符合标准
bool dfs2(TreeNode* root, vector<int> r1, vector<int> r2)
{
if(r1.empty() && r2.empty()) return true;
if(!r1.empty() && r2.empty())
{
for(auto i:r1)
{
if(i>=root->val)return false;
}
}
if(r1.empty() && !r2.empty())
{
for(auto i:r2)
{
if(i<=root->val)return false;
}
}
for(auto i:r1)
{
if(i>=root->val)return false;
}
for(auto i:r2)
{
if(i<=root->val)return false;
}
return true;
}

//对每个进行判断
bool df3(TreeNode* root)
{
vector<int> left;
dfs1(root->left,left);
vector<int> right;
dfs1(root->right,right);
return dfs2(root,left,right);
}
//遍历并返回判断结果
void df4(TreeNode* root, bool& flag)
{
if(!root) return;

if(!df3(root)) flag = false;
isValidBST(root->left);
isValidBST(root->right);
}
bool isValidBST(TreeNode* root) {
if(!root) return true;

bool flag=true;
df4(root,flag);
if(flag==true)return true;
return false;

}
};


bool fun(struct TreeNode* root, long low, long high) {
if (root == NULL) return true;
long num = root->val;
if (num <= low || num >= high) return false;
return fun(root->left, low, num) && fun(root->right, num, high);
}
bool isValidBST(struct TreeNode* root){
return fun(root, LONG_MIN, LONG_MAX);
}



# 100. 相同的树

/**
* 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:
bool isSameTree(TreeNode* p, TreeNode* q) {
//一种适用性很强的办法，都通过层序遍历，比较最后的结果，但这确定不是最优解法
if(p==NULL && q==NULL)return true;
if(p==NULL && q!= NULL)return false;
if(p!=NULL && q==NULL)return false;
if(p->val != q->val)return false;
return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}
};


# 101. 对称二叉树

/**
* 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:
bool dfs(TreeNode* root1, TreeNode* root2)
{
if(root1==NULL && root2==NULL){return true;}
if(root1==NULL && root2!=NULL){return false;}
if(root1!=NULL && root2==NULL){return false;}
if(root1->val!=root2->val){return false;}

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

bool isSymmetric(TreeNode* root) {
if(root==NULL){return true;}
return dfs(root->left,root->right);

}
};


# 102. 二叉树的层序遍历

/**
* 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 {
private:
vector<vector<int> > res;
public:
void dfs(vector<TreeNode*> cur)
{
if(cur.size()==0){return;}
vector<int> temp;
vector<TreeNode*> next;
for(auto i:cur)
{
temp.push_back(i->val);
if(i->left!=NULL){next.push_back(i->left);}
if(i->right!=NULL){next.push_back(i->right);}
}
res.push_back(temp);
dfs(next);

}
vector<vector<int>> levelOrder(TreeNode* root) {
if(root==NULL){return res;}
vector<TreeNode*> cur;
cur.push_back(root);
dfs(cur);
return res;
}
};


class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
vector<int> level;
if(root == nullptr) return res;
queue<TreeNode*> que;
que.push(root);
que.push(nullptr);
TreeNode *cur = nullptr;
while(que.size()){
cur = que.front();
que.pop();
if(cur){
level.push_back(cur->val);
if(cur->left) que.push(cur->left);
if(cur->right) que.push(cur->right);
}else{
res.push_back(level);
level.resize(0);
if(que.size() > 0) que.push(nullptr);
}
}
return res;
}
};


# 103. 二叉树的锯齿形层次遍历

/**
* 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 {
private:
vector<vector<int> > res;
bool flag;
public:
void dfs(vector<TreeNode*> cur)
{
if(cur.size()==0){return;}
vector<TreeNode*> next;
vector<int> temp;
for(auto i:cur)
{
if(i->left!=NULL){next.push_back(i->left);}
if(i->right!=NULL){next.push_back(i->right);}
temp.push_back(i->val);
}
if(!flag){reverse(temp.begin(),temp.end());}
flag = !flag;
res.push_back(temp);
dfs(next);
}
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
if(root==NULL){return res;}
vector<TreeNode*> temp;
temp.push_back(root);
flag = 1;
dfs(temp);
return res;
}
};


# 104. 二叉树的最大深度(***********)

/**
* 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:
int maxDepth(TreeNode* root) {
if(root==NULL)return 0;
return max(  maxDepth( root->left) , maxDepth( root->right)  )+1;
}
};


/**
* 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 {
private:

int max;
public:
void dfs(TreeNode* root, int num)
{
if(root->left==NULL&&root->right==NULL){return;}

if(root->left!=NULL)
{
num++;
if(max<num){max=num;}
dfs(root->left,num);
num--;
}
if(root->right!=NULL)
{
num++;
if(max<num){max=num;}
dfs(root->right,num);
num--;
}

}
int maxDepth(TreeNode* root) {
max=0;
if(root==NULL){return max;}
max=1;
dfs(root,1);
return max;
}
};


# 105. 从前序与中序遍历序列构造二叉树

/**
* 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 {
private:

public:
TreeNode* dfs(vector<int>& preorder, vector<int>& inorder)
{
if(preorder.size()==0){return NULL;}
if(preorder.size()==1)
{
TreeNode* temp = new TreeNode(preorder[0]);
return temp;
}
int mid = find(inorder.begin(),inorder.end(),preorder[0])-inorder.begin();
TreeNode* root= new TreeNode(preorder[0]);

vector<int> p1(preorder.begin()+1,preorder.begin()+ mid+1);
vector<int> q1(inorder.begin() ,inorder.begin()+ mid);
root->left = dfs(p1,q1);

vector<int> p2(preorder.begin()+mid+1, preorder.end());
vector<int> q2(inorder.begin()+mid+1 ,inorder.end());
root->right =dfs(p2,q2);

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

if(preorder.size()==0){return NULL;}
TreeNode* root = dfs(preorder,inorder);
return root;
}
};


/**
* 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:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int pos = 0;
return buildTree(preorder, pos, inorder, 0, inorder.size()-1);
}

TreeNode* buildTree(vector<int>& preorder, int& pos, vector<int>& inorder, int left, int right) {
if (pos >= preorder.size()) return 0;
int i = left;
for (i = left; i <= right; ++i) {
if (inorder[i] == preorder[pos]) break;
}
TreeNode* node = new TreeNode(preorder[pos]);
if (left <= i-1) node->left = buildTree(preorder, ++pos, inorder, left, i-1);  // 左子树
if (i+1 <= right) node->right = buildTree(preorder, ++pos, inorder, i + 1, right);  // 右子树
return node;
}
};



# 106. 从中序与后序遍历序列构造二叉树

/**
* 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:
TreeNode* dfs(vector<int>& inorder,vector<int>& postorder)
{
if(inorder.size()==0){return NULL;}
if(inorder.size()==1)
{
TreeNode* temp = new TreeNode(inorder[0]);
return temp;
}

int mid = find(inorder.begin(), inorder.end(), postorder[postorder.size()-1] )- inorder.begin();
TreeNode* root = new TreeNode(inorder[mid]);
vector<int> l1(inorder.begin(), inorder.begin()+mid);
vector<int> l2(postorder.begin(), postorder.begin()+mid);
root->left = dfs(l1, l2);
vector<int> r1(inorder.begin()+mid+1, inorder.end());
vector<int> r2(postorder.begin()+mid, postorder.end()-1);
root->right = dfs(r1,r2);
return root;
}

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if(postorder.size()==0){return NULL;}
TreeNode* root =  dfs(inorder,postorder);
return root;
}
};


# 107. 二叉树的层次遍历 II

/**
* 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 {
private:
stack<vector<int>> res;
public:
void dfs(vector<TreeNode*> cur)
{
if(cur.size()==0){return;}

vector<int> temp;
vector<TreeNode*> next;
for(auto i:cur)
{
if(i->left!=NULL){next.push_back(i->left);}
if(i->right!=NULL){next.push_back(i->right);}
temp.push_back(i->val);
}
res.push(temp);
dfs(next);
}

vector<vector<int>> levelOrderBottom(TreeNode* root) {

vector<TreeNode*> temp;
temp.push_back(root);
vector<vector<int>> r;
if(root==NULL){return r;}
dfs(temp);
while(!res.empty())
{
r.push_back(res.top());
res.pop();
}
return r;
}
};


# 108. 将有序数组转换为二叉搜索树(****)

dfs方法

class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return bst(nums,0,nums.size()-1);
}
TreeNode* bst(vector<int>& a,int l,int r){
if(l>r) return NULL;
int mid=(r-l)/2+l;
TreeNode* root=new TreeNode(a[mid]);
root->left=bst(a,l,mid-1);
root->right=bst(a,mid+1,r);
return root;
}
};



# 109. 有序链表转换二叉搜索树

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
/**
* 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:
TreeNode* dfs(vector<int>& nums, int left, int right)
{
if(left>right) return NULL;
int mid = left+(right-left)/2;
auto root = new TreeNode(nums[mid]);
root->left = dfs(nums,left,mid-1);
root->right = dfs(nums,mid+1,right);
return root;

}
//其实跟上一题区别不大，只是数组换成了链表，能够把链表转换成数组，而后和上题同样
vector<int> v;
int len = v.size();
return dfs(v,0,len-1);
}
};


# 110. 平衡二叉树

/**
* 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:
bool isBalanced(TreeNode* root) {
if(!root) return true;

int d = abs(depth(root->left)-depth(root->right)); //当前节点的左右子树的高度差

return (d<=1) && (isBalanced(root->left)) && (isBalanced(root->right));
}

// 求解二叉树深度（104题）
int depth(TreeNode* node)
{
if(node ==NULL) return 0;
return max( depth(node->left), depth(node->right) )+1;
}

};



# 111. 二叉树的最小深度

/**
* 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:
int minnn(TreeNode* root)
{
if(!root->left && !root->right){return 0;}
if(root->left && !root->right){return minnn(root->left)+1;}
if(!root->left && root->right){return minnn(root->right)+1;}
return min(minnn(root->left),minnn(root->right))+1;
}
int minDepth(TreeNode* root) {
if(!root){return 0;}
return minnn(root)+1;
}
};


# 112. 路径总和

1.当根节点为空，其路径和不存在而不是为空，0和空在这里是不同的，以前这个地方就错过
2.这题的终止条件是到叶节点，因此终结条件（正+负）必须是关于叶节点的
3.不管是最大最小仍是其余，逻辑关系都体如今dfs的返回方式的逻辑关系上
4.sum这种变化的值能够做为参数

/**
* 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:
bool dfs(TreeNode* root, int sum)
{
if(!root->left && !root->right)
{
if(root->val==sum)return true;
return false;
}
if(!root->left && root->right)return dfs(root->right,sum-root->val);
if(!root->right && root->left)return dfs(root->left,sum-root->val);
return dfs(root->left,sum-root->val) || dfs(root->right,sum-root->val);

}
bool hasPathSum(TreeNode* root, int sum) {
if(!root)return false;
return dfs(root,sum);
}
};


# 113. 路径总和 II

/**
* 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 {
private:
vector<vector<int>> res;
vector<int> path;
public:
void dfs(TreeNode* root,int sum)
{

if(!root->left && !root->right)
{
path.push_back(root->val);
if(root->val==sum) res.push_back(path);
path.pop_back();
return;
}
if(root->left)
{
path.push_back(root->val);
dfs(root->left,sum-root->val);
path.pop_back();
}
if(root->right)
{
path.push_back(root->val);
dfs(root->right,sum-root->val);
path.pop_back();
}

}
vector<vector<int>> pathSum(TreeNode* root, int sum) {
if(!root)return res;
dfs(root,sum);
return res;
}
};


# 114. 二叉树展开为链表

/**
* 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 {
private:
vector<int> list;
public:
//先序遍历
void dfs(TreeNode* root)
{
if(!root ) return ;
list.push_back(root->val);
dfs(root->left);
dfs(root->right);
}

void dfs2(TreeNode* root,int pos, vector<int> list)
{
if(pos==list.size()) return;
TreeNode* temp = new TreeNode(list[pos]);
root->left = NULL;
root->right = temp;
dfs2(temp,pos+1,list);
}
void flatten(TreeNode* root) {
//作一下层序遍历，求出数组，而后都放到右孩子上
if(!root)return;
dfs(root);
dfs2(root,1,list);
return;

}
};


# 115. 不一样的子序列

class Solution {

public:
void dfs(int& num,vector<int>& path, int pos, vector<vector<int>>& board)
{
if(path.size()==board.size())
{
num++;
return;
}

for(int i:board[pos])
{
if( pos==0 || (pos>0 && i>path[path.size()-1])  )
{
path.push_back(i);
dfs(num,path,pos+1,board);
path.pop_back();
}
}
}

int numDistinct(string s, string t) {
if(s.empty())return 0;
int lens = s.size();
int lent = t.size();
vector<vector<int>> board;
for(int i = 0 ; i<lent ; i++)
{
vector<int> temp;
for(int j = 0; j<lens ; j++)
{
if(s[j]==t[i])
{
temp.push_back(j);
}

}
board.push_back(temp);
}
int num = 0;
vector<int> path;
int pos = 0;
dfs(num,path,pos,board);
return num;

}
};


# 116. 填充每一个节点的下一个右侧节点指针(bfs)

dfs是深度优先遍历，有前序中序后序，参数为根节点；bfs是广度优先遍历，没有什么序之说，在遍历是后习惯用一个数组存放每一层的全部节点或者节点值，参数为数组

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

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

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

Node(int _val, Node* _left, Node* _right, Node* _next)
: val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
vector<vector<Node*>> res;
public:
void bfs(vector<Node*> cur)
{
if(cur.empty())return;
vector<Node*> temp;
for(auto i:cur)
{
if(i->left)temp.push_back(i->left);
if(i->right)temp.push_back(i->right);
}

bfs(temp);
res.push_back(temp);
}

Node* connect(Node* root) {
if(!root) return NULL;
vector<Node*> cur;
cur.push_back(root);
res.push_back(cur);
bfs(cur);
for(auto i : res)
{
if(i.size()==1){continue;}
int m = i.size();
for(int j = 0 ; j< m-1; j++)
{
i[j]->next=i[j+1];
}
}
return root;
}
};


# 118. 杨辉三角

class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> res;
if(numRows==0) return res;
vector<int> t = {1};
res.push_back(t);
if(numRows==1) return res;
t.push_back(1);
res.push_back(t);
if(numRows==2) return res;
numRows -=2;
vector<int> cur = {1,1};
while(numRows--)
{
vector<int> temp;
temp.push_back(1);
int len = cur.size();
for(int i = 0 ; i<len-1 ; i++)
{
temp.push_back(cur[i]+cur[i+1]);
}
temp.push_back(1);
cur.assign(temp.begin(),temp.end());
res.push_back(cur);
}
return res;
}
};


# 119. 杨辉三角 II

class Solution {
public:
vector<int> getRow(int numRows) {
vector<int> t = {1};
if(numRows==0) return t;
t.push_back(1);
if(numRows==1) return t;
numRows -=1;
vector<int> cur = {1,1};
while(numRows--)
{
vector<int> temp;
temp.push_back(1);
int len = cur.size();
for(int i = 0 ; i<len-1 ; i++)
{
temp.push_back(cur[i]+cur[i+1]);
}
temp.push_back(1);
cur.assign(temp.begin(),temp.end());
}
return cur;
}
};


line用于记录n层到n-1层最短的路径长度，其初始值为triangle的第n行。其递归公式为：

line[j] = triangle[i][j] + min(line[j], line[j + 1])，i 表示当前自下向上到达第 i 层。
line[j]=triangle[i][j]+min(line[j],line[j+1])，i表示当前自下向上到达第i层。

class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();
vector<int> line(triangle[n - 1]);
for (int i = n - 2; i >= 0; i--)
for (int j = 0; j <= i; j++)
line[j] = triangle[i][j] + min(line[j], line[j + 1]);
return line[0];
}
};



# 121. 买卖股票的最佳时机（dp）

class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.empty())return 0;
int dp=prices[0],res = 0;
for(int i = 1; i< (int)prices.size() ;i++)
{
dp = min(dp,prices[i]);
res = max(res, prices[i]-dp);
}
return res;
}
};


class Solution {
public:
int maxProfit(vector<int>& prices) {
int inf = 1e9; //很大的值
int minprice = inf, maxprofit = 0;
for (int price: prices) {
maxprofit = max(maxprofit, price - minprice);
minprice = min(price, minprice);
}
return maxprofit;
}
};


class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
if(len==0 || len==1)return 0;
int minvalue = prices[0];
int maxvalue = INT_MIN;
for(int i = 1 ; i<len ; i++)
{
minvalue = min(minvalue,prices[i-1]);
maxvalue = max(maxvalue,prices[i]-minvalue);
}
if(maxvalue<0)return 0;
return maxvalue;
}
};


class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if (n == 0) return 0; // 边界条件
int minprice = prices[0];
vector<int> dp (n, 0); //新建一个数组
//在动态变化中维护了最小值，老是能得到这个点以前的最小值
//最后原本不用再和本身比较了，可是题目有一个特殊要求，就是不能小于0，因此再生成这个动态数组的时候，每次都要和0比较，若是小于0就不要了
for (int i = 1; i < n; i++){
minprice = min(minprice, prices[i]);
dp[i] = max(dp[i - 1], prices[i] - minprice);
}
return dp[n - 1];
}
};



# 122. 买卖股票的最佳时机 II

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


class Solution {
public:
int maxProfit(vector<int>& prices) {
//快慢指针标记
int i=0,j=1,sum=0;
//判断vector大小
if(prices.size()<=1)
return 0;

//两个指针一直紧挨在一块儿，只有j的值大于i的值时，就把差值加入sum中
while(j<prices.size()){
if(prices[j]-prices[i]>0)
sum+=(prices[j]-prices[i]);

i++;
j++;
}
return sum;
}
};



# 123. 买卖股票的最佳时机 III

class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.empty())return 0;
int res1 = 0, dp1 = prices[0], res = 0;
for(int i =1 ; i< (int)prices.size() ;i++)
{
dp1 = min(dp1, prices[i]);
res1 = max(res1, prices[i]-dp1);
int dp2 = prices[i];
int res2 = 0;
for(int j = i+1 ; j<(int)prices.size() ;j++)
{
dp2 = min(dp2, prices[j]);
res2 = max(res2, prices[j]-dp2);
}
res = max(res, res1+res2);
}
return res;
}
};


# 124. 二叉树中的最大路径和(dfs,不懂)

/**
* 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:
//一个 根，左，右 的路径状况有（根，左+根，根+右，左+根+右）
//可是该根做为其父亲的孩子时，其max 应该为 max（根，左+根，根+右）.若是包含左+根+右，则加上其父亲就构不成路径了
int maxPathSum(TreeNode* root) {
long long gMax = LLONG_MIN;
maxPathSumCore(root, gMax);
return gMax;
}

int maxPathSumCore(TreeNode* root, long long& gMax){
if(root==nullptr) return 0;
int curVal = root->val;
int leftMax = maxPathSumCore(root->left, gMax);
int rightMax = maxPathSumCore(root->right, gMax);
long long curMax = max(curVal, max(curVal+leftMax, max(curVal+rightMax, curVal+leftMax+rightMax)));
if(curMax>gMax) gMax = curMax;
return max(curVal, max(curVal+leftMax, curVal+rightMax));
}
};



# 128. 最长连续序列

class Solution {
public:
int longestConsecutive(vector<int>& nums) {
if(nums.empty()){
return 0;
}
unordered_set<int> myset(nums.begin(), nums.end());
int res = 0;

for(auto num : nums){
if(myset.count(num-1)==0){
int x = num + 1;
while(myset.count(x)){
x ++;
}
res = max(res, x-num);
}
}
return res;
}
};



# 129. 求根到叶子节点数字之和

## 字符串转数字

int num = 0 ;
string s = "sdfsf";
num = std::atoi(s.c_str());

/**
* 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 {
private:
vector<string> res;
string s;
public:
void dfs(TreeNode* root)
{
if(!root->left && !root->right)
{
s = s + to_string(root->val);
res.push_back(s);
s.pop_back();
}
if(root->left)
{
s = s + to_string(root->val);
dfs(root->left);
s.pop_back();
}
if(root->right)
{
s = s + to_string(root->val);
dfs(root->right);
s.pop_back();
}

}
int sumNumbers(TreeNode* root) {
if(!root)return 0;
dfs(root);
int sum = 0;
for(auto i:res)
{
sum += atoi(i.c_str());
}
return sum;
}
};


# 130. 被围绕的区域

/*
First, check the four border of the matrix. If there is a element is
'O', alter it and all its nei***or 'O' elements to '1'.

Then ,alter all the 'O' to 'X'

At last,alter all the '1' to 'O'

For example:

X X X X           X X X X             X X X X
X X O X  ->       X X O X    ->       X X X X
X O X X           X 1 X X             X O X X
X O X X           X 1 X X             X O X X
*/
class Solution {
public:
void solve(vector<vector<char>>& board) {
if(board.size()==0){
return;
}
int rows=board.size(),cols=board[0].size();
//对边界上的进行dfs
for(int i=0;i<rows;i++){
dfs(board,i,0);
dfs(board,i,cols-1);
}
for(int j=1;j<cols-1;j++){
dfs(board,0,j);
dfs(board,rows-1,j);
}
//遍历所有的，1变0，其余为X，很巧妙的先把这些量都标出来来了
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
if(board[i][j]=='1'){
board[i][j]='O';
}
else{
board[i][j]='X';
}
}
}
}
private:
void dfs(vector<vector<char>>& board,int i,int j){
//若是既不在边界上并且又为X的直接跳过，当此边界上的点为0时才有动做
//若是在边界上为O，就直接改为1
if(i>=0&&i<board.size()&&j>=0&&j<board[0].size()&&board[i][j]=='O'){
board[i][j]='1';
dfs(board,i-1,j);
dfs(board,i+1,j);
dfs(board,i,j-1);
dfs(board,i,j+1);
}
}
};


在这里插入代码片


# 144. 二叉树的前序遍历

/**
* 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 {
private:
vector<int> res;
public:
void dfs(TreeNode* root)
{
if(root==NULL)return;
res.push_back(root->val);
dfs(root->left);
dfs(root->right);
}
vector<int> preorderTraversal(TreeNode* root) {
dfs(root);
return res;
}
};


# 146. LRU缓存机制

// key 映射到 Node(key, val)
HashMap<Integer, Node> map;
// Node(k1, v1) <-> Node(k2, v2)...
DoubleList cache;

int get(int key) {
if (key 不存在) {
return -1;
} else {
将数据 (key, val) 提到开头；
return val;
}
}

void put(int key, int val) {
Node x = new Node(key, val);
if (key 已存在) {
把旧的数据删除；
将新节点 x 插入到开头；
} else {
if (cache 已满) {
删除链表的最后一个数据腾位置；
删除 map 中映射到该数据的键；
}
将新节点 x 插入到开头；
map 中新建 key 对新节点 x 的映射；
}
}


class LRUCache {
public:
//删除、查找、插入的复杂度都O（1）
LRUCache(int capacity) {
cap=capacity;
}
int get(int key) {
if(hashtable.count(key)==0) return -1;
else//更新到表头
{
auto iter = hashtable[key];//找到对应结点地址
cache.splice(cache.begin(),cache,iter);//移动到链表头
return cache.begin()->second;//返回value
}
}

void put(int key, int value) {
if(hashtable.count(key)==0) {
//若是容量到了，删除尾部元素,再加上新结点
if(cache.size()==cap)   {
hashtable.erase(cache.back().first);
cache.pop_back();
}//直接添加
cache.push_front(make_pair(key,value));
hashtable[key]=cache.begin();
}
else {//若是插入相同key的元素，除了要移动，value也须要更新
auto iter = hashtable[key];
iter->second=value;//更新地址value
cache.splice(cache.begin(),cache,iter);//移动到链表头
hashtable[key]=cache.begin();   //更新hashtable的value
}
}
unordered_map<int,list<pair<int,int>>::iterator> hashtable;
list<pair<int,int>> cache;//key value
int cap=0;
};

/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/


class LRUCache {
public:
LRUCache(int capacity) {
_capacity = capacity;
}

int get(int key) {
if(_map.count(key) != 0)
{
int ret = (*_map[key]).second;
_list.erase(_map[key]);
_list.push_front({key, ret});
_map[key] = _list.begin();
return ret;
}
else return -1;
}

void put(int key, int value) {
if(_map.count(key) == 0)
{
if(_list.size() == _capacity)
{
int k = _list.back().first;
_map.erase(_map.find(k));
_list.pop_back();
}
}
else{
_list.erase(_map[key]);
_map.erase(_map.find(key));
}
_list.push_front({key, value});
_map[key] = _list.begin();
}

private:
unordered_map<int, list<pair<int, int>>::iterator> _map;
list<pair<int, int>> _list;
int _capacity;
};

/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/



# 150. 逆波兰表达式求值

class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<string> st;
//bool flag = true;第一次遇到的符号须要特殊处理，用flag来表示是不是第一个
for(auto token:tokens)
{
if(token=="+")
{
int t1 =atoi(st.top().c_str());
st.pop();
int t2 = atoi(st.top().c_str());
st.pop();
st.push(to_string(t1+t2));
}
else if(token=="-")
{
int t1 =atoi(st.top().c_str());
st.pop();
int t2 = atoi(st.top().c_str());
st.pop();
st.push(to_string(t2-t1));
}
else if(token=="*")
{
int t1 =atoi(st.top().c_str());
st.pop();
int t2 = atoi(st.top().c_str());
st.pop();
st.push(to_string(t1*t2));
}
else if(token=="/")
{
int t1 =atoi(st.top().c_str());
st.pop();
int t2 = atoi(st.top().c_str());
st.pop();
st.push(to_string(t2/t1));
}
else
{
st.push(token);
}
}
return atoi(st.top().c_str());
}
};


# 152. 乘积最大子数组(dp)

class Solution {
public:
int maxProduct(vector<int>& nums) {
int res = INT_MIN , imax = 1, imin =1;
for(int i = 0 ; i< (int)nums.size() ;i++)
{
if(nums[i]<0)swap(imax,imin);
imax = max(nums[i],imax*nums[i]);
imin = min (nums[i],imin*nums[i]);
res = max(res,imax);
}
return res;
}
};


# 153. 寻找旋转排序数组中的最小值

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


# 155. 最小栈

class MinStack {
private:
queue<int> q1;
queue<int> q2;
public:
/** initialize your data structure here. */
MinStack() {

}

void push(int x) {
if(q1.empty()&&q2.empty())q1.push(x);
else if(q1.empty())q2.push(x);
else if(q2.empty())q1.push(x);
}

void pop() {
if(q1.empty())
{
while(q2.size()>1)
{
q1.push(q2.front());
q2.pop();
}
q2.pop();
}
else
{
while(q1.size()>1)
{
q2.push(q1.front());
q1.pop();
}
q1.pop();
}
}

int top() {
int res;
if(q1.empty())
{
while(q2.size()>1)
{
q1.push(q2.front());
q2.pop();
}
res = q2.front();
q1.push(q2.front());
q2.pop();

}
else
{
while(q1.size()>1)
{
q2.push(q1.front());
q1.pop();
}
res = q1.front();
q2.push(q1.front());
q1.pop();
}
return res;
}

int getMin() {
int res = INT_MAX;
if(q1.empty())
{
while(!q2.empty())
{
res = min(res, q2.front());
q1.push(q2.front());
q2.pop();
}
}
else
{
while(!q1.empty())
{
res = min(res,q1.front());
q2.push(q1.front());
q1.pop();
}
}
return res;
}
};

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


class MinStack {
public:
stack<int> s;//数据栈
stack<int> min;//辅助栈
/** initialize your data structure here. */
MinStack() {

}

void push(int x) {
s.push(x);
if(min.empty()||x<=min.top())
{
min.push(x);
}
}

void pop() {
if(s.top()==min.top())
min.pop();
s.pop();
}

int top() {
return s.top();
}
int getMin() {
return min.top();
}
};



# 162. 寻找峰值

class Solution {
public:
int findPeakElement(vector<int>& nums) {
int len =nums.size();
if(len==0 || len ==1) return 0;
if(len==2)
{
int i = nums[0]>nums[1]? 0:1;
return i;
}
for(int i = 1 ; i<len-1 ;i++)
{
if(nums[i]>nums[i-1] && nums[i]>nums[i+1]) return i;
}
if(nums[0]>nums[1])return 0;
if(nums[len-1]>nums[len-2])return len-1;
return INT_MIN;

}
};


class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int len = numbers.size();
for(int i = 0 ;i<len ;i++)
{
auto iter = find(numbers.begin()+i+1,numbers.end(), target- numbers[i]);
if( iter!=numbers.end())
{
int temp = iter-numbers.begin();
vector<int> res={i+1,temp+1};
return res;
}
}
return {};
}
};


# 169. 多数元素

class Solution {
public:
int majorityElement(vector<int>& nums) {
int len = nums.size();
if(len==1) return nums[0];
sort(nums.begin(),nums.end());
return nums[len/2];
}
};


# 179. 最大数

————————————————

class Solution {
public:
string largestNumber(vector<int>& nums) {
string res = "";
sort(nums.begin(), nums.end(), [](int a, int b){
});
for(auto num : nums){
res += to_string(num);
}
return res[0] == '0' ? "0" : res;
}
};


class Solution {
public:
static inline bool func(const string& a, const string& b)
{
return a+b>b+a;
}
string largestNumber(vector<int>& nums) {
vector<string> st;
//st.assign(nums.begin(),nums.end());
for(auto i:nums)st.push_back(to_string(i));
sort(st.begin(),st.end(),func);
string res;
for(auto i:st)res += i;
while( (int)res.size()>1 && res[0]=='0')res = res.substr(1,(int)res.size()-1);
return res;
}
};


# 189. 旋转数组

class Solution {
public:
void rotate(vector<int>& nums, int k) {
int len = nums.size();
reverse(nums.begin(),nums.