本文总结下TopK相关算法,分为两个部分,一为讨论TopK问题的类型,二为相关的解题思路和C++代码实现。
TopK 问题一般为海量数据问题,可以分为两大类:
- 找最大/最小的 K 个数
这种问题一般分为两种类型,一为内存不够无法一次性加载,二为内存充足可以完全处理数据。
- 找重复次数最大的 K 个数
这种问题一般是涉及极其庞大的数据量,内存不可能一次性加载完成。必须采用 分治法。… 阅读全文
讨论几个二分查找的变换问题,主要分为两类:
查找 第一个大于/大于等于 target 的数(左边界)
查找 最后一个小于/小于等于 target的数(右边界).
重点是注意临界条件,小心会死循环。本文假设数组为单调递增。… 阅读全文
总结一下缓存置换算法。
最近最不常使用,缓存容量满的时候,置换使用频次最小的那个。
最近最少使用,缓存容量满的时候,置换最长时间没有使用的那个。
LRU-k 有两个队列,一个队列是数据队列,一个队列是缓存队列,只有当数据队列数据的访问次数到达 K次,才将它放入缓存队列。
缓存队列按照 LRU 的方法置换数据。… 阅读全文
给定一个排列,如 "aazz" ,求按照字典排列方式的下一个字符,这里是:"azaz".
以 "aazz" 为例,字典序的算法步骤如下:
本例中为 'a', left = 1;
本例中为 'z', right = 3;
本例变成:'azaz';
将 left 以后的字符按照从小到大排列。
重复上述过程
结束条件: 如果第一步中,找不到左邻小于右邻的字符,则说明已经是字典序的最后一个排列了。… 阅读全文
目前,公网 IP 地址数量稀少,我们的个人电脑大都在重重内网内部,端口号通过 NAT 层层映射,导致无法向公网提供一个稳定的访问入口。若想让公网提供服务(比如搭建一个的Web服务器)我们一般选择购买云服务器,但是性能强大的云服务器价格很高,因此我们应该找一个办法让内网的电脑能向公网暴露一个 稳定的 访问入口。