dsa

Heap 作为一种重要的数据结构，有许多应用场景，比如优先级队列，每次出队的都是最大值或者最小值的元素。很多语言都集成了相关实现，比如 Java 的 PriorityQueue，而 Python 提供了 heapq 模块。 因为 Heap 通常用数组而不是链表存储，所以 Python 里面的 Heap 实质上就是一个列表，而 heapq 提供的几个函数也是以列表对象作为参数的： from heapq import heappush, heappop, heappify, heapreplace, heappushpop heap = [] heappush(heap, 1) item = heap[0] # 第一个元素代表堆顶元素 heappop(heap) heapify([3, 2, 1, 5, 6, 4]) # 把普通列表转化为堆结构 [1, 2, 3, 4, 5, 6] heapreplace([3, 4, 5], 1) # 直接将堆顶元素 3 替换为 1，最后堆结构为 [1, 4, 5] heappushpop([3, 4, 5], 1) # 先将 1 插入堆中，再 pop 出堆顶元素，最后堆结构为 [3, 4, 5] 为什么 heapq 提供的是最小堆而不是更常见的最大堆呢？这就得从源码中找答案了。...

LRUCache 是一种经典的缓存机制，它的基本思路是按照最近使用的时间对元素排序，在清理时优先把搁置最久的删除掉。 如果不想给每个缓存元素都记录一个时间戳的话，可以应用哈希链表来简单地实现 LRU 算法。也就是对一个哈希表中的所有元素增加指针，从而串起一个双链表，这样既可以快速 get value，又可以通过把最近使用过的元素放到头部来维护顺序，删除的时候从末尾开始就好了。 手写双链表并不困难，但是借助 OrderedDict 的话，可以写出非常简短的代码： from collections import OrderedDict class LRUCache: def __init__(self, capacity): self.capacity = capacity self.hashtable = OrderedDict() def get(self, key: int) -> int: if key in self.hashtable: self.hashtable.move_to_end(key, last=False) return self.hashtable[key] return -1 def put(self, key: int, value: int) -> None: self.hashtable[key] = value self.hashtable.move_to_end(key, last=False) if len(self....

在 Simple Recursion 之后，我一度把递归当作一种算法。但通过比较 Divide and Conquer 和 Dynamic Programming，我才发现之前的理解有点问题。 一切还是要从 Algorithmic Paradigm 说起： An algorithmic paradigm or algorithm design paradigm is a generic model or framework which underlies the design of a class of algorithms. An algorithmic paradigm is an abstraction higher than the notion of an algorithm, just as an algorithm is an abstraction higher than a computer program. 算法范式，是在算法的层面上抽象出来的一种更泛化的思想，常用的有： Brute-force search 暴力解法 Backtracking 回溯算法 Greedy algorithm 贪心算法 Divide and conquer 分治法 Dynamic programming 动态规划 Divide and Conquer 的基本思路是把复杂的问题分解成多个类似的简单问题，解决之后再组合起来得到最终结果。这种算法有很多应用，比如排序中的 Merge Sort，先将数列分解成单个元素，然后再归并，这时子数组都已经排好顺序了，所以过程很快。...

无意中看到一种叫 look-and-say 的数列，很有意思，有点儿 Fibonacci 的感觉。数列如下： 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, … 从第二位开始，每个数字都是对前一个数的计数结果的描述。比如 11 表示前面的 1 有一个 1，而 21 表示前面的 11 有两个 1，1121 表示 21 有一个 2 和一个 1，依次类推，可以无穷循环出新的结果。（除了 22 这个数字，因为会一直重复 22 本身） 后来查了查才发现原来 Leetcode 也有这道题，不过名字叫做 count-and-say。基本就是给 n 然后求此数列的第 n 项结果。 想了想思路并不难，无非是对一个数字的所有位数循环再计数就好了，不过写的时候很犯难，竟然还写出了一个无比冗长的 for 循环加 if 面条代码。这让我意识到了自己对于循环的认识有多么不够深刻。 之所以犯难，其实是不知道怎样把几种逻辑合并在一起，如果粗暴地列举所有分支大概是这样： def find_next(num: str): result = '' cur, count = num[0], 1 size = len(num) for i in range(1, size): if num[i] == cur and i == size - 1: # count 加一 # 更新 result elif num[i] == cur: # count 加一 elif i == size - 1: # 更新 result # 更新 cur&count # 更新 result else: # 更新 result # 更新 cur&count # 还有一种情况就是并没有进入 for 循环 # 那么也需要更新 result 直接按照这些分支把代码填满肯定很难看，所以要挑选合并。看起来只有第二个分支不需要更新 result，于是我决定把它单拎出来：如果 num[i]==cur 那么 count 加一；否则就更新 result 以及 cur&count....

祸从天降的一天。 早上起不来，于是刷手机清醒一下，突然看到一个 ACMer 楼主提到自己没有刷过 Leetcode，面试的时候差点儿被打脸了。 看了一下题目，要求是 O(logn) 的复杂度，默默想了想，没有特别清晰的思路。 结果翻了翻评论，很多人都在蜻蜓点水般地表示二分查找不断分割就可以了。 要那么简单还用你说吗？起床了起床了。 题目是这样的： 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。 我本来的想法是归并之后计算中位数，但只能做到 O(m+n)，再优化感觉只能二分了。 于是又开始想分别取两个数组的中位数，比较之后就可以各扔掉一半，然后对两个折半的数组继续取中位数比较。 比如一开始找到的中位数是这样：[…5…], […10…]，那么 5 的左边和 10 的右边就可以丢掉了，因为最终的中位数肯定在 5 和 10 中间。 如果接下来是这样：[5..8…], […7..10]，那么 8 的右边和 7 的左边也可以丢掉，因为比 8 大的元素数量达不到这两个小数组的一半，所以中位数不会在里面，比 7 小的同理。 一直重复这个流程，最后得到的肯定就是一个或两个数，平均下就好了，时间复杂度也是符合要求的 O(logn). 结果等到看完标答后我才反应过来自己错在哪里了，这是后话。（因为 m 和 n 不一定一样大，所以显然折半的逻辑不对） 最优的解决方案是可以做到 O(log min(m, n)) 的，核心也是二分法，不过思路要复杂一些： 首先明确中位数的定义。对于奇数个数字来说是最中间的元素，偶数则是中间两个元素的平均值。 要做的是将两个数组各分一刀，假设划分的下标分别是 i 和 j，那么 nums1 被分成 nums1[0, i], nums1[i:]，而 nums2 分为 nums2[0, j], nums2[j:]....