9.14 leetcode刷题复习
经验总结：
常用方法：
空间换时间法：开辟新的数组去记录信息
多索引方法：多指针、标记定位+遍历、碰撞指针、滑动窗口
查表法
回溯法：
暴力搜索的实现手段；
for循环遍历当前的所有可能选项；
要么选择，要么不选；
递归：
假设实现，找关系；
子函数递归，主函数调用子函数，以及主函数自身递归）
动态规划：
1.0-1背包问题
2.要么选择，要么不选
3.考虑从[0..n]并选中n
11 盛水容器
方法：碰撞指针
解题思路：
瓶颈在于高
注意left，right边界的操作
13 罗马数字转整数 **
方法：查表法
解题思路：
1.找到规律--数字的表达式？
2.逐个查表
实现：
写成了面向过程逐个if分支的程序，导致代码比较冗长
17 电话号码组合
方法：回溯法
解题思路：
1.构建字母表
2.设计回溯算法（通过递归子函数来实现，调用递归时通过一个for循环遍历每一种可能的选择）
19 删除链表倒数第N个节点
方法：快慢指针法
解题思路：
设计2个指针，一个先走N步，然后下一个再开始走，删除用虚拟头结点
20 有效的括号
方法：栈
解题思路：
根据入栈、出栈来判断
21 合并两个有序链表
方法：多指针法
解题思路：
设计多个指针，操作
22 括号生成 **
方法：回溯法
解题思路：
0.画一个树形图，来判断需要的变量
1.当前操作要么生成（，要么生成）
2.我考虑的是用两个变量来记录左括号和右括号
class Solution {
public:
vector<string> generateParenthesis(int n) {
ret.clear();
getRet(0,0,n,"");
return ret;
}
private:
vector<string> ret;
void getRet(int left,int right,int n,const string temp){
if(left==n && right==n){
ret.push_back(temp);
return ;
}
if(left<n)
getRet(left+1,right,n,temp+'(');
if(left>right)
getRet(left,right+1,n,temp+')');
}
};
代码实现：
用left，right2个变量去记录左括号和右括号的数量，然后每次要么生成左括号，要么生成右括号，注意条件限制，首先左括号数量要保证多于右括号才能生右括号，其次左括号的数量不能超过n
24.两两交换链表中的节点
方法：多指针技术
解题思路：
把需要操作的节点用指针去标记、追踪，即可
26.删除排序数组中的重复项
方法：多索引技术
解题思路：
设计2个索引，1个用来标记位置cur，1个用来遍历i
遍历i指向的元素若符合条件，便放入cur标记的位置
27.移除元素
方法：多索引技术（标记定位+遍历）
解题思路：
同上
39.组合总和 *
方法：回溯法
解题思路：
0.先画树形图，判断哪些是需要的
1.设计递归结构，每次递归前用for去遍历所有可能的选项
2.设计终止条件
经验：
回溯算法的一个小技巧，是把需要维护的状态变量作为形参去引用传递，这样回溯时就可以不用维护了
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
ret.clear();
int n=candidates.size();
if(n==0)
return ret;
vector<int> temp;
getRet(candidates,target,0,0,temp);
return ret;
}
private:
vector<vector<int>> ret;
void getRet(vector<int>& candidates,int target,int index,int sum,vector<int>& temp){
if(sum==target){
ret.push_back(temp);
return ;
}
int n=candidates.size();
for(int i=index;i<n;i++){
if(sum+candidates[i]<=target){
temp.push_back(candidates[i]);
getRet(candidates,target,i,sum+candidates[i],temp);
temp.pop_back();
}
}
}
};
46.全排列
方法：
回溯法
解题思路：
同上
51.N皇后 *
方法：
回溯法
解题思路：
1.设计出对角线、副对角线的判断方式
2.同上
经验：
回溯法和递归设计有1个区别是回溯法是遍历各种可能的选择，然后去判断；递归则类似于数学归纳法，设计好出口，然后假设已经完成该功能，然后向出口去迭代
66.加一 *
方法：
递归
解题思路：
大数加法：
1.基本操作
2.处理进位
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int n=digits.size();
if(n==0) return digits;
int carr=1;
for(int i=n-1;i>=0;i--){
int d=digits[i]+carr;
digits[i]=d%10;
carr=d/10;
if(carr==0) break;
}
if(carr) digits.insert(digits.begin(),carr);
return digits;
}
};
代码思路：
因为是加1，直接让carry初值为1即可，没必要拆分成2部分去驱动（拆分是指先做一次加1，再讨论）
69.求平方根 *
方法：
二分查找
牛顿迭代法
扩展：
辗转相除法求最大公约数
class Solution {
public:
int mySqrt(int x) {
if(x<2)
return x;
long long low=1L,high=(long long)x/2+1;
while(low<=high){
long long mid=(long long)low+(high-low)/2;
long long key=mid*mid;
if(key==x)
return mid;
else if(key<x)
low=mid+1;
else
high=mid-1;
}
return high;
}
};
现在有些搞不清楚二分查找法什么时候用等号了。。。
举例子即可
70.爬楼梯
方法：
dp、递归、循环都可以
75.颜色分类
方法：
桶排序？
77.组合
方法：
回溯法
78.子集 **
方法：
回溯法
解题思路：
0.画树形图
1.要么选择当前元素，要么不选择当前元素
79.单词搜索
方法：
回溯法
问题拆解：
1.边界判断，是否越界
2.4个方向，用1个二维数组记录，这样可以通过for循环去遍历
解题思路：
0.遍历每个单元格
1.从单元格开始查找
80.删除数组重复元素II
方法：
多索引（标记定位+遍历）
88.合并两个有序数组
方法：
开辟新空间法
101.对称二叉树
方法：
递归
102、104、111树的问题
方法：递归
112.路径总和
方法：
递归（子函数递归，主函数调用子函数，以及主函数自身递归）
解题思路：
子函数递归，主函数调用子函数，以及主函数自身递归）
118、119.杨辉三角形 **
方法：
循环、记录、空间换时间法
问题拆分：
1.杨辉三角各行之间的关系（当前行和上一行的规律）
解题思路：
记录上一行
根据上一行计算出当前行
迭代
121.股票买卖时机 *
方法：
贪心？假设法
解题思路：
允许反悔，买高了允许反悔；涨价了，立马收益（卖价-成本价）；多次求值取最大值
122.股票买卖时机II *
方法：
贪心？假设法
解题思路：
允许反悔，买高了允许成本降价；涨价了立马收益（卖价-成本价；成本价更新为当前卖价）；最终求和
136.找出只出现一次的数字
方法：
异或运算，自己与自己异或为0；0与A异或得A
144、145树的遍历
方法：
1.递归
2.循环（用栈模拟） **
146.LRU算法 ***
方法：
双向链表+hash表映射；头、尾指针
148.链表排序 ***
方法：
递归（子函数递归or非递归实现+主函数调用子函数、主函数递归调用自身）
解题思路：
归并排序：
1.分割链表
2.merge操作
