Outline
LinkedList:
Dummy Node
High Frequency
Array:
Sorted Array
Subarray
0 Template
- Dummy Node
When the structure changes, use dummy node
Dummy, pre, curt
Need dummy.next
Dummy = new; dummy.next = head; head = dummy; return dummy.next; give the start of the linked list - Worth to do questions
1 LinkedList
Dummy Node
Leetcode 25.Reverse Nodes in K-groups
https://leetcode.com/problems/reverse-nodes-in-k-group/description/
https://www.jiuzhang.com/solutions/reverse-nodes-in-k-group/
S: I, dummy, begin
D: reverse(begin, end)
{S: begin end/first, prev, curt, next
D: moving each times
E: curt != end, return first}
E: dummy.next
链表结构发生变化时就需要Dummy Node
如何使用 Dummy Node
head = dummy 这句话总是需要么？
什么时候使用 Dummy Node?
Dummy Node 是否需要删除？
使用 Dummy Node 算面试官会说我耗费了额外空间么？
Dummy Node 非用不可么？
Dummy Node 初始化的值重要么？
链表的问题都需要用到 Dummy Node 么？Related Questions
Leetcode 86.partition list
https://leetcode.com/problemset/all/?search=partition%20list
https://www.jiuzhang.com/solutions/?search=partition%20list
Leetcode 21.Merge Two Sorted Lists
https://leetcode.com/problemset/all/?search=merge%20two%20sorted%20lists
https://www.jiuzhang.com/solutions/?search=merge%20two%20sorted%20lists
Leetcode 206.Reverse Linked List
2(cur)->1
3(head)->4(head.next)->5
https://leetcode.com/problemset/all/?search=reverse%20linked%20list
https://www.jiuzhang.com/solutions/?search=reverse%20linked%20list
Leetcode 206.Reverse Linked List II
https://leetcode.com/problems/reverse-linked-list-ii/
https://www.jiuzhang.com/solutions/?search=reverse%20linked%20list
Leetcode 143.Reorder List
快慢指针，分成两段，重新连接
https://leetcode.com/problemset/all/?search=reorder%20list
https://www.jiuzhang.com/solutions/?search=reorder%20list
Leetcode 61.Rotate List
分成两段，重新拼接
https://leetcode.com/problemset/all/?search=rotate%20list
https://leetcode.com/problems/rotate-list/discuss/22842/97.63-Python-Solution
https://www.jiuzhang.com/solutions/?search=rotate%20listCopy
Leetcode 138.Copy List with Random Pointer
https://leetcode.com/problemset/all/?search=Copy%20List%20with%20Random%20Pointer
https://www.jiuzhang.com/solutions/?search=Copy%20List%20with%20Random%20Pointer
Version 1
S: g: map, head, dummy, pre, newNode;
D: while(head check; head.random check)
E: dummy.next;
Version 2
S:
D: Use hashmap
No extra space
Copy random: Head.next.random = head.random.next-
LinkedList cycle
Linked List Cycle 1& 2
https://leetcode.com/problemset/all/?search=Linked%20List%20Cycle
https://www.jiuzhang.com/solutions/?search=Linked%20List%20Cycle
http://www.lintcode.com/en/problem/linked-list-cycle/ http://www.jiuzhang.com/solutions/linked-list-cycle/
follow up: http://www.lintcode.com/en/problem/linked-list-cycle-ii/ http://www.jiuzhang.com/solutions/intersection-of-two-linked-lists/- Cycle check if it has
S: fast = head.next , slow = head, head
D: Runner technique
Check fast and fast.next == null then return false
Slow = slow.next
Fast = fast.next.next - Cycle return the node where the cycle begin
S: fast, slow, head
D:Runner technique 2
Runner technique 1
head != slow.next then head = head.next slow = slow.next
E: head
- Cycle check if it has
Quick and merge sort list
Sort List
https://leetcode.com/problemset/all/?search=Sort%20List
https://www.jiuzhang.com/solutions/?search=Sort%20List
http://www.lintcode.com/en/problem/sort-list/ http://www.jiuzhang.com/solutions/sort-list/
Merges: findMiddle, merge, sort
Quicks: findMiddle, concat, gettail, sortRelated question
Convert Sorted List to Binary Search Tree
https://leetcode.com/problemset/all/?search=Convert%20Sorted%20List%20to%20Binary%20Search%20Tree
https://www.jiuzhang.com/solutions/?search=Convert%20Sorted%20List%20to%20Binary%20Search%20Tree
Delete Node in a Linked List
https://leetcode.com/problemset/all/?search=Delete%20Node%20in%20a%20Linked%20List
https://www.jiuzhang.com/solutions/?search=Delete%20Node%20in%20a%20Linked%20List
Convert Binary Search Tree to Doubly Linked List
https://www.jiuzhang.com/solutions/?search=Convert%20Binary%20Search%20Tree%20to%20Doubly%20Linked%20List
Other:
http://www.lintcode.com/problem/convert-sorted-list-to-balanced-bst/
http://www.lintcode.com/problem/delete-node-in-the-middle-of-singly-linked-list/
http://www.lintcode.com/problem/convert-binary-search-tree-to-doubly-linked-list/
3 Array
Sorted Array
Merge Two Sorted Arrays
https://leetcode.com/problemset/all/?search=Merge%20Two%20Sorted%20Arrays
https://www.jiuzhang.com/solutions/?search=Merge%20Two%20Sorted%20Arrays
D: small first, then big
Merge Sorted Array
https://leetcode.com/problemset/all/?search=Merge%20Sorted%20Array
https://www.jiuzhang.com/solutions/?search=Merge%20Sorted%20Array
D: same as above
Median of Two Sorted Arrays
http://www.lintcode.com/problem/median-of-two-sorted-arrays/ http://www.jiuzhang.com/solutions/median-of-two-sorted-arrays/Related questions
Merge sorted array
将小数组归并到大数组
http://www.lintcode.com/problem/merge-sorted-array/
http://www.jiuzhang.com/solutions/merge-sorted-array/
Intersection of Two Arrays
两个数组的交
https://leetcode.com/problemset/all/?search=Intersection%20of%20Two%20Arrays
https://www.jiuzhang.com/solutions/?search=Intersection%20of%20Two%20Arrays
Use two hashset
Sort and compare
Sort one and Binary search itSubarray
令 PrefixSum[i] = A[0] + A[1] + … A[i - 1], PrefixSum[0] = 0 易知构造 PrefixSum 耗费 O(n) 时间和 O(n) 空间 如需计算子数组从下标i到下标j之间的所有数之和 则有 Sum(i~j) = PrefixSum[j + 1] - PrefixSum[i]
Maximum Subarray
https://leetcode.com/problemset/all/?search=Maximum%20Subarray
https://www.jiuzhang.com/solutions/?search=Maximum%20Subarray
S: max, sum, minSum
D: Prefix sum: sum, max, minsum compare max and sum - minSum continued to update the lowest first values
Sum += A[i]
Max(sum, sum - minSum)
Min(minSum, sum);
Subarray sum
http://www.lintcode.com/en/problem/subarray-sum/ http://www.jiuzhang.com/solutions/subarray-sum/
S: List<Integer> ans, HashMap<Integer, Integer> map
D: use sum to store the first n items, store it into map, compare which one is equal, use index difference to get result;
Subarray Sum Closest
http://www.lintcode.com/en/problem/subarray-sum-closest/ http://www.jiuzhang.com/solutions/subarray-sum-closest/
