月度归档: 2019 年 8 月

二分查找寻找左右边界

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

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

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

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

(更多…)

LRU、LFU、LRU-K算法

总结一下缓存置换算法。

  • LFU(Least Frequently Used) 算法

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

  • LRU(Least Recently Used) 算法

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

  • LRU-K 算法

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

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

(更多…)

字典序算法

给定一个排列,如 "aazz" ,求按照字典排列方式的下一个字符,这里是:"azaz".

以 "aazz" 为例,字典序的算法步骤如下:

  • 从右至左遍历,找出第一个左邻小于右邻的字符,记下位置 left;

本例中为 'a', left = 1;

  • 再次从右至左遍历,找出第一个比 str[left] 大的字符,记下位置为 right;

本例中为 'z', right = 3;

  • 交换 str[left] 和 str[right]

本例变成:'azaz';

  • 将 left 以后的字符按照从小到大排列。

  • 重复上述过程

结束条件: 如果第一步中,找不到左邻小于右邻的字符,则说明已经是字典序的最后一个排列了。