重新回来

2015年建了这个站点,一晃神,2022年都已经要结束了,7年时间,它还是这么 “干净” 。

翻了翻过往文章,也许曾经想把它建成技术博客,但实际上只记录了些随手可得的知识,不值一提。

也许我可以多写一点儿生活,多写一点儿感悟和总结。年龄愈长,想法愈多,它们值得被好好记录下来。

我决定重新来好好更新博客。

我想我能坚持下来,就像我正在做的大多数事情那样。


一个人知道自己为什么而活,就可以忍受任何一种生活。 -- 尼采

TopK算法问题

本文总结下TopK相关算法,分为两个部分,一为讨论TopK问题的类型,二为相关的解题思路和C++代码实现。

TopK 问题一般为海量数据问题,可以分为两大类:

  • 找最大/最小的 K 个数

  这种问题一般分为两种类型,一为内存不够无法一次性加载,二为内存充足可以完全处理数据。

  • 找重复次数最大的 K 个数

  这种问题一般是涉及极其庞大的数据量,内存不可能一次性加载完成。必须采用 分治法

(更多…)

KMP算法

把 KMP 算法做个详细总结,写成博文。

主要分为四个部分:

  • KMP 中的前缀后缀

  • 构建 Next数组

  • KMP算法匹配过程

  • 源码示例.

(更多…)

二分查找寻找左右边界

讨论几个二分查找的变换问题,主要分为两类:

  • 查找 第一个大于/大于等于 target 的数(左边界)

  • 查找 最后一个小于/小于等于 target的数(右边界).

重点是注意临界条件,小心会死循环。本文假设数组为单调递增。

(更多…)

LRU、LFU、LRU-K算法

总结一下缓存置换算法。

  • LFU(Least Frequently Used) 算法

  最近最不常使用,缓存容量满的时候,置换使用频次最小的那个。

  • LRU(Least Recently Used) 算法

  最近最少使用,缓存容量满的时候,置换最长时间没有使用的那个。

  • LRU-K 算法

  LRU-k 有两个队列,一个队列是数据队列,一个队列是缓存队列,只有当数据队列数据的访问次数到达 K次,才将它放入缓存队列。

缓存队列按照 LRU 的方法置换数据。

(更多…)