a.Dummy Node <br>
如何使用 Dummy Node
head = dummy 这句话总是需要么?
什么时候使用 Dummy Node? 结构变化，会导致头部变化，就可以用Dummy Node
Dummy Node 是否需要删除? 不用，Java会自动删除
使用 Dummy Node 算面试官会说我耗费了额外空间么?
Dummy Node 非用不可么? 不是，写起来可能很麻烦
Dummy Node 初始化的值重要么? 不重要
链表的问题都需要用到 Dummy Node 么? 90%都可以用到
总结：链表的题一般就使用dummy node
1.求中点 <br>
slow在中间或者偏右：
slow = fast = head
slow = slow.next
fast = fast.next.next
最后slow是在中间或者中间偏右的。
slow在中间或者偏左：
slow = head fast = head.next
但是归并排序，或者将链表分成二部分时，slow = head fast = head.next。因为对于归并排序，如果是2个元素后，slow=fast=head 会陷入拆分后还是2个元素。
2.求链表是否有环: Linked List Cycle <br>
常规解法1：extra空间 用hashSet
非常规解法2：快慢指针 follow up:判断两个链表是不是有交集，并且求出相交点；
slow = fast = head
slow = slow.next
fast = fast.next.next
Then check if equal.
3.求链表的相交点：
两个链表连起来看有没有环，将一个链表的头尾相连，判断有没有环，有环说明是相交的，然后求出相交点。
先判断有没有交点：slow = fast = head slow每次走一步，fast每次走2步
再求相交点：head slow分别出发，相遇点就是交点
特别注意：指针的题目特别注意有的地方要断开，有的地方链表已经变了Linked List - Reverse Linked List 总结：Reverse链表有2中解法，一种是递归。一种是非递归。都要熟记。
- 0206.Reverse Linked List (!!E)
需要熟背理解solution 1: interrative: 注意初始化 prev, curr = None, head 因为head需要point to None; solution 2: recurssive: 非常容易漏掉 head.next = None。 - 0092.Reverse_Linked_List_II (M)
Solution:reverse node from m to n: step1: find node_m and node_m_minus; find node_n and node_n_plus. step2:reverse the nodes from m to n; step3: hook up node_m_minus with node_n, node_m with node_n_plus. TODO: onepass - 0025.Reverse Nodes in k-Group (!!H)
Solution 1: recursion: step 1: exit of recursion: when less than k elements left, return head directly; step 2: reverse the first k elements; step 3: revursivey find the new head of the reversed list. Attention: prev is the head, curr represent the node you want put before the prev. - 0024.Swap_Nodes_in_Pairs (M)
Solution: 1: recursion, easier to implement. Solution 2: iterative. 想要reverse n1->n2->n3->n4->n5->n6 in pairs: step 1: 在n1前面添加一个dummy n0, 然后在while curr循环里每次都调用reverse函数，reverse函数做的事情是操作四个节点n0->n1->n2->n3, 将其变成n0->n2->n1->n3, 然后return n1，注意每次都是return想要swap的两个节点的前一个节点！step 2: curr = return的n1，然后继续循环. - 0086.Partition_List (!!M)
Solution: 遍历list，用2个dummy去记录2个链表，一个小于k, 一个大于等于k，最后把两个链表连起来。
Linked List - Cycle detection
- 0141.Linked List Cycle (E)
在做环形list的题目时,模板是 slow, fast = head, head; while fast and fast.next: - 0142.Linked_List_Cycle_II (!!M)
step 1: 快慢指针找到相遇的点; step 2: 重新定义两根指针p1, p2分别从head和上面相遇的点出发，然后p1,p2相遇的地方就是环的入口, 每次都移动curr = curr.next, 注意区别找环的时候的。 - 0160.Intersection of Two Linked Lists (E)
Solution: 1.暴力法
2.hash table
3.two point（推荐）. 两个指针同时遍历两个链表，当到达一个尾骨之后，换到另一的头部继续遍历，两个指针会在链表的相交节点相遇. two point method: 两个指针currA, currB; if not currA: currA = headB; if not currB: currB = headA.第三种方法解释：这样2个指针都走了相同的长度，所以会遇到。
4.将2个链表首尾相连，然后用快慢指针，求相交点 - 0021.Merge_Two_Sorted_Lists (E)
Solution:如果需要return一个新的headNode，一般定义一个dummyNode = ListNode(0), curr = dummyNode; 最后return dymmyNode.next - 0234.Palindrome_Linked_List.py (E)
Solution1: 题目要求O(n) time and O(1) space: 我们只能reverse 一半的linked list，先找到中点，然后reverse the left part，最后比较判断是否为panlindrome.
Solution2: stack, 但是会增加空间复杂度。 - 0287.Find_the_Duplicate_Number.py (M)
[1,5,3,6,2,2,4]: 1 -> 5 -> 2 -> 3 -> 6 -> 4 -> 2.... 形成了环. 把这个数组的每一个数num看成这样一个linked list node: num的下标代表.val, num的值代表.next指向下一个node。那么如果存在重复的num，那就表示有两个不同node都指向了同一个公共，也就是成环的地点。这么想这个题目就和142一样了，具体实现过程中对p取一个nums[p]，就相当于取一个p.next
Linked List - Copy Linked List
- 0138.Copy List with Random Pointer (M)
方法1：先复制点，再复制边，记录下来新老节点的映射关系，用hashMap存储。 缺点：用了额外的存储空间（nextTime可以用下这个方法）. 方法2：记住，讨巧的方式，改变链表结构变成1-1’-2-2‘-3-3’ 再分离，不用额外的空间. 解题时：复杂问题先分成几个小问题，定好小问题的输入和输出，再写小问题. Solution 1: O(N), O(N): Just iterate the linked list and create copies of the nodes on the go. Since a node can be referenced from multiple nodes due to the random pointers, make sure you are not making multiple copies of the same node. we can use extra space to keep old node --> new node mapping to prevent creating multiples copies of same node. Solution 2: O(N), O(1): use 3 steps, each step requires iterate the loop one time. step 1: create new node and interleave new node into original node; step 2: link the random pointer for the new nodes; step 3: seperate the interleaved old nodes and new nodes. - 0430.Flatten_a_Multilevel_Doubly_Linked_List (!!M)
递归即可，易错点是return head之前别忘了把head.child设置成None
sort: sort array: merge sort//quick sort but for list: only use merge sort
- 0148.Sort_List.py (M)
Solution1: divide and conquer.先找到中点 slow = head, fast = head.next rightHead = slow.next - 0912.Sort_an_Array.py (M)
Solution1: merge sort, quick sort, bubble sort
divide and conquer 就是merge sort
Linked List
- 0002.Add_Two_Numbers.py (!!M) solution: use carry bit.
本题的考点是关于如何新建一个linked list, 要用someNode.next = ListNode(someVal), 而不是简单的修改value; 还考察了是否细心, 最后很容易漏掉carryBit != 0的判断". - 0445.Add_Two_Numbers_II (M)
Solution 1: reverse the list, then do exactly the same as 0002, then reverse again. Solution 2: change str to int then add up. Solution 3: use stack to solve the problem. - 0019.Remove_Nth_Node_From_End_of_List.py (M)
fast 比 slow 先出发 n 步即可 - 0328.Odd_Even_Linked_List.py (M)
把dummy指向head.next的地方，因为一会儿会丢失掉head.next的位置, 害怕什么node的位置会丢掉就拿一个dummy指向那个位置 - 0844.Backspace_String_Compare.py (M)
Solution 1: use stack, memery space o(n) Solution 2: from tail to first scan string.
- hash time O(n+m) space O(min(n,m)) 一个数组放进去，另一个数组进行遍历在不在hash中
- merge two sorted arrays time O(nlogn + mlogm) space O(1) 先把两个数组排序，再用两个指针遍历merge
- Binary Search(n << m) time O(nlogn + mlogn) space O(1) 一个数组先排序，遍历另一个数组，查找在不在已经排好序的数组中，把小的数组排序，然后 for 循环大的数组
- 0006.Merge_Two_Sorted_Arrays (Lintcode E)
Solution: 同0088, follow up用binary search做 - 0088.Merge Sorted Array (M)
Solution: 将小数组归并到大数组里，从后往前merge - 0349.Intersection_of_Two_Arrays (!!E)
Facebook follow up: what if the lists are sorted and you are requred to use O(1) space. Approach: two-pointers solution, 注意去重的方法！！ - 0350.Intersection_of_Two_Arrays_II (!!E)
Fackbook follow up 1: what if sorted? solution is using two-pointers. Follow up 2: what if size of nums1 is small? solution is binary search. Follow up 3: what if nums2 is so large that it cannot fit in the memory? solution: Divide nums2 into n chunks of 1/n size and load 1/n piece each time. Follow up 4: What if neither nums1 or nums2 can fully fit in memory? solution: external sort + n chunks + two pointers. - 0004.Median_of_Two_Sorted_Arrays (H)
数组内积（点乘） 设计：数组index和value的形式，index相同的才乘起来。
- 记住: Sum(i~j) = PrefixSum[j + 1] - PrefixSum[i]
要点：子数组Subarray:令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]
- 问：为什么需要一个 (0,0) 的初始 Pair?
答：我们首先需要回顾一下，在 subarray 这节课里，我们讲过一个重要的知识点，叫做 Prefix Sum, 比如对于数组 [1,2,3,4]，他的Prefix Sum是[1,3,6,10]分别表示 前1个数之和，前2个数之和，前3个数之和，前4个数之和, 这个时候如果你想要知道子数组从下标1到下标2的这一段的和(2+3)，就用前3个数之和减去前1个数之和 = PrefixSum[2] - PrefixSum[0] = 6 - 1 = 5, 你可以看到这里的 前 x 个数，和具体对应的下标之间，存在 +-1 的问题.第x个数的下标是x - 1，反之下标x是第x + 1个数. 那么问题来了，如果要计算下标从 0~2 这一段呢？也就是第1个数到第3个数，因为那样会访问到 PrefixSum[-1].
所以我们把 PrefixSum 整体往后面移动一位，把第0位空出来表示前0个数之和，也就是0. => [0,1,3,6,10].
那么此时就用 PrefixSum[3] - PrefixSum[0] ，这样计算就更方便了。此时，PrefixSum[i] 代表 前i个数之和，也就是 下标区间在 0 ~ i-1 这一段的和
prefix_sum
- 0724.Find_Pivot_Index (E)
if pre_sum[i-1] == pre_sum[-1] - pre_sum[i]: return i - 1 - 0604.Window Sum (Lintcode)
Solution:求子数组，移动窗口，计算前缀和 - 0053.Maximum Subarray
Solution:step1:构造前缀和pre_sum. step2:the same as 127.best time to buy and sell stock. - 0560.Subarray_Sum_Equals_K
Solution:新建一个prefixSumDict = {0: 1}, key是prefixSum, val是how many times the prefixSum appears; if prefixSum - k in prefixSumDict: 等价于if prefixSum[j+1]-prefixSum[i] == k. - 0138.Subarray Sum （lintcode）
Solution:find a subarray where the sum of numbers is zero.use hashmap to record the value. - 0139.Subarray_Sum_Closest （lintcode）(M)
Solution: Given an integer array, find a subarray with sum closest to zero. Subarray Sum Closest 求出来后排个序. 讲解：http://www.jiuzhang.com/solutions/subarray-sum-closest/ - 1352.Product_of_the_Last_K_Numbers.py (!!M Google)
Solution:prefix sum. Keep all prefix products of numbers in an array, then calculate the product of last K elements in O(1) complexity. When a zero number is added, we need to reset the array of prefix products.Attention:初始化为[1]，遇到0时重新设置值为[1]
Prefix sum + Hashmap: subarray sum equals k problem with negative number (有正有负数，所以用不了滑动窗口) 通常使用了hashmap之后不用prefix sum数组了.
- 0560.Subarray_Sum_Equals_K
Solution:新建一个prefixSumDict = {0: 1}, key是prefixSum, val是how many times the prefixSum appears; if prefixSum - k in prefixSumDict: 等价于if prefixSum[j+1]-prefixSum[i] == k. - 0325.Maximum_Size_Subarray_Sum_Equals_k.py
由于arr中有正数有负数，所以不能用sliding window, 只能用prefix sum + hashmap. pre_sum_dict stores (pre_sum --> idx where the pre_sum occured) - 0525.Contiguous_Array.py
将0都变成-1，题目就变成了max subarray size with sum == 0, which is exactly the same as 325. Maximum Size Subarray Sum Equals k. 由于arr中有正数有负数，所以不能用sliding window, 只能用prefix sum + hashmap - 0974.Subarray_Sums_Divisible_by_K.py
subarray sum的问题都要往prefix sum方面去想, subarray sum的问题都要往prefix sum方面去想： pre_sum_dict is (pre_sum --> how many time pre_sum occured); prefixSum += num; prefixSum %= K. - 0523.Continuous_Subarray_Sum.py
prefixSumMap = {0: -1} # key: prefixSum[j], val: j/position, initial position should be -1; prefixSum += num; prefixSum = prefixSum % k 因为题目要求要能被subArray Sum 要能被k整除. - 1124.Longest_Well-Performing_Interval.py
step 1: 大于8小时的工作时间定义为1， 小于定义为-1， 这样就得到了一个nums， step 2: now the problem is to find the longest subarray with sum > 0. since there is negative numbers, we cannot use sliding window, for subarray sum at least/most k problem with negative number, we use prefix sum + mono deque. 因为这一题我们只需要check pre_sum - 1 in pre_sum_dict. 所以其实是一个subarray sum equals problem. for subarray sum equals k problem with negative number, we use prefix sum + hashmap.
Subarray sum at least / at most K problem and num have negative Solution: cannot use sliding window nor prefix sum, has to use mono deque. 这种情况最难implement, 需要在for循环里写两个while loop, 一个用sliding window udpate res, 另一个用clean the deque to maintain an increasing or decreasing deque.
TODO:862
总结：Pre-calculation: prefix sum 只是pre-calculation的一种，suffix sum, prefix max, prefix min, prefix product 等等都是pre-calculation的一种，我们要按照题目的具体要求选择pre-calculate prefix / suffix max / min / sum / product.
- [Binary Searchable](Solutions/Binary Searchable.py) (!!M Google)
没懂：prefix sum + binary search. 一个数是binary searchable的必须满足的条件是：前面的数都比他小，后面的数都比他大 - Max_Absolute_Difference_of_Subarrays.py (!!M Google)
prefix sum + dp. step 1: maintain一个prefix_sum list和一个suffix_sum list. step 2: 用这两个list计算出dp1 list and dp2 lsit, dp1[i] = the max subarray sum before i, dp2[i] = the min subarray sum before i; dp3[i] = the min subarray sum after i, dp4[i] = the max subarray sum after i. step 3: 从左到右遍历一遍，比较i左右两边的min 和 max, 更新max_abs_diff即可。O(N), O(N)
-
Find Two Non-overlapping Sub-arrays Each With Target Sum (!!!!M Google) prefix sum + dp. step 1: construct a pre_sum and a suf_sum. Step 2: then use the pre_sum and suf_sum to construct two lists: pre_min[i] = minimum lens of valid subarray that ends before i. suf_min[i] = minimum lens of valid subarray that starts after i. step 3: find the ans as we iterate the arr.
-
Product of the Last K Numbers (!!M Google) prefix sum. Keep all prefix products of numbers in an array, then calculate the product of last K elements in O(1) complexity. When a zero number is added, we need to reset the array of prefix products.
单调队列：
If there is no window size limitation, to find previous largest/smallest number, monotonous stack is always what we need.
Since in this problem, the window size is set to k, we can use monotonous queue to find largest/smallest element in a fixed size sliding window.
push: push an element into the queue; O (1) (amortized)
pop: pop an element out of the queue; O(1) (pop = remove, it can't report this element)
max: report the max element in queue;O(1)
注意如果题目需要我们在window里更新最大值或最小值，我们往往需要maintian一个mono increasing or mono decreasing deque.
在mono deque中会有两个while loop, 第一个while loop从左端pop作为sliding window去限定window size, 第二个while loop从右端pop作为monostack去maintain 最大值/最小值!
239 862 1438 1499 751