Outline
相向雙指針
同向雙指針
Two Sum
Partition
Sort
0 Templete
同向雙指針度迂，相向雙指針狗准，Two Sum
鏈表上的快慢指針
快速排序 & 歸并排序
Loop one variable, research the change of another variable, while(start < end)
類型：
- 背向雙指針
第一節(jié)課中的 Longest Palindromic Substring 的中心線枚舉算法
第二節(jié)課中的 Find K Closest Elements - 相向雙指針
Two Sum 的一大類題（兩位數(shù)的相關(guān)變形題）
Partition 的一大類題（兩位數(shù)相關(guān)變形題） - 同向雙指針
滑動(dòng)窗口類 Sliding Window
快慢指針類 Fast & Slow Pointers
1 同向雙指針
Lintcode 604.Window Sum
http://www.lintcode.com/problem/window-sum/
https://www.jiuzhang.com/solutions/?search=window%20sum
Leetcode 283.Move zeros
https://leetcode.com/problemset/all/?search=move%20zero
http://www.lintcode.com/problem/move-zeroes/
https://www.jiuzhang.com/solutions/?search=move%20zero
右邊指針指向的數(shù)字不是0的都堆到左邊指針指向的位置
S: Int left = 0, right = 0;
D: left is the index of first 0, right is current index
LeetCode 26.Remove Duplicates from Sorted Array
https://leetcode.com/problems/remove-duplicates-from-sorted-array/
http://www.lintcode.com/problem/remove-duplicate-numbers-in-array/
https://www.jiuzhang.com/solutions/?search=remove%20duplicate%20numbers%20in%20array
https://leetcode.com/problems/remove-duplicates-from-sorted-array/discuss/11751/Simple-Python-solution-O(n)
區(qū)分Sorted和Unsorted卷扮，如果是sorted用一個(gè)pointer標(biāo)識(shí)當(dāng)前位置期揪，如果是unsorted碎捺，還需要一個(gè)set來(lái)判斷是否有重復(fù)的
for (Map.Entry<Integer, Boolean> entry : mp.entrySet())
nums[result++] = entry.getKey();
2 相向雙指針
兩根指針一頭一尾彤枢，向中間靠攏直到相遇
時(shí)間復(fù)雜度 O(n)
Leetcode 125/680. Valid Palindrome I/II
驗(yàn)證一個(gè)字符串是否為回文串苍苞，忽略大小寫和非英文字母字符
https://leetcode.com/problemset/all/?search=valid%20palindrome
http://www.lintcode.com/problem/valid-palindrome/
http://www.jiuzhang.com/solution/valid-palindrome/
isalpha()和isdigit()來(lái)去掉非想要的字符串
Follow up: 可以刪掉一個(gè)字符
http://www.lintcode.com/problem/valid-palindrome-ii/
https://www.jiuzhang.com/solution/valid-palindrome-ii/
把is_palindrome抽象成一個(gè)函數(shù)來(lái)復(fù)用
Lintcode 8.Rotate string
http://www.lintcode.com/problem/rotate-string/
https://www.jiuzhang.com/solutions/?search=rotate%20string
S: offset = offset % str.length
D: 3 reverse method, careful with offset and place
Left,right and whole
Lintcode 39.Recover rotated sorted array
http://www.lintcode.com/en/problem/recover-rotated-sorted-array/
https://www.jiuzhang.com/solutions/?search=Recover%20rotated%20sorted%20array
三段翻轉(zhuǎn)即可固翰，用雙指針in place翻轉(zhuǎn)數(shù)組
D: find offset
And then use 3 reverse method, careful with left++ and right-- list.get()/.set(,)
Sort
Arrays.sort(m, Collections.reverseOrder());
Collections.sort(m, Collections.reverseOrder());
3 Two sum
Leetcode 1.Two sum
https://leetcode.com/problems/two-sum/
http://www.lintcode.com/problem/two-sum/ http://www.jiuzhang.com/solutions/two-sum/
哈希表(HashMap) vs 兩根指針(Two Pointers)
D: Use two pointer or Hashmap: store negative value in map, and find if anything remain match
Lintcode 607.Two sum III data structure design
http://www.lintcode.com/problem/two-sum-data-structure-design/ https://www.jiuzhang.com/solution/two-sum-iii-data-structure-design/
D: HashMap
Leetcode 167.Two Sum II - Input array is sorted
https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
http://www.lintcode.com/problem/two-sum-input-array-is-sorted/ http://www.jiuzhang.com/solutions/two-sum-input-array-is-sorted/
Two Pointers and narrow the range相向指針
D: Two pointers: should be sorted array, and 2 pointer from left to right
Lintcode Unique pairs
http://www.lintcode.com/en/problem/two-sum-unique-pairs/ http://www.jiuzhang.com/solutions/two-sum-unique-pairs/
D: Sort and remove duplicate in the while(left < right), that is remove duplicate before moving pointers
找到相等的時(shí)候別停下來(lái)，繼續(xù)找就行羹呵。
注意跳過(guò)相等元素避免重復(fù)方案骂际。
Lintcode 57.Three Sum
http://www.lintcode.com/problem/3sum/
http://www.jiuzhang.com/solutions/3sum/
統(tǒng)計(jì)所有的和為 0 的三元組 (Triples)
D: Sort and fix one point(remove duplicate) and do the two sum on the right of the point, because this point is checked, it will not be checked in the next index
Lintcode 382.Triangle Count
http://www.lintcode.com/problem/triangle-count/ http://www.jiuzhang.com/solutions/triangle-count/
S: left, right, ans
D: Fix the one value t = i 0->len-1, set left and right between 0-t find 2 sides > one side then ans = ans + (right - left) remember right and left is index
Two sum計(jì)數(shù)問(wèn)題
統(tǒng)計(jì)所有和 <= target 的配對(duì)數(shù)
Lintcode Two Sum - Less than or equal to target
http://www.lintcode.com/problem/two-sum-less-than-or-equal-to-target/ http://www.jiuzhang.com/solutions/two-sum-less-than-or-equal-to-target/
set a count and update count use right - left or left - right
'<=' target
D: use two pointers, when <= target, ans = ans + (right - left)
Lintcode Two Sum - Greater than target
http://www.lintcode.com/en/problem/two-sum-greater-than-target/ http://www.jiuzhang.com/solutions/two-sum-greater-than-target/
'>=' target
D: same as the above , 一個(gè)是左邊位置，一個(gè)是右邊
統(tǒng)計(jì)所有和 >= target 的配對(duì)數(shù)
Lintcode Two Sum Closest
http://www.lintcode.com/problem/two-sum-closest-to-target/ http://www.jiuzhang.com/solutions/two-sum-closest/
D: Return the difference, use Math.min()
Follow up:
Lintcode Three Sum Closest
http://www.lintcode.com/problem/3sum-closest/ http://www.jiuzhang.com/solutions/3sum-closest/
loop one value then do the 2 sumclosest
- Related questions
4Sum
http://www.lintcode.com/problem/4sum/
http://www.jiuzhang.com/solutions/4sum/
Two Sum - difference equals to target
(同向雙指針)
http://www.lintcode.com/problem/two-sum-difference-equals-to-target/
http://www.jiuzhang.com/solutions/two-sum-difference-equals-to-target/
總結(jié)
對(duì)于求 2 個(gè)變量如何組合的問(wèn)題
可以循環(huán)其中一個(gè)變量冈欢，然后研究另外一個(gè)變量如何變化
Trapping Rain Water
https://leetcode.com/problems/trapping-rain-water/
https://leetcode.com/problems/trapping-rain-water/discuss/17554/Share-my-one-pass-Python-solution-with-explaination
5 Partition
Leetcode 31.Partition Array
D: use two pointers, when left > target and right <= target then exchange each other
http://www.lintcode.com/problem/partition-array/ http://www.jiuzhang.com/solutions/partition-array/
Lintcode Quick select
http://www.lintcode.com/problem/kth-smallest-numbers-in-unsorted-array/
https://www.jiuzhang.com/solution/kth-smallest-numbers-in-unsorted-array/
http://www.lintcode.com/problem/kth-largest-element/
https://www.jiuzhang.com/solution/kth-largest-element/
小視頻：http://www.jiuzhang.com/video/quick-select/
Kth smallest numbers in unsorted array
D: first set the pivot and get it's place in the array, then you will know the kth is in the left or right
Kth largest element
D: same as above
- Related Questions
Partition Array by Odd and Even
http://www.lintcode.com/problem/partition-array-by-odd-and-even/
http://www.jiuzhang.com/solutions/partition-array-by-odd-and-even/
Interleaving Positive and Negative Numbers
http://www.lintcode.com/problem/interleaving-positive-and-negative-numbers/
http://www.jiuzhang.com/solutions/interleaving-positive-and-negative-integers/
Sort Letters by Case
http://www.lintcode.com/problem/sort-letters-by-case/
http://www.jiuzhang.com/solutions/sort-letters-by-case/
5 Sort
Quick Sort(binary search)
Quick sort is not stable, merge sort is stable but need O(n) space
Sort Colors
http://www.lintcode.com/problem/sort-colors/ http://www.jiuzhang.com/solutions/sort-colors/ 分成兩個(gè)部分 vs 分成三個(gè)部分
S: pl, pr, i
D: red, white and blue, Two pointers, use I to go through, pl to represent red end, pr to blue start
Rainbow sort
http://www.lintcode.com/en/problem/sort-colors-ii/ http://www.jiuzhang.com/solutions/sort-colors-ii/
S: colors[], left, right, colorFrom, colorTo
D: Use quick sort by 1-k, use colarMid = (colorFrom + colorTo)/2 as pivot
- Other Sort
Pancake sort
https://en.wikipedia.org/wiki/Pancake_sorting http://www.geeksforgeeks.org/pancake-sorting/
Like selection sort , use 2 reverse process to get the maximum value in the end
Use as few reversals as possible instead of comparison( you can only use flip here)
Sleep sort
https://rosettacode.org/wiki/Sorting_algorithms/
Use thread
Spaghetti sort
https://en.wikipedia.org/wiki/Spaghetti_sort
Parallel and lowering
Bogo sort
https://en.wikipedia.org/wiki/Bogosort
Shuffle and check
