55.常用算法思想
1.贪心算法思想 [455,376题]
每一次选择【正确】的且【最优】的解，然后不断地反复-循环。
eg：1元，5元，10元，20元，100元，200元，
付款 678最少得张数。
每次拿最大的面额，只要没超过总和，3张200,3张20,1张10元，1张5元，3张1元的。
[455] 孩子蛋糕问题。
child[1,2], cookie[1,2,3] 最优解2
child[1,5,2,3,4], cookie[1,3,7,8,2,1,1]
拿cookie中 拿最小的，去满足孩子里面最小的。 如何找最小的。先对数组进行排序。
int findContentChildren(vector<int> &g, vector<int> &s){
// s:cookie蛋糕, g:children
// 每次找完最小的，移除它。
sort(g.begin(), g.end()); // 数据先排序
sort(s.begin(), s.end());
int child =0;
int cookie =0;
while(child < g.length && cookie <s.length){
if(s[cookie] >= g[child]){
child++; // 满足了，学生后移。
}
cookie++;
}
return child;
}
2.回溯算法思想【78,90】
递归 和 回溯 密不可分，一般回溯都与递归结合使用。
回溯：不断地试探，发现选择不到目标时，就退回去重新选择。
eg：遍历二叉树，前序遍历，发现一直往左边找，找不到目标了，就退回去重新选择。
eg：RxJava，走到顶了，就回去。就是回溯思想。
eg：图的深度优先遍历，代表整个村庄都走过一遍，右手优先原则，不断地走 直到右边都走过了就放弃，。。。。
然后一个个节点退回去，看每个节点是否有子分支。
// 递归: 压栈和出栈的思想。
int sum(int num) {
if(num == 1) return 1;
return num + sum(num-1);
}
// 回溯：[1,2,3] 求所有的子序列 集。Sub sets
vector<vector<int>> subsets(vector<int> &nums) {
vector<vector<int>> res;
vector<int> path;
for(int i=0;i<nums.size(); i++) {
path.push_back(nums[i]);
res.push_back(path); //path 调用拷贝构造函数。得到集合[1],[1,2],[1,2,3]
}
return res;
}
// 递归实现，传引用进去。
void subsets(int index, vector<vector<int>> &res, vector<int> &path,vector<int> &nums){
if(index >= nums.size) return;
path.push_back(nums[index]);// 先往考虑的方向走完。
res.push_back(path); // 加入结果集合。
subsets(index+1, res, path, nums); // 继续递归
path.pop_back(); // 移除掉最后一个，不考虑了。
subsets(index+1, res, path, nums);
}
vector<vector<int>> subsets(vector<int> &nums) {
vector<vector<int>> res;
vector<int> path;
res.push_back(path); // 加入空集合
subsets(0,res, path,nums);
return res;
}
3.分治思想
把n的问题，分解成k个较小的子问题，这些问题是【相互独立】，求出子问题的解进行合并。就可以得到原问题的解。
eg：归并排序，
eg：【315】Count of smaller Numbers after self ： [5,2,6,1], 目标结果[2,1,1,0]
数数据后面，比自己小的数据个数。for循环两层嵌套，会超时。
4.动态规划算法思想，也有递归的思想。【70,198】
把n的问题，分解成k个较小的子问题，这些问题是【相互依赖】
把多个过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解.------动态规划，dp求解。
原问题+子问题，但是他们相互依赖。
eg: 列出所有爬楼梯的爬法。要么从i-1 爬一步上来，要么是从i-2爬二步上来。
eg: House Robber ，相邻的两个不能偷。求抢劫最大值。
// 加上前面的， 与前面item的最大值比较。
// 先求前面的，再求后面的，后面的item依赖前面的item的值。
int rob(vector<int> &nums) { 【1,2,3,1】--》【1,2,4,4】
// 最大，与前面的最大和 前面的签名最大+自己 的最大值。
if(nums.size() == 0) return 0;
if(nums.size() == 1) {
return nums[0];
}
if(nums.size() == 2) {
return max(nums[0], nums[1]);
}
vector<int> maxRob(nums.size(), 0); // 数组保存房间i，能偷的最大值，默认值0。
// 总数据大于2条。
maxRob[0] = nums[0];
maxRob[1] = max(nums[0], nums[1]);
// dp思想: 找最大的。
for(int i=2; i<nums.size(); i++) {
// 求最后一个房间的最大值：要求出前面房间的最大值，
// 取【当前房间值 nums[i]】+【前面的前面房间的最大值 maxRob[i-2]】 与 【当前房间签名房间最大值 maxRob[i-1]】 的最大值.
maxRob[i] = max(nums[i]+maxRob[i-2], maxRob[i-1]);
}
return maxRob[nums.size() -1]; // 返回最后能偷的最大值
}
快排，归并排序能手写。
