Grokking the Coding Interview: Patterns for Coding Questions

See Grokking Pattern 1.

2. Pattern: Two Pointers

Pair with Target Sum (easy) – LeetCode

这题第一感觉是map或者排序后二分查找，双指针是个什么操作？

双指针自然得用在排序后的数组上，头尾各一个，[left]+[right] == target返回，>target right–，<target left++。确实也比二分好写，如果不能用库函数二分，双指针编码不容易错，也是个很好的选择。

就是答案要求返回索引，排序后的索引怎么查也是个问题。代价还是不小的。

Remove Duplicates (easy) – LeetCode

原地当然是要原地替换了，那么应该被替换的地方需要一个指针，理应替换到前面去的需要一个指针。

比如，00111，第二位的0会被第三位1覆盖，那么第三位理论上是个空缺位，但编码上，不用管一位，因为一视同仁的话，序列等于是01111，第三位是1，也不并妨碍接着删除1。所以可以不用特别处理，代码会写的很简单。

Squaring a Sorted Array (easy) – LeetCode

非递增序列，类似概念还有：非递减，单调递增，单调递减。。。

单调就是相邻两个数不会相等，非xx自然是可能相等的。

用高数教材的定义，当x1<x2时，都有f(x1)<f(x2)，f(x)就是递增函数，increasing function。其实“单调”这个词有些干扰。

increasing就是上升，不存在横着走，non-decreasing就是不下降，那自然可能横着走走（也就是，可能相邻几个数相等）。剩下两个同理。

题目本身很简单，结果是从小到大，但是绝对值最小的数不好找，所以反其道而行之，找大的然后放在尾部就行了。

Triplet Sum to Zero (medium) – LeetCode

在此题必然用双指针的提示下，想到了固定1个数，然后变成两数之和问题，用双指针处理这一子问题。

但这个题的输出很多限制，需要排除的东西很多，示例

1
2

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

基本包含所有可能，完成这个test就能AC。

编码上，可以避开很多不必要计算，始终记住，假设当前固定的数是nu ms[i]=a，双指针肯定是i<left<right。不要把left始终设为从0开始，没必要。

Triplet Sum Close to Target (medium) – LeetCode

其实比上一题简单，因为不用担心解重复的问题。注意的是result一开始设置一个极大值以便更新，别写做10^4了，这个python里会解释为14。表示次方使用两个星号。

Triplets with Smaller Sum (medium, google) – LintCode

不是直接套用模板能搞定的了，好好理解下面这个example。

1
2
3
4
5
6

Input:  nums = [-2,0,1,3], target = 2
Output: 2
Explanation:
Because there are two triplets which sums are less than 2:
[-2, 0, 1]
[-2, 0, 3]

应该是能O(n^2)解决的。

稍微暴力点，但容易想到的解法是for i, for j in [i+1, n)，这一层，可能有多个k可以是三数之和<target。这里可以考虑二分找，lower bound还是upper bound，不用细想，但可以知道二分方法能做到。但是复杂度就是n^2 * logn，肯定有优化点。忘记二分，如果我们顺序找k，从左或者从右都行，但考虑到“如果这一轮j找到了，j++后k是不需要跳回最右边的，k可以就从当前位置开始”，这个应该很好懂。所以如果k是从右往左找，代码就可以写的很简洁。而且明显降低了复杂性。

再来思考下复杂度是多少，由于固定i后，j和k又是最多只会遍历[i+1,n)的部分，所以总的是O(n^2)。

Subarrays with Product Less than a Target (medium) *

要求输出所有subarrays，也有要求输出subarrays个数。输出要求都不太难。

套用双指针或者说是滑动窗口模板时，需要考虑到乘积的写法。尤其是当某一个数本身就>=k时，窗口应该收缩成0。这个用双while写起来就很怪，所以我是在最开头就判断下，如果是就重新设置那一堆变量，进入下一次循环。官方代码使用for-while把这一情况包含了，不用单独判断。这里可以再思考下，官方的是不是正确，当nums内有数字1或者k==1时又会不会有奇怪的问题出现？

for-while的写法，就是可能会出现while结束后，start == end + 1，此时product == 1，因为没有取到任何一个数。接着会马上进入下一次外层for，end++后就会是start == end，即想选择[end]这一个数作为subarrary，然后接着while判断。这一整段没毛病。

至于nums内有数字1，完全不影响计算。而k==1，也不会有问题，走一遍逻辑就知道了，k==1时无论数组长什么样，结果都是0个，不存在<1的正整数，更不会有乘积<1了。

官方还有二分查找法，乘积[0, i]是非递减的，确实有道理。而且由于乘积可能很大，还用对数，很强势，看一看。

• 取对数后很难是正整数，那么必然有精度损失，不影响正确性？

Problem Challenge 1 - Quadruple Sum to Target (medium) *

四数之和，数组是整数但可零可负。

在已知此题可用双指针的情况下，自然去思考如何利用双指针，但双指针只能用于两数和问题（指定这两个数和为某定值，找出两数的所有可能解），那四数还有两个数怎么办，最简单的想法就是把这两个数所有可能列出来。于是平方复杂度列举出所有a和b的可能，对每一对ab，用线性复杂度的双指针找出c和d的所有可能解。大约就是三次方的复杂度了（可能真实复杂度可以算的更精确点，但反正小于等于三次方复杂度，暂不纠结这个问题，简单看待）。

想到这里，三次方的复杂度让我有点虚。不过，转头想这个题如果是暴力解法就是四次方，如果是定三个数再利用有序二分找第四个数，就是n^3*logn，n^3的复杂度好像瞬间就容易接受了。

题目有个麻烦点是不能有重复的四元组，如果不通过某种方式设置set（对四元组去重）的话，就需要跳过那些重复的组合。也能写出来，就是代码有点丑，也需要case来调试。不能一气呵成。

这个比较顺畅的思路是：

1. 首先思考第一个和第二个数，简写为a和b，它们都是for循环，比较类似。

   假设a固定，看b的移动。b如果右移还是同样的值，“右移之后的解集”只会小于等于“右移前”的（cd因为b的右移，可能性变少了），可以想到，解集不会增加任何可能性，反而只可能减少，b的取值却又是一模一样，那么右移后的abcd组合，在右移前遍历中都考虑完了，自然完全没必要重复遍历，所以b要一直跳到和前一个值不一样的地方，才需要进行遍历求解。

   而a的情况也一样，a的右移只可能使得bcd组合减少，没有新花样，a右移前后的解，值都一样，右移后的完全可以被跳过。所以a也是要跳到和前一个值不一样的地方。

2. 再思考cd两个值，如何过滤重复的解。

   c+d不等于想要的值时，方向很明确，只会left或者right某一个移动。如果c移动到下一个值还是不变，那还是c+d不等于期望值。所以不等于的情况不用过滤。而c+d==期望值时，如果只有left右移，那么肯定要跳过重复的值。但如果是right那边重复，只left跳过重复值，能否解决问题？答案是可以。举例说明，当left这边序列是11111xxx时，1+d==期望值，那么left一直移动到最后一个1，下一个数就不是1的时候，abcd这个组合可以成为一个合法解，然后left++，那么下一次while时就是大于1的数+没有动的d，那肯定是大于期望值，right那边就会左移，遇到重复的right还是左移，并不需要考虑过滤。

   当然，只做right的重复过滤也可以。没必要做两边的。当然两边都跳过也行，但少写代码少错😄。

再思考下几数和问题，两数和就是双指针，线性复杂度，三数和就是指定一个数再解决两数和，平方复杂度，四数和三次方复杂度。

Problem Challenge 2 - Comparing Strings containing Backspaces (medium)

顺序找规律怎么也找不到时，一定要记得反向试试。数组题一定要记得反向可能有奇效！！！

此题没有什么巧妙写法，写出来的代码有点长，不过容易调试成功。

Problem Challenge 3 - Minimum Window Sort (medium) *

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

Given an array, find the length of the smallest subarray in it which when sorted will sort the whole array.

Example 1:

Input: [1, 2, 5, 3, 7, 10, 9, 12]
Output: 5
Explanation: We need to sort only the subarray [5, 3, 7, 10, 9] to make the whole array sorted

Example 2:

Input: [1, 3, 2, 0, -1, 7, 10]
Output: 5
Explanation: We need to sort only the subarray [1, 3, 2, 0, -1] to make the whole array sorted

Example 3:

Input: [1, 2, 3]
Output: 0
Explanation: The array is already sorted

Example 4:

Input: [3, 2, 1]
Output: 3
Explanation: The whole array needs to be sorted.

这个题没找到OJ地址。思考的时候想到了拐点，不过后续思考没跟上。

首先，找到了subarray之后，这个subarray一旦能排好序，整个array就有序了。那么，非subarray的值就应该是它们应该在的位置。

Example1中1和2在应该在的位置，就很容易想到指针找到第一个比右边还大的值（也就是拐点），也就是5。但Example2直接打脸，1本就不在该在的位置。

到这儿就没继续沿着这个思路继续下去了。然后就没找到思路了。。。

找到左右两边的拐点后，拐点之间的这个区间必然不是都在正确位置上，所以这个区间肯定在subarray里面。但Example2也提示了，找到了拐点区间[3,2,0,-1]，可以看到前面的1也是错的，为什么呢？因为1排序后也不应该站在它现在的位置，也就是说subarray应该还需要扩张。

扩张的依据是什么？这个元素是否在当前区间的最大最小值之间。因为如果在之间，全局排序后，这个元素和当前区间的位置都是要变的。画一下折线图，纵坐标表示值的大小，横坐标是元素位置，就可以很直观的看到，区间的扩张是简单的，因为它只需要往外1个1个check就行了，没有什么复杂规则。

• code

Grokking the Coding Interview: Patterns for Coding Questions

See Grokking Pattern 1.

3. Pattern: Fast & Slow pointers

LinkedList Cycle (easy)

题目描述很反人类，但其实就是给你一个链表（只有head指针），让你判断是否有环。进阶是只使用O(1)的空间，也就是常量空间。

有环的链表肯定会访问到重复的节点，环内有1个或以上的节点。搞一个空间存已经访问过的节点，查到之前访问过就能判断了，但空间最坏能到O(n)。常量空间，自然要用快慢指针。

推理一下，快慢指针什么时候能证明链表有环？

猜想肯定是快慢指针指向同一个节点时，但怀疑是否存在“有环链表下快慢指针也不会同时指向同一个节点”。画画图，列一下方程式，假设链表入环前有s个节点，环上有c个节点，可以知道，当走整数倍c（2倍起，同时还得>s）的时候快慢指针是能遇到的，这个值不会不存在，还会多次相遇。所以不用担心快慢节点会永远遇不到。

编码上很简单了，记住init时fast，slow都指向head，然后while内先走再check。

Middle of the LinkedList (easy)

很简单的题，把两个case都手动推理一遍，就知道了。hint：fast先走，提前退出，slow就不用走了。

Start of LinkedList Cycle (medium)

这个题猜得到是需要快慢指针相遇后再加点什么操作的，但是推理容易卡壳。主要还是对快慢指针相遇的情况理解的不够。

快慢指针相遇很好写，node地址相等就是了。但相遇时，快慢指针并不是可能走了无数圈。这里有一个点必须记住，就是“慢指针入环后，和快指针相遇时，慢指针在环上是不会走超过一圈的”。也就是慢指针入环后继续走，一圈以内必定碰到快指针。

这个知识点，我以前应该用方程式推过，也不记得推理有没有漏洞了，这次做题还没推出来。所以这里最直观也正确的解法是数学归纳法。我们讲slow入环后和fast相遇，那么最快相的情况，当然是slow和fast直接在入环点直接相遇，0步。再麻烦点，就是fast在slow的前面（此刻的位置是fast.next==slow），这样两个相邻的节点，只需1步就能相遇。假设fast更远一点，即fast.next.next==slow，就需要2步，以此类推，入环时刻，fast和slow的距离（fast的n个next==slow）假设为n，就需要n步相遇。但fast和slow之间最大距离就是fast在slow的前一个，假设环里有k个节点，fast和slow的最大距离就是k-1，所以最多k-1步，fast和slow必定相遇。所以slow不可能在相遇前走几圈。

知道slow在一圈内就会和fast相遇，其中几个关键长度如下图所示。那么相遇时slow的公式应该写为，slow=a+b，fast=a+b+n(b+c)。

(leetcode图源，可能会挂，自行戳网址)

再回到题目本身，当两指针在紫色点上相遇时，代入化简一下已有式子，得a+b=n(b+c)，即a=c+(n-1)(b+c)，为什么化简成这样？不是因为这样a可以通过等式右边得到，右边这式子也没法继续求。而是因为，右边写成这样，b+c是一整圈，也就是说，如果一个指针从链表头开始走起，另一个指针从紫色点走了c长度又走了几个完整圈，它们会在入环口相遇，另一个指针走几圈完全不用在意。

但注意，这个式子可能有坑，思考下有没有可能a很小，c很大？

n必然>=1，因为fast肯定走的多点，不然fast=a+b+n(b+c)就不对了。那么，a最小就等于c，不可能比c小。这个事情挺有趣的。没有想到一个很通俗易懂的表达，但数学证明了也就证明了吧。

Happy Number (medium)

这题现在是简单😂

题目没有读仔细，所以第一时间没能察觉到和快慢指针有什么联系。题目表述为“也可能是 无限循环 但始终变不到 1”，我简单地想到了不能一直计算，但忘记了无限循环不是每一次结果都不一样，它只是每次结果都是不是1，不是说每次结果都是从未出现的数字。

接着，就排除了用定义一直计算这种思路，变成了想利用数学之类的其他方法来解决。虽然也推理出了平方和计算中，不能爆出非常大的值，最大32bit的数，十进制也就是13位，就算13位都是9，一次平方和计算下来，也不过1053。而1053的平方和也挺小的，1053以内能算出较大平方和的也就是999。而999再算一步也就是243。

可以明显感觉到，不可能出现一个小的数字经过多次计算膨胀的很大，只可能很大的初始数一下子变得很小。当然像case1中19经过计算会变大，但这都是一定范围，最大不可能超过1053。

然而，从这里开始，我就期待用动态规划一类的方式，类似斐波那契数列，提前算好所有快乐数。所以我认为，可以从1，10，100，1000反推平方和等于它们的数，但是反推的链路有点长，说不定反推也会不能停止，毕竟这个思路不太对劲，可能有不少漏洞。

总结还是应该利用平方和结果范围有限这一点，也就是抽象成链表的有环判定。当然，因为平方和都是即时算的，不像链表问题提前准备好链表。简单的方案就是直接保存之前计算出的结果，也就是不用快慢指针，而是用是否已存在来判断。而如果还是想用快慢指针，可以def一个next函数，考虑到节约空间，next函数只管计算不用缓存。快指针两次next，慢指针一次next就好了。

纯数学的角度其实也可以继续推下去。但需要更仔细的范围研究。所以，回顾之前的推理，最大的数字13个9，也会瞬间收缩到1053，再归纳总结，12个9收缩到。。。4个9收缩到324，这里特别的来了，999到243。为什么说999到243特别，因为这里位数不降了，之前的那些大数都会收缩位数，变得更小，999虽然会经过一次计算变小，但位数不会收。所以一旦计算结果收缩到3位数，接下来的所有平方和结果都是三位数以内，不可能膨胀，且跌入三位数后（三位数后再计算一次），必然困在243以下。而为什么就243了，有没有可能实际数字更小？简单举例99就知道，它能变大到162，也就是涨到三位数，但不可能从三位数继续变大。所以，计算进入243以内后，可能会振荡，比如2位数蹦到3位数，但不可能比243更大，也就是出不去了。

那么，假设计算结果小于等于243时，我们能直接给出结论，是不是快乐数。就不用进入无限的循环了。所以问题变成243以内的数字，哪些是快乐数？

而这样的问题缩减，有什么好处呢？好处在于，243个数字，最大值也就是243，大可以暴力算加是否已存在判定，最大空间复杂度也就到243，比起给一个数就缓存，空间占用要小一些。（其实应该也小不了多少，毕竟收缩很快）但把<=243的数字直接打成表，对于频繁查快乐数的情况，就会节约时间的多。oj时间上节省的会比较明显。如果只是一次快乐数判定，当然打表反而还浪费时间。

Problem Challenge 1 - Palindrome LinkedList (medium)

难度简单。

很明显快慢指针能够找到链表的中部。而中部开始向左向右比对，就能判定是否回文。右半边很顺畅，不用改动，关键在于左半部分。但左半部分再快慢指针途中是被遍历访问过的。这其实也就提示了，如果修改链表，就能降低空间复杂度。题目进阶就是希望用O(1)空间，那大概率就是原地修改链表的左半部分。

很直接的就能想到是反向指。写写画画，不难得到简单的代码。得到了链表中部的指针后，当然是往两边走，逐个对比。但注意，奇数回文串和偶数回文串比较的起点是不一样的。我粗心的只想到了偶数回文，跑测试才发现奇数回文跑不过。

P.S.

这个题还有个递归解法，我不太擅长递归，经常起手就是迭代，所以这里值得再学习下。首先，递归能给我们什么？假设我们只是简单的print val，那么递归就能从尾到头，逆序读出每个节点的值。假设我们递归到底了，现在能读到尾部节点，这个时候我们应该拿头部节点和它进行比较，接着递归会读倒数第二个，而这时又应该拿顺数第二个节点比较。可以看到，从头部开始读也可以用一个指针来解决，但这个指针得是外部的变量，放在递归函数里面太困难了。再思考奇偶情况，奇数节点两指针地址会指向同一个节点，容易判断，偶数情况本来以为会麻烦点，但还好，因为两个指针指向的节点是相邻的，所以只要next判断一下就好了。leetcode官方解更飘逸，全遍历，不用提前返回，那对栈空间要求更高了。不大实用，但可以多熟悉下递归。论简单，还是递归这个写法代码少。

Problem Challenge 2 - Rearrange a LinkedList (medium)

1
2
3
4
5
6
7
8
9
10
11
12
13

Given the head of a Singly LinkedList, write a method to modify the LinkedList such that the nodes from the second half of the LinkedList are inserted alternately to the nodes from the first half in reverse order. So if the LinkedList has nodes 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null, your method should return 1 -> 6 -> 2 -> 5 -> 3 -> 4 -> null.

Your algorithm should not use any extra space and the input LinkedList should be modified in-place.

Example 1:

Input: 2 -> 4 -> 6 -> 8 -> 10 -> 12 -> null
Output: 2 -> 12 -> 4 -> 10 -> 6 -> 8 -> null

Example 2:

Input: 2 -> 4 -> 6 -> 8 -> 10 -> null
Output: 2 -> 10 -> 4 -> 8 -> 6 -> null

跟challenge1类似，尝试了一下递归的写法，比较容易写，就是先把偶数链表搞定，再补一下奇数情况的判断就行了。但是注意，debug时别打印链表，修改中途的临时链表很可能是有环的，打印也打不出来。当然可以限制下打印的node个数，调试时还是可以有的。

如果不用递归写法，这个题还是和challenge1一样，可以把后半部分链表原地反转。不多赘述。

Problem Challenge 3 - Cycle in a Circular Array (hard)

题目有点难读，但解析下来，题目的意思是，首先有个环有n个节点，节点里的值表示下一步会向前or向后跳几个节点，可以理解为在做链表的next链接。这样下来很可能会出现环状的链表，而且题目定义的链表更狭窄点，k=1（一个节点自环）的不算，不算一会儿前进一会儿后退的。

根据“链表next”和“判断是否循环”，就知道可以用快慢指针。但快慢指针会测到自环，所以即使判断有环，还得再一次确认是否是k=1自环的情况。

而“不算一会儿前进一会儿后退”这一点很重要，题目的说法是循环的下标序列不是全正就是全负。那么指针跑的时候去要看自己现在所处的位置i，这个位置指定的步数，也就是nums[i]如果和之前的nums[…]符号不同，就可以直接判断为False。

那么，还剩两个问题。

1. 快慢指针没有null作为退出条件了，不知道能不能结束。这里可以考虑防御性编程，加个一定限制。但其实不需要，原因是，如果一个nums值全为正，选一个元素来看，它必然得指向某个元素，这个元素如果是它自己，就会发现一个自环；如果不是，它势必要指向一个新元素（我们还未访问的）。但访问得一直继续，如果每次都不是循环（快慢指针查不到的），不会停止，一直访问下去，那么元素迟早被访问完，那下一步会去哪儿呢？所以必然会有快慢指针能够查到的环，虽然自环不能算本题定义的“循环”。
   1. 总结一下，就是，除了不是全正or全负会提前退出，快慢指针是必然会相遇的。自信点，不用防御编程。
2. 此题不是简单的从数组头开始。拿个示例画一下，也能发现，从某个下标开始跑快慢指针，结果都是不一样的。所以理论上，每个数组元素都是可能的循环的开始。

总结到这里，突然想到一个问题，既然只有全正全负会陷入while loop不能提前退出，而全正全负又一定能有广义的环。那么完全不用快慢指针，只需要把每个点当作可能的入环口，也就是从这个点开始我能转回这个点，就找到了一个广义环。并不是非得快慢指针。只是这里有个坑，那就是这个点只是可能的入环口，它也有可能是类似有环链表的直线部分，走了几步才入环。所以得有个限制退出while步进，不然会死循环出不去。又由前面整理的结果，想要全正or全负没有环是不可能的，最大的环也就到整个数组的长度（当然，可能链表箭头走的很骚，不是说只能沿着数组+1/-1步这么走，但长度是不能再长了）。

这个思路比快慢指针代码上简单点，时间复杂度上却不是变少，因为这个思路走满环，最坏时能达到数组长度，O(n)，快慢指针中fast指针和slow指针第一次相遇时slow也没有走满环，fast多一倍步数，也没差多少。所以这个思路也不会带来质变，聊胜于无。

Grokking the Coding Interview: Patterns for Coding Questions

See Grokking Pattern 1.

4. Pattern: Merge Intervals

Merge Intervals (medium)

挺简单的题，尤其是我对这种merge interval的题有一个印象，就是“反着比正着简单”。所以很容易就想到了，这题应该反向来看intervals，所以遍历顺序是end大的到end小的，合并interval或者即时push interval到result里，都很简单，不用多注意什么。

Insert Interval (medium) *

这个题目纯粹是恶心人，没啥别的作用了。由于每个interval都有两个数表示，又得两个interval之间比较，绕的很晕。

大概逻辑很好想，由于加入new interval（后面简称new），可能new和intervals内的多个interval（后面简称i）有重叠，所以可能会消除多个i，为了代码简洁，肯定是新建一个list，符合条件的才插入，这个逻辑比较好。

又回到new和多个i的合并上，重叠就需要合并，合并后的new’可能还是不应该插入，毕竟可能多个i都需要跟new合并，所以需要一个tmp interval。很容易发现，直接用new来做这个tmp interval正好。

本来思路到这儿还是很清晰的，但是由于对“重叠”的定义没先弄清楚，所以写出了漏洞百出的算法。这一点需要吸取教训。算法如果一开始用数学很难表示，就应该先用形容，能把算法定义清晰了，再翻译为数学。不要总想一步到位。

而“重叠”定义，最简单的办法就是画图，画两个interval的相对位置关系，可以看到，分四种情况，a的右边跟b重叠，a的左边跟b重叠，a完全在b内，a完全包容b。当然数学上，由于与或非关系，可以把前三个写为一个判断式，但第四个无法合并，很容易忘记这一种情况，要细心。

当然，可以反向来看，那就是“不重叠”的非集就是“重叠”。而“不重叠”的判定更简单（我一开始是这么想的，但当时对“重叠”情况的处理很混乱，所以换了思路）。如果再次做此题，正向反向都容易想到，没有特别的坑。

当扩展后的new和当前i不再重合时，需要把new和i都加入result里。这里需要一个布尔量表示new有没有已经被加入，这个步骤没办法写的更优雅。

coding时，还可以注意，我在妄想一步到位时，写满了[0]，[1]。。。把自己都给绕进去了。python是可以for left, right in intervals这么写的，所以别折磨自己，python is beautiful!

Intervals Intersection (medium)

拟定一下算法流程，照着流程过一遍example，就没什么坑了。没什么巧思，一个一个if-else保证正确就行了。

Conflicting Appointments (medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Problem Statement
Given an array of intervals representing ‘N’ appointments, find out if a person can attend all the appointments.

Example 1:

Appointments: [[1,4], [2,5], [7,9]]
Output: false
Explanation: Since [1,4] and [2,5] overlap, a person cannot attend both of these appointments.

Example 2:

Appointments: [[6,7], [2,4], [8,12]]
Output: true
Explanation: None of the appointments overlap, therefore a person can attend all of them.

Example 3:

Appointments: [[4,5], [2,3], [3,6]]
Output: false
Explanation: Since [4,5] and [3,6] overlap, a person cannot attend both of these appointments.

最简单的区间问题，排序完了，遍历就行了。排序是正着还是反着都行。反正拍完序，只需要看相邻两个区间有没有相交。

Problem Challenge 1 - Minimum Meeting Rooms (hard)

https://leetcode-cn.com/problems/meeting-rooms-ii/ plus

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

Given a list of intervals representing the start and end time of ‘N’ meetings,
find the minimum number of rooms required to hold all the meetings.

Example 1:

Meetings: [[1,4], [2,5], [7,9]]
Output: 2
Explanation: Since [1,4] and [2,5] overlap, we need two rooms to hold these two meetings. [7,9] can
occur in any of the two rooms later.

Example 2:

Meetings: [[6,7], [2,4], [8,12]]
Output: 1
Explanation: None of the meetings overlap, therefore we only need one room to hold all meetings.

Example 3:

Meetings: [[1,4], [2,3], [3,6]]
Output:2
Explanation: Since [1,4] overlaps with the other two meetings [2,3] and [3,6], we need two rooms to
hold all the meetings.

Example 4:

Meetings: [[4,5], [2,3], [2,4], [3,5]]
Output: 2
Explanation: We will need one room for [2,3] and [3,5], and another room for [2,4] and [4,5].

因为所有intervals都得被满足，所以贪心策略可能可以得到最优解？

简单设想一下，已经排序好的intervals，一个一个尽量排，重叠了就新增一个room。

假设，此时已经用贪心策略得到了2个room，r1和r2，假设r1.end <= r2.end，这时又想加入一个interval，它的start如果比两个end都小，那必然得出第三个room，这个不可能缩减。而如果start比一个小比一个大，那肯定是放入，但放1还是2？我们先比较，肯定是选r1（end最小的room）来比，如果end最小都放不下新的itv，就新增room。如果r1能放下新的itv，为了代码简洁，也应该直接放下了。（假设r2也放得下新itv，那么下一个itv也能放到r2，不会新建room；假设r2放不下新的itv，那就更不可能放r2了，至于下一个itv，就看更新后的r1r2能否满足了。）

——这一部分用数学推理下。

但显然，room不可能只限2个，所以可以考虑一个排序的容器，保存room的end。容器需要支持重复key，因为多个room的end可能数字一样。容器只需要取的出最小的end，之后end可能更新变大再插回容器，其他位置不用管。所以用优先队列最符合要求，而且python没有multiset，想不用优先队列都不行。

代码写起来还是很简单，rooms只会“堆顶被pop再更新push”和“pop新的room”两种情况。不过题解里有一个很骚的操作，就是会把rooms里end<=itv.start的元素都pop掉。怎么理解这个东西？

首先按我原本的设计，rooms的len只会不变和变大，不仅如此，当前itv的end是必然会进优先队列的，区别只在于堆顶会不会pop（也可以理解为itv是会进入优先队列的，因为这里需要考虑itv.start了）。原本设计里优先队列“时刻对应”rooms的已有排列。但前面的思考里，也体现出了，rooms内可能多个room的end都<=itv.start，这部分rooms不会对当前itv和之后的itv产生影响。无法产生影响，就可以直接当做“不存在”。“不存在”，所以可以从heapq里剔除掉，当前itv必然加入heapq（itv会不会影响，要看下一个itv的比较），当然，这时的heapq可能比“当前实际rooms len”小，所以用max来追踪heapq的len最长的时候。

（题解思路还不够清晰，有空再思考下）

Problem Challenge 2 - Maximum CPU Load (hard)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

We are given a list of Jobs. Each job has a Start time, an End time, and a CPU load when it is running.
Our goal is to find the maximum CPU load at any time if all the jobs are running on the same machine.

Example 1:

Jobs: [[1,4,3], [2,5,4], [7,9,6]]
Output: 7
Explanation: Since [1,4,3] and [2,5,4] overlap, their maximum CPU load (3+4=7) will be when both the
jobs are running at the same time i.e., during the time interval (2,4).

Example 2:

Jobs: [[6,7,10], [2,4,11], [8,12,15]]
Output: 15
Explanation: None of the jobs overlap, therefore we will take the maximum load of any job which is 15.

Example 3:

Jobs: [[1,4,2], [2,4,1], [3,6,5]]
Output: 8
Explanation: Maximum CPU load will be 8 as all jobs overlap during the time interval [3,4].

很容易发现这个题和上一题安排会议，抽象下来是一样的。最容易想到的push/poppush的方法，但由于题目是求max load，所以要尝试改造，然后发现不行。因为这种方法没办法跟踪当前load sum。举例说明，假设itv已经排好序，start小的排前面，start相等时end小的排前面，如果itv1和itv2重合一部分，itv3和itv2重合，但是它并不与itv1重合，在看itv2和3重合的那一段时，load应该是2和3的load之和；而如果itv3和itv1也重合了，这时就应该是三个itv的load之和。但push/poppush是区分不了的，因为它只和heap top比较了一下，摸不到别的itv。

再想到while pop这个方法，虽然在上一题里它很不容易理解，但这道题反而该使用这个方法。核心在于while pop出和当前itv无关的itv，并相应减掉它们的load，就能够实时追踪到某一个时刻的load之和了。

• 再理解下上一题和while pop方法。

Problem Challenge 3 - Employee Free Time (hard)

https://leetcode-cn.com/problems/employee-free-time/ plus

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

For ‘K’ employees, we are given a list of intervals representing the working hours of each employee.
Our goal is to find out if there is a free interval that is common to all employees.
You can assume that each list of employee working hours is sorted on the start time.

Example 1:

Input: Employee Working Hours=[[[1,3], [5,6]], [[2,3], [6,8]]]
Output: [3,5]
Explanation: Both the employess are free between [3,5].

Example 2:

Input: Employee Working Hours=[[[1,3], [9,12]], [[2,4]], [[6,8]]]
Output: [4,6], [8,9]
Explanation: All employess are free between [4,6] and [8,9].

Example 3:

Input: Employee Working Hours=[[[1,3]], [[2,4]], [[3,5], [7,9]]]
Output: [5,7]
Explanation: All employess are free between [5,7].

这题本质是一种反向，题目提过工作时间，让你求非工作的某种时间，所以可以用交集并集差集来理解这个题，方便快速的分辨多个解法的复杂度。当然，最佳算法可能比这种逻辑运算的计算量更小，但不熟悉这类题目的情况下，越抽象的思考越容易做。

可以看到k个list，每个list都多个interval，所有的interval的并集，就是所有员工的工作时间，这个集合的反，就是所有的空闲区间（空闲区间显然也可以是多个）。

题目说明了，k个list，list内的区间都是有序的。这很像k路归并排序。按理可以比所有inteval混在一起排序更高效。那我们先mark这个归并思路，放在一边。（有序基本就是在提醒我们存在“利用有序”的优化算法）

简单思路

假设经过某种算法，已经计算出了所有working hours的并集，这个并集当然可能是多个区间，不一定是一个连续区间。求反只需要遍历这一堆区间就行了。

再来考虑，这个“某种算法”求并集，怎么做。最简单的肯定是全排序。每个区间先比较start，小的排在前面，end随意。这里很可能会出现连续几个区间是有重合部分的，所以，求并集，还得遍历一边，重组一下区间，得到并集（不重合的区间组成的数组）。然后还得再遍历求反。

简单一想，也知道，最后一次遍历多余了。

所以，可以立马优化为，遍历已排序的区间时就求空闲区间。

可以再思考一下，我先每个list先求反，得到每个员工的空闲时间，所有的空闲时间的交集也是最终答案。但空闲时间区间个数不见得比工作区间个数少多少（应该是，对每个list，空闲区间=工作区间-1）。并没有把复杂降低。而且求交集比求并集复杂，因为空闲区间没办法全部一起求交集。想象一下，假设5个员工，有1个在[0,t]之间都不空闲，但是另外4个却可以在[0,t]这个时间内存在交集，但是这个交集是不能要的，因为那一个人不空闲。区间全混在一起时，根本无法判断。所以还是求并集吧。

归并思路

每个list“有序“，自然是提醒我们要充分利用这个特性。全排序肯定不够用。而list内interval有序，很显然可以做类似归并排序的操作。

归并思路，k个list也就是k路，每次都从k个list的头上选出最小的。这k个区间比还呆在list里的区间的start都要小，在k个中选出来的start最小的区间，也就是全局start最小的区间。所以，当我们将k个中选start最小看作一个模块时，我们从这个模块中拿出“剩余区间”中start最小那个区间。一个一个拿，就是总能按顺序拿出区间了。

核心是这个模块如何实现，即考虑“k个中选最小的”怎么高效，归并算法如果只有两路，当然if-else都能行，但k路肯定是不可能一个一个比的，很明显可以利用最小堆，每次的top就是最小的，top取出来后，top所在的list就应该补充一个区间进入最小堆。python中也就是使用heapq，可以极快的写完代码。

堆算法解释见Heap。

具体到这个题目，首先要思考这个堆该如何运行，放多少数据，pop出来后又push多少进去，初步设计应该尽量分割步骤，目标是迅速写出正确的算法，后面再做优化。

所以初步设想是，k路数组，每个数组自己内部有序，但k个数组的头，我们是不知道谁最小的，所以把k个数组的头放进堆，我们就可以立马拿到最小的数，此时堆里剩k-1个数，这时候应该将pop出去的那一路的新头补充进堆，因为我们知道数组内的都比堆里的大，只有堆里的有资格比拼一下，所以堆大小在运行期间应该保持为k，不需要多放，多了增加复杂度，少了就比不出全局最小了。

Grokking标准答案也是使用python heapq来做，这个确实写得最快。

败者树

堆解法不是终点， 如果提到有没有别的思路，就肯定要说到败者树算法了。本质都是树，不会有数量级提升。但总有些区别。

外排序todo

winner/loser tree很像B+树，非叶子节点是不存值的，所以，和B+树类似，它们可以用在“外排序external sorting”上。

https://www.cise.ufl.edu/~sahni/cop5536/ 这个网站有很详细的exteral sorting的ppt，需要好好看看。（但是很难懂。。可以当作提纲）

针对winner/loser tree（统一可以叫做Tournament Tree）来讲，你需要知道，Tournament Tree可以利用于improve run generation, 也可以improve run merging。

解释下run generation。外排序不可能把所有的扔进内存里，所以只能先切分成小部分排序，然后做merge，这两步叫做，run generation和run merging。A run is a sorted squence of records。

improve run generation最简单的就是reduce the number of runs(也就是increase average run length)。但这也是有极限的，而且由于外排序在IO上很耗时，所以overlap IO也是一个优化方法。都在课件里，之后再慢慢看。

返回tournament tree

败者树和胜者树是可以一起看的类似结构。胜/败者树都是类似B+树，只有叶子节点是真实值，非叶子节点是胜者/败者的标号，而且它是完全二叉树，不会有歧义。但胜者树和败者树不是单纯的一个非叶子节点记录胜者，一个非叶子节点记录败者，否则这两种就应该是一种树，只要compare函数求个反就行了。

胜者树

胜者树更简单，我们先看胜者树，比如小的是胜者，那么每个非叶节点都是它的子节点中更小的那一个。原理很简单，实现上要捋一捋。

可以把整个建树过程理解为打比赛，那比赛，肯定是从下往上打。最下层的非叶子结点先被填上值。按最简单的想法，胜者树用数组表示，每个元素是值（比较大小的值，不是索引）。这样子会有什么问题？当我们把胜者根节点拿出去，我们都不知道应该补上哪个list的元素。所以这个胜者树的节点，应该有索引，标记第i个list，这样就可以补充list[i].top进来。节点可以又保存值，又保存list标号，不过被拿来建树用的k个区间，本来也会放在一个地方，可以叫做ext数组，这样，胜者树节点只需要保存list标号就行了。ext[i]可以取值，list[i].top可以拿到补充用的区间。

而且注意，胜者树是所有参赛者都作为叶子节点的，比如，有3个叶子节点时怎么建树？有6个叶结点时，上一层3个节点，那它的上一层又怎么办？

注意，胜者树定义为complete binary tree，完全二叉树，它只有最底层可能少尾部一些节点，其他节点都是满的。所以，不会存在6个叶节点，上一层只有3个节点的情况，这棵树必须是最底层6个节点（理论上是8个），上一层4个节点（即使这一层最右的这个节点是没意义的，可以用max值，这样不影响比赛结果）。

解决胜者树的节点结构和树形，这两个问题，就可以写算法了。Ref

https://gist.github.com/vagetablechicken/8a2fc94da27f127921c0b6dd08d7863f

败者树

而败者树呢，非叶节点是记录败者，但是往上送的参赛者是“胜者”（关键点）。

为什么这么做呢？假设胜者树的重新比赛，一个叶子节点被换了，那么它要和它的兄弟节点比。而败者树里，更新的节点只需要找它的parent，就能决定parent是否要更新，不用去访问兄弟节点。

这里粗略一想，觉得很莫名，也没有节约多少东西？

假设两个兄弟节点n1、n2，n1之前不是胜者，但现在比较一下发现n1是胜者，n1的parent就要被我更新为n1？而在败者树里面，我虽然只需要访问n1和n1的parent，不用访问n2，但这能节约多少？

这个问题，如果只看算法题目这种规模当然节约不了什么。但败者树通常用于外排序，外排序的数据规模就很可观了。就访问而言，以前要访问两个，现在要访问一个，访问总次数一多，耗时差距就很大了。（应该不用觉得兄弟节点会需要单独一次I/O从磁盘里读出来，毕竟外部排序的归并部分也是应该保证在内存里进行的，归并部分都要存硬盘了，这个归并k选的也不太对了。）

逻辑上走通了，再来说说code的问题。两个叶子节点比较，得到败者作为父节点，这里还很常规，但是还得往上送胜者，这里就微妙了。难道代表败者树的数组，每个元素都得存两个东西，胜者和败者？还是说，得用node指针来构建树？

complete binary tree不用数组怪浪费的。而且node指针构建树，一开始只有k个单节点的败者树，还要把它们merge起来。merge得先两两merge，注意，要一直保持每棵树的complete binary tree性质。所以，还总是需要构建无意义的节点，为了保持complete binary tree。有点离谱。

还是尝试用数组来表示败者树。其实败者树从构建成功起，就不会再变更树结构，所以建树期间的胜者可以用单独变量来保存，建好树之后，它们就没有意义了，只有全局的那个胜者有意义。

还是在 https://gist.github.com/vagetablechicken/8a2fc94da27f127921c0b6dd08d7863f

注意，胜者树可以随便更新参赛者，并且需要从叶子一路更新到根节点，不然可能存在问题。因为，新参赛者即使曾经是某一层的winner，现在值变了还是winner，但它的值变了，往上走它可能就不是了。只有它之前是loser，现在跟之前的winner比还是loser时，才可以停下来。这个优化可以，但没必要，容易写错。建议先写出简单不易错的算法，再谈要不要优化。

败者树则是必须更新winner所在的值，因为败者树要保证只更改胜者走的那条路径。有了这个保证，才能肯定parent存的败者一定是兄弟节点，才可以避免访问兄弟节点。败者树也得一路到根节点，不能因为以前是胜者，现在还是，就不往上比较了，值变了！！！

Grokking the Coding Interview: Patterns for Coding Questions

See Grokking Pattern 1.

5. Pattern Cyclic Sort

这个cyclic sort，需要一点预备知识。cyclic sort条件是，数组元素必须是1到n，虽然乱序，但我们可以确定这个n长的数组里一定是1到n这n个数字，不会有别的数字。如果要对这种特别的数组排序，就可以环型排序，也可以叫圈排序。都知道1到n了还排序就很离谱，所以这并不是cyclic sort的使用场景。事实上，使用场景是Cyclic Sort这一题之外的题目。

Cyclic Sort (easy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Problem Statement
We are given an array containing ‘n’ objects. Each object, when created, was assigned a unique number from 1 to ‘n’ based on their creation sequence.
This means that the object with sequence number ‘3’ was created just before the object with sequence number ‘4’.

Write a function to sort the objects in-place on their creation sequence number in O(n) and without any extra space.
For simplicity, let’s assume we are passed an integer array containing only the sequence numbers, though each number is actually an object.

Example 1:

Input: [3, 1, 5, 4, 2]
Output: [1, 2, 3, 4, 5]

Example 2:

Input: [2, 6, 4, 3, 1, 5]
Output: [1, 2, 3, 4, 5, 6]

Example 3:

Input: [1, 5, 6, 4, 3, 2]
Output: [1, 2, 3, 4, 5, 6]

这个题目着实惊呆我了，我遍历一遍直接将第i个元素改成i+1都通过测试。

不过老实做题的话，这个确实可以用cyclic sort做。cyclic sort具体步骤是，遍历，当当前的元素不在它应该在的位置时，把它和它应该在的那个位置的值做个交换，比如数组[4,3,2,1]，当前看第一个元素4，它应该在最后，所以就交换一下，变成[1,3,2,4]。并且下一个要处理的元素还是当前，因为被交换了过来的元素可能也不是正确位置。

这个排序法的时间复杂度看起来很诡异，不知道怎么算。但可以这么考虑，因为我每一次swap，必然把一个元素放对位置了，所以swap次数最多就n-1次。因为n-1个元素位置对了，自然最后一个元素位置就对了，所以只有n-1次。

可以举个最差例子，[3,1,2]每个元素都不在正确位置。看3，swap后为[2,1,3]，3就放对了，继续看2，swap后[1,2,3]，由于2放对了，最后剩的一个元素就对了。

代码很好写，不用赘述。

但这个排序算法的意义何在呢？接下来的题目里可以提现。

Find the Missing Number (easy) – LeetCode

这个题目当然可以用cyclic sort做，但是需要注意，题目中是0-n少了某一个，然后乱序放在n长的数组里。假设缺少的那个数不是n，那么数组里就有n，上个题解中的cyclic sort，当然是不能把n这个数放对位置的，因为n长数组idx最大到n-1，没有n。

这怎么办呢？看了Coding Patterns: Cyclic Sort - emre.me就知道了，只需要忽略n就可以了，如果访问到n，就跳过n，往后访问。这样，遍历操作一遍后，就会出现，n在“不存在的那个数”的位置上，其他数都在对应的位置上。再遍历一次数组，就可以找到missing number了，显然如果遍历一遍数字都对，那么就是missing n这个数了。

这个题目有多种解法，bitmap等等，还能用数学的方法来做。但cyclic sort有一个好处，就是完全没有用额外空间。

Find all Missing Numbers (easy)

跟上题不一样了，输入n长的数组，里面就是1-n的某些，数字可重复，要输出all missing numbers。

但也容易做出来，拿example 1推演一遍就知道该怎么做了。把”错误位置的元素swap到正确位置“这一条规则不变，但如果有重复元素，就会出现nums[i]!=i and nums[nums[i]] == nums[i]（意思是这么，但实际上idx从0到n-1，数值从1-n，代码里得偏移），此时nums[i]这个元素就是多余的，做一个特殊标记就行了，比如0或者-1，遍历中也要先ignore特殊值。于是missing numbers就是有特殊标记的那些，因为找不到值放在这些特殊位置上，说明这些值不存在。代码也简单，不多赘述。

同样，什么bitmap之类的都能做这个题，但cyclic sort可以O(n) and without extra space。

说代码简单，但也撞上错误了。主要是想节约空间，就直接拿nums[nums[i]]来swap，python swap a,b = b,a 也是有执行顺序的，nums[i]中途变了，最后结果反而是没有swap。很神奇。

algorithm - How swapping variables is implemented in Python? - Stack Overflow可以知道，a,b=b,a实际上是x1=a, x2=b,a=x2,b=x1，当然x1、x2是栈空间，还是需要auxiliary temporary locations。swap也没有magic。

不过还有一个点，就是swap这个写法，等式右边也是寻址才能拿到值，不是常量值，这里的规则是先把=右边算出来，详情见algorithm - python a,b = b,a implementation? How is it different from C++ swap function? - Stack Overflow。假设nums[i]值为v1，nums[nums[i]]值为v2，

nums[i], nums[nums[i]] = nums[nums[i]], nums[i]这一句会先拿出=右边的值，于是等价于nums[i], nums[nums[i]] = v2, v1。

然后这个时候才会真正找左边的地址，走x1，x2那一套交换。先找nums[i]，找到了，然后赋值v2，然后nums[nums[i]]就是nums[v2]，会把v1赋值给nums[v2]。

本来这个写法最多就是触发了错误的赋值，因为nums[v2]这个位置原本不应该参与进来。

但有趣的是，如果case比较巧合，碰上了v2==i，例如[2,1,0]，取i=0，nums[i]=2，v1=2，nums[nums[i]]=0，v2=0，这就给循环上了。于是nums[i]先被赋值为v2，也就是nums[0]=0(v2)，然后nums[v2]被赋值v1，也就是nums[0]=2，搞了半天，什么也没有变，nums[i]这个位置的值变了又变回来。

恰好我随便写的例子[4,3,2,1]完美符合。

而leetcode的case1 [4,3,2,7,8,2,3,1]，也会死循环。举例说明，第一次交换时用的4和7(idx 0和3)，即num[i], nums[nums[i]-1] = (7, 4)，nums[0]=7，nums[7-1]=4，而第二次交换就要num[i], nums[nums[i]-1] = (4, 7)，nums[0]=4, nums[4-1]=7，第三次交换则是num[i], num[nums[i]-1]=(7, 4)，然后无限循环。这么说肯定很难懂，可以自己推演四五次交换，就会发现，由于第一次交换，无脑地使num[7-1]=4，导致之后，nums[4-1]和nums[7-1]就都不会变了，永远是7和4。然后nums[i]也就是nums[0]不是赋值为7就是赋值为4。

如果用nums[i]=v1,nums[v1]=v2来表示，假设nums[v2]可以访问，第一次交换后，nums[i]的值就会v1、v2反复横跳，nums[v1]永远=v2，nums[v2]永远=v1，虽然是（从1次开始计数）奇数次给v2赋值，偶数次给v1赋值，但第2次交换开始，给v1、v2赋的值永远一样，看起来就是永远不变。leetcode case1并没有太特别，只需要nums[v2]可以访问，就能永远死循环下去。

总之，一旦python swap的时候值是嵌套定位的，就要小心，最好避免swap里有嵌套。

Find the Duplicate Number (medium) – LeetCode

这个题目grokking和leetcode的要求不一样，grokking是不允许额外空间，但可以修改输入数组。leetcode则是不能修改输入数组，并且只是用常数量的额外空间。

grokking的限制下，当然还是cyclic sort了，sort途中就能发现重复的那一个数（题目说只有一个，发现后立刻返回就行了）。

leetcode的限制下，就不一样了，最简单当然是set/hash存，但不满足额外空间的限制。不能简单求和，因为他不是保证1到n都出现，而是只限制在[1, n]范围内，而且虽然只有一个数重复出现，但它可以出现2次以上。没有预备知识，很难想到这个题目可以用二分查找或者链表来解，链表还好说点，二分查找这个方法真有点过绕了，而且复杂度也要到nlogn，纯属脑筋急转弯。。。

不过确实也是个思路，而且不能直接套用基础版的二分查找，需要一定的改动，就算没改动，也需要证明可行性。整理了一下，没什么特别的坑，很容易做出来。算法设计期间需要注意，[left, right]这个搜索范围能不能缩小，如果某些情况不能缩小，自然不能最后缩小为最终答案一个值。

• 链表方法解这道题

Find all Duplicate Numbers (medium) – LeetCode

这一题grokking和leetcode要求类似了，grokking不允许额外空间（一些临时变量的栈空间肯定是允许的，不然代码都写不了），也就是常数量级的空间了。

这题用cyclic sort很容易做。因为题目保证了数字最多出现2次，“出现2次”在cyclic sort框架里是可以判断的，比如规则写为“出现一次的就在对应的位置上，当又想swap该值到对应位置，就说明该值第二次出现，该位置记为-2”，当你读到-2的时候就说明i这个值出现了2次。出现更多次也可以以此类推。cyclic sort可以说是完美的，不论统计出现几次的值，都可以做到。

但包括这个题和之前的题目，都有另一种常见做法。本质上是hash算法，因为通过自定义的hash，我们能把原数组变成hash桶，原来的nums内每一个位置都是一个数值，hash以后，nums每一个位置i都表示“数值i”出现的情况（这个情况实际当然是数字，而且由于是原地修改nums数组，这个“情况”是编码后的样子，得对应解码才能得出真实信息。）核心就是“编码规则”。设想下，如果你不编码，假设遇到i位置上值为x，你改了nums[x]，并且不理会nums[x]原来位置的值，如果x大于i，你之后遍历到x位置时，就丢了这个数。所以必须编码，用一种方法，能够保留住原数值信息，同时也能存下这个位置i表示的数i出现了多少次。

最简单的做法就是+n+1，因为值最大到n，当你遍历数组时，发现i处的数值>n+1时，说明i值在前面出现过，而出现几次就相应+n+1，这样数值为x时，可以x//(n+1)得到出现次数，而x%(n+1)就可以得到i位置原始的数值，不会漏数。这就是一种编解码规则。

P.S. 也可以+n，当然，计算公式要跟着改变，[1,n]中如果取值n，求余就只能得到0了，所以值-1再求余，才可以。刚好，余数直接对应idx，+n+1的情况余数是真实数值，还得减一才能得到idx。

取反也是可以使用的编解码规则，出现一次就取反，但出现第二次还取反的话，就不行了，所以最多做到得出“出现两次”这个信息（都只能即时拿到，不能二次取反写入nums数组，这样跟一次没出现的情况就混在一次了），不可能辨别有没有出现第三次。

Problem Challenge 1 - Find the Corrupt Pair (easy)

1
2
3
4
5
6
7
8
9
10
11
12
13

We are given an unsorted array containing ‘n’ numbers taken from the range 1 to ‘n’. The array originally contained all the numbers from 1 to ‘n’, but due to a data error, one of the numbers got duplicated which also resulted in one number going missing. Find both these numbers.

Example 1:

Input: [3, 1, 2, 5, 2]
Output: [2, 4]
Explanation: '2' is duplicated and '4' is missing.

Example 2:

Input: [3, 1, 2, 3, 6, 4]
Output: [3, 5]
Explanation: '3' is duplicated and '5' is missing.

题目不难，还是满足cyclic sort，但if-else有点多，不太简洁。因为我没有当发现duplicate number后即时保存，而是标记为-2，missing number则是标记为0。这样的算法，覆盖面更广，如果有多个duplicate或者missing number，都可以被查出来。但这个题已经明确说了dup和missing都只有一个，所以可以更简化一点。

回归最简单的cyclic sort，拿example推演一下，如果发现了nums[i]想要换到的位置已经有了，这个时候dup就知道了，但是这一次要不要swap？

举例说明，[1,2,3,2]，当我们看到第二个2时，显然不能swap，会死循环。不swap，那怎么做呢？按前面的算法逻辑，就该把[i]这个位置标记为0或者什么。但这么做的话，又会增加if-else，因为下一次读[i]可能有0这个值了，必须单独考虑。

所以，再简单点，不swap，我也不操作了，就i+=1去搞下一个元素。这么做，是没问题的，很类似Find the Missing Number (easy)“n长的数组，是0到n这n+1个数缺了某个数”。Find the Missing Number (easy)的数组中可能有n，n是没办法交换到它应该在的位置的，所以放着就好了，它会在missing的那个位置上，或者整个数组都ok，n这个值就是missing的那一个。

再总结，例如[1,2,3,2]这个数组，我们忽略第二个2，那么数组最后的样子就是[1,2,3,2]，再次遍历数组，i为3时[i]!=i+1，说明了什么？说明这个地方应该出现的值没在，所以i+1是missing number，而[i]==2，说明2是多的那个，所以[i]是dup number。

最后，再理解一下，这个题目其实和Find the Missing Number一模一样，因为dup和missing number都是通过错误的那一个位置可以得到。

代码见 https://gist.github.com/vagetablechicken/31b210446ec55944cb490c658c3c6a04

Problem Challenge 2 - Find the Smallest Missing Positive Number (medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Given an unsorted array containing numbers, find the smallest missing positive number in it.

Example 1:

Input: [-3, 1, 5, 4, 2]
Output: 3
Explanation: The smallest missing positive number is '3'

Example 2:

Input: [3, -2, 0, 1, 2]
Output: 4

Example 3:

Input: [3, 2, 5, 1]
Output: 4

这个题目简单一想，就是cyclic sort，sort完后第一个nums[i]!=i+1的地方就是the smallest missing positive number。但是要注意到（就算没注意到，example 3也过不了），nums中可能会出现>len+1的数，cyclic sort时也没办法把这种数放到“正确的位置”。再细想一下，总共就len这么多个数字，如果真就[1,len]每个数字出现一次，smallest missing positive number自然就只能是len+1了。所以，smallest missing positive number的取值范围只可能是[1,len+1]，不会更大了。

Problem Challenge 3 - Find the First K Missing Positive Numbers (hard)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Given an unsorted array containing numbers and a number ‘k’, find the first ‘k’ missing positive numbers in the array.

Example 1:

Input: [3, -1, 4, 5, 5], k=3
Output: [1, 2, 6]
Explanation: The smallest missing positive numbers are 1, 2 and 6.

Example 2:

Input: [2, 3, 4], k=3
Output: [1, 5, 6]
Explanation: The smallest missing positive numbers are 1, 5 and 6.

Example 3:

Input: [-2, -3, 4], k=2
Output: [1, 2]
Explanation: The smallest missing positive numbers are 1 and 2.

看起来是挺简单的变种题目，但并不是。首先数组内元素没有限制，如果数组里存在>len的数，它是会影响结果的，不能直接忽略。

可以也先不管>len的数，但这样的结果就是，可以O(n)知道<=len的missing numbers，更大的missing numbers只能枚举，而且还得排除存在于nums数组里的，所以得有个set保存nums中存在的>len的数，每个数都要查一次是否存在，O(nlogn)。

这个>len的查询是省不掉的。参考答案里也是这个方法，简单朴实。

注意一下example1，因为它有重复的5和5，不能用最简单的

1
2
3
4
5

while i<len:
    if cond and nums[i] != i+1:
        swap
    else:
        i+=1

这么的话，经过几次swap，num[0]==5了，5想要被换到idx 4的地方，但恰好这里又是5，陷入死循环。

更好的逻辑是

1
2
3
4
5
6

while i<len:
    j = nums[i]-1
    if cond and nums[i] != nums[j]:
        swap
    else:
        i+=1

因为nums[i]==i+1时，j就等于i，指向的同一个位置i，[i]!=[j]就可以判断了，还避免了重复情况。

其他坑，例如要保证output个数为k个等等都比较好修复。

Grokking the Coding Interview: Patterns for Coding Questions

See Grokking Pattern 1.

6. Pattern In-place Reversal of a LinkedList

Reverse a LinkedList (easy)

1
2

Given the head of a Singly LinkedList, reverse the LinkedList.
 Write a function to return the new head of the reversed LinkedList.

反转的基本操作：两个指针，一前一后，改变后一节点的next指针，同时就会失去后一节点的原next，所以需要第三个指针，保住后一节点的原next。

再优化：由于每一次新的比较，都只需要两个指针，指向“后一节点的next节点”的指针是可以在此基础上再找到的，不需要一直追着。

遍历结束后，最后一个节点就是头节点，所以不需要别的额外的变量。

Reverse a Sub-list (medium)

1

Given the head of a LinkedList and two positions ‘p’ and ‘q’, reverse the LinkedList from position ‘p’ to ‘q’.

p,q是positions，也就是第几个元素。不是value，更不是直接的node地址。

Reverse every K-element Sub-list (medium) *

1
2
3

Given the head of a LinkedList and a number ‘k’, reverse every ‘k’ sized sub-list starting from the head.

If, in the end, you are left with a sub-list with less than ‘k’ elements, reverse it too.

首先看边界，因为末尾不足k的也翻转，所以可以无脑翻转。如果题目末尾变成不足k的不可以翻转（leetcode 原题），那么就得先数k，不到k个就退出，有k个再翻转，多了一次遍历，不过也是O(n)。

题目有些细节，但本质还是两个指针的事情，不难做对。不过我第一反应是不会改动初始链表的，但这一题如果加哨兵（一个dummy node接上链表head），会更简单点，不用在遍历while里写if判断是不是首次翻转，如果是首次，需要存下这个new head。（效率还是更高的，虽然不算太重要）

Problem Challenge 1 - Reverse alternating K-element Sub-list (medium)

1
2
3

Given the head of a LinkedList and a number ‘k’, reverse every alternating ‘k’ sized sub-list starting from the head.

If, in the end, you are left with a sub-list with less than ‘k’ elements, reverse it too.

Problem Challenge 2 - Rotate a LinkedList (medium)

推荐站点：

https://qoogle.top/xiaoxu-explaination-leetcode/

https://codetop.cc/

https://codetop.cc/ 微软

227. 基本计算器 II 2012/03/22-23

这道题，用栈是最快速的，可以现场推理思路，完成80%应该不是问题。
但这种表达式，很可能会被考变种，比如加了括号，加了UnaryOp，甚至更难。
括号，UnaryOp或是自定义函数，这几类还是可以通过少量修改代码支持。但要能做到像高级计算器一样的，抵抗各种灵活拷问，我目前知道的万能方法就是，编译器的基本思路，也就是词法-解析-翻译，这种流程。毕竟我们使用的编译器就是这个思路，没有比这个更完善的了。

当然，编译器思路不好写。总结来说，基本思路需要Lexer，Interpreter。如果Token过于复杂，最好加个Parser，Parser解析出AST，Interpreter再遍历AST树，计算结果。

面试时使用这个思路，写代码会慢一点，但是比栈思路，更深更硬核。

双栈思路

一个栈存操作符Op，一个栈存数字Int。双栈思路的核心就是“先算乘除”，所以扫描处理完整个表达式后，Op栈里应该只有加减号，没有乘除号。

但还有一个点要考虑，就是Op里已有+号，此时你扫描到了新的+号，要怎么做？

如果将栈中的+号及时处理了（也就是同优先级优先计算前面的符号），那么整个表达式算完，就只有一个加号或减号，没什么问题。

如果选择了加减号不先算，直接放栈里，就需要注意，之后的计算顺序。举例说明，一个复杂的表达式化简成只剩加减号时，可能是1-2-3，这时候Op栈是“-，-”，Int栈是“1，2，3”，不能再使用栈的pop，那样就变成了1-(2-3)，得用list/vector的顺序计算。
（我临时推理时用了这个思路，大概率以后还会这么干😅。我习惯思维是只push进栈，不爱随时pop，最后会统一pop出来计算。大概是觉得这种流程，代码会比较好看。）

还是推荐大家尽量改善自己的思路，选择第一种方式，以免现场推理出来的逻辑不够完备。

单栈

Leetcode官方题解其实是单栈，但如果你亲手写了双栈，你一定会感受到，如果及时计算同优先级的运算符，Op栈最多只会有一个运算符（+/-号），所以不需要栈，一个变量就能保存了。这就是单栈思路，没什么特别。

边界

栈的大体思路都是如此，如果加入括号或是其他二元运算符，都还能work。加入括号的话，请一定要用第一种方式😂，处理起来方便很多，不然思路容易卡住。

如果加入UnaryOp正负号，尤其是负号，也就是说leetcode 227题的表达式中的整数不保证是非负整数，又需要一次变化。巧妙的思路是给“-”打头的表达式开头添“0”，变成“0-正整数”。将所有”(-“替换为”(0-“，用字符串replace，还可以不用改变算法主体代码，很简单。
而如果还加正号，比如“3++4”合理，这种情况就比有负数的情况还要麻烦了。这要求你的算法能，判断第二个+号是和整数结合的正号（Unary Plus）。再扩展下，“3–++2”等等。代码上就得增加一段逻辑，来处理好UnaryOp。这样当然可以work，但是这也暴露了栈思路的一个问题，就是它没有符合逻辑的解析能力。它似乎只是我们在努力的修补规则，“3–++2”是读取了“3-”后发现还是符号，才会开始解释为一元符号，从左到右计算到底是正号还是负号。但按照逻辑，我们应该是将表达式看作3-(-(+(+(2))))，也就是，真的计算的时刻，2是和前面的正负号结合，然后作为整体又跟前面的正负号结合。也就是解析是顺序，计算是倒序，有种递归下降，然后逐层返回结果的感觉。

其实没什么差别，但是我个人觉得，栈的思路是有些勉强的。因此，当学了一点点编译原理后，我就想用编译的思路来解决这道题了。

TODO

所有计算器题目，都总结下。

224. 双栈，加减括号，注意允许(+4)这种写法出现，但不用考虑1++2。

225. 双栈，加减乘除，无括号，不用考虑(+4)或一元运算符的情况。

226. 基本计算器 IV，只可能使用编译器思路来解决了，而且还要能处理变量。

编译器思路

编译器思路，自然是难的，写起来也不够快。但是学习编译器基本原理，我觉得是有意义的，因为底层到程序编译，稍高层的SQL解析，都是这套思路。Parser，Token，blabla。

• 细节，新开一页讲，也可看https://ruslanspivak.com/lsbasi-part1/ 一步一步跟着做

简单来说，就是用代码实现几行范式。加入新的符号，就修改范式。

比如，只有加减乘除：

加入括号(LPAREN,RPAREN)：

再加入一元运算符（正负号）：

Parser/Interpreter实现这几条规则就可以了。

91. 解码方法 2021/03/24-25

需要注意dp访问越界的问题。
通常dp[i]负责看第i个元素（索引其实是i-1），就可以保护住需要访问dp[i-1]的dp公式，因为计算dp数组是i从1开始，dp[0]不会越界。
如果dp公式有dp[i-2]，不要慌，dp[1]特殊处理后，dp[2]开始又可以通用处理了。

124. 二叉树中的最大路径和 2021/03/26

• wait zx

224. Basic Calculator 2021/03/31-04/03

s consists of digits, ‘+’, ‘-‘, ‘(‘, ‘)’, and ‘ ‘.

227类型的题。这个版本由于没有乘除，用Lexer+Interpreter的版本，范式也不难写。

• TODO 写一下范式

当然更简单的，还是可以使用双栈。

而且建议只记忆双栈，不用去记一些扩展性不够高的思路。

注意，test case有”1-(+1+1)”这种。虽然不用考虑1+-1这种写法，但’(‘号后跟’+/-‘号是要被考虑的。
因此是基本的双栈思路，加过滤空格，再加处理’(+/-‘。

具体说下双栈思路。

首先，框架是逐个字符扫描，但考虑到数字可能是多位，所以最方便的做法应该是while i < len(s):，解析数字时i可能会多加点，其他符号只需+1。

再是每个字符c可能是些什么，各自需要如何处理。如果没什么印象，建议逐个分析，有需要的再合并，想不清楚，直接逐个if-else都行，总比写错了强。
所以，逐个看待，伪代码写作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

if c is space:
    pass
elif c is digit:
    # func parse_int TODO
    num = parse_int()
    # TODO calc or push to nums?
elif c is '(':
    # TODO handle '(+/-'
    push to ops queue
elif c is ')':
    # ops top is '('
    ops pop
    num = nums.pop()
    # TODO calc or push to nums?
elif c is '+' or '-':
    push to nums queue

上面就是最详细的分支情况，由于没有乘除，所以分支数量也没什么可以优化的点。注意我写的TODO，基本都应该封装为一个函数，以免主逻辑太难读，给自己增加难度。

特别的，calc or push to nums是最需要注意的一个地方，明显的，两个分支都用到这一逻辑，封成函数是最好的，我命名为calc_with()。

而这个数什么时候用来计算，什么时候直接push进栈呢？

举例分析，我想把nums栈顶top和现有的num拿来计算，那么ops栈顶当然得是+/-号，如果栈顶是’(‘，那自然不该算。只需要考虑这一个条件。

如果不计算，直接push。如果pop栈顶计算了一次，之后的结果，该如何处理？

很容易想到，这个结果，还是应该push进栈。但还是应该多思考一下，有没有什么坑？

这一点可能有点不直观，但你可以手写推理或者debug代码测试，就会知道，calc_with()总是在尽力地合并，只有遇到’(‘才会无法合并，导致nums和ops栈多增一个元素。

简单起见，假设只有+号没有-号，某个时刻的栈只能是+(+((+，不会有++(++(++。

假设此时ops栈为+(+((+,现有num，ops栈pop出+号，再nums栈里pop一个数num1，计算出结果res，这个res push回nums栈是合理的。无论后面跟什么符号，都能正确处理。

770. 基本计算器 IV

这个题太长了，看的人头皮发麻。但是抽象一下，就能发现，它实际上难点在于括号展开。因为我们已有的知识已经能把一个有括号的表达式解析出来了，可以转成AST树，也可以在解析parse时及时计算。但是，没有包含过“括号展开”的逻辑。

简单的想一下，AST树完全不知道该怎么去实现括号的展开，所以pass。

所以就考虑下parse时及时计算的时候能不能加上“括号展开”。

parse时，可以知道pre_calc * new term的，具体2 * (a-b)，new term为(a-b)，之前的计算结果为2（简单起见，用数字举例）。

接下来，该怎么做？

应该做到拆出2 * a-2 * b。这一步即括号展开，是此题的核心。题目也暗示了可以理解为2 * a与-2 * b两项，那么也就是2要跟（1 * a)和(-1 * b)都分别乘一下。代码上其实就是for循环。当然(a-b)这个factor得拆成一个数组（2个元素，a和-b）。还需要拆成系数和word，那系数和word怎么对上号呢？

考虑到2 * a + 1 * a能合并为3 * a，主要功劳是在word上，所以以word为key，系数为value是很合适的。

所以可以用dict，{a: 1, b: -1}这样来表示。

再进一步完善，如果是(c * d - 2 * f) * (a - b)，那pre_calc，即(c * d - 2 * f)，也得用dict来表示。其实pre_calc没有什么特别，就是一个factor，无论是一个数，还是圆括号扩起来的长表达式。所以用一样的规则，{c*d: 1, f: -2}，很通用，也合理。

整理思路

• TODO 写出范式

也就是说，每个factor（不可再拆分的元素）都可以用一组kv来表示，也就是一个dict。一个term是多个dict合并，最终可以得到1个dict（遍历所有dict，体现加法，因为负号作为系数去了，所以可以当作只有加法）。

term和term之间的乘法，也就是dict和dict组合出一个新的dict（二维for循环，体现乘法）。从左到右一个一个组合，最后得到一个dict，即为最后结果。

剑指 Offer 40. 最小的k个数

TopK，面试时也遇到过，我认为heap K最稳定，但面试官更希望我用快排思想，虽然快排思想有一定几率会很慢–最坏O(n^2)。除了复杂度，实际运行，由于现代计算机架构，inner loop可以很快，见wiki。具体的复杂度算法也可以看wiki。不要仅考虑理论复杂度。

不过有个点，我也不知道是不是记错了，面试官当时可能说c++ stl的paritial_sort是快排思想，但实际paritial_sort就是先构建k大小的堆，然后把剩下的都和堆顶比。nth_element才是快排的思路。

核心快排思路见 Quick Sort。

最小k个、最大k个，第k大，第k小问题底层都是一样的，快排，变换一下都可以变为“左边<=，pivot，右边>=”这样的格式。类似golang或stl里，pred作为参数传入。

Bookmarks

C & Go 对照表：https://hyperpolyglot.org/c

vim等使用方法快查：https://hyperpolyglot.org/text-mode-editors

JAVA String Charset

JAVA的String使用上一般不会考虑到编码字符集的问题，即encode charset。但如果出现数据交互，就需要考虑了，因为不同环境就可能存在差别。如果编码对不上，可能会出现乱码。JAVA中我经常见到的是?乱码（多个问号），不排除其他可能。

An Example

host A用utf-8编码String，以byte[]形式发送到host B，如果host B只简单的用

1

new String(receivedBytes)

来转成String使用，这里使用的charset就是default charset。

The Java platform depends heavily on a property called the default charset. The Java Virtual Machine (JVM) determines the default charset during start-up.

可以用下面的方法测试出当前平台的default charset。

1

Charset.defaultCharset().displayName();

我个人的jvm default charset是US-ASCII，所以不设置String的charset就出现乱码。

解决方法

1. new String时指定charset
2. 修改JVM的default charset，方法自行搜索

Further

即使String的编码正确了，也不代表console output或output file就不会乱码。涉及了多个模块，可能需要更多的配置，请随机应变。

Hexo

Hexo的创建使用不多赘述。注意，先搞清楚hexo是否满足书写要求，可能你需要的是sphinx。

With github

Hexo通过hexo d来发布到github，因此github中deploy到的分支是网站目录。也就是deploy后在本地可以看到的.deloy_git。
我个人使用了另一个branch来保存hexo项目的原始文件，也就是_config.yml配置，md文档等等。

Q&A

名字解释：
<root>: 指的网页根目录，或者说是hexo deploy到的repo分支根目录。

Q: 遇到网站repo中路径是存在的，比如<root>/categories/index.html确实存在，但是浏览器点击却是404？
A: 可以自行访问尝试下<root>/categories/或者全路径，看看index.html是不是有问题。如果这样就能访问到正常页面，那么问题大概就是缓存了。你可以换个浏览器快速检查下，或清除该页面缓存重试下。

附赠-chrome清除单个页面缓存

chrome的开发者工具-setting中Network-Disable cache(while DevTools is open)，此选项打开后，在你想要调试的页面，打开开发者工具，就不会出现一些奇怪的缓存现象了。

Hexo cmds

1
2
3
4
5
6
7
8
9

npm install -g hexo-cli
cd <blog-source>
npm install
# if ERROR Package xxx is not installed
npm install xxx

hexo new draft <draft_name> # just the name, no .md
# writing, writing, ...
hexo publish <draft_name>

1

hexo clean && hexo d

If you want to delete a post, just delete it in the source folder.

Localhost debug way:

1

hexo s --debug

Hexo writing

link to another post

Ref Include Posts.

1

{% post_link 要跳转文章md文件名(不要后缀) %}

pics

hexo默认的图片格式不是markdown的语法，想要写md时预览，可能需要vscode安装插件Hexo Utils。
但有个方法可以继续用md的image格式（https://hexo.io/docs/asset-folders#Embedding-an-image-using-markdown）：

1
2

npm i --save hexo-renderer-marked
npm i --save hexo-asset-link

然后确保_config.yml中有（一般都有）：

1
2
3
4

post_asset_folder: true
marked:
  prependRoot: true
  postAsset: true

NPM install

如果apt install npm遇到gcc update-alternatives slave问题，就先把update-alternatives清理了，再添加也方便，清除参考写法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# cleanup
update-alternatives --remove-all gcc
# set one g++
update-alternatives --install /usr/bin/g++ g++ /usr/bin/g++-9 10
# recover
update-alternatives --remove-all cc
update-alternatives --remove-all c++
update-alternatives --remove-all gcc 
update-alternatives --remove-all g++
update-alternatives --remove-all clang
update-alternatives --remove-all clang++
update-alternatives --remove-all icc
update-alternatives --remove-all icc++
update-alternatives --install /usr/bin/gcc gcc /usr/bin/gcc-8 80 --slave /usr/bin/g++ g++ /usr/bin/g++-8 --slave /usr/bin/gcov gcov /usr/bin/gcov-8 --slave /usr/bin/c++ c++ /usr/bin/g++

slave有个好处是不怕个别版本被修改，还是建议维持这个样子。

但ubuntu版本早的话，node.js版本可能太低了，hexo没法用，报错：

1
2

TypeError: line.matchAll is not a function
       at res.value.res.value.split.map.line (/root/vagetablechicken.github.io/node_modules/hexo-util/lib/highlight.js:121:26

比如，我ubuntu20.04装的node就是10.19.0，需要12及以上的。
升级：

1
2
3

sudo apt -y install curl dirmngr apt-transport-https lsb-release ca-certificates
curl -sL https://deb.nodesource.com/setup_12.x | sudo -E bash -
sudo apt -y install nodejs

hexo version可以查到相关version。

然后又可能遇到npm rebuild node-sass很慢的问题，卡在github上下载node-sass了。可以换下源试试，npm i node-sass --sass_binary_site=https://npm.taobao.org/mirrors/node-sass/。socks5代理会hang up，不知道是不是暂时的不稳定。

node版本再升高，https://github.com/nodesource/distributions#debian-and-ubuntu-based-distributions 。

hexo-renderer-sass有点旧，node版本高了不行，升高sass版本就没有问题了。

我想要个block admonition，但没有插件能做到解析’{note}‘这种。只能改用现有语法，缺陷是vscode没法preview，只能deploy/server后看效果。最终还是决定使用hexo next主题自带的。preview的问题不大，用的频率不会太多。
切换sphinx有点麻烦，hexo配reStructuredText插件，例如hexo-renderer-pandoc，没成功，据说这个插件也比较大，deploy会慢。

Next Dark

@media (prefers-color-scheme: dark) {}删了，只保留内层。否则，会考察OS或浏览器的主题，可能不能dark，强制弄黑，保护眼睛。