Implement LRU/LFU Cache

常见的缓存算法有 FIFO LFU LRU FIFO: 淘汰最先进入缓存 LRU: 淘汰最久未被访问的 LFU: 淘汰访问次数最少的 实现一个 LRU Cache 可以通过 HashMap 和 链表来实现。HashMap 负责保证 O(1) 的读取,链表负责按访问时间排序 class LRUCache: """ LRUCache »

powMod 的实现

今天做 Codewars 的 Haskell 练习时遇到了 powMod。 powMod 是一个比较常用的操作,就是求 x 的 n 次幂对 m 取余。Python builtin pow 自身提供了 powMod 的功能 In [2]: pow? Signature: pow( »

Python sort 的实现 - Timsort 算法

近日阅读编程珠玑,对算法突然又萌生了兴趣,于是翻看资料查找到了 Python 的排序算法 概述 Timsort 是 Python builtin sort 所使用的一种算法,结合了归并排序与插入排序。最优时间复杂度为 n, 最差时间复杂度为 nlogn, 平均时间复杂度同为 nlogn, 空间复杂度为 n ,并且是稳定排序。Java 中对于非基础类型的排序也是使用的这个算法 各种排序算法时间/空间复杂度可以从 »

编程珠玑 1-9 证明

似乎找到了丢失的脑子 中午书到货了,下午上课时翻了翻编程珠玑,对于第一章的习题 9 比较困惑 问题大致如下: 空间很廉价,时间很宝贵且向量很稀疏的情况下,如何设计一种技术,在第一次访问向量的项时将其初始化为 0 通俗点说就是有一个很长的数组,只会用到其中几个元素。所以不想去遍历数组将每一项初始化为 0, 设计一种惰性的初始化方法 书后解法: 借助于两个长度为 n 的数组 from 和 to 和一个整型变量 top。 »

二叉树常用操作总结

我们将二叉树结点定义如下 class TreeNode(object): def __init__(self, x): self.val = x self.left = None self.right = None 测试用例 3 / \ 9 20 / \ 15 7 \ / \ 8 2 12 »