Wei
0%

Grokking Pattern 2

Posted on Edited on In

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