Unit 4 Two Pointers | LeetLintcode
2根指针有3种题型:
- 一个数组, 从两边向中间移动(对撞型)
- 一个数组, 同时向前移动(前向型)
- 两个数组(并行型)
- 重点是记住: 模版是死的, 人是活的. 不要拘泥于模版. 参见min Substring contains target把题做少, 即所有新题都往会的方法上面靠.
对撞型
inspired by Qsort's partition. 有2个类型的题目:
- 2 sum
- partition
- 模版
- Two sum模版
int i = 0, j = leng-1; while (i < j) { if (a[i] + a[j] > sum) { do something j--; } else if (a[i] + aj] < sum) { do something i++; } else { do something i++/j--/ } - 灌水模版
int i = 0, j = leng-1; while (i < j) { if (a[i] > a[j]) { do something j--; } else if (a[i] < a[j]) { do something i++; } else { do something i++/j-- } - 总结模版
int i = 0, j = leng-1; while (i < j) { if (A[i]和A[j]满足某个条件) { j--; // 直接跳过k ∈ [i+1, j-1] 和j组成的pair, 这需要证明. 也是O(n^2)-> O(n)的关键. do something } else if (A[i]和A[j]不满足某个条件) { i++; // 直接跳过i和k E [i+1, j-1]组成的pair. do something } else { do something i++或者j--. } } Trapping water area
container with most water
方法1: brute force.
- 通过2层循环, 找到每一个pair组合构成的面积. O(n^2).
方法2: 灌水型的都想到对撞型指针.
- 条件是什么呢? 这里有个数学分析: 先找到l/r里面的短板. 那么重点来了: 不用循环i跟[i~j]的板子组成的container. 因为面积由短板决定. 所以若[i~j]之间有比i更小的板, 那么面积只会是heights[k] (k-i). 所以比[i,j]组成的小. 或者, 如果[i~j]之间有比i大的板子, 那么面积也只会是heights[i] (k-i). 因为k < j. 所以更小. 于是证明了, 每次只要找到短板构成的面积, 然后和全局res来update.
前向型
2类题目:
- 窗口类: 注意和sliding window不同, sliding window是给定了窗口大小, 找一个符合条件的窗口; 而two pointer的窗口型是指大小不确定, 找一个符合条件的窗口. 所以前者使用heap, deque维护. 后者通过指针来维护.
- 快慢类
- 模版:
int i,j; while (i < leng) { while (j < leng) { if (满足条件) { 更新结果/HashMap j++; } else { break; } } 更新结果/HashMap i++; }
Minimum Window Substring contains target string in source
题目: Given a set T of characters and a string S, find the minimum window in S which will contain all the characters in T in complexity O(n). S = "ADOBECODEBANC" T = "ABC" Minimum window is "BANC".
类似题目: longest substring with at most k distinct characters
Key: 重点在于理解前向型双指针的算法思想. 而不是生搬硬套九章模版(应该适当修改). 学习如何用HashMap来作为数组存在判定.
分析: 我一开始按照九章的前向型模版套着写的, 很简单, 但是也不太好. 因为每一次都要对256个数字判断. 所以Time complexity是O(256N). 老师讲了用source hash - target hash的方法. 但是我写的有错. 不知道怎么处理找到window的时候怎么去掉第一个char, 以及更新状态(即所有全局变量).
然后搜到了Leetcode的答案, 以及Rui Bi精彩的Java实现. 其实就是前向型双指针的使用, 不过和template有点小小区别.
- 意思如图:
. 关键在于实现. 特别是找到window之后, 怎么advance pointer以及更新状态?
- 意思如图:
代码如下
/** * http://xmruibi.github.io/2015/10/08/minimum-window-substring/ * http://articles.leetcode.com/2010/11/finding-minimum-window-in-s-which.html */ public String minWindow(String source, String target) { // preload for target checking if (source == null || source.length() == 0 || target == null || target.length() == 0) return ""; int tarLen = target.length(); HashMap<Character, Integer> dict = new HashMap<>(); // target hash for (char c : target.toCharArray()) // 简洁 dict.put(c, dict.containsKey(c) ? dict.get(c) + 1 : 1); // 好写法! int hitCount = 0; // record current window hits how many characters in target int l = 0; // record the left bound of current window int minWindow = source.length() + 1; // initial the minimum window length int start = 0; // hold the global left bound of min window for (int r = 0; r < source.length(); r++) { char cur = source.charAt(r); // 因为只考虑一个char, 所以保存起来, 避免每次都用charAt求. if (!dict.containsKey(cur)) continue; // 若不符合, 就找下一个点.即增加right. dict.put(cur, dict.get(cur) - 1); // 更新Target hash. 注意这个也同时表示了Diff hash. 即当前window和target hash之差. 所以找到一个window并不是说Target hash全为0. 例如AAAABC里面找ABC. 则第一个window就会导致Thash的A为-3. if (dict.get(cur) >= 0) hitCount++; // 关键之一: 通过Target hash, 判定是否已经找到了一个有效字符. 负数的次数也是有用的, 表明当前window有多于target的target[j]. 这在前移left的时候用到. // check the windows has amount of this char more than it in target string // loop until the amount back to normal, but always reduce the prev index char while (hitCount == tarLen) { // 满足条件的情况. if (minWindow > r - l + 1) { start = l; minWindow = r - l + 1; } char prevChar = source.charAt(l); if (dict.containsKey(prevChar)) { // hashmap比int[256]好处在于存在就是target里的char. dict.put(prevChar, dict.get(prevChar) + 1); // 关键2: 如何更新状态? 恢复dict即说明下一次for要继续找到prevChar. if (dict.get(prevChar) > 0) hitCount--; // 当Target hash里面有正数个prevChar, 那就要找这个char, 于是hitcount恢复为自减1. } l++; } } // if (minWindow > source.length()) return ""; // 注意如果没找到, 应该回复空. return source.substring(start, start + minWindow); }Read full article from Unit 4 Two Pointers | LeetLintcode
