LRU和LFU LRU是最近最少使用页面置换算法(Least Recently Used),也就是首先淘汰最长时间未被使用的页面! LFU是最近最不常用页面置换算法(Least Frequently Used),也就是淘汰一定时期内被访问次数最少的页! frist,如何使用链表实现LRU(简单) 我们维护一个有序单链表,越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时,我们从链表头开始顺序遍历链表。 如果此数据之前已经被缓存在链表中了,我们遍历得到这个数据对应的结点,并将其从原来的位置删除,然后再插入到链表的头部。 如果此数据没有在缓存链表中,又可以分为两种情况: 如果此时缓存未满,则将此结点直接插入到链表的头部 如果此时缓存已满,则链表尾结点删除,将新的数据结点插入链表的头部。 这样我们就用链表实现了一个 LRU 缓存,是不是很简单? #include <iostream> #include <list> #include <vector&g 继续阅读 >>


刘生玺 19/01/18 15:41:25
迪杰斯特拉算法 数据结构图这一部分中的迪杰斯特拉算法,在实际中找最短路径应用广泛,本篇博文主要描述它的实现思路。准备另一篇再将代码实现陈述一遍,主要目的是让其在我脑海中刻骨铭心一点。因为这个算法已经让我耗费了不少的时间和精力。 i代表下标,Y右侧代表已经访问过的路径,= 标记已经找到最短路径,pm代表上一个已经找到最端口路径的节点,每一列的数字表示从原点到当前节点之间的长度,无穷表示没有可达路径。(由于空间有限还有本人较懒,就写一下开始的路径,后面就不写了)。 i N \ Y A B C D G E F 2 B 2(A->B) = = = = = = 3 C 4(A->B) 3(A->B->C) = = = = = 4 D ∞(A->B) 5 5 = = = = 5 E ∞(A->B) ∞ ∞ 7(A->B->D->E) 6(A->B->C->G->E) = = 6 F ∞(A-> 继续阅读 >>


畅柯 18/12/25 21:13:33
1.冒泡与选择 冒泡:冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个数据进行比较,如果前者比后者大,就互相交换,最后就会找到一个最大的落在数组最后.重复以上工作n次即可完成排序. void BubbleSort(vector<int> a) { int len = a.size(); if (len <= 1) return; for (int i = 0; i < len; i++) { for (int j = 0; j < len - i - 1; j++) { if (a[j + 1] < a[j]) std::swap(a[j], a[j + 1]); } } } 时间复杂度:平均时间复杂度O(n^2). 空间复杂度O(1).原地排序 是否稳定:稳定 选择:每次找到最小的一个元素放 继续阅读 >>


刘生玺 18/12/07 22:31:36
十大经典排序算法(动图演示) 0、算法概述 0.1 算法分类 十种常见排序算法可以分为两大类: 非线性时间比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此称为非线性时间比较类排序。 线性时间非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此称为线性时间非比较类排序。  0.2 算法复杂度 0.3 相关概念 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面。 不稳定:如果a原本在b的前面,而a=b,排序之后 a 可能会出现在 b 的后面。 时间复杂度:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。 空间复杂度:是指算法在计算机内执行时所需存储空间的度量,它也是数据规模n的函数。  1、冒泡排序(Bubble Sort) 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素, 继续阅读 >>


胡锦雲 18/11/25 20:53:41
最简单的二分 1.循环实现 template <typename T> int binary_search(const vector<T> &set, const T &value) { auto low = set.begin(); auto high = set.end(); auto high_dump = high; auto low_dump = low; auto mid = low + ((high - low) >> 1); /*1. mid=(low+high)/2,如果 low 和 high 太大就会产生溢出*/ while ((low <= high) && (mid != high_dump)) /*2. 一定是 <= */ { if (*mid == value) return mid - low_dump; /*3. 一定要+1,-1,不然当  继续阅读 >>


刘生玺 18/11/04 22:52:10
动态规划初步 在这周算法题公布之前,我对动态规划的了解是只停留在表面的,只知道一个名词而已。 而这次的算法题,让我对动态规划有了一个初步的了解 我在做题的过程中,总结出了动态规划我认为比较重要的几个点 1.大问题化小问题:即问题是可以化为子问题的 2.记忆性,下一步会用到上一步的结果,所以这个结果必须是可记忆的,是层层递进的 3.状态的转移:状态转移方程是一个关键点(埋坑) HDU 2084 #include<stdio.h> int dp[100][100]; int main(int argc, char const *argv[]) { int num,line; int i,j; scanf("%d",&num); while(num--) { scanf("%d",&line); for(i=0;i<line;i++) for(j=0;j<=i;j++) { 继续阅读 >>


李高晋 18/08/12 21:44:24
题目1 : 单词搜索 给定一个二维网格和一个单词,找出该单词是否存在于网格中。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 示例: board = [ [‘A’,’B’,’C’,’E’], [‘S’,’F’,’C’,’S’], [‘A’,’D’,’E’,’E’] ] 给定 word = “ABCCED”, 返回 true. 给定 word = “SEE”, 返回 true. 给定 word = “ABCB”, 返回 false. 解题思路:简单DFS,注意边界条件的判断和点的回溯(index和visted) #include <iostream> #include <vector> #include <string> using namespace std; class Solution { public: strin 继续阅读 >>


刘生玺 18/08/11 09:54:45
一、 对象已死嘛 引用计数法 给对象添加一个引用计数器,每当有一个地方引用它时,计数器值就加1;当引用失效时,计数器值就减1;任何时刻计数器为0的对象就是不可能再被利用的。 引用计数法的实现简单,判定效率也高,但是它很难解决对象间相互循环引用的问题。 比如对象A和B都有字段instance,赋值令A.instance = B且B.instance = A,除此之外,这两个对象再无任何引用。实际上这两个对象已经不可能再被访问,但是它们因为互相引用着对方,导致它们的引用计数都不为0,于是引用计数法无法通知GC收集器回收它们。 可达性分析算法 通过一系列称为“GC Roots”的对象作为起始点,从这些节点开始向下搜索,搜索所走过的路径称为引用链,当一个对象到GC Roots没有任何引用链相连时,则表明此对象是不可用的。 可作为GC Roots的对象包括下面几种: 虚拟机栈(栈帧中的本地变量表)中引用的对象 方法区中类静态属性、常量引用的对象 本地方法栈中JNI引用的对象 引用 继续阅读 >>


李猛 18/08/10 15:04:26
一.动态规划的基本思想 动态规划(Dynamic Programming,简称DP),虽然抽象后进行求解的思路并不复杂,但具体的形式千差万别,找出问题的子结构以及通过子结构重新构造最优解的过程很难统一。 在做这些题之前,没有接触过任何关于动态规划的概念,所以写的很吃力,很难过 下去了解了一些关于动态规划的概念,在此做个记录和总结 动态规划的基本模型: 确定问题的决策对象 对决策问题划分阶段 对各个阶段确定状态变量 根据状态变量来确定费用函数和目标函数 确定状态转移方程 动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足,故有时需要引入一定的近似)。简单地说,问题能够分解成子问题来解决。并且保存子问题的解 动态规划是一种牺牲了空间,换取时间的算法. 如何正确的理解动态规划算法? A * "1+1+1+1+1+1+1+1 =?" * A : "上面等式的值是多少" B : *计算* "8!" 继续阅读 >>


吕海东 18/08/09 17:59:20
基本搜索算法(DFS|BFS) 这周的题目中设计到的算法:DFS 和 BFS 都是基本的图算法,图是一种数据结构,可以表示出节点之间的关系。 基本搜索算法有两种策略: 深度优先 广度优先 [1] 深度优先搜索 我们对一个图进行搜索,无非就是寻找某种状态,深度优先顾名思义,就是寻找某种状态的时候选择一条路走到底,走不通就退回去换另一条路。 就像走迷宫那样,我们把迷宫抽象为一个图,路就是图里面的边,路两端的地方抽象为节点。走出这个迷宫就可以看作是我们要寻找的一个状态,在不清楚迷宫构造和不破换游戏规则的情况下,找到出口只能一个一个去尝试,为了不出现在同一条路上绕来绕去的尴尬情况,我们需要标记过我们到过的地方,然后一直往深处走,走到头若发现此路不通或已经走过,那自然就要原路返回到前一个岔路口去走另一条路。这种方法虽然比较笨比较低效,但只要迷宫有出口就一定可以出的去。 有了这个例子,很容易归纳出深度优先的基本方法: 选择一个初始节点 从这个初始节点开始寻找,标记走过的节点 如果走到不能再 继续阅读 >>


张小翔 18/08/05 17:58:17