力扣 day 6
1 Combination sum: dfs recursive, append to results each time
2 sort list O(1) space: bottom up binary sort *AMAZING!* (don’t know its real name…)
3 coin change: seems like a combination sum problem (no, it doesn’t), but actually backpack problem. DP
4 group anagrams: categorize by sorted string / count, set can not be the key of a dict, but tuple(set()) can
5 longest substring without repeating characters: O(n) solution: 2 pointers, find out the longest substring without repeating characters before it at each location (hashmap, i.e., dict)
6 merge intervals: classic question, O(nlogn) time complexity: so sort first, compare results with the input, do not need to modify the input
7 rotate array: trick sol (O(1) extra space): reverse the array, reverse first k array, first last n-k array
8 odd even linked list: O(1) space, only need to store pointers of odd head, even head, odd cur and even cur
9 LRU cache
(I have no idea what I am talking about)
楼主: ztamber
狗仔卡
