leetcode

思路总结

分解

1. 分析问题，得到多个需求点
2. 单独对每个需求点思考，对每个需求点挑选合适的数据结构与算法
3. 考虑需求点之间的关系，如何串联起来

eg1: LRU cache实现

分析需求点及对应方案：

1. 支持put_kv、get_k、del_k方法，锁定哈希map
2. 支持LRU规则清理，按使用时间线性排序，而且每次操作会修改排序，锁定双向链表
3. 每次操作key需要修改排序，需要根据key定位到链表，哈希map存链表节点指针
4. LRU清理key需要抹掉记录，链表中需要存key

总结整体方案：使用哈希map和双向链表，相互指向。

eg2：86链表分隔实现

分析需求点及对应方案：

1. 找到分隔点，也就是链表中第一个>=x的点。可以用一个额外变量存储节点，也可以定义一个flag表示已经找到分隔点
2. 分隔点之后的每个小于x的点都要移动到分隔点之前，需要存储可插入位置
3. 遍历链表时需要一个当前节点
4. 需要从当前节点断开，还要插入到目标位置，所以用前节点比较方便

总结整体方案：使用一个flag标识是否找到分隔点，使用一个临时节点存当前可插入的点，使用一个当前节点遍历链表；当找到分隔点之后，小于x的点都插入到临时节点之后。

要考虑问题规模

1. 小范围数据，暴力遍历效率很高。
2. 一次性需求，暴力遍历效率最高：如果需要额外数据结构，那么构造这个数据结构就需要一次遍历了，还不如直接一次遍历操作。

通用性

1. 比如链表反转、奇偶排列等，这些移动其实使用数组来做更加方便和通用。而且数组存指针的空间损耗很小，时间复杂度上多一次构建数组遍历和一次构建链表结果遍历，影响也不大。但是用数组的方式是一种几何到代数的转换，调整起来准确性可以简单得到严格证明。

正确性

边界情况

循环终止条件，递归终止条件，条件判断等，最常见的是要不要等于边界，从0开始还是从1开始等