#Algo

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

Quick Sort

快速排序

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

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

单循环思路

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

  1. 单次循环,又每个元素都得参与比较,所以for循环肯定是[l, r-1] 或者[l+1, r]的。
  2. pivot选最右的那一个,这样可以直接利用range左闭右开的性质。(这里很容易想成最左作为pivot,然后就会陷入pivot的空洞怎么swap的疑惑里。注意只要想不要交换空洞就好了。也就是如果最左为pivot,那也是从l+1开始才会有交换。)
  3. 遍历用i,那么还得有个标号j来表示[left, j]区间都是<=pivot的,初始可以j = left - 1,表示此时还没有能保证<=pivot的数,每次都先++再交换(不然就动了left-1的数了,也不可能)。划重点,[left, j]闭区间都是<=pivot的。
  4. 什么时候交换?可以看到<=pivot的空间要增大,那么[i]<=pivot时,就应该挪到前面去。为什么不是 < pivot才交换?其实都可以😂,例如这个题解就是用的小于做判断。j先++再i、j交换,j++后的值可能是已经被访问过的>pivot的,也可能是i自身,但都ok,>pivot的放后面不会错,自己跟自己交换也不会错。极端情况就是pivot就是最大的值,一路访问过来,到r-1的位置都不会实际交换。
  5. 最后结果是i访问完了,没有什么指示性。j则肯定代表点什么。j位置必然是<= pivot的,那j本身肯定不能跟pivot交换,不能把小于等于pivot的换到尾部吧。所以应该是j+1。

判断条件用 <= 或 < 应该都可以,oj上也没测出问题来。

单mark重点在于保证mark左边都是<=piv的,所以初始时mark可以是-1,意味着还没有保证任何元素<=piv。保证左边,那pi当然没理由在左边找,游标到pi位置时怎么整,还得折磨一番。所以pi选最右。自然游标从left到right-1就好了,不用看最右这个right(也是pi)。循环结束后,pi这个位子的piv是==piv的,完全可以又交换到左边(被交换到最右的那个值必然是>piv的,合理),成为一个分界点。

3 while思路

3 while思路,推荐在陈斌老师的写法上改进一点点,一点点就可以。重点就是双mark由于写法过长容易产生的坑。

首先看基础思路:

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

而游标停下来有几种情况?因为我们涉及交换,所以可以想想离得近的情况,比如lmark+1=rmark,或lmark==rmark。第一个相邻好说,你都停下来了,必然是lmark的数> piv,rmark的数< piv,它们需要交换,正常进行。而lmark==rmark这是不可能的,因为一个数它跟piv比只有三种情况,而三种情况,两个游标都不可能同时停下,必然有人要跨过去,所以安全。内层双while结束时,很可能有lmark>rmark的(不会有==,当然,如果有保护机制,可能影响)。那我们就应该在lmark>rmark时终止,==不应该存在(甚至可以assert看看),也别去记它,干扰思路。反正lmark>rmark时不能交换,交换前也要判断这一情况,所以可以外层True,内层break(陈斌老师用的done变量,没必要)。重点记忆,“交错”(lmark>rmark)就停止

外层while也跳出后,是个什么样子?lmark>rmark了,piv该放哪儿,和左还是右交换?由于piv是拿的最左边,交换到最左边的当然应该是<=piv的,所以拿rmark是ok的。rmark已经在lmark左边了,它必然指向了<=piv的值,没必要用lmark做更多的处理。那么交换一下rmark和pi(最左)就ok了

所以partition初步的伪代码为:

1
2
3
4
5
6
7
while True:
while … and [lmark]<=piv: lmark++
while … and [rmark]>=piv: rmark--
if lmark > rmark:
break
exchange
exhange rmark and left

现在还需要加保护。比如piv刚好是最小的值,lmark能一直走穿,partition函数如果只对局部数组做,还可能踩到错误地方。lmark可以<=right(当前partition输入数组的最右),也可以<=rmark,因为lmark>rmark就会退出循环了,不需要让它继续发展。所以推荐rmark。那rmark也一样,只要交错就可以退了,不需要用最左边当边界,所以rmark>=lmark就行了。需要有==,不然就保护太过了,不可能出现游标交错。

可以理解为,核心是“交错”,交错就停止,只要不交错,3 while都可以继续

1
2
3
4
5
6
7
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

二叉树遍历

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

中序遍历

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

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

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

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

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

伪代码写作:

1
2
3
4
5
6
7
8
9
10
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往左走就行了,所以只需存右子,且是先进后出。用简单例子演示一遍也可以知道,伪代码可以写作:

1
2
3
4
5
6
7
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/

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.

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)

Grokking the Coding Interview: Patterns for Coding Questions

课程原地址

题目目录与答案 Python版——完整题目目录,包含challenge。

题目目录与答案 C++版(附题目OJ的地址)——推荐用OJ测试自己的算法,但是这个repo里基本没有challenge题目。

1. Pattern: Sliding Window

Maximum Sum Subarray of Size K (easy) – GeeksforGeeks

k长的连续子序列,使该子序列和最大,这个和为output。
窗口长度都固定了,只需在遍历一遍时加后一个减前一个就行了,O(n)。

Smallest Subarray with a given sum (medium) – LeetCode

注意读题,nums都是正整数,target也是正整数。这个条件大概率需要用到。

假设有一段连续子序列了,它已经>=target了,就不需要再继续加入元素了(序列外右边第一个元素),因为再加的话size就变大了。而这个size可以向右横移一格,可以立马算出新的sum(这里很节约时间,降低算法复杂度)。

这个sum如果 >= target,那么它就有机会再小一点,而这一次需要的是减去序列内的第一个元素,可以理解为“收缩窗口”。
这个sum如果 < target,那就可以再向右横移了,因为size扩大,对结果没有任何帮助。

总体看下来,只要横移和收缩,算法复杂度是O(n)。

初步思路

初步思路是,先算个nums[0…x]之和 >= target的窗口,然后这个窗口开始向右移并尝试收缩。但其实不对,因为第一个窗口,不是非得从第0个元素开始,这个窗口自身就应该尝试收缩。这个逻辑补上后是能ac的。
不过,初步思路翻译为代码,还是有些小坑,肉眼很难查。建议背一个滑动窗口模板。

滑动窗口模板思路

此思路最核心的思想就是,不强求窗口横移,反正先向右扩展1个,再左边收缩一个,就达到了横移。
因此滑动窗口的头尾都可以移动,而且是分别移动,用两个变量来表示,(start,end)。
因为收缩(start向右移)和扩展(end向右移)可以各做各的,所以没必要先找到一个总和 >= target的初始窗口了。

所以,步骤可以化简为,每一次都扩展1下,然后尽力收缩(while不定次收缩)。

1
2
3
4
5
6
7
while end < n:
tmp_sum += nums[end]
while tmp_sum >= target:
win_size = min(win_size, end-start+1)
tmp_sum -= nums[start]
start += 1
end += 1

至于几个变量的初始值,现场推理一下也可以得到,不做赘述。
P.S. win_size没必要用int的max,用len(nums)+1就可以了,反正都是不可能的值。

补充

滑动窗口的算法,nums就算有负数也无所谓。(被烟雾弹迷惑🐶)这个条件大概是为“前缀和”这一方法准备的。

前缀和方法,简单来讲就是nums[0..i]之和组成一个sum数组,这个数组严格递增,都不存在相等的元素。

然后就可以用二分来找了(看到有序就要想到二分),当前sum[i]为0到i元素的和,sum[j] - sum[i] >= target转换为sum[j]>=target+sum[i],那么就是在sum数组里找target+sum[i]的lower bound。

为什么不是以j为结尾,sum[j] - sum[x] >= target转换成sum[x] <= sum[j]-target,找sum[x]呢?因为是upper bound(第一个>某值的元素)的前一个(必定<=某值),不如直接找lower bound简洁,而且不用处理减出负数的情况。

Longest Substring with K Distinct Characters (medium, google) – LintCode

Given a string, find the length of the longest substring in it with no more than K distinct characters.

也就是LeetCode340题 Longest Substring at Most K Distinct Characters。

这道题输出是最长子串的长度,所以显然可以套用滑动窗口的模板。和上一个题目一样,都是扩展会使得条件不符,要通过收缩来满足条件。
即,窗口扩展一旦字符种类超过k,就可以通过窗口收缩来削减字符种类。
唯一不同的点是:update longest string的时机(其实就是用end-start+1来尝试更新记录的longest)
因为while distinct_count(dict) > k时是去收缩,break while时说明distinct_count(dict) 已经<=k了,这个时候的[start, end]才是一个可能解,符合条件的可能解。
所以update longest string len是在while循环外,而且是之后。
至于如何实现dict和distinct_count,随便吧,简单也好,高效也好。

P.S.注意到了吗,这个题目和前面一题Smallest Subarray的区别?

看不出来也正常,我做了几道题才突然回头发现的😂而且明明之前做过笔记,重蹈覆撤🙄️

果然人类的本质都是复读机

这个题已经开始了longest之路,也就是说,只是想求一个最长的长度,根本不在意“重复无意义的更新”。

按之前的模板,此题的伪代码应写为:

1
2
3
4
5
6
7
8
9
while end < n:
dic[s[end]]+=1
while len(dic)>k:
dic[s[start]]-=1
if dic[s[start]]==0:
del dic[s[start]]
start+=1
longest = max(longest, end-start+1)
end+=1

这样的写法,保证了longest变量更新时,当前窗口都是len(dic)<=k的,也就是合法的情况。但确实可能会出现窗口被收缩的很小的时候(为了合法),此时max更新也是白干的(longest还是原值)。

而如果代码将内层while变为if:

1
2
3
4
5
6
7
8
9
while end < n:
dic[s[end]]+=1
if len(dic)>k:
dic[s[start]]-=1
if dic[s[start]]==0:
del dic[s[start]]
start+=1
longest = max(longest, end-start+1)
end+=1

自然,在longest更新时,当前窗口可能都还满足条件,不合法,但仍旧去做了一次longest的更新。但从数值上来讲,由于不满足条件会被收缩一次,加上前面的end扩展一次,窗口等于做了一次平移。那么end=start+1的值就不会变大,longest的更新自然也是不会有实际作用的。

这一个改动,它到底好在了哪里呢?光看经过,start,end两个游标都是单向前进的,2-while和while-if都不会使两个游标左右飘。但由于2-while会保证每次窗口都是合法的,和while-if相比,start这个游标可能会更靠右。举个极端例子,如果longest是[0, n-2]这个窗口,下一次扩展end就会到末尾n-1,while-if此时发现窗口不合法,收缩一次,就溜了。而2-while,会愣是要求[start, n-1]窗口合法,可能start从0不断右移,直到n-1才停止。无用操作在这个例子就占了一半。具体例子就是AAAAB, k =1。

这个优化并不容易读,我也不建议平时代码搞这么tricky。在这个题目里,仅仅在节省len查询和dict更新,都是较高效的操作,而且有次数上限(由于start标最多都走到末尾,操作次数最多n次)。优化效果仅仅锦上添花。但这个将while改为if,在其他题目中可能有奇效。因为while的判断条件如果复杂度较高,这里的收益就很大了,见Longest Substring with Same Letters after Replacement一题。

Fruits into Baskets (medium) – LeetCode

跟上题一模一样。题目暗示着连续区间,就可以尝试滑动窗口方法。

但这一题case比上一题的规模大,最简单的dict实现(不及时删除value为0的项,每次都要遍历得到distinct count)这种方法就超时了。还是推荐及时删除value为0的项,其实比不删还简单,因为删除这个操作只会在收缩时出现(只有此处count–)。

可优化为while-if。

No-repeat Substring (medium) – LeetCode

和前面的题目毫无差别。

但注意第二层while的判断条件是什么,如果判断条件是“窗口dict的value全为1”,那么你可以改出while-if。

如果是“当前字符c的count>1”,就改不了了。因为现在只看当前字符,那就意味着窗口必须是合法的,然后扩展,加入当前字符。while-if便不可用。

“只看当前字符”这种方法的优化思路是,如果start要跳,直接让start去“当前字符上一次出现的位置的右边”。 因为前面的字符都可以跳过了。还可以再化简代码,但会很难读,所以还是适合而止吧。

Longest Substring with Same Letters after Replacement (medium, amazon) – GeeksforGeeks

We have a string s of length n, which consist only UPPERCASE characters and we have a number k (always less than n and greater than 0). We can make at most k changes in our string such that we can get a sub-string of maximum length which have all same characters.

Example 1:

1
2
3
Input: s = "ABAB", k = 2
Output: 4
Explanation: Change 2 'B' into 'A'.

Example:

1
2
3
Input: s = "ABCD", k = 1
Output: 2
Explanation: Change one 'B' into 'A'.

这种要替换字符的题目,往往不用真的替换,只要数值上达到某个条件就行了。比如这个题,不用想着应该替换哪些字符,而应该想“总字符个数 - 不需要被替换的字符个数 >= k”就行了。很容易想到,“不需要被替换的字符个数”就是区间内个数最多的那个字符,这样,总字符数才能多一点(对某个区间而言,不需要理会那些无意义的可能解,“保留频率最高的字符,把其他的替换为该字符”肯定是操作数最少的)。于是,替不替换的问题就化简为简单的统计问题。

统计问题虽然简单,但是复杂度略高。想要快速,可能需要两个map,ch->count, count->ch。所以,while-if就很适合了,由于只收缩一次,max_count就从dict里统计一次就好了,不用强求更快速。

Longest Subarray with Ones after Replacement (medium) – GeeksforGeeks

比上题更简单,只需要一个int变量就能描述一个窗口内的0的个数。

Problem Challenge 1 - Permutation in a String (hard)

排列,不允许多一个字符,所以窗口大小是固定的,滑动用来节省“更新窗口属性的代价”。题目如果对字符多加限制,比如此题限制只有小写字母,也就只有26个可能,其实描述窗口用长26的数组都可以,不用非要用counter。用counter有个麻烦点在于当某个字符的count为0时,你需要删掉它,不然就没法和s1的counter比大小。如果两个字符串的counter都先把26个字母的空间开出来,那还不如数组节省空间。

Problem Challenge 2 - String Anagrams (hard)

和challenge1没有区别

Problem Challenge 3 - Smallest Window containing Substring (hard) *

没啥特别,就是用collections.Counter()减法,比自己写的比较函数要慢不少,1200ms vs 500ms。

Problem Challenge 4 - Words Concatenation (hard)

注意读题!words长度相同!匆忙读题后,我还以为要处理不同的切割方式,以为会出现“一个substring里有几种正确的word排列”。那这题可能不止hard了。

可以简单想到的办法就是窗口从0一直滑到尾,step为1,每一次窗口都得重新计算下word-count,然后和words参数比较。

显然这个没有什么巧妙点,没有节约计算量,所以想要利用滑动窗口,当然得想点骚方法。其实就是,每一次都设置一个起点,从这个起点开始,只会按词长来拓展,这样就能像字符型的题目一样,充分利用滑动窗口的扩展收缩,减少计算。举例说明,就是一个单词长度为len,s串总长为n的话,第一趟是从0开始一个len切一刀,这样切割后的串扩展和收缩都是一个词的,第二趟就是从1开始切,以此类推,最后一次是len-1开始切。可以想到,这样也是把所有可能性都考虑到了。

改进后的滑动窗口方法效果是明显的,1000ms到100ms。

Additional

Sliding Window Maximum (hard) – LeetCode

这个题跟滑动窗口模板毫无关系,窗口大小都固定牢了。唯一的问题点在于用什么结构体来提炼窗口信息,既能很快查到最大值,又能在窗口滑动时很快更新好(滑动本质就是加入一个数,去掉一个数)。快速查到最大值,可以想到利用堆。但是堆有一个明显问题,就是它不适合去删除内部的某个元素(不是堆首)。而“去掉一个数”这个操作很可能就是去删除某个中间的值。堆的删除操作是个不太ok的操作,因为这个堆是简单的堆(并非压平了看,完全有序的,不是堆排序之后的结果),也就是删除操作不能快速定位到要删除的元素。

但是别直接放弃堆(我就放弃了,想别的方法,走远了)。这时候,尝试多推导一下,就会发现,不用着急删除元素。因为元素可以跟上自己的位置idx,如果堆顶拿到的idx已经不在窗口内,再删除也不迟。也就是延迟了删除操作,正好还让删除操作符合堆的操作习惯,只删堆顶。

到这里,起码算是题目做出来了,而且这个方法也不差,能交差。

但这道题更想考的点是别的,所以还需要再优化。说是优化,不如说是换了解法。从堆想到单调队列,反正我是做不到。。。

单调队列是什么东西?先记住它能够动态地维护定长序列中的最值。所以只要定长、最值,就可以想到尝试单调队列。具体来讲,单调队列是,push元素前会把前面的元素都从后往前访问一遍(遇到比自己大的停止),比当前元素小的都删除,再将元素放在队尾。其实,全访问也没关系,最后结果没有差别,不过,遇到比自己大的就停止可以节省点时间。最后的结果就是队列里头到尾是从大到小有序的。

举例说明(为了多点情况,和leetcode原例子有差别):

1
nums = [1,3,-1,-3,-2,3,6,7], k = 3

单调队列应该长什么样?

[1,3,-1]初始窗口入队列后,q=[3,-1],那么这个窗口的最值就是3;

[3,-1,-3], q=[3,-1,-3],最值还是3;

[-1,-3,-2], q=[3,-1,-2],最值3,但3已经不在窗口内,所以pop,q=[-1,-2],最值-1;

[-3,-2,3], q=[3],最值3;

[5,3,6], q=[6],最值6;

[3,6,7], q=[7],最值7。

可以看到,只用进行简单比较,就能维持着最值,比堆的时间复杂度低。

单调队列它为什么做到了呢?

可以这么想,首先简单起见,只考虑窗口内元素的单调队列情况,比如3,1,2序列,k=3,很明显1会在2进入时被扔掉,因为2进入了之后,怎么也是2比1晚出窗口,就算可能是最大值,也是2可能,1是完全没有可能竞争最大值的。

再考虑队列前部还有窗口外元素的情况,窗口外的元素还留在队列里(可以称为过期元素),也就是说窗口内的单调队列最大值(也就是队列列首)比过期元素小。但这并不影响窗口元素那部分的选择,无论有没有过期元素,窗口那部分的单调队列都长一个样。所以过期元素可以简单地pop出来扔掉。

总的来说,单调队列就是剔除了“必然不能争最大值”的那部分无用值。单调队列实现上没有什么难度,不再赘述。

P.S. Python实现遇到超时问题,因为我没有用pop,而是选择到一个点,取出切片[:x],然后又append。具体细节待调查。从耗时来看,很明显这一连串操作应该搞出了deep copy之类的耗时操作。都叫单调队列了,就好好用python collections里的deque。

Shortest Subarray with Sum at Least K (hard) – LeetCode

仔细读题,这个题的数组里有负数。滑动窗口的算法模板是没办法直接套用的,因为窗口收缩的停止条件是sum < k,由于有负数,你不能在窗口sum < k时停止,你必须继续收缩,否则就可能错过解。

停留在滑动窗口算法模板这个框架里,是没办法找到解法的。

这时候只能躺平

只能说先回答个O(n^2)的解法吧,聊胜于无。很明显,所有区间和都是可能的最佳答案,所以前缀和加二级遍历所有区间,能得到答案。

当然可以优化,但是很难凭空想出来参考答案“单调队列”。接下来的说明是以知道“前缀和+单调队列是较好解法”为前提来看这个题目,所以没有什么顺理成章推导,全凭参考答案提示。

单调队列维护什么?

题目核心是求最短的合法子串,所以短是最核心的,和只要>=k什么都行。那么假设当前看i,以i开头的最佳子串,当然是从i开始寻找第一个j,能使sum[i..j]>k(前缀和数组里两个数减一下就好了)。j之后的都不用找了,没有比i到j更短的了。那么反过来思考,从i到j,中间可能有多个值,一一遍历就是暴力解法,优化当然是更快找到j,那么如何迅速定位到j呢?

或者换个说法,i到j中间的多个可能性,有哪些是必然不可能的,可以直接过滤?答案是没得😛。因为如果从[i, n)区间提取出单调递增的部分,可以使用二分,但这个题应该用不着。那这个思路还有什么优势呢?我们一一遍历到j,然后得到这个i的最优解,然后i++,然后你还是得遍历过去,因为单调递增队列本身不能有更多的改动,最多把队列头比i小的pop出来。那换个角度,递增队列是不是能从后往前看,当某个靠后的j满足了条件,你能把它怎么样?你不能动它,因为接下来的i(更大的i)和j一起也能满足条件,这个窗口长度肯定比现在的短,你删了这个j,就丢掉了解。

那么就应该考虑换个顺序,以当前j为标杆,去找前面的i,它有个什么好处呢?当你从前往后找i,某个i满足条件后,你可以大胆删了它,因为j会++,当前的i充分发挥价值(用来更新window len)后,就不需要了,后面的j和这个i组合是无意义的。

P.S. 我想到了以j找i,但又想的是从j-1往0这个方向找,想想看,跟以i找j没什么差别,它们跟暴力解法比,完全不是稳定降低复杂度,甚至可以劣到没区别。(于是Python实现也完美超时了)

总的看“前缀和+单调队列”,大概的最好状态是每次O(1),然后n个j,所以O(n),比如,每次看队列头d[0]的preSum都很大,不能让preSum[j]-preSum[d[0]]>=k,单调递增的d后面的元素也不能满足要求了,所以每次就立马完成。最差的状态可能是某次j,从0到j遍历,每次都符合条件,都要pop并更新window len。但很明显,队列最多跟n一样长,而且pop出去了又不会回来,所以次数最多n次,并不会膨胀。所以总的复杂度还是O(n)的。

这道题还是很难的,难在拼出正确的方法,知道方法后,代码实现不难。

Max Consecutive Ones III

突如其来的一道复习题。while-if即可,虽然和while-while实测没什么区别,大概是case的原因。

Replace the Substring for Balanced String (medium) – LeetCode

题目是说要替换的字符包含在一个子串里,要求子串最短,子串符合某个条件即可,那就很适合套用滑动窗口模板了。

Count Number of Nice Subarrays (medium) – LeetCode

这题一看就不适合立马套用模板,扩展和收缩求最长最短很有效,但这里没有用处。举例说明,当我们找到一个窗口恰好有k个奇数,此时可以滑动窗口么?当然不能。所以放弃吧。然后考虑到奇数是核心,先找到k个奇数的最小可能,它的左右两边如果分别有a个偶数和b个偶数,那么这里就有很多个子串可能,1+a+b+a*b。而找奇数,可以直接抽出奇数,这样奇数数组里每k个就是一个base,延展下两边的偶数。既没有重复也不会漏算。

滑动窗口完结撒花🎉

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,可以极快的写完代码。

首先是二叉堆,巩固下:

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

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

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

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

再来说说二叉树的基本操作逻辑。

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

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

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

而且heapq提供heapreplace,也就是把堆的pop和push两步放在一步完成,因为size恒定。你如果pop[0],就把新的元素放在[0]就行,让它下沉,就pop了堆化一次,又push,加一个尾部元素,又堆化一次。

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

如果没有这一点保证,你想做的就是push后pop,因为你想从heap和想push的新值一起看的集合中最小的值,可以使用headpq.heappushpop。不过,这个自己写也行,逻辑不复杂,就是先peek一下堆顶,如果push的新值更小,就直接返回,如果不是,就把堆顶值取出,把新值放在堆顶,然后堆化。

返回题目

具体到这个题目,首先要思考这个堆该如何运行,放多少数据,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个等等都比较好修复。

推荐站点:

https://qoogle.top/how-to-brush-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

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

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

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

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

编译器思路

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

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

比如,只有加减乘除:

加入括号(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,右边>=”这样的格式?

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×