基础算法

二分

通常可以把O(n)优化到O(logn)，每次做出选择后有一半的区间可以舍弃，这要求区间的属性在某种程度上是有序的。本质上是一种剪枝的枚举

常用于最小化最大值/最大化最小值。此情形下，常用二分枚举一个特定的、有可能区间范围的值

洛谷P2678 跳石头

• 枚举最大的最短举例
• 带点贪心的色彩，每次距离不够了就把下块石头挪走

力扣LCR 073 懒猴子吃香蕉

• 相同的思路
• 猴子每次吃相同的数量，可以利用这个特点直接计算出当前堆要吃多久，避免重复计算

贪心

每次贪婪、目光短浅的选择当前的最优解。不一定为整体最优解

洛谷P1090 合并果子

• 使用优先级队列做数据结构，每次合并最小的两堆
• 循环条件是，堆数>1

洛谷P4995 跳跳

• 每次跳高度差最大的，为此需要先给高度排个序，然后上下横跳
• 下一个跳的位置也难以确定，要么一个循环跳两次，要么根据当前位置和最终位置的相对位置确定跳哪里
• 上下横跳有点难以确定什么时候终止循环。可以先计算出来最终的位置，再进行循环。或者一个循环跳两次，下小于上即继续循环

LC 2611 两个老鼠吃奶酪

• 从两个序列中挑选数据，要求总和最大且必须从第一个序列中挑选k个
• 无法让两个序列排序，但可把二者合并到一个差值序列中然后排序贪心
• 对差值排序，正的给1负的给2，选最大的k个给1，剩下的都给2

递归&分治

将问题分解为同类型子问题。寻找边界条件。小样例推导递归代码

分治与递归其实差不多，但是子问题不一定是相同种类

一种编程思路

LC08.06 汉诺塔

• 抽象过程，一个函数看成一个黑箱
• 问题划分为同类型子问题

LC53 最大子数组和

• 这题可以用双指针，此处用递归/分治
• 问题划分为同类型子问题

很玄乎，主要体会下思想