ArMiku Blog

# 加油站 题目链接🔗 # 思路一 直接对全局进行贪心选择： 情况一：如果 gas 的总和小于 cost 总和，那么无论从哪里出发，一定是跑不了一圈的 情况二：rest [i] = gas [i]-cost [i] 为一天剩下的油，i 从 0 开始计算累加到最后一站，如果累加没有出现负数，说明从 0 出发，油就没有断过，那么 0 就是起点。 情况三：如果累加的最小值是负数，汽车就要从非 0 节点出发，从后向前，看哪个节点能把这个负数填平，能把这个负数填平的节点就是出发节点。 class Solution {public: int...

# 买卖股票的最佳时机 II 题目链接🔗 将最终利润分解。 假如第 0 天买入，第 3 天卖出，那么利润为：prices [3] - prices [0]。 相当于 (prices [3] - prices [2]) + (prices [2] - prices [1]) + (prices [1] - prices [0])。 把利润分解为每天的维度： (prices[i]−prices[i−1])+...+(prices[1]−prices[0])(prices[i] - prices[i-1]) + ... + (prices[1] -...

# 贪心算法理论基础 贪心的本质是选择每一阶段的局部最优，从而达到全局最优。 贪心算法一般分为如下四步： 将问题分解为若干子问题 找出适合的贪心策略 求解每一个子问题的最优解 将局部最优解堆叠成全局最优解 # 分发饼干 题目链接🔗 大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子，那么就应该优先满足胃口大的。 这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。 可以尝试使用贪心策略，先将饼干数组和小孩数组排序。 然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。 class Solution...

# 全排列 题目链接🔗 以 [1, 2, 3] 为例，将问题抽象成如下树形结构： 回溯函数参数和返回值 排列是有序的，所以 [1, 2] 和 [2, 1] 是两个集合，不需要像组合问题一样用 startIndex 控制起始位置。 但排列问题需要一个 used [] 数组来标记已选择元素。 终止条件 当到达叶子节点时终止，即 path.size() == nums.size() 。 单层搜索逻辑 用 used [] 数组来记录此时 path 里都有哪些元素使用了，一个排列里一个元素只能用一次。 class Solution {public:...

# 子集 题目链接🔗 如果把子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！ 子集也是一种组合问题，因为它的集合是无序的，子集 {1,2} 和 子集 {2,1} 是一样的。 遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合。 确定回溯函数参数和返回值 全局变量数组 path 为子集收集元素，二维数组 result 存放子集组合。 用 startIndex 保证元素不会重复取。 终止条件 剩余集合为空的时候，就是叶子节点。就是 startIndex...

# 组合总和 题目链接🔗 本题的搜索过程抽象成如下树形结构： 因为本题没有组合数量要求，仅仅是总和的限制，所以递归没有层数的限制，只要选取的元素总和超过 target，就返回！ 确定回溯函数参数和返回值 依然是定义两个全局变量，二维数组 result 存放结果集，数组 path 存放符合条件的结果。 sum 来统计单一结果 path 里的总和，startIndex 来控制 for 循环的起始位置。 确定终止条件 sum==targetsum == targetsum==target 的时候，需要收集结果，sum>targetsum >...

# 回溯算法理论基础 回溯算法是一种搜索的方式，因为是递归的副产品，所以有递归就有回溯。 回溯的本质是穷举，穷举所有可能选出想要的答案，因此回溯的效率并不高。 但是一些问题只能用回溯算法来做，例如： 组合问题：N 个数里面按一定规则找出 k 个数的集合 切割问题：一个字符串按一定规则有几种切割方式 子集问题：一个 N 个数的集合里有多少符合条件的子集 排列问题：N 个数按一定规则全排列，有几种排列方式 棋盘问题：N 皇后，解数独等等 回溯解决的问题都可以抽象为树形结构，集合的大小构成了树的宽度，递归的深度构成了树的深度。 # 模板 回溯函数的返回值和参数 回溯算法的返回值一般为...

# 删除二叉搜索树中的节点 题目链接🔗 # 递归 确定递归函数参数和返回值 和在二叉搜索树中插入一样，也可以通过递归函数返回值删除节点。 确定终止条件 遇到空返回，其实这也说明没找到删除的节点，遍历到空节点直接返回了。 确定单层递归的逻辑 有五种情况： 第一种情况：没找到删除的节点，遍历到空节点直接返回了 找到删除的节点 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回 NULL...

# 二叉搜索树中的众数 题目链接🔗 如果不是二叉搜索树，可以将树遍历一遍，用 map 统计频率，再将 map 转化为 vector 排序，最后取前面的高频元素集合。 但二叉搜索树的中序遍历是有序的。 遍历有序数组的出现频率，从头遍历，那么一定是相邻两个元素作比较，然后就把出现频率最高的元素输出就可以了。 在树上，使用 pre 和 cur 两个指针，pre 指向前一个节点，每次 cur（当前节点）才能和 pre（前一个节点）作比较。 class Solution {private: int maxCount = 0; // 最大频率 int count = 0; //...

# 合并二叉树 题目链接🔗 同时遍历两个树的逻辑和遍历一个树的逻辑一样，只不过传入的是两个树的节点并同时操作。 # 递归 确定递归函数的参数和返回值 传入两个树的根节点，返回的是合并后的根节点。 确定递归的终止条件 传入了两个树，那么就有两个树遍历的节点 t1 和 t2，如果t1==NULLt1 == NULLt1==NULL 了，两个树合并就应该是 t2 了（如果 t2 也为 NULL 也无所谓，合并之后就是 NULL）。 反过来如果t2==NULLt2 == NULLt2==NULL，那么两个数合并就是 t1（如果 t1 也为 NULL 也无所谓，合并之后就是...