分类:: 算法

双向链表和哈希表实现 LRUCache

LRUCache 是一个很常用的缓存实现,我们简单用 Python 实现它 定义LRU 是 Least Recently Used 的缩写,近期最少使用算法。LRUCache 意味着一个带有容量的缓存,当缓存的容量已满而且需要插入新值的时候,缓存需要淘汰一个旧值。如何去淘汰呢,这个时候就需要用到 LRU 算法。 LRU 意味着这样的功能1234567# 如果 Cache 里有两个 key =&

两道算法题

前言昨天参与了某个互联网公司的在线笔试,里面有两道算法题,无奈时间不够只写了一道。 更糟糕的是,今天醒来才发现自己花了好大心思写的那道题,却由于粗心把题意弄反了。 遗憾之余,今天用现代化的编程工具写一遍,弥补自己悲伤的情绪。 题目第 k 大数描述输入两个数 n 和 k ,给出一个长度为 n 的数组,参考快速排序,输出出数组里第 k 大的数并换行。多组数据,当输入的 n 为 0 时结束。 诡异的是,

简明数据结构

数据结构是一门很重要的计算机基础课,知识点多而且难度不小,这里列出了数据结构中比较容易遗忘的内容。 在这篇博客中,我尽量用我觉得最好理解的方式描述一个算法,简明扼要,相关的代码可能不完全,如果有兴趣的话欢迎访问我的 GitHub 字符串快速匹配 - KMP next 数组的求解,即部分匹配值 123456789int q = 1, k = 0;next[0] = 0;for (q = 1;

使用二分法求整数幂

引言 在应用中求幂是一个经常使用到的运算。那么我们求幂的时候是不是经常这样写 1234567int power(int x, int n){ int result = 1; while (n--) result *= x; return result;} 这样写简单直观,但是时间复杂度太高了。 解决思路 为了减少时间的消耗,我们可以使用二分法。