抽象算法

很多题目都有基础的数据结构和算法，但也有它独特的corner case。所以，本文主要记录抽象的算法，避免重复记录。

Quick Sort

快速排序

快排容易想的方法是3个while，一个while外循环，加每次左标移动和右标移动两个while。但这个翻译成代码很容易出错，主要是感觉while的保护和退出条件不容易记忆。出错了，你没法跑单测就很难补好洞。虽然面试的自己可能都写不出来，但他复制你的代码去跑，那就还是你gg。所以我倾向于记忆单循环的写法，主要是不需要什么保护和退出，简单。不过，3 while确实更加贴近抽象算法的原理，可以尝试记忆一下。

我们记锚点为pi，它位置上的值为piv。

单循环思路

快排建议记忆单循环的写法，该写法也不用死记，需要记住几个点：

• 单次循环，那么就是把每个比piv（pivot的value）小的数都挪到前面去。
• 第一次挪怎么挪？第一个数是piv，从第二个数开始比大小，如果第二个数小于piv，是原地不动还是扔到第一个位置？这里重点记忆不要交换pivot，pivot最后再交换。可以推理出，第二个数如果小于piv，就应该放在第二个位置，就是原处。如果它大于等于piv，它不动，就比下一个数，如果它小于piv，就挪到前面去。
  • 总结规则是：当某数大于等于piv时，是跳过，直接看下一个数。如果小于piv，交换，交换到此处的值，可能是大于等于piv的，也可能就是原地交换（比如piv就是最大的值，就会一直触发原地交换），但反正不用再次考虑，还是可以直接下一个数。
• 遍历完成后，就形成了三块区域，[piv, < piv, >=piv]。这个时候交换piv和< piv的最后一个数，区域就可以变成[< piv, piv, >=piv]，符合快排partition后的结果。
• partition函数有了，快排的递归partition怎么写？重点要注意的是怎么标记partition的输入范围，是左闭右开，还是全闭？目前感觉都可以，因为快排的衍生问题都是pivot很重要，区间问题不影响pivot，pivot不会漂移。
  所以伪代码写为：

  def partition:
  	# [lo, hi)
  	piv, j = a[lo], lo
  	for i in range(lo+1,hi):
  		if a[i] < piv:
  			j ++
  			swap i,j
  	swap lo, j
  	return h
  def qsort:
  	if lo + 1 >= hi: # 长度为1或0都不需要排序
  		return
  	pi = partition(a, lo, hi)
  	qsort(a, lo, pi) # 这里指排序[lo,pi)，pi不参与排序
  	qsort(a, pi+1, hi)

如果partition函数像做成全闭的，那么< piv的游标j和循环的取值范围，以及qsort里的退出条件和qsort递归范围变化一下就好了，没什么坑。
如果侥幸你记得pivot可以选最右（我每次都记不得），那么< piv的游标j和循环的取值范围要改一下，以及最后应该交换pivot和j+1。感觉没简单化什么东西，不必记忆。

判断条件用 <= 或 < 应该都可以，只要能保证最后pivot的交换能满足快排定义。看网上题解 <= 多，但我觉得 < 挺好用的，减少一些swap可能，比如这个题解就是用的小于做判断，oj上也没测出问题来。

3 while思路

3 while思路，推荐在陈斌老师的写法上改进一点点，也就是去掉done这个flag，没什么必要加它。3 while思路的难写点在于，双mark写法过长，可能做不好越界保护。

首先看基础思路：

我们先暂时放下while的保护条件，先讨论理想情况。两个游标怎么游？算法中不是要< piv, piv, > piv，毕竟可能piv有多个，而是<=piv, piv, >=piv，注意，两边都可能==piv，不是必须在哪一边。因此内层两个while判定条件是<=piv ++, >=piv –，遇到等于的可以继续游，不需要停下。
所以伪代码可写为：

while True:
	while … and [lmark]<=piv: lmark++
	while … and [rmark]>=piv: rmark--
	some cases
	exchange
handle pivot

很明显，内层2个while不可能让2个mark一直++/–，所以我在2个while判断的最前面都留了保护条件。

让我们思考下这个保护和2个while结束后，哪些情况不能走到exchange，或者得直接退出外层while。

首先，可以提醒自己交换价值，就是2个mark什么时候是需要交换的，值得交换的，不值得的时候，可能要跳过或退出（也就是上面代码的some cases）。通常的看，当然是lmark < rmark时应该交换，lmark==rmark和lmark > rmark时都是不应该交换的。那么，假设走完内层2个while时可以存在lmark==rmark的情况，我们该干什么？

如果while保护条件为lmark < rmark，那很可能出现这个lmark==rmark。可能是lmark知道了前面的值<= piv，所以++到了此处，由于保护条件，第2个while就也跳过了。又或者lmark确实到了此处，它>piv，rmark又走过>=piv的值，到了此处，被保护条件卡住。可能还有别的情况，但总的来讲，就是你无法明确lmark==rmark时，这个位置的值是个什么情况，它没有保证。为了这个情况，就得单独去判定大小，并看往哪儿放。不是说不可以这么写，就是挺麻烦。

举例说明：

[5,7,2,8]它以5为piv，会交换一次7和2，成为[5,2,7,8]，然后就会遇到lmark==rmark，也就是7所在的位置2。简单地想，pivot 5和双mark指向的7应该交换，但是这个例子不能，得先判断出7比piv大，不能动，然后往左看到2，发现它可以和piv交换。这里又会衍生，要不要保护，pivot是不是就是最小的，不用交换等等情况。特殊情况就很多，很烦，容易想漏想错。

所以再换个思路。如果保护条件是lmark <= rmark，就会发现，走过2个while后，不存在lmark==rmark的情况（可以assert看看）。因为一个数它跟piv比只有三种情况，而三种情况，两个游标都不可能同时停下，必然有人要跨过去，所以安全。那么，lmark>rmark时我们退出外层while，这时候如何处理pivot？会不会比前面思路的处理逻辑简单？

lmark > rmark除了这个位置关系，数组当前会是什么情况，能保证一些什么关系？首先明确它们只可能是lmark=rmark+1，就是相邻的，不可能交错后继续拉开距离。

• lmark > rmark可能是lmark先走，触发保护，然后rmark的while直接跳过。这个情况，lmark都能穿过rmark，自然lmark的左边（不包含自己）都是<=piv的。此时rmark可能是走动过，也可能是完全没移动过，但都ok。走动过，那么它必然是停在了< piv 的值上，也保证它的右边全是>= piv的。这个大小关系下，很自然，pivot和rmark交换下就好了，把< piv的值放到最左边，很合理。如果rmark没走动，那它就在最右边，lmark又保证了除pivot以外整个区间都<=piv。这个情况把pivot扔到最右边也很合理。
• lmark停在了>piv的值上，rmark一直往左，穿过了lmark。这里也保证了rmark的右边都是>=piv的，rmark当前位置好像unknown，因为rmark只是因为保护停下。但考虑到lmark停在此处，当然是rmark停在了<=piv的值上，而lmark在紧邻的右边。这个关系下，pivot和rmark交换，也很合理。那如果lmark压根儿没走动，rmark就走到了pivot这个最左边的点上，原地交换下也没错。

可以看到，保护条件是lmark <= rmark时，rmark指向的值有明显的大小保证，不需要再次确认什么。所以，用lmark <= rmark这样的保护条件最好，对应的lmark > rmark时退出外层while。重点记忆，“交错”(lmark>rmark)就停止，自然，不交错的话游标还可以继续跑，所以内层2while的保护条件是lmark <= rmark。（这个记忆法仅用于记忆，没办法去推理代码的完备性。）

总结

核心是“交错”，交错就停止，只要不交错，3 while都可以继续。

while True:
	while lmark<=rmark and [lmark]<=piv: lmark++
	while lmark<=rmark and [rmark]>=piv: rmark--
	if lmark > rmark:
		break
	exchange
exhange rmark and left

实际oj测试，还是双mark速度快点。

另一种写法见leetcode题解，3 while用的i < j，注意写法是右标先移动，否则有问题。这种大概率记不住，先左后右比较顺。

Binary Tree Traversal

二叉树遍历

二叉树的三种遍历递归写法都没难度，不过稍微加点东西就容易搞不定了。还是不够熟悉递归，不够熟悉将稍复杂的逻辑想清楚，所以转换为代码会卡住。

另外，再注意一下，先序、中序、后序都是看的当前节点cur，所以先是cur-left-right，中是left-cur-right，后是left-right-cur。不要认为后序就是right要放前面了，有时候容易脑子短路。

中序遍历

https://leetcode.cn/problems/binary-tree-inorder-traversal/

中序递归遍历，一般就用result数组来存结果就行了，因为result在递归中也是一个一个append结果的。拼接的写法inorder(root.left)+[root]+inorder(root.right)大可不必，空间消耗有点过分了，也没简单多少。

而中序迭代遍历，该怎么写？首先得加个辅助结构，或者改当前的数据结构，否则不够用。

我们先说“加辅助结构”的算法。中序是左-中-右，递归不用额外结构因为它可以回到中，即使已经在左子树游了一圈了。那迭代就需要记住中，因二叉树单向的，往下走回不来，不缓存起来就回不去。不管是栈还是队列，一维数组肯定够了。当然一般“递归->迭代”都是栈，递归本质也是先进后出。

再看怎么使用栈，其实就是模仿递归，递归往左下走到底后，可以逐步回来，所以迭代里就应该往左下走，并且记录每个“中”节点。到底后，就可以向result加结果了。拿最左的叶子节点举例，它左子节点None了，就类似递归回到了它，它作为中节点，被加入result，那么此时还应该考虑它的右子节点。而以这个右子节点作为起始，做的实际还是中序遍历，不过是子树的中序遍历，所以这里代码可以复用，只需要以右子节点作为起始节点。可以看出，中先进栈，左子再进，把左子和中都弹出栈后，右子才会进栈，不用担心右子节点遍历完了后就断了，因为中的上一层还在栈里面。

伪代码写作：

cur = root
stack = []
while ?:
	while cur:
		cur -> stack
		cur = cur.left
	# no more left child, cur == None now
	top = stack.pop
	top -> result
	cur = top.right # next loop will traversal the right child

最后看终止条件怎么写，stack为空，没法pop，肯定得保护，但是因为内层while也在填充stack，所以并不是stack为空就得终止，内层while可能会补充。不过如果cur和stack都为空，那就没必要了。

所以终止条件为while cur or stack。

前序遍历/先序遍历

https://leetcode.cn/problems/binary-tree-preorder-traversal/

递归写法是“中-左子-右子”，因为中就是当前，左子就.left往左走就行了，所以只需存右子，且是先进后出。用简单例子演示一遍也可以知道，伪代码可以写作：

stack, cur = [], root
while ?:
	if not cur:
		cur = stack.pop
	cur -> result
	if cur.right: -> stack
	cur = cur.left # be the new traversal root

最后看终止条件，stack为空，如果有cur，也可以走下去（比如root节点）；如果cur为空，stack还有，也能走（比如走到树的最底层，但树右边还有节点没遍历到）。所以终止条件还是while cur or stack。

后序遍历

https://leetcode.cn/problems/binary-tree-postorder-traversal/

依然要记牢，迭代就是模拟递归，所以这里依旧需要用栈来模拟递归时天然拥有的栈信息。递归是“左子-右子-中”，所以还是先把最左边的路走通，存下每个左子。每个左子从栈中取出时，我们假设某个节点名为node1，都应该先把node1右子当作新的root，把右子树走完，才回到这个node1。只拿到node1，是可以找到其右子的，但是node1此时不出栈，我们会再次拿到它，如何区别它的两个状态（该让右子进栈，还是就该它出栈，它完成遍历）？

这里比较常规的想法是要不栈就存< node, flag >，通过flag来，进栈的flag都为false，如果我们将它右子放进栈，就把flag改为true。下次pop出flag为true的node，就跳过压右子，直接让它进入result，视为它和它的子树都完成了遍历。

但其实还可以更简单，需要察觉到一个关系问题。比如，栈目前是[1,2]，然后2是叶子，2出栈。然后我们看到1，1有右子3，那么此时就是[1,3]，注意一定有node1.right==node3这个关系。3的子树怎么操作，不用关心，假设它已经完成了，此时应该3出栈了，栈又变成了[1]，而如果我们记住了3，当我们看到栈里的1，有node1.right==node3时，就知道了，node1的右子node3已经访问过了，node1可以出栈了。这个关系完全是即时的，它只需要记住出栈的节点，所以只需要一个变量就可以，通常记为pre。pre可行的原因就是遍历的连续性，右子节点出了，马上就是中这个节点出，中间不会夹杂别的。记住右子，就能判断出中是第二个状态了，不需要再管右子节点。

skiplist

https://mp.weixin.qq.com/s/czkZcQL8mEqG2xeX8huqsA

Heap

堆，一般指二叉堆。

我们希望有一个数据结构，它可以迅速pop出最小的，push一个新的数也希望是对数时间里完成，这样的时间复杂度才有价值，不然简单的有序数组pop/push都是O(n)就足够了，还简单。

这个理想的数据结构，应该考虑树形，毕竟对数时间。

再说什么树，因为没有什么限定条件，二叉树就是最简单的。然后再想，n个数去构建二叉树，如果n不是2^k-1，那这个二叉树就不满，不满也不能乱搞，因为对数时间，你当然希望这个树足够矮小，不然最坏情况又是线性了。所以平衡二叉树是理想形态。

而平衡二叉树并不必须用链表作为节点，它可以用连续数组表示。这也是让代码更简单的一个优点。

再来说说堆的基本操作逻辑。

一个是pop，pop出堆顶后，树的根节点就空了，这个“树”就不是有效的树了，那得想个办法修好，办法就是把最尾部的元素移动到堆顶，这个时候不满足堆有序，那么就去让它有序，画画图也可以发现，只有堆顶也就是根节点不符合堆有序，那么调整根节点和它的两个子节点，比如它和左子节点交换，它们三个就堆有序了。但因为左子节点变了，它和它的两个子节点可能又乱了，就继续调整。一层一层往下，也叫做“下沉”。只会沿着某一条路径下沉到叶子，所以复杂度是logn，不会影响别的路径。

二是push，新增一个元素到已形成的堆，将新元素塞入树中间显然不合理，放在最后一个位置，就像是多给某个节点加了个子节点。然后，这个节点和它的一个或两个子节点，可能不满足堆有序，就需要调整。调整后，它作为子节点，可能又不能有序，于是就一直“上浮”，上浮到根节点就结束了。同样的，只会影响一条路径，也是O(k)（k层的树，n个节点树高也就是k=logn）。（如果当前堆已经满了呢？新加的节点，在逻辑上看，就是树多加了一层，这一层只有一个节点。说得通。）

Python heapq

再提一嘴python的heapq，优先队列一般底层结构就是二叉堆，具体二叉堆怎么实现都行，python这里也是使用数组，但是它的内部方法实现不是前面提到的算法，它更高效，可以仔细看下heapq的实现和注释，实名diss了前面的常规算法???。但这个不影响时间复杂度，不可能比logn更小，只是时间优化。（heapq算法里的siftup,siftdown和上浮下沉就对不上了。有空可以学习下。）

heapq原理在代码里也不过，就观察下整个源码实现吧。

• heappush，就是新加一个elem到heap，源码实现为，append到数组末尾，然后siftdown(0,last),第二个参数last指从这个节点开始，往上走到第一个参数0，也就是根节点。其实就是一次上浮（对应Algorithm 4th的swim），但不知道为什么叫down？

  Pasanen, Tomi (November 1996). Elementary Average Case Analysis of Floyd’s Algorithm to Construct Heaps (Technical report). Turku Centre for Computer Science. CiteSeerX 10.1.1.15.9526. ISBN 951-650-888-X. TUCS Technical Report No. 64. Note that this paper uses Floyd’s original terminology “siftup” for what is now called sifting down.
  https://en.wikipedia.org/wiki/Binary_heap#cite_ref-13

  Floyd大概是这一篇，里面siftup确实是j=2*i，往下走的，可能python heapq按照这个逻辑来的吧。

• heappop，和抽象的算法没有区别，把堆顶拿走，把最后一个数放到堆顶，然后下沉（sink），只是heapq里叫siftup。siftup有个神奇的点是它在最后call了一次siftdown。注意整个siftup的实现，简化一下是这样的：

   siftup(pos):
  newitem = heap[pos]
  while childpos < endpos:
  	childpos = max(left, right)
  	heap[pos] = heap[childpos]
  	pos = childpos
  heap[pos] = newitem
  siftdown(pos)

  它并不是在while里，用当前pos跟它的两个子节点比大小，选择跟哪个子节点交换，而是无条件交换。也就是说while不是一次完整下沉，所以是while+siftdown组成一次完整下沉。
  看下它的注释。

在这个函数之前的评论区中，作者已经解释了他们为什么做出这样的选择，这初看起来效率较低，但在实践中却发现会导致更少的比较。

We could break out of the loop as soon as we find a pos where newitem <= both its children, but turns out that’s not a good idea, and despite that many books write the algorithm that way. During a heap pop, the last array element is sifted in, and that tends to be large, so that comparing it against values starting from the root usually doesn’t pay (= usually doesn’t get us out of the loop early). See Knuth, Volume 3, where this is explained and quantified in an exercise.

heapq提供heapreplace，也就是把堆的pop和push两步放在一步完成，因为size恒定。你如果pop[0]，就把新的元素放在[0]就行，让它下沉。

注意heapq.heapreplace是一定replace的，它不会管你想push的元素会不会比heap top更小。它一定输出heap的top，再把push值塞进heap里。不过我们这个题目，是可以保证push的大于等于heap top的，不会有问题。

如果没有这一点保证，你想做的事情就应该抽象为“push后pop”（当然内部应该优化，不是愚蠢地真的push后又pop），因为你想从heap和想push的新值一起看的集合中最小的值，可以使用headpq.heappushpop。不过，这个自己写也行，逻辑不复杂，就是先peek一下堆顶，如果push的新值更小，就直接返回，如果不是，就把堆顶值取出，把新值放在堆顶，然后堆化。

Ugly Number

https://leetcode.cn/problems/ugly-number-ii/

丑数，听到题目很自信，dp[i]表示i这个数字是不是丑数。然后直接超时GG。一个重要现实，大部分的数不是丑数，所以会很膨胀，比如n=476时，第476个丑数已经达到737280，73w了，太多数字不是丑数了。所以不应该用动态规划的i表示i这个数，而是表示第i个丑数。

去判断1个数字是否为丑数，这种一次性的判定，不去利用缓存是可以理解的，但找第i个丑数，当然不可能每个每个数字去判定，应该去找与前面的丑数的规律。所以，如果没想出动态规划怎么做，收集所有丑数，直到第n个，也是个办法。由于一个数2，3，*5都是丑数，但下一个丑数 *2不一定比前面的丑数 *3大，所以得排序。于是有了直接把数字插入堆里排序，这种方法，保证每次拿出最小的丑数来。第一次将1放入，1取出，2，3，5都放进去，反正1是最小的，可以安心输出。再从堆里取最小，2，2的2，3，5倍都是丑数又放进堆里。但注意得到2的3倍6进去了，3的2倍6又会进入堆一次，所以堆中拿出的丑数有重复，堆中拿出的丑数需要确认无重复，可以用map/set的key来去重，等map/set收集到第n个丑数时，停止收集。

再仔细理解一下人的解题思路。我们知道最小丑数是1，此时只能衍生出3个丑数2、3、5都是丑数，就三个选择，取最小的2，作为下一个丑数，而这个丑数又可以衍生出22,23,2*5三个，加上前面还没用上的的3和5，可以看到，这么想的话很膨胀，备选数会越来越多。但当前最后的丑数2，它的3倍5倍都很大，没必要此时就参与比较，只有2 * 2较小，可以和1的3倍和5倍比一比，谁是下一个丑数。但它们也不能被丢掉，后面的比较里它们也要成为备选。所以，换个角度，不要从“每个数的2、3、5倍都是丑数”这样发散，而是从“每个丑数都要被2、3、5乘”来考虑。也就是说，2、3、5它们三个要跟我们已生成的丑数序列的每个数都乘一次，且只需要一次，用完就扔，跳到下一个丑数去。

这个题解的说明更加清晰，推荐阅读。

这个思路可行后，还需要注意2 * 3和3 * 2这个重复问题，以2为例，看到当前的a[i] * 2 == a[-1]，那么应该取下一个a[i+1] * 2作为竞争者，跳过a[i]。所以我的代码是：

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        a = [1]
        L = [0,0,0,0,0,0]
        # L[i] = pi, candidate is a[L[i]]*i, i = 2,3,5
        while len(a) < n:
            if a[L[2]]*2 == a[-1]: L[2]+=1
            if a[L[3]]*3 == a[-1]: L[3]+=1
            if a[L[5]]*5 == a[-1]: L[5]+=1

            # 3 candidates
            m = 2
            min_n = a[L[2]]*2
            if min_n >= a[L[3]]*3:
                m,min_n = 3, a[L[3]]*3
            if min_n >= a[L[5]]*5:
                m,min_n = 5, a[L[5]]*5
            L[m] += 1
            a.append(min_n)
        # print(a)
        return a[-1]

就是在侯选前，去跳越重复值。
但更简单的写法是，在后面跳跃，比如[1,2,3,4,5]后的下一个丑数备选是3 * 2，2 * 3，2 * 5这三个，它们取出的最小值是6，但没必要取看它是丑数 *2还是 *3的结果，因为这两个指针都应该++。所以，更简洁的代码是：

while :
	min_n = min(a[p2]*2, a[p3]*3, a[p5]*5)
	if min_n == a[p2]*2:
		p2 += 1
	if min_n == a[p3]*3:
		p3 += 1
	if min_n == a[p5]*5:
		p5 += 1
	a.append(min_n)