0%

各种算法

你时间花在哪里,就表示你重视哪里。

一、概念

AOI算法

AOI(area of interested)算法


红包算法

红包算法(总和870,随机分成3份,每一份不大于300)


字符串匹配算法


LRU

一、概念

  1. LRU是Least Recently Used的缩写,即最近最少使用,常用于页面置换算法,是为虚拟页式存储管理服务的。
  2. 设计原则:如果一个数据在最近一段时间没有被访问到,那么在将来它被访问的可能性也很小。当限定的空间已存满数据时,应当把最久没有被访问到的数据淘汰。

二、实现

  1. 数组方式
    • 用一个数组来存储数据,给每一个数据项标记一个访问时间戳;
    • 每次插入新数据项的时候,先把数组中存在的数据项的时间戳自增,并将新数据项的时间戳置为0并插入到数组中;
    • 每次访问数组中的数据项的时候,将被访问的数据项的时间戳置为0;
    • 当数组空间已满时,将时间戳最大的数据项淘汰。
  2. 链表方式
    • 用一个链表来存储数据;
    • 每次新插入数据的时候将新数据插到链表的头部;
    • 每次数据被访问到将数据移到链表头部;
    • 当链表满的时候,就将链表尾部的数据丢弃。

三、常见缓存淘汰算法

  1. FIFO:first in first out,先进先出,即假定刚刚加入的数据总会被访问到;
  2. LRU:least recently used,最近最少使用,判断最近被使用的时间,假定未被使用的时间越久就不可能在被使用;
  3. LFU:least frequently used,数据使用次数最少的,优先被淘汰。