重新回来
2015年建了这个站点，一晃神，2022年都已经要结束了，7年时间，它还是这么 “干净” 。
翻了翻过往文章，也许曾经想把它建成技术博客，但实际上只记录了些随手可得的知识，不值一提。
也许我可以多写一点儿生活，多写一点儿感悟和总结。年龄愈长，想法愈多，它们值得被好好记录下来。
我决定重新来好好更新博客。
我想我能坚持下来，就像我正在做的大多数事情那样。
一个人知道自己为什么而活，就可以忍受任何一种生活。 -- 尼采
TopK算法问题
本文总结下TopK相关算法，分为两个部分，一为讨论TopK问题的类型，二为相关的解题思路和C++代码实现。
TopK 问题一般为海量数据问题，可以分为两大类：
- 找最大/最小的 K 个数
这种问题一般分为两种类型，一为内存不够无法一次性加载，二为内存充足可以完全处理数据。
- 找重复次数最大的 K 个数
这种问题一般是涉及极其庞大的数据量，内存不可能一次性加载完成。必须采用 分治法。
KMP算法
二分查找寻找左右边界
讨论几个二分查找的变换问题，主要分为两类：
-
查找 第一个大于/大于等于 target 的数(左边界)
-
查找 最后一个小于/小于等于 target的数(右边界).
重点是注意临界条件，小心会死循环。本文假设数组为单调递增。
LRU、LFU、LRU-K算法
总结一下缓存置换算法。
- LFU(Least Frequently Used) 算法
最近最不常使用，缓存容量满的时候，置换使用频次最小的那个。
- LRU(Least Recently Used) 算法
最近最少使用，缓存容量满的时候，置换最长时间没有使用的那个。
- LRU-K 算法
LRU-k 有两个队列，一个队列是数据队列，一个队列是缓存队列，只有当数据队列数据的访问次数到达 K次，才将它放入缓存队列。
缓存队列按照 LRU 的方法置换数据。