转自：labuladong的算法小抄
⼀、什么是 LRU 算法
就是⼀种缓存淘汰策略。
计算机的缓存容量有限，如果缓存满了就要删除⼀些内容，给新内容腾位置。但问题是，删除哪些内容呢？我们肯定希望删掉哪些没什么⽤的缓存，⽽把有⽤的数据继续留在缓存⾥，⽅便之后继续使⽤。那么，什么样的数据，我们判定为「有⽤的」的数据呢？LRU 缓存淘汰算法就是⼀种常⽤策略。LRU 的全称是 Least RecentlyUsed，也就是说我们认为最近使⽤过的数据应该是是「有⽤的」，很久都没⽤过的数据应该是⽆⽤的，内存满了就优先删那些很久没⽤过的数据。
⼆、LRU 算法描述
LRU 算法实际上是让你设计数据结构：⾸先要接收⼀个 capacity 参数作为缓存的最⼤容量，然后实现两个 API，⼀个是 put(key, val) ⽅法存⼊键值对，另⼀个是 get(key) ⽅法获取 key 对应的 val，如果 key 不存在则返回-1。注意哦，get 和 put ⽅法必须都是 O(1) 的时间复杂度，我们举个具体例⼦来看看 LRU 算法怎么⼯作。
/* 缓存容量为 2 */
LRUCache cache = new LRUCache(2);
// 你可以把 cache 理解成⼀个队列
// 假设左边是队头，右边是队尾
// 最近使⽤的排在队头，久未使⽤的排在队尾
// 圆括号表⽰键值对 (key, val)
cache.put(1, 1);
// cache = [(1, 1)]
cache.put(2, 2);
// cache = [(2, 2), (1, 1)]
cache.get(1); // 返回 1
// cache = [(1, 1), (2, 2)]
// 解释：因为最近访问了键 1，所以提前⾄队头
// 返回键 1 对应的值 1
cache.put(3, 3);
// cache = [(3, 3), (1, 1)]
// 解释：缓存容量已满，需要删除内容空出位置
// 优先删除久未使⽤的数据，也就是队尾的数据
// 然后把新的数据插⼊队头
cache.get(2); // 返回 -1 (未找到)
// cache = [(3, 3), (1, 1)]
// 解释：cache 中不存在键为 2 的数据
cache.put(1, 4);
// cache = [(1, 4), (3, 3)]
// 解释：键 1 已存在，把原始值 1 覆盖为 4
// 不要忘了也要将键值对提前到队头
三、LRU 算法设计
分析上⾯的操作过程，要让 put 和 get ⽅法的时间复杂度为 O(1)，我们可以总结出 cache 这个数据结构必要的条件：查找快，插⼊快，删除快，有顺序之分。因为显然 cache 必须有顺序之分，以区分最近使⽤的和久未使⽤的数据；⽽且我们要在 cache 中查找键是否已存在；如果容量满了要删除最后⼀个数据；每次访问还要把数据插⼊到队头。那么，什么数据结构同时符合上述条件呢？哈希表查找快，但是数据⽆固定顺序；链表有顺序之分，插⼊删除快，但是查找慢。所以结合⼀下，形成⼀种新的数据结构：哈希链表。LRU 缓存算法的核⼼数据结构就是哈希链表，双向链表和哈希表的结合体。这个数据结构⻓这样：
image
思想很简单，就是借助哈希表赋予了链表快速查找的特性嘛：可以快速查找某个 key 是否存在缓存（链表）中，同时可以快速删除、添加节点。回想刚才的例⼦，这种数据结构是不是完美解决了 LRU 缓存的需求？也许读者会问，为什么要是双向链表，单链表⾏不⾏？另外，既然哈希表中已经存了 key，为什么链表中还要存键值对呢，只存值不就⾏了？想的时候都是问题，只有做的时候才有答案。这样设计的原因，必须等我们亲⾃实现 LRU 算法之后才能理解，所以我们开始看代码吧〜
分治
实现
1.分解：将原问题分解成一系列子问题
2.解决：递归地求解各个子问题，若子问题足够小，则直接求解
3.合并：将子问题合并成原问题
满足条件
1.原问题与分解成的子问题具有相同的模式
2.原问题分解成的子问题可以独立求解，子问题没有关联性
3.具有分解终止条件，问题足够小时，可以直接求解
4.将子问题合并成原问题，这个合并操作不能复杂度不能太高，否则起不到减少复杂度的效果。
暴力递归
⾸先，这个问题是动态规划问题，因为它具有「最优⼦结构」的。要符合「最优⼦结构」，⼦问题间必互相独⽴。啥叫相互独⽴？你肯定不想看数学证明，我⽤⼀个直观的例⼦来讲解。
⽐如说，你的原问题是考出最⾼的总成绩，那么你的⼦问题就是要把语⽂考到最⾼，数学考到最⾼……为了每门课考到最⾼，你要把每门课相应的选择题分数拿到最⾼，填空题分数拿到最⾼…… 当然，最终就是你每门课都是满分，这就是最⾼的总成绩。
得到了正确的结果：最⾼的总成绩就是总分。因为这个过程符合最优⼦结构，“每门科⽬考到最⾼”这些⼦问题是互相独⽴，互不⼲扰的。
但是，如果加⼀个条件：你的语⽂成绩和数学成绩会互相制约，此消彼⻓。这样的话，显然你能考到的最⾼总成绩就达不到总分了，按刚才那个思路就会得到错误的结果。因为⼦问题并不独⽴，语⽂数学成绩⽆法同时最优，所以最优⼦结构被破坏。
既然知道了这是个动态规划问题，就要思考如何列出正确的状态转移⽅程！
回溯
解决⼀个回溯问题，实际上就是⼀个决策树的遍历过程。你只需要思考 3 个问题：
1、路径：也就是已经做出的选择。
2、选择列表：也就是你当前可以做的选择。
3、结束条件：也就是到达决策树底层，⽆法再做选择的条件。
image
其核⼼就是 for 循环⾥⾯的递归，在递归调⽤之前「做选择」，在递归调⽤之后「撤销选择」
网友评论