总体来说，这部分题目思路上难度都不大，感觉就Sliding Window 难一些，拿到题目以后基本上可以快速反应，但是编程上细节很多，尤其是linked List 容易错，思路都搞定了，其他就通过练习来搞定！
题目数据结构: Array, String, LinkedList.
解题技巧: Two Pointer, Three Pointer, Index, Sliding Window
Two Pointers 三种类型
1. 两个Pointer 从start, end 往中间走: 主要是 Array的题目。
在Array的问题里面，Two Pointer 解决的问题主要是 O(n^2) 的Brute Force的效率问题，下面的题目Brute Force 都能做，但是这不是考点， LeetCode 上这类题目一定Two Pointer 才能AC.
- Two Sum
- 3Sum
- 3Sum closest
- 4Sum
- Sort Colors
- Container With Most Water
- Trapping Rain Water
- Binary Search (See Summary 1) O(n) -> O(log(n))
1. Two Sum
Two pointers 的方法要注意，数组是没有sorted的， Two Pointer 一定要用在sorted 数组上，复制数组不能直接用 引用，必须new 新的出来，用Arrays.arraycopy 复制内容. HashMap的方法记住，存的是Key 是 numbers[i], value 是index
2. 3Sum
跟Two Sum 的不同就是，1.多了一个元素，2.有重复，3. 结果不唯一，结束条件不同。 这样需要套一层循环，固定住第一个数，剩下的 i+1 到 n - 1的部分，套用two Sum的方法。这道题去重很重要，在于 i, start, end 坐标移动时候的重复值的skip
3. 3Sum closest
找close to target 的值，需要维护一个minValue 使得 Math.abs(sum - target)，因为假设有一个solution，所以不用管duplicates, 3Sum是要找所有的duplicate，自然要去重。
4. 4Sum
跟3Sum一样, 需要在i, j, start, end 除去重
5. Sort Colors
只走一遍，需要two pointer，redIndex 之前都是 0， blueIndex 之后都是2， 偏离A, 根据不同情况交换，1的时候i++.
挺有意思的
6. Container With Most Water
这个题目的一些特性使得我们可以用Two Pointer，容量取决于Math.min(height[i], height[j]).
每次移动height 短得那个pointer，就一定不会skip最大值, 极端情况就是在在边界的时候最大，移动以后, j-i变小，面积也变小。
7 .Trapping Rain Water
对于每点，都需要计算window, [leftMost, rightMost], 当前的water = Min(leftMost, rightMost) - A[i].
优化一下，计算maxLeft[] 和maxRight[]. 在计算maxRight同时可以直接计算结果了，不必再用一个loop
Two pointers 的方法要注意，数组是没有sorted的， Two Pointer 一定要用在sorted 数组上，复制数组不能直接用 引用，必须new 新的出来，用Arrays.arraycopy 复制内容. HashMap的方法记住，存的是Key 是 numbers[i], value 是index
2. 3Sum
跟Two Sum 的不同就是，1.多了一个元素，2.有重复，3. 结果不唯一，结束条件不同。 这样需要套一层循环，固定住第一个数，剩下的 i+1 到 n - 1的部分，套用two Sum的方法。这道题去重很重要，在于 i, start, end 坐标移动时候的重复值的skip
3. 3Sum closest
找close to target 的值，需要维护一个minValue 使得 Math.abs(sum - target)，因为假设有一个solution，所以不用管duplicates, 3Sum是要找所有的duplicate，自然要去重。
4. 4Sum
跟3Sum一样, 需要在i, j, start, end 除去重
5. Sort Colors
只走一遍，需要two pointer，redIndex 之前都是 0， blueIndex 之后都是2， 偏离A, 根据不同情况交换，1的时候i++.
挺有意思的
6. Container With Most Water
这个题目的一些特性使得我们可以用Two Pointer，容量取决于Math.min(height[i], height[j]).
每次移动height 短得那个pointer，就一定不会skip最大值, 极端情况就是在在边界的时候最大，移动以后, j-i变小，面积也变小。
7 .Trapping Rain Water
对于每点，都需要计算window, [leftMost, rightMost], 当前的water = Min(leftMost, rightMost) - A[i].
优化一下，计算maxLeft[] 和maxRight[]. 在计算maxRight同时可以直接计算结果了，不必再用一个loop
2. 两个Pointer 从头往后走，快慢指针. 这是绝大多数Linked List题目设计的操作。Array 中也有部分题目利用这种思想，一般叫Sliding Window，解决一些跟序列有关的问题。
- Implement strStr()
- Minimum Window String
- Longest Substring without Repeating Characters
- Substring with Concatenation of All Words
- Remove Duplicates from Sorted Array
- Remove Duplicates from Sorted Array II
- Remove Element
- Remove Duplicates from Sorted List
- Remove Duplicates from Sorted List II
- Remove Nth Node From End of Test
- Reverse Linked List II
- Rotate List
- Swap Nodes in Paris
1. Implement strStr()
注意 i < haystack.length() - needle.length() + 1. 一定别忘了+1.
O(m*n) m,n 为haystack, needle 长度
2. Minimum Window String
同样是Sliding Window, 主要是需要处理好什么时候包含所有T中字符，这里用count 和 HashMap的组合来控制.
添加时候移动window右边，满足后，移动窗口左边直到不满足条件.
不同的地方是，window中包含不在dict中的字符，所以才构成了上述的解决方法。
3. Longest Substring without Repeating Characters
需要一个leftBound 和i一起维护一个Sliding window,
在用一个Hashset 来判断 下一个字符是否是重复字符, 比 遍历window中字符快的多
重点在于控制i遇到重复字符时候 窗口左端的移动
4. Substring with Concatenation of All Words
之前用permutation + strStr的思路超时. 等下再不这个题，跟 longest substring 差不多
5. Remove Duplicates from Sorted Array
in place. 定义size 指向不重复的最后一个，每次从A[i] 和 A[size] 比较，重复，就continue. 然后就A[++size] = A[i]
6. Remove Duplicates from Sorted Array II
需要跳过相同的，并且存储了两次以上得点，跟I基本一样，加了条件 size!=0 && A[size] == A[size - 1]
7. Remove Element
跟Remove Duplicates from Sorted Array 一样，区别是，因为elem 可能出现在 index = 0 的位子，而且每次A[i] 是跟
elem 比较而不是 A[size], 所以A[size++] = A[i]
8. Remove Duplicates from Sorted List
以后固定都用 current = head, runner = head.next while(runner != null)
每次在定义runner的时候都考虑是runner = head还是next，还有终止条件是current !=null or current.next != null.
以后都是用runner 快一步，runner != null.
9. Remove Duplicates from Sorted List II -- dummy Node
特殊性在于找到duplicate, 不能直接move forward, 因为如果move了下次不知道这是不是duplicate了，所以要用while一次性全部删除
10. Remove Nth Node From End of Test -- dummy Node
N可以能等于List length, head可能被删除。p2 走n 步，然后p1,p2一起走 p2 走到头是 length - n, p1正好下一个点是Nth.
11. Reverse Linked List II dummy Node
in place. in one pass.
这个题目记得分段考虑，(1- m-1), (m,n) (n+1, end) part 主要是中间reverse part，需要标记prem，m, n, postn Node. reverse 从 m+1开始，因为是独立的部分，到时候还要拼接，没必要从m开始然后连上preMNode. 实际操作几点为postnNode.
12. Rotate List dummy Node
跟removeNth 差不多，找到以后nth node, rotate 即可，这道题目test case n > length. 所以要先得到length,再取余.
13. Swap Nodes in Paris
跟 reverse m,n 题目差不多, 需要一个lastNode 记录pre位，然后直接swap head, head.next. 不用把head 提到dummy 位. lastNode 一开始在dummy处.
3. 两个Pointer 控制两个不同的数组或者链表，一般出现在Merge相关的题目上
- Add Binary
- Add Two Numbers
- Multiply Strings
- Merge Sorted Array
- Merge Two Sorted Lists
- Partition List
第一小部分都是String类型的计算题，binary的，还有 +，*. 第二小部分全是merge题.
1. Add Binary
跟merge的感觉一样，短的先结束，然后长得， 为了方便，如果a < b. 交换，让a 最长，最后都加完之后，记得判断carry > 0
2. Add Two Numbers
因为是list，不能判断长度，merge以后只能 判断 l1 != null l2 !=null. 跟Add Binary 基本是一样的
3. Multiply Strings
比 Add Binary, Add Two Numbers 明显复杂一些，每次product计算需要考虑当前位置的值，因为当前值由两次计算加成. 还要记得最后trim 前面的无用的0.
3. Merge Sorted Array
注意到最后，如果 n > 0，要把B的再复制过来，m > 0 则不用，因为A前面已经sorted了
4. Merge Two Sorted Lists dummyNode
唯一要记得就是比较时候要，l1.val <= l2.val 小心漏掉 = 的情况
6. Partition List
根据value 不同，分到两个List中，这样可以保证preserve original order，然后merge一下，注意right.next = null 最后要，否则可能有相连.
1. Add Binary
跟merge的感觉一样，短的先结束，然后长得， 为了方便，如果a < b. 交换，让a 最长，最后都加完之后，记得判断carry > 0
2. Add Two Numbers
因为是list，不能判断长度，merge以后只能 判断 l1 != null l2 !=null. 跟Add Binary 基本是一样的
3. Multiply Strings
比 Add Binary, Add Two Numbers 明显复杂一些，每次product计算需要考虑当前位置的值，因为当前值由两次计算加成. 还要记得最后trim 前面的无用的0.
3. Merge Sorted Array
注意到最后，如果 n > 0，要把B的再复制过来，m > 0 则不用，因为A前面已经sorted了
4. Merge Two Sorted Lists dummyNode
唯一要记得就是比较时候要，l1.val <= l2.val 小心漏掉 = 的情况
6. Partition List
根据value 不同，分到两个List中，这样可以保证preserve original order，然后merge一下，注意right.next = null 最后要，否则可能有相连.
No comments:
Post a Comment