回溯算法
基础理论
- 溯法并不是什么高效的算法
- 回溯的本质是穷举,穷举所有可能,然后选出我们想要的答案
- 解决的问题:
组合问题:N个数里面按一定规则找出k个数的集合
切割问题:一个字符串按一定规则有几种切割方式
子集问题:一个N个数的集合里有多少符合条件的子集
排列问题:N个数按一定规则全排列,有几种排列方式
棋盘问题:N皇后,解数独等等 - 回溯法解决的问题都可以抽象为树形结构,集合的大小就构成了树的宽度,递归的深度,都构成的树的深度
思路
- 递归函数的返回值以及参数
- 回溯函数终止条件
- 回溯搜索的遍历过程
- 剪枝(在深度方向搜索过程中将重复部分去掉,结合目前所需的深度和剩余可有的深度)
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
处理节点;
backtracking(路径,选择列表); // 递归
回溯,撤销处理结果
}
}
组合
组合问题如何剪枝
77
216 组合总和III
回调函数的题目,在搜索时必须要重视加入和弹出的操作
17.电话号码的字母组合
如何将字符串变成整数
39. 组合总和
40.组合总和II
如何判断相同的数在同一层所产生的重复情况,用一个数组表示数字当前使用状态;将其排序后也可寻找与当前数值不相同的下一个数
无返回值函数中,可被修改的数组在调用时,必须使用指针或取址(&,*)
分割
131.分割回文串
isPalindrome.resize(s.size(), vector(s.size(), false));
如何判断回文
如何结束分割
标准函数库中的函数 string substr
93.复原IP地址
判断字符串是否符合规定,另写函数
子集
78.子集
经典回溯问题,无顺序问题
90.子集II
经典去重题,排序
491.递增子序列
哈希表:记录本层中重复数字是否使用
ans.back() 取数组最后一个数
排列
46.全排列
不存在某个元素的选择和不选择,每个元素都需要使用。利用数组记录每个元素的使用状态。
47.全排列 II
排序完判断同一层是否搜索过,再判断树枝上的元素是否使用过。
去重思路
使用unordered_set记录同一层已经使用过的元素 insert 判断当前元素是否在该无需集合中 find
332.重新安排行程
- 字典排序是什么意思:越快找到越好,即回溯的越少越好,因此递归函数返回为真即结束回溯,就是最好结果。
- 避免死循环出现:unordered_map<string, map<string, int>> targets
unordered_map<出发机场, map<到达机场, 航班次数>> targets
pair<const string, int>& target : targets[result[result.size() - 1]] pair const用法
51. N皇后
std::vectorstd::string chessboard(n, std::string(n, ‘.’));
37. 解数独
二维递归,遍历每一行每一列,因此回溯函数中有两个for循环。
回溯终止条件 bool返回,循环结束
贪心算法
贪心算法理论基础
- 选择每一阶段的局部最优,从而达到全局最优。
- 如何在贪心算法和动态规划算法中进行选择:举反例,若没有反例就可以使用贪心算法。
一般解题步骤
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
不好意思了,贪心没有套路,说白了就是常识性推导加上举反例。
题
455.分发饼干
根据饼干找人,同一饼干,看何人恰好满足饼干(两层for循环)
根据胃口找饼干(一层for循环,结合递减 index即可)
376. 摆动序列
需要统计数组的峰值数量
注意一些特殊情况,需要考虑
53. 最大子序和
假设累加和为负值时,重新开始计数
122.买卖股票的最佳时机II
记录每天的正利润,进行累加
55. 跳跃游戏
最大步数是否能覆盖终点
45.跳跃游戏II
判断什么时候进行步数加一,边界问题如何处理;何时结束;
1005.K次取反后最大化的数组和
sort(A.begin(), A.end(), cmp);
static bool cmp(int a, int b) {
return abs(a) > abs(b);
}
数组按照绝对值大小从大到小排序
134. 加油站
当前余量大于0才可为初始点
总余量小于0必然不可行
135. 分发糖果
- 一次是从左到右遍历,只比较右边孩子评分比左边大的情况。
一次是从右到左遍历,只比较左边孩子评分比右边大的情况。 - 就取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量
candyVec[i]只有取最大的才能既保持对左边candyVec[i - 1]的糖果多,也比右边candyVec[i + 1]的糖果多。
860.柠檬水找零
按顺序统计即可
406.根据身高重建队列
- 使用vector是非常费时的,C++中vector(可以理解是一个动态数组,底层是普通数组实现的)如果插入元素大于预先普通数组大小,vector底部会有一个扩容的操作,即申请两倍于原先普通数组的大小,然后把数据拷贝到另一个更大的数组上。
- 链表
- 将身高进行排序后,通过下标和迭代器实现链表插入
452. 用最少数量的箭引爆气球
找重叠部分即可,无重叠部分则加1
435. 无重叠区间
与上题一致
763.划分字母区间
哈希表存储最远边界;
遍历过程中不断寻找真实最远边界
更新左边界
56. 合并区间
easy
738.单调递增的数字
从后向前遍历,若出现递减的情况,高一位的减一,低一位的变为9
将数字变字符串 to_string, 字符串变整数stoi
714. 买卖股票的最佳时机含手续费
寻求最小买入价格,寻求获利日期
变更最小买入价格(重要)
初始化数据时不能不赋值,一定要赋值
968.监控二叉树
- 首先学会遍历二叉树,前中后序遍历方法(后序遍历方式)
- 让叶子节点的父节点安摄像头,所用摄像头最少,整体最优:全部摄像头数量所用最少
- 0:该节点无覆盖
1:本节点有摄像头
2:本节点有覆盖
最后判断根节点是否有覆盖
文章评论