Grokking Pattern 2

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
环境note Grokking Pattern 3
Your browser is out-of-date!

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

×