今天是个好天气
今天是个好天气
今天是个好天气
LRU 算法（Least Recently Used）就是一种缓存淘汰策略。也就是说我们认为最近使用过的数据应该是是「有用的」，很久都没用过的数据应该是无用的，内存满了就优先删那些很久没用过的数据。
比如手机后台使用程序，最近使用的app放在前面，之前的程序排在后面会被优先清理。
可以把cache理解成一个队列，最近使用的排在左边（队头），久未使用的放在右边（队尾）。
put的操作，如果之前队列没有会插入到队头，有的话会更新value，并放置到队头。如果内存满了，就要删除队尾的元素（久未使用），再插入到队头。
get的操作，如果队列中有，就返回值，并放置到前列，如果没有返回-1。
因此本体需要考虑，cache中元素必须是有序的，以区分最近使用的和长久未使用的，当容量满了方便删除。
要在cache中快速找某个key，每次返回cache中的某个key，变更为最近使用的，所以cache要支持任意位置的快速插入和删除元素。
哈希表查找快，但是元素没有固定无法区分使用事件。链表有顺序之分，插入删除块，查找慢。
我以为的两数相加，直接相加，链表反转。实际的两数相加，如果位数不统一怎么办，还有进位。
给长度不足的一方补0，同时记录进位。
最高位如果还有进位再补1。
情况一：顺时针转 90 度：先转置再左右镜像
1 2 3 7 4 1
4 5 6 8 5 2
7 8 9 9 6 3
情况二：顺时针转 180 度:先上下镜像，再左右镜像（先左右再上下也可）
1 2 3 9 8 7
4 5 6 6 5 4
7 8 9 3 2 1
情况三：顺时针转 270 度：先转置再上下镜像
1 2 3 3 6 9
4 5 6 2 5 8
7 8 9 1 4 7
//属实想不到这个规律
摩尔投票法: 遇到相同的数，就投一票，遇到不同的数，就减一票，最后还存在票的数就是众数。
语文证明：candidate为擂台，count 为擂台上的人数，擂台上没有人的时候，直接上台。如果有人并且是一伙的则上台（同时站在台上）；如果发现擂台上有人但不是一伙的，则不上台，同时拉下去一个。由于非maj的人数比maj的人数少并且还会自相残杀，非maj们无法吧maj们全拉下来。
自己想的思路是：TL
- 通过先横向搜索，如果当前数小于target，纵向搜索
- 如果当前数大于target，换到下一行。
- 这样的三层for，O(mnm)。
- 直接两层for暴力都过了。
看到有序想到二分，在每一行中进行二分查找。
优化二分搜索。