LeetCode 题解,内容包括:编程技巧、线性表、字符串、栈和队列、树、排序、查找、暴力枚举法、广度优先搜索、深度优先搜索、分治法、贪心法、动态规划、图、细节实现题,每一章都介绍的非常详细

注脚

1. LeetCode 题解 (soulmachine@gmail.com) https://github.com/soulmachine/leetcode 2016-1-28 Creative Commons - - 3.0 Unported (cc by-nc-sa) http://creativecommons.org/licenses/by-nc-sa/3.0/ ACM LeetCode Online Judge(http://leetcode.com/onlinejudge) 题 C++ 11 LeetCode Online Judge : • OJ .h .cpp • Shorter is better STL • malloc()/new nullptr ① ② C++ Java GitHub GitHub https://github.com/soulmachine/leetcode http://q.weibo.com/1312378 ① http://book.douban.com/subject/2024655/ ② Algorithms Robert Sedgewick, Addison-Wesley Professional, http://book.douban.com/subject/4854123/ i

2.1 1 2.1.20 Set Matrix Zeroes . . . . 33 2.1.21 Gas Station . . . . . . . 35 2 2 2.1.22 Candy . . . . . . . . . . 36 2.1 . . . . . . . . . . . . . . . 2 2.1.23 Single Number . . . . . 37 2.1.1 Remove Duplicates 2.1.24 Single Number II . . . . 38 from Sorted Array . . . 2 2.2 . . . . . . . . . . . . . 40 2.1.2 Remove Duplicates 2.2.1 Add Two Numbers . . . 40 from Sorted Array II . . 3 2.2.2 Reverse Linked List II . 41 2.1.3 Search in Rotated 2.2.3 Partition List . . . . . . 42 Sorted Array . . . . . . 5 2.2.4 Remove Duplicates 2.1.4 Search in Rotated from Sorted List . . . . 43 Sorted Array II . . . . . 6 2.2.5 Remove Duplicates 2.1.5 Median of Two Sorted from Sorted List II . . . 44 Arrays . . . . . . . . . . 7 2.2.6 Rotate List . . . . . . . 46 2.1.6 Longest Consecutive 2.2.7 Remove Nth Node Sequence . . . . . . . . 8 From End of List . . . . 47 2.1.7 Two Sum . . . . . . . . 10 2.2.8 Swap Nodes in Pairs . . 47 2.1.8 3Sum . . . . . . . . . . 12 2.2.9 Reverse Nodes in k-Group 49 2.1.9 3Sum Closest . . . . . . 13 2.2.10 Copy List with Random 2.1.10 4Sum . . . . . . . . . . 14 Pointer . . . . . . . . . 50 2.1.11 Remove Element . . . . 18 2.2.11 Linked List Cycle . . . . 51 2.1.12 Next Permutation . . . . 19 2.2.12 Linked List Cycle II . . 52 2.1.13 Permutation Sequence . 21 2.2.13 Reorder List . . . . . . 53 2.1.14 Valid Sudoku . . . . . . 23 2.2.14 LRU Cache . . . . . . . 55 2.1.15 Trapping Rain Water . . 24 2.1.16 Rotate Image . . . . . . 27 3 57 2.1.17 Plus One . . . . . . . . 28 3.1 Valid Palindrome . . . . . . . . 57 2.1.18 Climbing Stairs . . . . . 30 3.2 Implement strStr() . . . . . . . . 58 2.1.19 Gray Code . . . . . . . 31 3.3 String to Integer (atoi) . . . . . 60 ii

3. iii 3.4 Add Binary . . . . . . . . . . . 61 5.1.5 Binary Tree Level Or- 3.5 Longest Palindromic Substring . 62 der Traversal II . . . . . 94 3.6 Regular Expression Matching . . 66 5.1.6 Binary Tree Zigzag 3.7 Wildcard Matching . . . . . . . 67 Level Order Traversal . 96 3.8 Longest Common Prefix . . . . 69 5.1.7 Recover Binary Search 3.9 Valid Number . . . . . . . . . . 70 Tree . . . . . . . . . . . 98 3.10 Integer to Roman . . . . . . . . 72 5.1.8 Same Tree . . . . . . . 99 3.11 Roman to Integer . . . . . . . . 73 5.1.9 Symmetric Tree . . . . . 100 3.12 Count and Say . . . . . . . . . . 74 5.1.10 Balanced Binary Tree . . 102 3.13 Anagrams . . . . . . . . . . . . 75 5.1.11 Flatten Binary Tree to 3.14 Simplify Path . . . . . . . . . . 76 Linked List . . . . . . . 103 5.1.12 Populating Next Right 3.15 Length of Last Word . . . . . . 77 Pointers in Each Node II 105 4 79 5.2 . . . . . . . . . 106 4.1 . . . . . . . . . . . . . . . . 79 5.2.1 Construct Binary Tree 4.1.1 Valid Parentheses . . . . 79 from Preorder and In- 4.1.2 Longest Valid Paren- order Traversal . . . . . 106 theses . . . . . . . . . . 80 5.2.2 Construct Binary Tree 4.1.3 Largest Rectangle in from Inorder and Pos- Histogram . . . . . . . . 82 torder Traversal . . . . . 107 4.1.4 Evaluate Reverse Pol- 5.3 . . . . . . . . . . . 108 ish Notation . . . . . . . 84 5.3.1 Unique Binary Search 4.2 . . . . . . . . . . . . . . . 85 Trees . . . . . . . . . . 108 5.3.2 Unique Binary Search 5 86 Trees II . . . . . . . . . 110 5.1 . . . . . . . . . 86 5.3.3 Validate Binary Search 5.1.1 Binary Tree Preorder Tree . . . . . . . . . . . 111 Traversal . . . . . . . . 86 5.3.4 Convert Sorted Array to 5.1.2 Binary Tree Inorder Binary Search Tree . . . 112 Traversal . . . . . . . . 88 5.3.5 Convert Sorted List to 5.1.3 Binary Tree Postorder Binary Search Tree . . . 113 Traversal . . . . . . . . 90 5.4 . . . . . . . . . 114 5.1.4 Binary Tree Level Or- 5.4.1 Minimum Depth of Bi- der Traversal . . . . . . 92 nary Tree . . . . . . . . 115

4.iv 5.4.2 Maximum Depth of Bi- 8.3.2 next_permu- nary Tree . . . . . . . . 116 tation() . . . . . . . . . 142 5.4.3 Path Sum . . . . . . . . 117 8.3.3 . . . . . . . . . . 143 5.4.4 Path Sum II . . . . . . . 118 8.4 Permutations II . . . . . . . . . 144 5.4.5 Binary Tree Maximum 8.4.1 next_permutation() . . . 144 Path Sum . . . . . . . . 119 8.4.2 next_permu- 5.4.6 Populating Next Right tation() . . . . . . . . . 144 Pointers in Each Node . 120 8.4.3 . . . . . . . . . . 144 5.4.7 Sum Root to Leaf Num- 8.5 Combinations . . . . . . . . . . 146 bers . . . . . . . . . . . 121 8.5.1 . . . . . . . . . . 146 8.5.2 . . . . . . . . . . 147 6 123 8.6 Letter Combinations of a Phone 6.1 Merge Sorted Array . . . . . . . 123 Number . . . . . . . . . . . . . 147 6.2 Merge Two Sorted Lists . . . . . 124 8.6.1 . . . . . . . . . . 148 6.3 Merge k Sorted Lists . . . . . . 124 8.6.2 . . . . . . . . . . 149 6.4 Insertion Sort List . . . . . . . . 125 9 150 6.5 Sort List . . . . . . . . . . . . . 126 9.1 Word Ladder . . . . . . . . . . 150 6.6 First Missing Positive . . . . . . 127 9.2 Word Ladder II . . . . . . . . . 154 6.7 Sort Colors . . . . . . . . . . . 128 9.3 Surrounded Regions . . . . . . . 162 9.4 . . . . . . . . . . . . . . . 164 7 131 9.4.1 . . . . . . . . 164 7.1 Search for a Range . . . . . . . 131 9.4.2 . . . . . . 164 7.2 Search Insert Position . . . . . . 132 9.4.3 . . . . . . . . 165 7.3 Search a 2D Matrix . . . . . . . 133 10 173 8 135 10.1 Palindrome Partitioning . . . . . 173 8.1 Subsets . . . . . . . . . . . . . 135 10.2 Unique Paths . . . . . . . . . . 176 8.1.1 . . . . . . . . . . 135 10.2.1 . . . . . . . . . . 176 8.1.2 . . . . . . . . . . 137 10.2.2 . . . . . . . . 176 8.2 Subsets II . . . . . . . . . . . . 138 10.2.3 . . . . . . . . . . 177 8.2.1 . . . . . . . . . . 138 10.2.4 . . . . . . . . 178 8.2.2 . . . . . . . . . . 141 10.3 Unique Paths II . . . . . . . . . 179 8.3 Permutations . . . . . . . . . . 142 10.3.1 . . . . . . . . 179 8.3.1 next_permutation() . . . 142 10.3.2 . . . . . . . . . . 180

5. v 10.4 N-Queens . . . . . . . . . . . . 181 13.4 Maximal Rectangle . . . . . . . 213 10.5 N-Queens II . . . . . . . . . . . 184 13.5 Best Time to Buy and Sell Stock 10.6 Restore IP Addresses . . . . . . 186 III . . . . . . . . . . . . . . . . 214 10.7 Combination Sum . . . . . . . . 188 13.6 Interleaving String . . . . . . . 215 10.8 Combination Sum II . . . . . . 189 13.7 Scramble String . . . . . . . . . 217 10.9 Generate Parentheses . . . . . . 190 13.8 Minimum Path Sum . . . . . . . 222 10.10 Sudoku Solver . . . . . . . . . 192 13.9 Edit Distance . . . . . . . . . . 224 10.11 Word Search . . . . . . . . . . 193 13.10 Decode Ways . . . . . . . . . 226 10.12 . . . . . . . . . . . . . . 195 13.11 Distinct Subsequences . . . . . 227 10.12.1 . . . . . . . 195 13.12 Word Break . . . . . . . . . . 228 10.12.2 . . . . . . 195 13.13 Word Break II . . . . . . . . . 230 10.12.3 . . . . . . . 197 14 232 10.12.4 . 197 14.1 Clone Graph . . . . . . . . . . . 232 10.12.5 . . 197 15 题 235 11 199 15.1 Reverse Integer . . . . . . . . . 235 11.1 Pow(x,n) . . . . . . . . . . . . . 199 15.2 Palindrome Number . . . . . . . 236 11.2 Sqrt(x) . . . . . . . . . . . . . . 200 15.3 Insert Interval . . . . . . . . . . 237 12 201 15.4 Merge Intervals . . . . . . . . . 238 12.1 Jump Game . . . . . . . . . . . 201 15.5 Minimum Window Substring . . 239 12.2 Jump Game II . . . . . . . . . . 202 15.6 Multiply Strings . . . . . . . . . 241 12.3 Best Time to Buy and Sell Stock 204 15.7 Substring with Concatenation 12.4 Best Time to Buy and Sell Stock II205 of All Words . . . . . . . . . . . 244 12.5 Longest Substring Without Re- 15.8 Pascal’s Triangle . . . . . . . . 245 peating Characters . . . . . . . 206 15.9 Pascal’s Triangle II . . . . . . . 246 12.6 Container With Most Water . . . 207 15.10 Spiral Matrix . . . . . . . . . . 247 15.11 Spiral Matrix II . . . . . . . . . 248 13 209 15.12 ZigZag Conversion . . . . . . 250 13.1 Triangle . . . . . . . . . . . . . 209 15.13 Divide Two Integers . . . . . . 251 13.2 Maximum Subarray . . . . . . . 210 15.14 Text Justification . . . . . . . . 253 13.3 Palindrome Partitioning II . . . 212 15.15 Max Points on a Line . . . . . 255

6.vi

7. 1 a b a==b fabs(a-b) 1e-9 x % 2 != 0 x % 2 == 1 x char char unsigned int unsigned char C++ STL Effective STL vector string vector new delete BUG delete new int** ary = new int*[row_num]; for(int i = 0; i < row_num; ++i) ary[i] = new int[col_num]; vector vector<vector<int> > ary(row_num, vector<int>(col_num, 0)); reserve 1

8. 2 题 2.1 2.1.1 Remove Duplicates from Sorted Array Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory. For example, Given input array A = [1,1,2], Your function should return length = 2, and A is now [1,2]. 1 // LeetCode, Remove Duplicates from Sorted Array // O(n) O(1) class Solution { public: int removeDuplicates(vector<int>& nums) { if (nums.empty()) return 0; int index = 0; for (int i = 1; i < nums.size(); i++) { if (nums[index] != nums[i]) nums[++index] = nums[i]; } return index + 1; } }; 2

9.2.1 3 2 // LeetCode, Remove Duplicates from Sorted Array // STL O(n) O(1) class Solution { public: int removeDuplicates(vector<int>& nums) { return distance(nums.begin(), unique(nums.begin(), nums.end())); } }; 3 // LeetCode, Remove Duplicates from Sorted Array // STL O(n) O(1) class Solution { public: int removeDuplicates(vector<int>& nums) { return distance(nums.begin(), removeDuplicates(nums.begin(), nums.end(), nums.begin()) } template<typename InIt, typename OutIt> OutIt removeDuplicates(InIt first, InIt last, OutIt output) { while (first != last) { *output++ = *first; first = upper_bound(first, last, *first); } return output; } }; 题 • Remove Duplicates from Sorted Array II §2.1.2 2.1.2 Remove Duplicates from Sorted Array II Follow up for ”Remove Duplicates”: What if duplicates are allowed at most twice? For example, Given sorted array A = [1,1,1,2,2,3], Your function should return length = 5, and A is now [1,1,2,2,3] 题 解 hashmap

10.4 2 1 // LeetCode, Remove Duplicates from Sorted Array II // O(n) O(1) // @author hex108 (https://github.com/hex108) class Solution { public: int removeDuplicates(vector<int>& nums) { if (nums.size() <= 2) return nums.size(); int index = 2; for (int i = 2; i < nums.size(); i++){ if (nums[i] != nums[index - 2]) nums[index++] = nums[i]; } return index; } }; 2 occur < 2 occur < 3 3 // LeetCode, Remove Duplicates from Sorted Array II // @author (http://weibo.com/u/1666779725) // O(n) O(1) class Solution { public: int removeDuplicates(vector<int>& nums) { const int n = nums.size(); int index = 0; for (int i = 0; i < n; ++i) { if (i > 0 && i < n - 1 && nums[i] == nums[i - 1] && nums[i] == nums[i + 1]) continue; nums[index++] = nums[i]; } return index; } }; 题 • Remove Duplicates from Sorted Array §2.1.1

11.2.1 5 2.1.3 Search in Rotated Sorted Array Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. // LeetCode, Search in Rotated Sorted Array // O(log n) O(1) class Solution { public: int search(const vector<int>& nums, int target) { int first = 0, last = nums.size(); while (first != last) { const int mid = first + (last - first) / 2; if (nums[mid] == target) return mid; if (nums[first] <= nums[mid]) { if (nums[first] <= target && target < nums[mid]) last = mid; else first = mid + 1; } else { if (nums[mid] < target && target <= nums[last-1]) first = mid + 1; else last = mid; } } return -1; } }; 题 • Search in Rotated Sorted Array II §2.1.4

12.6 2 2.1.4 Search in Rotated Sorted Array II Follow up for ”Search in Rotated Sorted Array”: What if duplicates are allowed? Would this affect the run-time complexity? How and why? Write a function to determine if a given target is in the array. 题 A[m]>=A[l], [l,m] [1,3,1,1,1] A[m]>=A[l] • A[m]>A[l] [l,m] • A[m]==A[l] l++ // LeetCode, Search in Rotated Sorted Array II // O(n) O(1) class Solution { public: bool search(const vector<int>& nums, int target) { int first = 0, last = nums.size(); while (first != last) { const int mid = first + (last - first) / 2; if (nums[mid] == target) return true; if (nums[first] < nums[mid]) { if (nums[first] <= target && target < nums[mid]) last = mid; else first = mid + 1; } else if (nums[first] > nums[mid]) { if (nums[mid] < target && target <= nums[last-1]) first = mid + 1; else last = mid; } else //skip duplicate one first++; } return false; } };

13.2.1 7 题 • Search in Rotated Sorted Array §2.1.3 2.1.5 Median of Two Sorted Arrays There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log(m + n)). 题 题 k O(m + n) 解 merge k k m pA pB A B merge sort A pA++ m++ B pB++ m++ m k O(k) O(1) k m+n O(m + n) k k k A B A B k/2 A k/2 A[k/2-1] B k/2 B[k/2-1] k k • A[k/2-1] == B[k/2-1] • A[k/2-1] > B[k/2-1] • A[k/2-1] < B[k/2-1] A[k/2-1] < B[k/2-1] A[0] A[k/2-1] A∪B top k A[k/2-1] A∪B k A k/2 A[k/2-1] > B[k/2-1] B k/2 A[k/2-1] == B[k/2-1] k A[k/2-1] B[k/2-1] • A B B[k-1] A[k-1] • k=1 min(A[0], B[0]) • A[k/2-1] == B[k/2-1] A[k/2-1] B[k/2-1]

14.8 2 // LeetCode, Median of Two Sorted Arrays // O(log(m+n)) O(log(m+n)) class Solution { public: double findMedianSortedArrays(const vector<int>& A, const vector<int>& B) { const int m = A.size(); const int n = B.size(); int total = m + n; if (total & 0x1) return find_kth(A.begin(), m, B.begin(), n, total / 2 + 1); else return (find_kth(A.begin(), m, B.begin(), n, total / 2) + find_kth(A.begin(), m, B.begin(), n, total / 2 + 1)) / 2.0; } private: static int find_kth(std::vector<int>::const_iterator A, int m, std::vector<int>::const_iterator B, int n, int k) { //always assume that m is equal or smaller than n if (m > n) return find_kth(B, n, A, m, k); if (m == 0) return *(B + k - 1); if (k == 1) return min(*A, *B); //divide k into two parts int ia = min(k / 2, m), ib = k - ia; if (*(A + ia - 1) < *(B + ib - 1)) return find_kth(A + ia, m - ia, B, n, k - ia); else if (*(A + ia - 1) > *(B + ib - 1)) return find_kth(A, m, B + ib, n - ib, k - ib); else return A[ia - 1]; } }; 题 • 2.1.6 Longest Consecutive Sequence Given an unsorted array of integers, find the length of the longest consecutive elements sequence. For example, Given [100, 4, 200, 1, 3, 2], The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4. Your algorithm should run in O(n) complexity.

15.2.1 9 O(n log n) 题 O(n) O(n) unordered_map<int, bool> used // Leet Code, Longest Consecutive Sequence // O(n) O(n) class Solution { public: int longestConsecutive(const vector<int> &nums) { unordered_map<int, bool> used; for (auto i : nums) used[i] = false; int longest = 0; for (auto i : nums) { if (used[i]) continue; int length = 1; used[i] = true; for (int j = i + 1; used.find(j) != used.end(); ++j) { used[j] = true; ++length; } for (int j = i - 1; used.find(j) != used.end(); --j) { used[j] = true; ++length; } longest = max(longest, length); } return longest; } }; 2 , union,find . . , , . unordered_- map<int, int> map . http://discuss.leetcode.com/questions/1070/

16.10 2 longest-consecutive-sequence // Leet Code, Longest Consecutive Sequence // O(n) O(n) // Author: @advancedxy class Solution { public: int longestConsecutive(vector<int> &nums) { unordered_map<int, int> map; int size = nums.size(); int l = 1; for (int i = 0; i < size; i++) { if (map.find(nums[i]) != map.end()) continue; map[nums[i]] = 1; if (map.find(nums[i] - 1) != map.end()) { l = max(l, mergeCluster(map, nums[i] - 1, nums[i])); } if (map.find(nums[i] + 1) != map.end()) { l = max(l, mergeCluster(map, nums[i], nums[i] + 1)); } } return size == 0 ? 0 : l; } private: int mergeCluster(unordered_map<int, int> &map, int left, int right) { int upper = right + map[right] - 1; int lower = left - map[left] + 1; int length = upper - lower + 1; map[upper] = length; map[lower] = length; return length; } }; 题 • 2.1.7 Two Sum Given an array of integers, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

17.2.1 11 You may assume that each input would have exactly one solution. Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2 1 O(n2 ) 2 hash O(n). 3 O(n log n) O(n) O(n log n) 题 //LeetCode, Two Sum // 2 hash // O(n) O(n) class Solution { public: vector<int> twoSum(vector<int> &nums, int target) { unordered_map<int, int> mapping; vector<int> result; for (int i = 0; i < nums.size(); i++) { mapping[nums[i]] = i; } for (int i = 0; i < nums.size(); i++) { const int gap = target - nums[i]; if (mapping.find(gap) != mapping.end() && mapping[gap] > i) { result.push_back(i + 1); result.push_back(mapping[gap] + 1); break; } } return result; } }; 题 • 3Sum, §2.1.8 • 3Sum Closest, §2.1.9 • 4Sum, §2.1.10

18.12 2 2.1.8 3Sum Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: • Elements in a triplet (a, b, c) must be in non-descending order. (ie, a ≤ b ≤ c) • The solution set must not contain duplicate triplets. For example, given array S = {-1 0 1 2 -1 -4}. A solution set is: (-1, 0, 1) (-1, -1, 2) O(n2 ) k-sum k−2 O(max{n log n, n k−1 }) // LeetCode, 3Sum // O(n^2) O(1) class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> result; if (nums.size() < 3) return result; sort(nums.begin(), nums.end()); const int target = 0; auto last = nums.end(); for (auto i = nums.begin(); i < last-2; ++i) { auto j = i+1; if (i > nums.begin() && *i == *(i-1)) continue; auto k = last-1; while (j < k) { if (*i + *j + *k < target) { ++j; while(*j == *(j - 1) && j < k) ++j; } else if (*i + *j + *k > target) { --k; while(*k == *(k + 1) && j < k) --k; } else { result.push_back({ *i, *j, *k }); ++j;

19.2.1 13 --k; while(*j == *(j - 1) && *k == *(k + 1) && j < k) ++j; } } } return result; } }; 题 • Two sum, §2.1.7 • 3Sum Closest, §2.1.9 • 4Sum, §2.1.10 2.1.9 3Sum Closest Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution. For example, given array S = {-1 2 1 -4}, and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2). O(n2 ) // LeetCode, 3Sum Closest // O(n^2) O(1) class Solution { public: int threeSumClosest(vector<int>& nums, int target) { int result = 0; int min_gap = INT_MAX; sort(nums.begin(), nums.end()); for (auto a = nums.begin(); a != prev(nums.end(), 2); ++a) { auto b = next(a); auto c = prev(nums.end()); while (b < c) { const int sum = *a + *b + *c; const int gap = abs(sum - target);

20.14 2 if (gap < min_gap) { result = sum; min_gap = gap; } if (sum < target) ++b; else --c; } } return result; } }; 题 • Two sum, §2.1.7 • 3Sum, §2.1.8 • 4Sum, §2.1.10 2.1.10 4Sum Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. Note: • Elements in a quadruplet (a, b, c, d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d) • The solution set must not contain duplicate quadruplets. For example, given array S = {1 0 -1 0 -2 2}, and target = 0. A solution set is: (-1, 0, 0, 1) (-2, -1, 1, 2) (-2, 0, 0, 2) O(n3 ) hashmap O(n3 ) 3Sum

21.2.1 15 // LeetCode, 4Sum // O(n^3) O(1) class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> result; if (nums.size() < 4) return result; sort(nums.begin(), nums.end()); auto last = nums.end(); for (auto a = nums.begin(); a < prev(last, 3); ++a) { for (auto b = next(a); b < prev(last, 2); ++b) { auto c = next(b); auto d = prev(last); while (c < d) { if (*a + *b + *c + *d < target) { ++c; } else if (*a + *b + *c + *d > target) { --d; } else { result.push_back({ *a, *b, *c, *d }); ++c; --d; } } } } sort(result.begin(), result.end()); result.erase(unique(result.begin(), result.end()), result.end()); return result; } }; map // LeetCode, 4Sum // hashmap // O(n^2) O(n^4) O(n^2) class Solution { public: vector<vector<int> > fourSum(vector<int> &nums, int target) { vector<vector<int>> result; if (nums.size() < 4) return result; sort(nums.begin(), nums.end()); unordered_map<int, vector<pair<int, int> > > cache; for (size_t a = 0; a < nums.size(); ++a) { for (size_t b = a + 1; b < nums.size(); ++b) { cache[nums[a] + nums[b]].push_back(pair<int, int>(a, b)); } }

22.16 2 for (int c = 0; c < nums.size(); ++c) { for (size_t d = c + 1; d < nums.size(); ++d) { const int key = target - nums[c] - nums[d]; if (cache.find(key) == cache.end()) continue; const auto& vec = cache[key]; for (size_t k = 0; k < vec.size(); ++k) { if (c <= vec[k].second) continue; // result.push_back( { nums[vec[k].first], nums[vec[k].second], nums[c], nums[d] }); } } } sort(result.begin(), result.end()); result.erase(unique(result.begin(), result.end()), result.end()); return result; } }; multimap // LeetCode, 4Sum // hashmap // O(n^2) O(n^2) // @author (http://weibo.com/luangong) class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> result; if (nums.size() < 4) return result; sort(nums.begin(), nums.end()); unordered_multimap<int, pair<int, int>> cache; for (int i = 0; i + 1 < nums.size(); ++i) for (int j = i + 1; j < nums.size(); ++j) cache.insert(make_pair(nums[i] + nums[j], make_pair(i, j))); for (auto i = cache.begin(); i != cache.end(); ++i) { int x = target - i->first; auto range = cache.equal_range(x); for (auto j = range.first; j != range.second; ++j) { auto a = i->second.first; auto b = i->second.second; auto c = j->second.first; auto d = j->second.second; if (a != c && a != d && b != c && b != d) { vector<int> vec = { nums[a], nums[b], nums[c], nums[d] }; sort(vec.begin(), vec.end()); result.push_back(vec); }

23.2.1 17 } } sort(result.begin(), result.end()); result.erase(unique(result.begin(), result.end()), result.end()); return result; } }; 4 // LeetCode, 4Sum // O(n^3logn) O(1) // 1 class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> result; if (nums.size() < 4) return result; sort(nums.begin(), nums.end()); auto last = nums.end(); for (auto a = nums.begin(); a < prev(last, 3); a = upper_bound(a, prev(last, 3), *a)) { for (auto b = next(a); b < prev(last, 2); b = upper_bound(b, prev(last, 2), *b)) { auto c = next(b); auto d = prev(last); while (c < d) { if (*a + *b + *c + *d < target) { c = upper_bound(c, d, *c); } else if (*a + *b + *c + *d > target) { d = prev(lower_bound(c, d, *d)); } else { result.push_back({ *a, *b, *c, *d }); c = upper_bound(c, d, *c); d = prev(lower_bound(c, d, *d)); } } } } return result; } }; 题 • Two sum, §2.1.7 • 3Sum, §2.1.8 • 3Sum Closest, §2.1.9

24.18 2 2.1.11 Remove Element Given an array and a value, remove all instances of that value in place and return the new length. The order of elements can be changed. It doesn’t matter what you leave beyond the new length. 1 // LeetCode, Remove Element // O(n) O(1) class Solution { public: int removeElement(vector<int>& nums, int target) { int index = 0; for (int i = 0; i < nums.size(); ++i) { if (nums[i] != target) { nums[index++] = nums[i]; } } return index; } }; 2 // LeetCode, Remove Element // remove() O(n) O(1) class Solution { public: int removeElement(vector<int>& nums, int target) { return distance(nums.begin(), remove(nums.begin(), nums.end(), target)); } }; 题 •

25.2.1 19 2.1.12 Next Permutation Implement next permutation, which rearranges numbers into the lexicographically next greater permu- tation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascend- ing order). The replacement must be in-place, do not allocate extra memory. Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column. 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1 2-1 http://fisherlei.blogspot.com/2012/12/leetcode-next-permutation.html 2-1

26.20 2 // LeetCode, Next Permutation // O(n) O(1) class Solution { public: void nextPermutation(vector<int> &nums) { next_permutation(nums.begin(), nums.end()); } template<typename BidiIt> bool next_permutation(BidiIt first, BidiIt last) { // Get a reversed range to simplify reversed traversal. const auto rfirst = reverse_iterator<BidiIt>(last); const auto rlast = reverse_iterator<BidiIt>(first); // Begin from the second last element to the first element. auto pivot = next(rfirst); // Find `pivot`, which is the first element that is no less than its // successor. `Prev` is used since `pivort` is a `reversed_iterator`. while (pivot != rlast && *pivot >= *prev(pivot)) ++pivot; // No such elemenet found, current sequence is already the largest // permutation, then rearrange to the first permutation and return false. if (pivot == rlast) { reverse(rfirst, rlast); return false; } // Scan from right to left, find the first element that is greater than // `pivot`. auto change = find_if(rfirst, pivot, bind1st(less<int>(), *pivot)); swap(*change, *pivot); reverse(rfirst, pivot); return true; } }; 题 • Permutation Sequence, §2.1.13 • Permutations, §8.3 • Permutations II, §8.4 • Combinations, §8.5

27.2.1 21 2.1.13 Permutation Sequence The set [1,2,3, ,n] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3): "123" "132" "213" "231" "312" "321" Given n and k, return the kth permutation sequence. Note: Given n will be between 1 and 9 inclusive. k−1 next_permutation() k k n k a1 , a2 , a3 , ..., an a1 a1 a2 , a3 , ..., an , n−1 n−1 (n − 1)! a1 = k/(n − 1)! a2 , a3 , ..., an k2 = k%(n − 1)! a2 = k2 /(n − 2)! ··· kn−1 = kn−2 %2! an−1 = kn−1 /1! an = 0 next_permutation() // LeetCode, Permutation Sequence // next_permutation() TLE class Solution { public: string getPermutation(int n, int k) { string s(n, '0'); for (int i = 0; i < n; ++i)

28.22 2 s[i] += i+1; for (int i = 0; i < k-1; ++i) next_permutation(s.begin(), s.end()); return s; } template<typename BidiIt> bool next_permutation(BidiIt first, BidiIt last) { // 题 Next Permutation } }; // LeetCode, Permutation Sequence // O(n) O(1) class Solution { public: string getPermutation(int n, int k) { string s(n, '0'); string result; for (int i = 0; i < n; ++i) s[i] += i + 1; return kth_permutation(s, k); } private: int factorial(int n) { int result = 1; for (int i = 1; i <= n; ++i) result *= i; return result; } // seq template<typename Sequence> Sequence kth_permutation(const Sequence &seq, int k) { const int n = seq.size(); Sequence S(seq); Sequence result; int base = factorial(n - 1); --k; // 0 for (int i = n - 1; i > 0; k %= base, base /= i, --i) { auto a = next(S.begin(), k / base); result.push_back(*a); S.erase(a); } result.push_back(S[0]); // return result; }

29.2.1 23 }; 题 • Next Permutation, §2.1.12 • Permutations, §8.3 • Permutations II, §8.4 • Combinations, §8.5 2.1.14 Valid Sudoku Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules http://sudoku.com.au/TheRules.aspx . The Sudoku board could be partially filled, where empty cells are filled with the character '.'. 2-2 A partially filled sudoku which is valid 题 // LeetCode, Valid Sudoku // O(n^2) O(1) class Solution { public: bool isValidSudoku(const vector<vector<char>>& board) { bool used[9];

30.24 2 for (int i = 0; i < 9; ++i) { fill(used, used + 9, false); for (int j = 0; j < 9; ++j) // if (!check(board[i][j], used)) return false; fill(used, used + 9, false); for (int j = 0; j < 9; ++j) // if (!check(board[j][i], used)) return false; } for (int r = 0; r < 3; ++r) // 9 for (int c = 0; c < 3; ++c) { fill(used, used + 9, false); for (int i = r * 3; i < r * 3 + 3; ++i) for (int j = c * 3; j < c * 3 + 3; ++j) if (!check(board[i][j], used)) return false; } return true; } bool check(char ch, bool used[9]) { if (ch == '.') return true; if (used[ch - '1']) return false; return used[ch - '1'] = true; } }; 题 • Sudoku Solver, §10.10 2.1.15 Trapping Rain Water Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

31.2.1 25 2-3 Trapping Rain Water min(max_left, max_- right) - height 1. 2. 3. 1. 2. 3. 1 // LeetCode, Trapping Rain Water // 1 O(n) O(n) class Solution { public: int trap(const vector<int>& A) { const int n = A.size(); int *max_left = new int[n](); int *max_right = new int[n](); for (int i = 1; i < n; i++) { max_left[i] = max(max_left[i - 1], A[i - 1]); max_right[n - 1 - i] = max(max_right[n - i], A[n - i]); } int sum = 0; for (int i = 0; i < n; i++) {

32.26 2 int height = min(max_left[i], max_right[i]); if (height > A[i]) { sum += height - A[i]; } } delete[] max_left; delete[] max_right; return sum; } }; 2 // LeetCode, Trapping Rain Water // 2 O(n) O(1) class Solution { public: int trap(const vector<int>& A) { const int n = A.size(); int max = 0; // for (int i = 0; i < n; i++) if (A[i] > A[max]) max = i; int water = 0; for (int i = 0, peak = 0; i < max; i++) if (A[i] > peak) peak = A[i]; else water += peak - A[i]; for (int i = n - 1, top = 0; i > max; i--) if (A[i] > top) top = A[i]; else water += top - A[i]; return water; } }; 3 解 // LeetCode, Trapping Rain Water // // // O(n) O(n) class Solution { public: int trap(const vector<int>& A) { const int n = A.size(); stack<pair<int, int>> s; int water = 0; for (int i = 0; i < n; ++i) {

33.2.1 27 int height = 0; while (!s.empty()) { // int bar = s.top().first; int pos = s.top().second; // bar, height, A[i] water += (min(bar, A[i]) - height) * (i - pos - 1); height = bar; if (A[i] < bar) // break; else s.pop(); // } s.push(make_pair(A[i], i)); } return water; } }; 题 • Container With Most Water, §12.6 • Largest Rectangle in Histogram, §4.1.3 2.1.16 Rotate Image You are given an n × n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). Follow up: Could you do this in-place? 2-4 Rotate Image

34.28 2 1 // LeetCode, Rotate Image // 1 O(n^2) O(1) class Solution { public: void rotate(vector<vector<int>>& matrix) { const int n = matrix.size(); for (int i = 0; i < n; ++i) // for (int j = 0; j < n - i; ++j) swap(matrix[i][j], matrix[n - 1 - j][n - 1 - i]); for (int i = 0; i < n / 2; ++i) // for (int j = 0; j < n; ++j) swap(matrix[i][j], matrix[n - 1 - i][j]); } }; 2 // LeetCode, Rotate Image // 2 O(n^2) O(1) class Solution { public: void rotate(vector<vector<int>>& matrix) { const int n = matrix.size(); for (int i = 0; i < n / 2; ++i) // for (int j = 0; j < n; ++j) swap(matrix[i][j], matrix[n - 1 - i][j]); for (int i = 0; i < n; ++i) // for (int j = i + 1; j < n; ++j) swap(matrix[i][j], matrix[j][i]); } }; 题 • 2.1.17 Plus One Given a number represented as an array of digits, plus one to the number.

35.2.1 29 1 // LeetCode, Plus One // O(n) O(1) class Solution { public: vector<int> plusOne(vector<int> &digits) { add(digits, 1); return digits; } private: // 0 <= digit <= 9 void add(vector<int> &digits, int digit) { int c = digit; // carry, for (auto it = digits.rbegin(); it != digits.rend(); ++it) { *it += c; c = *it / 10; *it %= 10; } if (c > 0) digits.insert(digits.begin(), 1); } }; 2 // LeetCode, Plus One // O(n) O(1) class Solution { public: vector<int> plusOne(vector<int> &digits) { add(digits, 1); return digits; } private: // 0 <= digit <= 9 void add(vector<int> &digits, int digit) { int c = digit; // carry, for_each(digits.rbegin(), digits.rend(), [&c](int &d){ d += c; c = d / 10; d %= 10; }); if (c > 0) digits.insert(digits.begin(), 1);

36.30 2 } }; 题 • 2.1.18 Climbing Stairs You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? f (n) n n • n−1 1 • n−1 2 f (n) = f (n − 1) + f (n − 2) 1 2 [( √ )n ( √ )n ] 1 1+ 5 1− 5 3 an = √ − 5 2 2 // LeetCode, Climbing Stairs // O(n) O(1) class Solution { public: int climbStairs(int n) { int prev = 0; int cur = 1; for(int i = 1; i <= n ; ++i){ int tmp = cur; cur += prev; prev = tmp; } return cur; } };

37.2.1 31 // LeetCode, Climbing Stairs // O(1) O(1) class Solution { public: int climbStairs(int n) { const double s = sqrt(5); return floor((pow((1+s)/2, n+1) + pow((1-s)/2, n+1))/s + 0.5); } }; 题 • Decode Ways, §13.10 2.1.19 Gray Code The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0. For example, given n = 2, return [0,1,3,2]. Its gray code sequence is: 00 - 0 01 - 1 11 - 3 10 - 2 Note: • For a given n, a gray code sequence is not uniquely defined. • For example, [0,2,3,1] is also a valid gray code sequence according to the above definition. • For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that. (Gray Code) http://en.wikipedia.org/wiki/Gray_code g0 = b0 , gi = bi ⊕ bi−1 1001 1 1 2 0 1 2 2 0 3 0 0 3 3 0 4 1 1 4 1101 b0 = g0 , bi = gi ⊕ bi−1

38.32 2 1000 1 1 1 2 0 1 2 2 1 3 0 1 3 3 1 4 0 1 4 1111 n n ⊕ (n/2) 题 n 1 0 ∼ 2n − 1 2 n n−1 §2-5 2-5 The first few steps of the reflect-and-prefix method. // LeetCode, Gray Code // O(2^n) O(1) class Solution { public: vector<int> grayCode(int n) { vector<int> result; const size_t size = 1 << n; // 2^n result.reserve(size); for (size_t i = 0; i < size; ++i) result.push_back(binary_to_gray(i)); return result; } private: static unsigned int binary_to_gray(unsigned int n) { return n ^ (n >> 1); } };

39.2.1 33 Reflect-and-prefix method // LeetCode, Gray Code // reflect-and-prefix method // O(2^n) O(1) class Solution { public: vector<int> grayCode(int n) { vector<int> result; result.reserve(1<<n); result.push_back(0); for (int i = 0; i < n; i++) { const int highest_bit = 1 << i; for (int j = result.size() - 1; j >= 0; j--) // result.push_back(highest_bit | result[j]); } return result; } }; 题 • 2.1.20 Set Matrix Zeroes Given a m × n matrix, if an element is 0, set its entire row and column to 0. Do it in place. Follow up: Did you use extra space? A straight forward solution using O(mn) space is probably a bad idea. A simple improvement uses O(m + n) space, but still not the best solution. Could you devise a constant space solution? O(m + n) bool 0 1 // LeetCode, Set Matrix Zeroes // O(m*n) O(m+n) class Solution { public: void setZeroes(vector<vector<int> > &matrix) { const size_t m = matrix.size(); const size_t n = matrix[0].size();

40.34 2 vector<bool> row(m, false); // 0 vector<bool> col(n, false); // 0 for (size_t i = 0; i < m; ++i) { for (size_t j = 0; j < n; ++j) { if (matrix[i][j] == 0) { row[i] = col[j] = true; } } } for (size_t i = 0; i < m; ++i) { if (row[i]) fill(&matrix[i][0], &matrix[i][0] + n, 0); } for (size_t j = 0; j < n; ++j) { if (col[j]) { for (size_t i = 0; i < m; ++i) { matrix[i][j] = 0; } } } } }; 2 // LeetCode, Set Matrix Zeroes // O(m*n) O(1) class Solution { public: void setZeroes(vector<vector<int> > &matrix) { const size_t m = matrix.size(); const size_t n = matrix[0].size(); bool row_has_zero = false; // 0 bool col_has_zero = false; // 0 for (size_t i = 0; i < n; i++) if (matrix[0][i] == 0) { row_has_zero = true; break; } for (size_t i = 0; i < m; i++) if (matrix[i][0] == 0) { col_has_zero = true; break; } for (size_t i = 1; i < m; i++) for (size_t j = 1; j < n; j++) if (matrix[i][j] == 0) { matrix[0][j] = 0;

41.2.1 35 matrix[i][0] = 0; } for (size_t i = 1; i < m; i++) for (size_t j = 1; j < n; j++) if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0; if (row_has_zero) for (size_t i = 0; i < n; i++) matrix[0][i] = 0; if (col_has_zero) for (size_t i = 0; i < m; i++) matrix[i][0] = 0; } }; 题 • 2.1.21 Gas Station There are N gas stations along a circular route, where the amount of gas at station i is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations. Return the starting gas station’s index if you can travel around the circuit once, otherwise return -1. Note: The solution is guaranteed to be unique. O(N 2 ) 解 O(N ) 解 sum total 解 sum -1 // LeetCode, Gas Station // O(n) O(1) class Solution { public: int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { int total = 0; int j = -1; for (int i = 0, sum = 0; i < gas.size(); ++i) { sum += gas[i] - cost[i]; total += gas[i] - cost[i];

42.36 2 if (sum < 0) { j = i; sum = 0; } } return total >= 0 ? j + 1 : -1; } }; 题 • 2.1.22 Candy There are N children standing in a line. Each child is assigned a rating value. You are giving candies to these children subjected to the following requirements: • Each child must have at least one candy. • Children with a higher rating get more candies than their neighbors. What is the minimum candies you must give? // LeetCode, Candy // O(n) O(n) class Solution { public: int candy(vector<int> &ratings) { const int n = ratings.size(); vector<int> increment(n); // for (int i = 1, inc = 1; i < n; i++) { if (ratings[i] > ratings[i - 1]) increment[i] = max(inc++, increment[i]); else inc = 1; } for (int i = n - 2, inc = 1; i >= 0; i--) { if (ratings[i] > ratings[i + 1])

43.2.1 37 increment[i] = max(inc++, increment[i]); else inc = 1; } // n return accumulate(&increment[0], &increment[0]+n, n); } }; // LeetCode, Candy // O(n) O(n) // @author fancymouse (http://weibo.com/u/1928162822) class Solution { public: int candy(const vector<int>& ratings) { vector<int> f(ratings.size()); int sum = 0; for (int i = 0; i < ratings.size(); ++i) sum += solve(ratings, f, i); return sum; } int solve(const vector<int>& ratings, vector<int>& f, int i) { if (f[i] == 0) { f[i] = 1; if (i > 0 && ratings[i] > ratings[i - 1]) f[i] = max(f[i], solve(ratings, f, i - 1) + 1); if (i < ratings.size() - 1 && ratings[i] > ratings[i + 1]) f[i] = max(f[i], solve(ratings, f, i + 1) + 1); } return f[i]; } }; 题 • 2.1.23 Single Number Given an array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

44.38 2 1 // LeetCode, Single Number // O(n) O(1) class Solution { public: int singleNumber(vector<int>& nums) { int x = 0; for (auto i : nums) { x ^= i; } return x; } }; 2 // LeetCode, Single Number // O(n) O(1) class Solution { public: int singleNumber(vector<int>& nums) { return accumulate(nums.begin(), nums.end(), 0, bit_xor<int>()); } }; 题 • Single Number II, §2.1.24 2.1.24 Single Number II Given an array of integers, every element appears three times except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? 题 题 Single Number 1 sizeof(int) count[sizeof(int)] count[i] i 1 count[i] 3

45.2.1 39 2 one 1 1 mod 3 1 two 1 2 mod 3 2 one two 1 1 3 one 1 // LeetCode, Single Number II // 1 O(n) O(1) class Solution { public: int singleNumber(vector<int>& nums) { const int W = sizeof(int) * 8; // bit int count[W]; // count[i] i 1 fill_n(&count[0], W, 0); for (int i = 0; i < nums.size(); i++) { for (int j = 0; j < W; j++) { count[j] += (nums[i] >> j) & 1; count[j] %= 3; } } int result = 0; for (int i = 0; i < W; i++) { result += (count[i] << i); } return result; } }; 2 // LeetCode, Single Number II // 2 O(n) O(1) class Solution { public: int singleNumber(vector<int>& nums) { int one = 0, two = 0, three = 0; for (auto i : nums) { two |= (one & i); one ^= i; three = ~(one & two); one &= three; two &= three; } return one; } };

46.40 2 题 • Single Number, §2.1.23 2.2 // struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) { } }; 2.2.1 Add Two Numbers You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Add Binary §3.4 // LeetCode, Add Two Numbers // Add Binary // O(m+n) O(1) class Solution { public: ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) { ListNode dummy(-1); // int carry = 0; ListNode *prev = &dummy; for (ListNode *pa = l1, *pb = l2; pa != nullptr || pb != nullptr; pa = pa == nullptr ? nullptr : pa->next, pb = pb == nullptr ? nullptr : pb->next, prev = prev->next) { const int ai = pa == nullptr ? 0 : pa->val; const int bi = pb == nullptr ? 0 : pb->val; const int value = (ai + bi + carry) % 10; carry = (ai + bi + carry) / 10;

47.2.2 41 prev->next = new ListNode(value); // } if (carry > 0) prev->next = new ListNode(carry); return dummy.next; } }; 题 • Add Binary, §3.4 2.2.2 Reverse Linked List II Reverse a linked list from position m to n. Do it in-place and in one-pass. For example: Given 1->2->3->4->5->nullptr, m = 2 and n = 4, return 1->4->3->2->5->nullptr. Note: Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list. 题 15 bug free // LeetCode, Reverse Linked List II // O(n) O(1) class Solution { public: ListNode *reverseBetween(ListNode *head, int m, int n) { ListNode dummy(-1); dummy.next = head; ListNode *prev = &dummy; for (int i = 0; i < m-1; ++i) prev = prev->next; ListNode* const head2 = prev; prev = head2->next; ListNode *cur = prev->next; for (int i = m; i < n; ++i) { prev->next = cur->next; cur->next = head2->next; head2->next = cur; // cur = prev->next; }

48.42 2 return dummy.next; } }; 题 • 2.2.3 Partition List Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions. For example, Given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5. // LeetCode, Partition List // O(n) O(1) class Solution { public: ListNode* partition(ListNode* head, int x) { ListNode left_dummy(-1); // ListNode right_dummy(-1); // auto left_cur = &left_dummy; auto right_cur = &right_dummy; for (ListNode *cur = head; cur; cur = cur->next) { if (cur->val < x) { left_cur->next = cur; left_cur = cur; } else { right_cur->next = cur; right_cur = cur; } } left_cur->next = right_dummy.next; right_cur->next = nullptr;

49.2.2 43 return left_dummy.next; } }; 题 • 2.2.4 Remove Duplicates from Sorted List Given a sorted linked list, delete all duplicates such that each element appear only once. For example, Given 1->1->2, return 1->2. Given 1->1->2->3->3, return 1->2->3. // LeetCode, Remove Duplicates from Sorted List // O(n) O(1) class Solution { public: ListNode *deleteDuplicates(ListNode *head) { if (!head) return head; ListNode dummy(head->val + 1); // head dummy.next = head; recur(&dummy, head); return dummy.next; } private: static void recur(ListNode *prev, ListNode *cur) { if (cur == nullptr) return; if (prev->val == cur->val) { // head prev->next = cur->next; delete cur; recur(prev, prev->next); } else { recur(prev->next, cur->next); } } };

50.44 2 // LeetCode, Remove Duplicates from Sorted List // O(n) O(1) class Solution { public: ListNode *deleteDuplicates(ListNode *head) { if (head == nullptr) return nullptr; for (ListNode *prev = head, *cur = head->next; cur; cur = prev->next) { if (prev->val == cur->val) { prev->next = cur->next; delete cur; } else { prev = cur; } } return head; } }; 题 • Remove Duplicates from Sorted List II §2.2.5 2.2.5 Remove Duplicates from Sorted List II Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. For example, Given 1->2->3->3->4->4->5, return 1->2->5. Given 1->1->1->2->3, return 2->3. // LeetCode, Remove Duplicates from Sorted List II // O(n) O(1) class Solution { public: ListNode *deleteDuplicates(ListNode *head) { if (!head || !head->next) return head;

51.2.2 45 ListNode *p = head->next; if (head->val == p->val) { while (p && head->val == p->val) { ListNode *tmp = p; p = p->next; delete tmp; } delete head; return deleteDuplicates(p); } else { head->next = deleteDuplicates(head->next); return head; } } }; // LeetCode, Remove Duplicates from Sorted List II // O(n) O(1) class Solution { public: ListNode *deleteDuplicates(ListNode *head) { if (head == nullptr) return head; ListNode dummy(INT_MIN); // dummy.next = head; ListNode *prev = &dummy, *cur = head; while (cur != nullptr) { bool duplicated = false; while (cur->next != nullptr && cur->val == cur->next->val) { duplicated = true; ListNode *temp = cur; cur = cur->next; delete temp; } if (duplicated) { // ListNode *temp = cur; cur = cur->next; delete temp; continue; } prev->next = cur; prev = prev->next; cur = cur->next; } prev->next = cur; return dummy.next; } };

52.46 2 题 • Remove Duplicates from Sorted List §2.2.4 2.2.6 Rotate List Given a list, rotate the list to the right by k places, where k is non-negative. For example: Given 1->2->3->4->5->nullptr and k = 2, return 4->5->1->2->3->nullptr. len k len k% = len next len − k // LeetCode, Remove Rotate List // O(n) O(1) class Solution { public: ListNode *rotateRight(ListNode *head, int k) { if (head == nullptr || k == 0) return head; int len = 1; ListNode* p = head; while (p->next) { // len++; p = p->next; } k = len - k % len; p->next = head; // for(int step = 0; step < k; step++) { p = p->next; // } head = p->next; // p->next = nullptr; // return head; } }; 题 •

53.2.2 47 2.2.7 Remove Nth Node From End of List Given a linked list, remove the nth node from the end of list and return its head. For example, Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5. Note: • Given n will always be valid. • Try to do this in one pass. p, q q n p q q p->next // LeetCode, Remove Nth Node From End of List // O(n) O(1) class Solution { public: ListNode *removeNthFromEnd(ListNode *head, int n) { ListNode dummy{-1, head}; ListNode *p = &dummy, *q = &dummy; for (int i = 0; i < n; i++) // q n q = q->next; while(q->next) { // p = p->next; q = q->next; } ListNode *tmp = p->next; p->next = p->next->next; delete tmp; return dummy.next; } }; 题 • 2.2.8 Swap Nodes in Pairs Given a linked list, swap every two adjacent nodes and return its head.

54.48 2 For example, Given 1->2->3->4, you should return the list as 2->1->4->3. Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed. // LeetCode, Swap Nodes in Pairs // O(n) O(1) class Solution { public: ListNode *swapPairs(ListNode *head) { if (head == nullptr || head->next == nullptr) return head; ListNode dummy(-1); dummy.next = head; for(ListNode *prev = &dummy, *cur = prev->next, *next = cur->next; next; prev = cur, cur = cur->next, next = cur ? cur->next: nullptr) { prev->next = next; cur->next = next->next; next->next = cur; } return dummy.next; } }; 题 // LeetCode, Swap Nodes in Pairs // O(n) O(1) class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode* p = head; while (p && p->next) { swap(p->val, p->next->val); p = p->next->next; } return head; } }; 题 • Reverse Nodes in k-Group, §2.2.9

55.2.2 49 2.2.9 Reverse Nodes in k-Group Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is. You may not alter the values in the nodes, only nodes itself may be changed. Only constant memory is allowed. For example, Given this linked list: 1->2->3->4->5 For k = 2, you should return: 2->1->4->3->5 For k = 3, you should return: 3->2->1->4->5 // LeetCode, Reverse Nodes in k-Group // O(n) O(1) class Solution { public: ListNode *reverseKGroup(ListNode *head, int k) { if (head == nullptr || head->next == nullptr || k < 2) return head; ListNode *next_group = head; for (int i = 0; i < k; ++i) { if (next_group) next_group = next_group->next; else return head; } // next_group is the head of next group // new_next_group is the new head of next group after reversion ListNode *new_next_group = reverseKGroup(next_group, k); ListNode *prev = NULL, *cur = head; while (cur != next_group) { ListNode *next = cur->next; cur->next = prev ? prev : new_next_group; prev = cur; cur = next; } return prev; // prev will be the new head of this group } };

56.50 2 // LeetCode, Reverse Nodes in k-Group // O(n) O(1) class Solution { public: ListNode *reverseKGroup(ListNode *head, int k) { if (head == nullptr || head->next == nullptr || k < 2) return head; ListNode dummy(-1); dummy.next = head; for(ListNode *prev = &dummy, *end = head; end; end = prev->next) { for (int i = 1; i < k && end; i++) end = end->next; if (end == nullptr) break; // k prev = reverse(prev, prev->next, end); } return dummy.next; } // prev first , [begin, end] null // 1 ListNode* reverse(ListNode *prev, ListNode *begin, ListNode *end) { ListNode *end_next = end->next; for (ListNode *p = begin, *cur = p->next, *next = cur->next; cur != end_next; p = cur, cur = next, next = next ? next->next : nullptr) { cur->next = p; } begin->next = end_next; prev->next = end; return begin; } }; 题 • Swap Nodes in Pairs, §2.2.8 2.2.10 Copy List with Random Pointer A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list.

57.2.2 51 // LeetCode, Copy List with Random Pointer // O(n) O(1) class Solution { public: RandomListNode *copyRandomList(RandomListNode *head) { for (RandomListNode* cur = head; cur != nullptr; ) { RandomListNode* node = new RandomListNode(cur->label); node->next = cur->next; cur->next = node; cur = node->next; } for (RandomListNode* cur = head; cur != nullptr; ) { if (cur->random != NULL) cur->next->random = cur->random->next; cur = cur->next->next; } // RandomListNode dummy(-1); for (RandomListNode* cur = head, *new_cur = &dummy; cur != nullptr; ) { new_cur->next = cur->next; new_cur = new_cur->next; cur->next = cur->next->next; cur = cur->next; } return dummy.next; } }; 题 • 2.2.11 Linked List Cycle Given a linked list, determine if it has a cycle in it. Follow up: Can you solve it without using extra space?

58.52 2 unordered_map<int, bool> visited O(n) O(N ) O(n) O(1) http://leetcode.com/2010/09/detecting-loop-in-singly-linked-list.html //LeetCode, Linked List Cycle // O(n) O(1) class Solution { public: bool hasCycle(ListNode *head) { // ListNode *slow = head, *fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) return true; } return false; } }; 题 • Linked List Cycle II, §2.2.12 2.2.12 Linked List Cycle II Given a linked list, return the node where the cycle begins. If there is no cycle, return null. Follow up: Can you solve it without using extra space? fast slow slow fast n (1 ≤ n) slow s fast 2s fast s n r 2s = s + nr s = nr

59.2.2 53 L a x x+a = nr = (n–1)r + r = (n − 1)r + L − x x = (n − 1)r + (L–x–a) L–x–a n−1 + head slow2 //LeetCode, Linked List Cycle II // O(n) O(1) class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode *slow = head, *fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) { ListNode *slow2 = head; while (slow2 != slow) { slow2 = slow2->next; slow = slow->next; } return slow2; } } return nullptr; } }; 题 • Linked List Cycle, §2.2.11 2.2.13 Reorder List Given a singly linked list L : L0 → L1 → · · · → Ln−1 → Ln , reorder it to: L0 → Ln → L1 → Ln−1 → L2 → Ln−2 → · · · You must do this in-place without altering the nodes’ values. For example, Given {1,2,3,4}, reorder it to {1,4,2,3}.

60.54 2 题 in-place O(1) reverse // LeetCode, Reorder List // O(n) O(1) class Solution { public: void reorderList(ListNode *head) { if (head == nullptr || head->next == nullptr) return; ListNode *slow = head, *fast = head, *prev = nullptr; while (fast && fast->next) { prev = slow; slow = slow->next; fast = fast->next->next; } prev->next = nullptr; // cut at middle slow = reverse(slow); // merge two lists ListNode *curr = head; while (curr->next) { ListNode *tmp = curr->next; curr->next = slow; slow = slow->next; curr->next->next = tmp; curr = tmp; } curr->next = slow; } ListNode* reverse(ListNode *head) { if (head == nullptr || head->next == nullptr) return head; ListNode *prev = head; for (ListNode *curr = head->next, *next = curr->next; curr; prev = curr, curr = next, next = next ? next->next : nullptr) { curr->next = prev; } head->next = nullptr; return prev; } };

61.2.2 55 题 • 2.2.14 LRU Cache Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set. get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item. (std::list) (std::unordered_map) • O(1) • • • hash • cache size capacity hash // LeetCode, LRU Cache // O(logn) O(n) class LRUCache{ private: struct CacheNode { int key; int value; CacheNode(int k, int v) :key(k), value(v){} }; public: LRUCache(int capacity) { this->capacity = capacity; }

62.56 2 int get(int key) { if (cacheMap.find(key) == cacheMap.end()) return -1; // map cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]); cacheMap[key] = cacheList.begin(); return cacheMap[key]->value; } void set(int key, int value) { if (cacheMap.find(key) == cacheMap.end()) { if (cacheList.size() == capacity) { // cacheMap.erase(cacheList.back().key); cacheList.pop_back(); } // , map cacheList.push_front(CacheNode(key, value)); cacheMap[key] = cacheList.begin(); } else { // , map cacheMap[key]->value = value; cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]); cacheMap[key] = cacheList.begin(); } } private: list<CacheNode> cacheList; unordered_map<int, list<CacheNode>::iterator> cacheMap; int capacity; }; 题 •

63. 3 3.1 Valid Palindrome Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. For example, "A man, a plan, a canal: Panama" is a palindrome. "race a car" is not a palindrome. Note: Have you consider that the string might be empty? This is a good question to ask during an interview. For the purpose of this problem, we define empty string as valid palindrome. // Leet Code, Valid Palindrome // O(n) O(1) class Solution { public: bool isPalindrome(string s) { transform(s.begin(), s.end(), s.begin(), ::tolower); auto left = s.begin(), right = prev(s.end()); while (left < right) { if (!::isalnum(*left)) ++left; else if (!::isalnum(*right)) --right; else if (*left != *right) return false; else { left++, right--; } } return true; } }; 57

64.58 3 题 • Palindrome Number, §15.2 3.2 Implement strStr() Implement strStr(). Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack. O(m ∗ n) KMP Boyer-Mooer Rabin-Karp BUG // LeetCode, Implement strStr() // 解 O(N*M) O(1) class Solution { public: int strStr(const string& haystack, const string& needle) { if (needle.empty()) return 0; const int N = haystack.size() - needle.size() + 1; for (int i = 0; i < N; i++) { int j = i; int k = 0; while (j < haystack.size() && k < needle.size() && haystack[j] == needle[k]) { j++; k++; } if (k == needle.size()) return i; } return -1; } }; KMP // LeetCode, Implement strStr() // KMP O(N+M) O(M) class Solution { public: int strStr(const string& haystack, const string& needle) { return kmp(haystack.c_str(), needle.c_str()); }

65.3.2 Implement strStr() 59 private: /* * @brief next . * * @param[in] pattern * @param[out] next next * @return */ static void compute_prefix(const char *pattern, int next[]) { int i; int j = -1; const int m = strlen(pattern); next[0] = j; for (i = 1; i < m; i++) { while (j > -1 && pattern[j + 1] != pattern[i]) j = next[j]; if (pattern[i] == pattern[j + 1]) j++; next[i] = j; } } /* * @brief KMP . * * @param[in] text * @param[in] pattern * @return -1 */ static int kmp(const char *text, const char *pattern) { int i; int j = -1; const int n = strlen(text); const int m = strlen(pattern); if (n == 0 && m == 0) return 0; /* "","" */ if (m == 0) return 0; /* "a","" */ int *next = (int*)malloc(sizeof(int) * m); compute_prefix(pattern, next); for (i = 0; i < n; i++) { while (j > -1 && pattern[j + 1] != text[i]) j = next[j]; if (text[i] == pattern[j + 1]) j++; if (j == m - 1) { free(next); return i-j; } } free(next); return -1; }

66.60 3 }; 题 • String to Integer (atoi) §3.3 3.3 String to Integer (atoi) Implement atoi to convert a string to an integer. Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases. Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are respon- sible to gather all the input requirements up front. Requirements for atoi: The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value. The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function. If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is per- formed. If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned. 题 1. ”-3924x8fc” ” + 413”, 2. ” ++c”, ” ++1” 3. ”2147483648” // LeetCode, String to Integer (atoi) // O(n) O(1) class Solution {

67.3.4 Add Binary 61 public: int myAtoi(const string &str) { int num = 0; int sign = 1; const int n = str.length(); int i = 0; while (str[i] == ' ' && i < n) i++; if (str[i] == '+') { i++; } else if (str[i] == '-') { sign = -1; i++; } for (; i < n; i++) { if (str[i] < '0' || str[i] > '9') break; if (num > INT_MAX / 10 || (num == INT_MAX / 10 && (str[i] - '0') > INT_MAX % 10)) { return sign == -1 ? INT_MIN : INT_MAX; } num = num * 10 + str[i] - '0'; } return num * sign; } }; 题 • Implement strStr() §3.2 3.4 Add Binary Given two binary strings, return their sum (also a binary string). For example, a = "11" b = "1" Return "100".

68.62 3 //LeetCode, Add Binary // O(n) O(1) class Solution { public: string addBinary(string a, string b) { string result; const size_t n = a.size() > b.size() ? a.size() : b.size(); reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); int carry = 0; for (size_t i = 0; i < n; i++) { const int ai = i < a.size() ? a[i] - '0' : 0; const int bi = i < b.size() ? b[i] - '0' : 0; const int val = (ai + bi + carry) % 2; carry = (ai + bi + carry) / 2; result.insert(result.begin(), val + '0'); } if (carry == 1) { result.insert(result.begin(), '1'); } return result; } }; 题 • Add Two Numbers, §2.2.1 3.5 Longest Palindromic Substring Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring. 题 O(n2 ) O(n2 ) f[i][j] [i,j] f[i][j] = if (i == j) S[i] if (S[i] == S[j] && f[i+1][j-1] == S[i+1][j-1]) S[i][j] else max(f[i+1][j-1], f[i][j-1], f[i+1][j])

69.3.5 Longest Palindromic Substring 63 O(n2 ) f(i,j) [i,j]   true ,i = j   f (i, j) = S[i] = S[j] ,j = i + 1    S[i] = S[j] and f (i + 1, j − 1) ,j > i + 1 Manacher s Algorithm, O(n) 解 http://leetcode.com/2011/11/longest- palindromic-substring-part-ii.html // LeetCode, Longest Palindromic Substring // // O(n^2) O(n^2) typedef string::const_iterator Iterator; namespace std { template<> struct hash<pair<Iterator, Iterator>> { size_t operator()(pair<Iterator, Iterator> const& p) const { return ((size_t) &(*p.first)) ^ ((size_t) &(*p.second)); } }; } class Solution { public: string longestPalindrome(string const& s) { cache.clear(); return cachedLongestPalindrome(s.begin(), s.end()); } private: unordered_map<pair<Iterator, Iterator>, string> cache; string longestPalindrome(Iterator first, Iterator last) { size_t length = distance(first, last); if (length < 2) return string(first, last); auto s = cachedLongestPalindrome(next(first), prev(last)); if (s.length() == length - 2 && *first == *prev(last)) return string(first, last); auto s1 = cachedLongestPalindrome(next(first), last); auto s2 = cachedLongestPalindrome(first, prev(last)); // return max(s, s1, s2) if (s.size() > s1.size()) return s.size() > s2.size() ? s : s2;

70.64 3 else return s1.size() > s2.size() ? s1 : s2; } string cachedLongestPalindrome(Iterator first, Iterator last) { auto key = make_pair(first, last); auto pos = cache.find(key); if (pos != cache.end()) return pos->second; else return cache[key] = longestPalindrome(first, last); } }; // LeetCode, Longest Palindromic Substring // O(n^2) O(n^2) class Solution { public: string longestPalindrome(const string& s) { const int n = s.size(); bool f[n][n]; fill_n(&f[0][0], n * n, false); // vector //vector<vector<bool> > f(n, vector<bool>(n, false)); size_t max_len = 1, start = 0; // for (size_t i = 0; i < s.size(); i++) { f[i][i] = true; for (size_t j = 0; j < i; j++) { // [j, i] f[j][i] = (s[j] == s[i] && (i - j < 2 || f[j + 1][i - 1])); if (f[j][i] && max_len < (i - j + 1)) { max_len = i - j + 1; start = j; } } } return s.substr(start, max_len); } }; Manacher s Algorithm // LeetCode, Longest Palindromic Substring // Manacher s Algorithm // O(n) O(n) class Solution { public: // Transform S into T. // For example, S = "abba", T = "^#a#b#b#a#$". // ^ and $ signs are sentinels appended to each end to avoid bounds checking string preProcess(const string& s) { int n = s.length();

71.3.5 Longest Palindromic Substring 65 if (n == 0) return "^$"; string ret = "^"; for (int i = 0; i < n; i++) ret += "#" + s.substr(i, 1); ret += "#$"; return ret; } string longestPalindrome(string s) { string T = preProcess(s); const int n = T.length(); // T[i] / T[i] // P[i] int P[n]; int C = 0, R = 0; for (int i = 1; i < n - 1; i++) { int i_mirror = 2 * C - i; // equals to i' = C - (i-C) P[i] = (R > i) ? min(R - i, P[i_mirror]) : 0; // Attempt to expand palindrome centered at i while (T[i + 1 + P[i]] == T[i - 1 - P[i]]) P[i]++; // If palindrome centered at i expand past R, // adjust center based on expanded palindrome. if (i + P[i] > R) { C = i; R = i + P[i]; } } // Find the maximum element in P. int max_len = 0; int center_index = 0; for (int i = 1; i < n - 1; i++) { if (P[i] > max_len) { max_len = P[i]; center_index = i; } } return s.substr((center_index - 1 - max_len) / 2, max_len); } }; 题 •

72.66 3 3.6 Regular Expression Matching Implement regular expression matching with support for '.' and '*'. '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). The function prototype should be: bool isMatch(const char *s, const char *p) Some examples: isMatch("aa","a") → false isMatch("aa","aa") → true isMatch("aaa","aa") → false isMatch("aa", "a*") → true isMatch("aa", ".*") → true isMatch("ab", ".*") → true isMatch("aab", "c*a*b") → true 题 // LeetCode, Regular Expression Matching // O(n) O(1) class Solution { public: bool isMatch(const string& s, const string& p) { return isMatch(s.c_str(), p.c_str()); } private: bool isMatch(const char *s, const char *p) { if (*p == '\0') return *s == '\0'; // next char is not '*', then must match current character if (*(p + 1) != '*') { if (*p == *s || (*p == '.' && *s != '\0')) return isMatch(s + 1, p + 1); else return false; } else { // next char is '*' while (*p == *s || (*p == '.' && *s != '\0')) { if (isMatch(s, p + 2)) return true; s++; } return isMatch(s, p + 2);

73.3.7 Wildcard Matching 67 } } }; 题 • Wildcard Matching, §3.7 3.7 Wildcard Matching Implement wildcard pattern matching with support for '?' and '*'. '?' Matches any single character. '*' Matches any sequence of characters (including the empty se- quence). The matching should cover the entire input string (not partial). The function prototype should be: bool isMatch(const char *s, const char *p) Some examples: isMatch("aa","a") → false isMatch("aa","aa") → true isMatch("aaa","aa") → false isMatch("aa", "*") → true isMatch("aa", "a*") → true isMatch("ab", "?*") → true isMatch("aab", "c*a*b") → false 题 '*' 题 p '*' '*' s s s++ // LeetCode, Wildcard Matching // 解题 // O(n!*m!) O(n) class Solution { public:

74.68 3 bool isMatch(const string& s, const string& p) { return isMatch(s.c_str(), p.c_str()); } private: bool isMatch(const char *s, const char *p) { if (*p == '*') { while (*p == '*') ++p; //skip continuous '*' if (*p == '\0') return true; while (*s != '\0' && !isMatch(s, p)) ++s; return *s != '\0'; } else if (*p == '\0' || *s == '\0') return *p == *s; else if (*p == *s || *p == '?') return isMatch(++s, ++p); else return false; } }; // LeetCode, Wildcard Matching // O(n*m) O(1) class Solution { public: bool isMatch(const string& s, const string& p) { return isMatch(s.c_str(), p.c_str()); } private: bool isMatch(const char *s, const char *p) { bool star = false; const char *str, *ptr; for (str = s, ptr = p; *str != '\0'; str++, ptr++) { switch (*ptr) { case '?': break; case '*': star = true; s = str, p = ptr; while (*p == '*') p++; //skip continuous '*' if (*p == '\0') return true; str = s - 1; ptr = p - 1; break; default: if (*str != *ptr) { // '*' if (!star) return false; s++; str = s - 1; ptr = p - 1; } } }

75.3.8 Longest Common Prefix 69 while (*ptr == '*') ptr++; return (*ptr == '\0'); } }; 题 • Regular Expression Matching, §3.6 3.8 Longest Common Prefix Write a function to find the longest common prefix string amongst an array of strings. 0 // LeetCode, Longest Common Prefix // 0 // O(n1+n2+...) // @author (http://weibo.com/zhouditty) class Solution { public: string longestCommonPrefix(vector<string> &strs) { if (strs.empty()) return ""; for (int idx = 0; idx < strs[0].size(); ++idx) { // for (int i = 1; i < strs.size(); ++i) { if (strs[i][idx] != strs[0][idx]) return strs[0].substr(0,idx); } } return strs[0]; } }; // LeetCode, Longest Common Prefix // 0 // // O(n1+n2+...) class Solution { public: string longestCommonPrefix(vector<string> &strs) {

76.70 3 if (strs.empty()) return ""; int right_most = strs[0].size() - 1; for (size_t i = 1; i < strs.size(); i++) for (int j = 0; j <= right_most; j++) if (strs[i][j] != strs[0][j]) // string::[] right_most = j - 1; return strs[0].substr(0, right_most + 1); } }; 题 • 3.9 Valid Number Validate if a given string is numeric. Some examples: "0" => true " 0.1 " => true "abc" => false "1 a" => false "2e10" => true Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one. 题 题 strtod() // LeetCode, Valid Number // @author (http://weibo.com/luangong) // finite automata O(n) O(n) class Solution { public: bool isNumber(const string& s) { enum InputType { INVALID, // 0 SPACE, // 1

77.3.9 Valid Number 71 SIGN, // 2 DIGIT, // 3 DOT, // 4 EXPONENT, // 5 NUM_INPUTS // 6 }; const int transitionTable[][NUM_INPUTS] = { -1, 0, 3, 1, 2, -1, // next states for state 0 -1, 8, -1, 1, 4, 5, // next states for state 1 -1, -1, -1, 4, -1, -1, // next states for state 2 -1, -1, -1, 1, 2, -1, // next states for state 3 -1, 8, -1, 4, -1, 5, // next states for state 4 -1, -1, 6, 7, -1, -1, // next states for state 5 -1, -1, -1, 7, -1, -1, // next states for state 6 -1, 8, -1, 7, -1, -1, // next states for state 7 -1, 8, -1, -1, -1, -1, // next states for state 8 }; int state = 0; for (auto ch : s) { InputType inputType = INVALID; if (isspace(ch)) inputType = SPACE; else if (ch == '+' || ch == '-') inputType = SIGN; else if (isdigit(ch)) inputType = DIGIT; else if (ch == '.') inputType = DOT; else if (ch == 'e' || ch == 'E') inputType = EXPONENT; // Get next state from current state and input symbol state = transitionTable[state][inputType]; // Invalid input if (state == -1) return false; } // If the current state belongs to one of the accepting (final) states, // then the number is valid return state == 1 || state == 4 || state == 7 || state == 8; } }; strtod() // LeetCode, Valid Number // @author (http://weibo.com/lianchengzju) // strtod() O(n) class Solution { public: bool isNumber (const string& s) {

78.72 3 return isNumber(s.c_str()); } private: bool isNumber (char const* s) { char* endptr; strtod (s, &endptr); if (endptr == s) return false; for (; *endptr; ++endptr) if (!isspace (*endptr)) return false; return true; } }; 题 • 3.10 Integer to Roman Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999. // LeetCode, Integer to Roman // O(num) O(1) class Solution { public: string intToRoman(int num) { const int radix[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}; const string symbol[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}; string roman; for (size_t i = 0; num > 0; ++i) { int count = num / radix[i]; num %= radix[i]; for (; count > 0; --count) roman += symbol[i];

79.3.11 Roman to Integer 73 } return roman; } }; 题 • Roman to Integer, §3.11 3.11 Roman to Integer Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999. IV = 5 – 1 VI = 5 + 1, II=1+1 // LeetCode, Roman to Integer // O(n) O(1) class Solution { public: inline int map(const char c) { switch (c) { case 'I': return 1; case 'V': return 5; case 'X': return 10; case 'L': return 50; case 'C': return 100; case 'D': return 500; case 'M': return 1000; default: return 0; } } int romanToInt(const string& s) { int result = 0; for (size_t i = 0; i < s.size(); i++) { if (i > 0 && map(s[i]) > map(s[i - 1])) { result += (map(s[i]) - 2 * map(s[i - 1])); } else {

80.74 3 result += map(s[i]); } } return result; } }; 题 • Integer to Roman, §3.10 3.12 Count and Say The count-and-say sequence is the sequence of integers beginning as follows: 1, 11, 21, 1211, 111221, ... 1 is read off as "one 1" or 11. 11 is read off as "two 1s" or 21. 21 is read off as "one 2", then "one 1" or 1211. Given an integer n, generate the nth sequence. Note: The sequence of integers will be represented as a string. // LeetCode, Count and Say // @author (http://weibo.com/lianchengzju) // O(n^2) O(n) class Solution { public: string countAndSay(int n) { string s("1"); while (--n) s = getNext(s); return s; } string getNext(const string &s) { stringstream ss;

81.3.13 Anagrams 75 for (auto i = s.begin(); i != s.end(); ) { auto j = find_if(i, s.end(), bind1st(not_equal_to<char>(), *i)); ss << distance(i, j) << *i; i = j; } return ss.str(); } }; 题 • 3.13 Anagrams Given an array of strings, return all groups of strings that are anagrams. Note: All inputs will be in lower-case. Anagram "dormitory" "dirty room" "tea" "eat" anagrams // LeetCode, Anagrams // O(n) O(n) class Solution { public: vector<string> anagrams(vector<string> &strs) { unordered_map<string, vector<string> > group; for (const auto &s : strs) { string key = s; sort(key.begin(), key.end()); group[key].push_back(s); } vector<string> result; for (auto it = group.cbegin(); it != group.cend(); it++) { if (it->second.size() > 1) result.insert(result.end(), it->second.begin(), it->second.end()); }

82.76 3 return result; } }; 题 • 3.14 Simplify Path Given an absolute path for a file (Unix-style), simplify it. For example, path = "/home/", => "/home" path = "/a/./b/../../c/", => "/c" Corner Cases: • Did you consider the case where path = "/../"? In this case, you should return "/". • Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/". In this case, you should ignore redundant slashes and return "/home/foo". 题 // LeetCode, Simplify Path // O(n) O(n) class Solution { public: string simplifyPath(const string& path) { vector<string> dirs; // for (auto i = path.begin(); i != path.end();) { ++i; auto j = find(i, path.end(), '/'); auto dir = string(i, j); if (!dir.empty() && dir != ".") {// '///' dir if (dir == "..") { if (!dirs.empty()) dirs.pop_back();

83.3.15 Length of Last Word 77 } else dirs.push_back(dir); } i = j; } stringstream out; if (dirs.empty()) { out << "/"; } else { for (auto dir : dirs) out << '/' << dir; } return out.str(); } }; 题 • 3.15 Length of Last Word Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string. If the last word does not exist, return 0. Note: A word is defined as a character sequence consists of non-space characters only. For example, Given s = "Hello World", return 5. 题 STL // LeetCode, Length of Last Word // STL // O(n) O(1) class Solution { public: int lengthOfLastWord(const string& s) { auto first = find_if(s.rbegin(), s.rend(), ::isalpha); auto last = find_if_not(first, s.rend(), ::isalpha);

84.78 3 return distance(first, last); } }; // LeetCode, Length of Last Word // word // O(n) O(1) class Solution { public: int lengthOfLastWord(const string& s) { return lengthOfLastWord(s.c_str()); } private: int lengthOfLastWord(const char *s) { int len = 0; while (*s) { if (*s++ != ' ') ++len; else if (*s && *s != ' ') len = 0; } return len; } }; 题 •

85. 4 4.1 4.1.1 Valid Parentheses Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. The brackets must close in the correct order, "()" and "()[]" are all valid but "(]" and "([)]" are not. // LeetCode, Valid Parentheses // O(n) O(n) class Solution { public: bool isValid (string const& s) { string left = "([{"; string right = ")]}"; stack<char> stk; for (auto c : s) { if (left.find(c) != string::npos) { stk.push (c); } else { if (stk.empty () || stk.top () != left[right.find (c)]) return false; else stk.pop (); } } 79

86.80 4 return stk.empty(); } }; 题 • Generate Parentheses, §10.9 • Longest Valid Parentheses, §4.1.2 4.1.2 Longest Valid Parentheses Given a string containing just the characters '(' and ')', find the length of the longest valid (well- formed) parentheses substring. For "(()", the longest valid parentheses substring is "()", which has length = 2. Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4. // LeetCode, Longest Valid Parenthese // O(n) O(n) class Solution { public: int longestValidParentheses(const string& s) { int max_len = 0, last = -1; // the position of the last ')' stack<int> lefts; // keep track of the positions of non-matching '('s for (int i = 0; i < s.size(); ++i) { if (s[i] =='(') { lefts.push(i); } else { if (lefts.empty()) { // no matching left last = i; } else { // find a matching pair lefts.pop(); if (lefts.empty()) { max_len = max(max_len, i-last); } else { max_len = max(max_len, i-lefts.top());

87.4.1 81 } } } } return max_len; } }; Dynamic Programming, One Pass // LeetCode, Longest Valid Parenthese // O(n) O(n) // @author (http://weibo.com/wjson) class Solution { public: int longestValidParentheses(const string& s) { vector<int> f(s.size(), 0); int ret = 0; for (int i = s.size() - 2; i >= 0; --i) { int match = i + f[i + 1] + 1; // case: "((...))" if (s[i] == '(' && match < s.size() && s[match] == ')') { f[i] = f[i + 1] + 2; // if a valid sequence exist afterwards "((...))()" if (match + 1 < s.size()) f[i] += f[match + 1]; } ret = max(ret, f[i]); } return ret; } }; // LeetCode, Longest Valid Parenthese // O(n) O(1) // @author (http://weibo.com/cpcs) class Solution { public: int longestValidParentheses(const string& s) { int answer = 0, depth = 0, start = -1; for (int i = 0; i < s.size(); ++i) { if (s[i] == '(') { ++depth; } else { --depth; if (depth < 0) { start = i; depth = 0; } else if (depth == 0) { answer = max(answer, i - start); }

88.82 4 } } depth = 0; start = s.size(); for (int i = s.size() - 1; i >= 0; --i) { if (s[i] == ')') { ++depth; } else { --depth; if (depth < 0) { start = i; depth = 0; } else if (depth == 0) { answer = max(answer, start - i); } } } return answer; } }; 题 • Valid Parentheses, §4.1.1 • Generate Parentheses, §10.9 4.1.3 Largest Rectangle in Histogram Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. 4-1 Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

89.4.1 83 4-2 The largest rectangle is shown in the shaded area, which has area = 10 unit. For example, Given height = [2,1,5,6,2,3], return 10. Container With Most Water(§12.6) O(n2 ) §4-2 i=4 3 3 3 3 4 2 4 1 0 // LeetCode, Largest Rectangle in Histogram // O(n) O(n) class Solution { public: int largestRectangleArea(vector<int> &height) { stack<int> s; height.push_back(0); int result = 0; for (int i = 0; i < height.size(); ) { if (s.empty() || height[i] > height[s.top()]) s.push(i++); else { int tmp = s.top(); s.pop(); result = max(result, height[tmp] * (s.empty() ? i : i - s.top() - 1)); } } return result;

90.84 4 } }; 题 • Trapping Rain Water, §2.1.15 • Container With Most Water, §12.6 4.1.4 Evaluate Reverse Polish Notation Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Each operand may be an integer or another expression. Some examples: ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9 ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6 // LeetCode, Evaluate Reverse Polish Notation // O(n) O(logn) class Solution { public: int evalRPN(vector<string> &tokens) { int x, y; auto token = tokens.back(); tokens.pop_back(); if (is_operator(token)) { y = evalRPN(tokens); x = evalRPN(tokens); if (token[0] == '+') x += y; else if (token[0] == '-') x -= y; else if (token[0] == '*') x *= y; else x /= y; } else { size_t i; x = stoi(token, &i); } return x; } private: bool is_operator(const string &op) { return op.size() == 1 && string("+-*/").find(op) != string::npos; } };

91.4.2 85 // LeetCode, Max Points on a Line // O(n) O(logn) class Solution { public: int evalRPN(vector<string> &tokens) { stack<string> s; for (auto token : tokens) { if (!is_operator(token)) { s.push(token); } else { int y = stoi(s.top()); s.pop(); int x = stoi(s.top()); s.pop(); if (token[0] == '+') x += y; else if (token[0] == '-') x -= y; else if (token[0] == '*') x *= y; else x /= y; s.push(to_string(x)); } } return stoi(s.top()); } private: bool is_operator(const string &op) { return op.size() == 1 && string("+-*/").find(op) != string::npos; } }; 题 • 4.2

92. 5 LeetCode // struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) { } }; 5.1 (root->left->right) root->right->left (left- >right->root) right->left->root (left->root->right) 5.1.1 Binary Tree Preorder Traversal Given a binary tree, return the preorder traversal of its nodes’ values. For example: Given binary tree {1,#,2,3}, 1 \ 2 / 3 return [1,2,3]. Note: Recursive solution is trivial, could you do it iteratively? 86

93.5.1 87 Morris // LeetCode, Binary Tree Preorder Traversal // O(n) O(n) class Solution { public: vector<int> preorderTraversal(TreeNode *root) { vector<int> result; stack<const TreeNode *> s; if (root != nullptr) s.push(root); while (!s.empty()) { const TreeNode *p = s.top(); s.pop(); result.push_back(p->val); if (p->right != nullptr) s.push(p->right); if (p->left != nullptr) s.push(p->left); } return result; } }; Morris // LeetCode, Binary Tree Preorder Traversal // Morris O(n) O(1) class Solution { public: vector<int> preorderTraversal(TreeNode *root) { vector<int> result; TreeNode *cur = root, *prev = nullptr; while (cur != nullptr) { if (cur->left == nullptr) { result.push_back(cur->val); prev = cur; /* cur */ cur = cur->right; } else { /* */ TreeNode *node = cur->left; while (node->right != nullptr && node->right != cur) node = node->right; if (node->right == nullptr) { /* */ result.push_back(cur->val); /* */ node->right = cur; prev = cur; /* cur */

94.88 5 cur = cur->left; } else { /* */ node->right = nullptr; /* prev = cur; cur */ cur = cur->right; } } } return result; } }; 题 • Binary Tree Inorder Traversal §5.1.2 • Binary Tree Postorder Traversal §5.1.3 • Recover Binary Search Tree §5.1.7 5.1.2 Binary Tree Inorder Traversal Given a binary tree, return the inorder traversal of its nodes’ values. For example: Given binary tree {1,#,2,3}, 1 \ 2 / 3 return [1,3,2]. Note: Recursive solution is trivial, could you do it iteratively? Morris // LeetCode, Binary Tree Inorder Traversal // O(n) O(n) class Solution { public: vector<int> inorderTraversal(TreeNode *root) { vector<int> result; stack<const TreeNode *> s; const TreeNode *p = root;

95.5.1 89 while (!s.empty() || p != nullptr) { if (p != nullptr) { s.push(p); p = p->left; } else { p = s.top(); s.pop(); result.push_back(p->val); p = p->right; } } return result; } }; Morris // LeetCode, Binary Tree Inorder Traversal // Morris O(n) O(1) class Solution { public: vector<int> inorderTraversal(TreeNode *root) { vector<int> result; TreeNode *cur = root, *prev = nullptr; while (cur != nullptr) { if (cur->left == nullptr) { result.push_back(cur->val); prev = cur; cur = cur->right; } else { /* */ TreeNode *node = cur->left; while (node->right != nullptr && node->right != cur) node = node->right; if (node->right == nullptr) { /* */ node->right = cur; /* prev = cur; cur */ cur = cur->left; } else { /* */ result.push_back(cur->val); node->right = nullptr; prev = cur; cur = cur->right; } } } return result; } };

96.90 5 题 • Binary Tree Preorder Traversal §5.1.1 • Binary Tree Postorder Traversal §5.1.3 • Recover Binary Search Tree §5.1.7 5.1.3 Binary Tree Postorder Traversal Given a binary tree, return the postorder traversal of its nodes’ values. For example: Given binary tree {1,#,2,3}, 1 \ 2 / 3 return [3,2,1]. Note: Recursive solution is trivial, could you do it iteratively? Morris // LeetCode, Binary Tree Postorder Traversal // O(n) O(n) class Solution { public: vector<int> postorderTraversal(TreeNode *root) { vector<int> result; stack<const TreeNode *> s; /* p q */ const TreeNode *p = root, *q = nullptr; do { while (p != nullptr) { /* */ s.push(p); p = p->left; } q = nullptr; while (!s.empty()) { p = s.top(); s.pop(); /* */ if (p->right == q) {

97.5.1 91 result.push_back(p->val); q = p; /* */ } else { /* */ s.push(p); /* */ p = p->right; break; } } } while (!s.empty()); return result; } }; Morris // LeetCode, Binary Tree Postorder Traversal // Morris O(n) O(1) class Solution { public: vector<int> postorderTraversal(TreeNode *root) { vector<int> result; TreeNode dummy(-1); TreeNode *cur, *prev = nullptr; std::function < void(const TreeNode*)> visit = [&result](const TreeNode *node){ result.push_back(node->val); }; dummy.left = root; cur = &dummy; while (cur != nullptr) { if (cur->left == nullptr) { prev = cur; /* */ cur = cur->right; } else { TreeNode *node = cur->left; while (node->right != nullptr && node->right != cur) node = node->right; if (node->right == nullptr) { /* */ node->right = cur; prev = cur; /* */ cur = cur->left; } else { /* */ visit_reverse(cur->left, prev, visit); prev->right = nullptr; prev = cur; /* */ cur = cur->right; } }

98.92 5 } return result; } private: // static void reverse(TreeNode *from, TreeNode *to) { TreeNode *x = from, *y = from->right, *z; if (from == to) return; while (x != to) { z = y->right; y->right = x; x = y; y = z; } } // static void visit_reverse(TreeNode* from, TreeNode *to, std::function< void(const TreeNode*) >& visit) { TreeNode *p = to; reverse(from, to); while (true) { visit(p); if (p == from) break; p = p->right; } reverse(to, from); } }; 题 • Binary Tree Preorder Traversal §5.1.1 • Binary Tree Inorder Traversal §5.1.2 • Recover Binary Search Tree §5.1.7 5.1.4 Binary Tree Level Order Traversal Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level). For example: Given binary tree {3,9,20,#,#,15,7},

99.5.1 93 3 / \ 9 20 / \ 15 7 return its level order traversal as: [ [3], [9,20], [15,7] ] // LeetCode, Binary Tree Level Order Traversal // O(n) O(n) class Solution { public: vector<vector<int> > levelOrder(TreeNode *root) { vector<vector<int>> result; traverse(root, 1, result); return result; } void traverse(TreeNode *root, size_t level, vector<vector<int>> &result) { if (!root) return; if (level > result.size()) result.push_back(vector<int>()); result[level-1].push_back(root->val); traverse(root->left, level+1, result); traverse(root->right, level+1, result); } }; // LeetCode, Binary Tree Level Order Traversal // O(n) O(1) class Solution { public: vector<vector<int> > levelOrder(TreeNode *root) { vector<vector<int> > result; queue<TreeNode*> current, next;

100.94 5 if(root == nullptr) { return result; } else { current.push(root); } while (!current.empty()) { vector<int> level; // elments in one level while (!current.empty()) { TreeNode* node = current.front(); current.pop(); level.push_back(node->val); if (node->left != nullptr) next.push(node->left); if (node->right != nullptr) next.push(node->right); } result.push_back(level); swap(next, current); } return result; } }; 题 • Binary Tree Level Order Traversal II §5.1.5 • Binary Tree Zigzag Level Order Traversal §5.1.6 5.1.5 Binary Tree Level Order Traversal II Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root). For example: Given binary tree {3,9,20,#,#,15,7}, 3 / \ 9 20 / \ 15 7 return its bottom-up level order traversal as: [ [15,7] [9,20], [3], ]

101.5.1 95 题 §5.1.4 reverse() // LeetCode, Binary Tree Level Order Traversal II // O(n) O(n) class Solution { public: vector<vector<int> > levelOrderBottom(TreeNode *root) { vector<vector<int>> result; traverse(root, 1, result); std::reverse(result.begin(), result.end()); // 题 return result; } void traverse(TreeNode *root, size_t level, vector<vector<int>> &result) { if (!root) return; if (level > result.size()) result.push_back(vector<int>()); result[level-1].push_back(root->val); traverse(root->left, level+1, result); traverse(root->right, level+1, result); } }; // LeetCode, Binary Tree Level Order Traversal II // O(n) O(1) class Solution { public: vector<vector<int> > levelOrderBottom(TreeNode *root) { vector<vector<int> > result; if(root == nullptr) return result; queue<TreeNode*> current, next; vector<int> level; // elments in level level current.push(root); while (!current.empty()) { while (!current.empty()) { TreeNode* node = current.front(); current.pop(); level.push_back(node->val); if (node->left != nullptr) next.push(node->left); if (node->right != nullptr) next.push(node->right); } result.push_back(level);

102.96 5 level.clear(); swap(next, current); } reverse(result.begin(), result.end()); // 题 return result; } }; 题 • Binary Tree Level Order Traversal §5.1.4 • Binary Tree Zigzag Level Order Traversal §5.1.6 5.1.6 Binary Tree Zigzag Level Order Traversal Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between). For example: Given binary tree 3,9,20,#,#,15,7, 3 / \ 9 20 / \ 15 7 return its zigzag level order traversal as: [ [3], [20,9], [15,7] ] bool // LeetCode, Binary Tree Zigzag Level Order Traversal // O(n) O(n) class Solution { public: vector<vector<int> > zigzagLevelOrder(TreeNode *root) { vector<vector<int>> result; traverse(root, 1, result, true); return result;

103.5.1 97 } void traverse(TreeNode *root, size_t level, vector<vector<int>> &result, bool left_to_right) { if (!root) return; if (level > result.size()) result.push_back(vector<int>()); if (left_to_right) result[level-1].push_back(root->val); else result[level-1].insert(result[level-1].begin(), root->val); traverse(root->left, level+1, result, !left_to_right); traverse(root->right, level+1, result, !left_to_right); } }; //LeetCode, Binary Tree Zigzag Level Order Traversal // bool // O(n) O(n) class Solution { public: vector<vector<int> > zigzagLevelOrder(TreeNode *root) { vector<vector<int> > result; queue<TreeNode*> current, next; bool left_to_right = true; if(root == nullptr) { return result; } else { current.push(root); } while (!current.empty()) { vector<int> level; // elments in one level while (!current.empty()) { TreeNode* node = current.front(); current.pop(); level.push_back(node->val); if (node->left != nullptr) next.push(node->left); if (node->right != nullptr) next.push(node->right); } if (!left_to_right) reverse(level.begin(), level.end()); result.push_back(level); left_to_right = !left_to_right; swap(next, current); } return result; }

104.98 5 }; 题 • Binary Tree Level Order Traversal §5.1.4 • Binary Tree Level Order Traversal II §5.1.5 5.1.7 Recover Binary Search Tree Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution? O(n) 解 O(n) Morris // LeetCode, Recover Binary Search Tree // Morris O(n) O(1) class Solution { public: void recoverTree(TreeNode* root) { pair<TreeNode*, TreeNode*> broken; TreeNode* prev = nullptr; TreeNode* cur = root; while (cur != nullptr) { if (cur->left == nullptr) { detect(broken, prev, cur); prev = cur; cur = cur->right; } else { auto node = cur->left; while (node->right != nullptr && node->right != cur) node = node->right; if (node->right == nullptr) { node->right = cur; //prev = cur; cur

105.5.1 99 cur = cur->left; } else { detect(broken, prev, cur); node->right = nullptr; prev = cur; cur = cur->right; } } } swap(broken.first->val, broken.second->val); } void detect(pair<TreeNode*, TreeNode*>& broken, TreeNode* prev, TreeNode* current) { if (prev != nullptr && prev->val > current->val) { if (broken.first == nullptr) { broken.first = prev; } // else {0,1} swap second nullptr // Runtime Error broken.second = current; } } }; 题 • Binary Tree Inorder Traversal §5.1.2 5.1.8 Same Tree Given two binary trees, write a function to check if they are equal or not. Two binary trees are considered equal if they are structurally identical and the nodes have the same value. // LeetCode, Same Tree // O(n) O(logn) class Solution { public: bool isSameTree(TreeNode *p, TreeNode *q) {

106.100 5 if (!p && !q) return true; // if (!p || !q) return false; // return p->val == q->val // && isSameTree(p->left, q->left) && isSameTree(p->right, q->right); } }; // LeetCode, Same Tree // O(n) O(logn) class Solution { public: bool isSameTree(TreeNode *p, TreeNode *q) { stack<TreeNode*> s; s.push(p); s.push(q); while(!s.empty()) { p = s.top(); s.pop(); q = s.top(); s.pop(); if (!p && !q) continue; if (!p || !q) return false; if (p->val != q->val) return false; s.push(p->left); s.push(q->left); s.push(p->right); s.push(q->right); } return true; } }; 题 • Symmetric Tree §5.1.9 5.1.9 Symmetric Tree Given two binary trees, write a function to check if they are equal or not. Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

107.5.1 101 // LeetCode, Symmetric Tree // O(n) O(logn) class Solution { public: bool isSymmetric(TreeNode *root) { if (root == nullptr) return true; return isSymmetric(root->left, root->right); } bool isSymmetric(TreeNode *p, TreeNode *q) { if (p == nullptr && q == nullptr) return true; // if (p == nullptr || q == nullptr) return false; // return p->val == q->val // && isSymmetric(p->left, q->right) && isSymmetric(p->right, q->left); } }; // LeetCode, Symmetric Tree // O(n) O(logn) class Solution { public: bool isSymmetric (TreeNode* root) { if (!root) return true; stack<TreeNode*> s; s.push(root->left); s.push(root->right); while (!s.empty ()) { auto p = s.top (); s.pop(); auto q = s.top (); s.pop(); if (!p && !q) continue; if (!p || !q) return false; if (p->val != q->val) return false; s.push(p->left); s.push(q->right); s.push(p->right); s.push(q->left); } return true;

108.102 5 } }; 题 • Same Tree §5.1.8 5.1.10 Balanced Binary Tree Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1. // LeetCode, Balanced Binary Tree // O(n) O(logn) class Solution { public: bool isBalanced (TreeNode* root) { return balancedHeight (root) >= 0; } /** * Returns the height of `root` if `root` is a balanced tree, * otherwise, returns `-1`. */ int balancedHeight (TreeNode* root) { if (root == nullptr) return 0; // int left = balancedHeight (root->left); int right = balancedHeight (root->right); if (left < 0 || right < 0 || abs(left - right) > 1) return -1; // return max(left, right) + 1; // } }; 题 •

109.5.1 103 5.1.11 Flatten Binary Tree to Linked List Given a binary tree, flatten it to a linked list in-place. For example, Given 1 / \ 2 5 / \ \ 3 4 6 The flattened tree should look like: 1 \ 2 \ 3 \ 4 \ 5 \ 6 1 // LeetCode, Flatten Binary Tree to Linked List // 1 O(n) O(logn) class Solution { public: void flatten(TreeNode *root) { if (root == nullptr) return; // flatten(root->left); flatten(root->right); if (nullptr == root->left) return; // root root->right TreeNode *p = root->left; while(p->right) p = p->right; // p->right = root->right; root->right = root->left; root->left = nullptr; } };

110.104 5 2 // LeetCode, Flatten Binary Tree to Linked List // 2 // @author (http://weibo.com/u/1234984145) // O(n) O(logn) class Solution { public: void flatten(TreeNode *root) { flatten(root, NULL); } private: // root tail TreeNode *flatten(TreeNode *root, TreeNode *tail) { if (NULL == root) return tail; root->right = flatten(root->left, flatten(root->right, tail)); root->left = NULL; return root; } }; // LeetCode, Flatten Binary Tree to Linked List // O(n) O(logn) class Solution { public: void flatten(TreeNode* root) { if (root == nullptr) return; stack<TreeNode*> s; s.push(root); while (!s.empty()) { auto p = s.top(); s.pop(); if (p->right) s.push(p->right); if (p->left) s.push(p->left); p->left = nullptr; if (!s.empty()) p->right = s.top(); } } };

111.5.1 105 题 • 5.1.12 Populating Next Right Pointers in Each Node II Follow up for problem ”Populating Next Right Pointers in Each Node”. What if the given tree could be any binary tree? Would your previous solution still work? Note: You may only use constant extra space. For example, Given the following binary tree, 1 / \ 2 3 / \ \ 4 5 7 After calling your function, the tree should look like: 1 -> NULL / \ 2 -> 3 -> NULL / \ \ 4-> 5 -> 7 -> NULL 题 题 解 Populating Next Right Pointers in Each Node I. // LeetCode, Populating Next Right Pointers in Each Node II // O(n) O(1) class Solution { public: void connect(TreeLinkNode *root) { if (root == nullptr) return; TreeLinkNode dummy(-1); for (TreeLinkNode *curr = root, *prev = &dummy; curr; curr = curr->next) { if (curr->left != nullptr){ prev->next = curr->left; prev = prev->next; } if (curr->right != nullptr){

112.106 5 prev->next = curr->right; prev = prev->next; } } connect(dummy.next); } }; // LeetCode, Populating Next Right Pointers in Each Node II // O(n) O(1) class Solution { public: void connect(TreeLinkNode *root) { while (root) { TreeLinkNode * next = nullptr; // the first node of next level TreeLinkNode * prev = nullptr; // previous node on the same level for (; root; root = root->next) { if (!next) next = root->left ? root->left : root->right; if (root->left) { if (prev) prev->next = root->left; prev = root->left; } if (root->right) { if (prev) prev->next = root->right; prev = root->right; } } root = next; // turn to next level } } }; 题 • Populating Next Right Pointers in Each Node §5.4.6 5.2 5.2.1 Construct Binary Tree from Preorder and Inorder Traversal Given preorder and inorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree.

113.5.2 107 // LeetCode, Construct Binary Tree from Preorder and Inorder Traversal // O(n) O(\logn) class Solution { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { return buildTree(begin(preorder), end(preorder), begin(inorder), end(inorder)); } template<typename InputIterator> TreeNode* buildTree(InputIterator pre_first, InputIterator pre_last, InputIterator in_first, InputIterator in_last) { if (pre_first == pre_last) return nullptr; if (in_first == in_last) return nullptr; auto root = new TreeNode(*pre_first); auto inRootPos = find(in_first, in_last, *pre_first); auto leftSize = distance(in_first, inRootPos); root->left = buildTree(next(pre_first), next(pre_first, leftSize + 1), in_first, next(in_first, leftSize)); root->right = buildTree(next(pre_first, leftSize + 1), pre_last, next(inRootPos), in_last); return root; } }; 题 • Construct Binary Tree from Inorder and Postorder Traversal §5.2.2 5.2.2 Construct Binary Tree from Inorder and Postorder Traversal Given inorder and postorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree.

114.108 5 // LeetCode, Construct Binary Tree from Inorder and Postorder Traversal // O(n) O(\logn) class Solution { public: TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { return buildTree(begin(inorder), end(inorder), begin(postorder), end(postorder)); } template<typename BidiIt> TreeNode* buildTree(BidiIt in_first, BidiIt in_last, BidiIt post_first, BidiIt post_last) { if (in_first ==in_last) return nullptr; if (post_first == post_last) return nullptr; const auto val = *prev(post_last); TreeNode* root = new TreeNode(val); auto in_root_pos = find(in_first, in_last, val); auto left_size = distance(in_first, in_root_pos); auto post_left_last = next(post_first, left_size); root->left = buildTree(in_first, in_root_pos, post_first, post_left_last); root->right = buildTree(next(in_root_pos), in_last, post_left_last, prev(post_last)); return root; } }; 题 • Construct Binary Tree from Preorder and Inorder Traversal §5.2.1 5.3 5.3.1 Unique Binary Search Trees Given n, how many structurally unique BST’s (binary search trees) that store values 1...n? For example, Given n = 3, there are a total of 5 unique BST’s. 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3

115.5.3 109 1 1 2 3 3 \ \ / \ / / 3 2 1 3 2 1 / \ / \ 2 3 1 2 1 0 2 2 1 1 1, 2, 3, ..., n BST i [1, i-1] [i+1, n] f (i) [1, i] Unique Binary Search Tree BST f (0) = 1 1 BST f (1) = 1 1,2 1 2 \ / 2 1 f (2) = f (0) ∗ f (1) 1 + f (1) ∗ f (0) 2 3 BST f (3) = f (0) ∗ f (2) 1 + f (1) ∗ f (1) 2 + f (2) ∗ f (0) 3 f ∑ i f (i) = f (k − 1) × f (i − k) k=1 题 // LeetCode, Unique Binary Search Trees // O(n^2) O(n) class Solution {

116.110 5 public: int numTrees(int n) { vector<int> f(n + 1, 0); f[0] = 1; f[1] = 1; for (int i = 2; i <= n; ++i) { for (int k = 1; k <= i; ++k) f[i] += f[k-1] * f[i - k]; } return f[n]; } }; 题 • Unique Binary Search Trees II §5.3.2 5.3.2 Unique Binary Search Trees II Given n, generate all structurally unique BST’s (binary search trees) that store values 1...n. For example, Given n = 3, your program should return all 5 unique BST’s shown below. 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 题 // LeetCode, Unique Binary Search Trees II // TODO TODO class Solution { public: vector<TreeNode *> generateTrees(int n) { if (n == 0) return generate(1, 0); return generate(1, n); } private: vector<TreeNode *> generate(int start, int end) { vector<TreeNode*> subTree; if (start > end) {

117.5.3 111 subTree.push_back(nullptr); return subTree; } for (int k = start; k <= end; k++) { vector<TreeNode*> leftSubs = generate(start, k - 1); vector<TreeNode*> rightSubs = generate(k + 1, end); for (auto i : leftSubs) { for (auto j : rightSubs) { TreeNode *node = new TreeNode(k); node->left = i; node->right = j; subTree.push_back(node); } } } return subTree; } }; 题 • Unique Binary Search Trees §5.3.1 5.3.3 Validate Binary Search Tree Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: • The left subtree of a node contains only nodes with keys less than the node’s key. • The right subtree of a node contains only nodes with keys greater than the node’s key. • Both the left and right subtrees must also be binary search trees. // LeetCode, Validate Binary Search Tree // O(n) O(\logn) class Solution { public: bool isValidBST(TreeNode* root) { return isValidBST(root, INT_MIN, INT_MAX); } bool isValidBST(TreeNode* root, int lower, int upper) { if (root == nullptr) return true;

118.112 5 return root->val > lower && root->val < upper && isValidBST(root->left, lower, root->val) && isValidBST(root->right, root->val, upper); } }; 题 • Validate Binary Search Tree §5.3.3 5.3.4 Convert Sorted Array to Binary Search Tree Given an array where elements are sorted in ascending order, convert it to a height balanced BST. // LeetCode, Convert Sorted Array to Binary Search Tree // O(n) O(logn) class Solution { public: TreeNode* sortedArrayToBST (vector<int>& num) { return sortedArrayToBST(num.begin(), num.end()); } template<typename RandomAccessIterator> TreeNode* sortedArrayToBST (RandomAccessIterator first, RandomAccessIterator last) { const auto length = distance(first, last); if (length <= 0) return nullptr; // // auto mid = first + length / 2; TreeNode* root = new TreeNode (*mid); root->left = sortedArrayToBST(first, mid); root->right = sortedArrayToBST(mid + 1, last); return root; } };

119.5.3 113 题 • Convert Sorted List to Binary Search Tree §5.3.5 5.3.5 Convert Sorted List to Binary Search Tree Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. 题 题 RandomAccessIt- erator 题 (bottom-up) http://leetcode.com/2010/11/convert-sorted-list-to-balanced- binary.html Convert Sorted Array to Binary Search Tree O(n log n) // LeetCode, Convert Sorted List to Binary Search Tree // Convert Sorted Array to Binary Search Tree // O(n^2) O(logn) class Solution { public: TreeNode* sortedListToBST (ListNode* head) { return sortedListToBST (head, listLength (head)); } TreeNode* sortedListToBST (ListNode* head, int len) { if (len == 0) return nullptr; if (len == 1) return new TreeNode (head->val); TreeNode* root = new TreeNode (nth_node (head, len / 2 + 1)->val); root->left = sortedListToBST (head, len / 2); root->right = sortedListToBST (nth_node (head, len / 2 + 2), (len - 1) / 2); return root; } int listLength (ListNode* node) { int n = 0; while(node) { ++n; node = node->next;

120.114 5 } return n; } ListNode* nth_node (ListNode* node, int n) { while (--n) node = node->next; return node; } }; // LeetCode, Convert Sorted List to Binary Search Tree // bottom-up O(n) O(logn) class Solution { public: TreeNode *sortedListToBST(ListNode *head) { int len = 0; ListNode *p = head; while (p) { len++; p = p->next; } return sortedListToBST(head, 0, len - 1); } private: TreeNode* sortedListToBST(ListNode*& list, int start, int end) { if (start > end) return nullptr; int mid = start + (end - start) / 2; TreeNode *leftChild = sortedListToBST(list, start, mid - 1); TreeNode *parent = new TreeNode(list->val); parent->left = leftChild; list = list->next; parent->right = sortedListToBST(list, mid + 1, end); return parent; } }; 题 • Convert Sorted Array to Binary Search Tree §5.3.4 5.4

121.5.4 115 §10.12.5 题 DFS 3! = 6 3 root->r->l r->root->l, r->l->root 5.4.1 Minimum Depth of Binary Tree Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. // LeetCode, Minimum Depth of Binary Tree // O(n) O(logn) class Solution { public: int minDepth(const TreeNode *root) { return minDepth(root, false); } private: static int minDepth(const TreeNode *root, bool hasbrother) { if (!root) return hasbrother ? INT_MAX : 0; return 1 + min(minDepth(root->left, root->right != NULL), minDepth(root->right, root->left != NULL)); } }; // LeetCode, Minimum Depth of Binary Tree // O(n) O(logn) class Solution { public: int minDepth(TreeNode* root) { if (root == nullptr) return 0; int result = INT_MAX; stack<pair<TreeNode*, int>> s;

122.116 5 s.push(make_pair(root, 1)); while (!s.empty()) { auto node = s.top().first; auto depth = s.top().second; s.pop(); if (node->left == nullptr && node->right == nullptr) result = min(result, depth); if (node->left && result > depth) // s.push(make_pair(node->left, depth + 1)); if (node->right && result > depth) // s.push(make_pair(node->right, depth + 1)); } return result; } }; 题 • Maximum Depth of Binary Tree §5.4.2 5.4.2 Maximum Depth of Binary Tree Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. // LeetCode, Maximum Depth of Binary Tree // O(n) O(logn) class Solution { public: int maxDepth(TreeNode *root) { if (root == nullptr) return 0; return max(maxDepth(root->left), maxDepth(root->right)) + 1; } };

123.5.4 117 题 • Minimum Depth of Binary Tree §5.4.1 5.4.3 Path Sum Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. For example: Given the below binary tree and sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1 return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22. 题 true false return 题 // LeetCode, Path Sum // O(n) O(logn) class Solution { public: bool hasPathSum(TreeNode *root, int sum) { if (root == nullptr) return false; if (root->left == nullptr && root->right == nullptr) // leaf return sum == root->val; return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val); } }; 题 • Path Sum II §5.4.4

124.118 5 5.4.4 Path Sum II Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum. For example: Given the below binary tree and sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 return [ [5,4,11,2], [5,8,4,5] ] 题 题 return // LeetCode, Path Sum II // O(n) O(logn) class Solution { public: vector<vector<int> > pathSum(TreeNode *root, int sum) { vector<vector<int> > result; vector<int> cur; // pathSum(root, sum, cur, result); return result; } private: void pathSum(TreeNode *root, int gap, vector<int> &cur, vector<vector<int> > &result) { if (root == nullptr) return; cur.push_back(root->val); if (root->left == nullptr && root->right == nullptr) { // leaf if (gap == root->val) result.push_back(cur); } pathSum(root->left, gap - root->val, cur, result); pathSum(root->right, gap - root->val, cur, result);

125.5.4 119 cur.pop_back(); } }; 题 • Path Sum §5.4.3 5.4.5 Binary Tree Maximum Path Sum Given a binary tree, find the maximum path sum. The path may start and end at any node in the tree. For example: Given the below binary tree, 1 / \ 2 3 Return 6. 题 题 §13.2 Array Binary Tree Array Binary Tree Binary Tree dfs L R L 0 L R 0 R // LeetCode, Binary Tree Maximum Path Sum // O(n) O(logn) class Solution { public: int maxPathSum(TreeNode *root) { max_sum = INT_MIN; dfs(root); return max_sum; } private: int max_sum; int dfs(const TreeNode *root) { if (root == nullptr) return 0; int l = dfs(root->left); int r = dfs(root->right);

126.120 5 int sum = root->val; if (l > 0) sum += l; if (r > 0) sum += r; max_sum = max(max_sum, sum); return max(r, l) > 0 ? max(r, l) + root->val : root->val; } }; return L->root->R L->root R->root 题 • Maximum Subarray §13.2 5.4.6 Populating Next Right Pointers in Each Node Given a binary tree struct TreeLinkNode { int val; TreeLinkNode *left, *right, *next; TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {} }; Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL. Note: • You may only use constant extra space. • You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children). For example, Given the following perfect binary tree, 1 / \ 2 3 / \ / \ 4 5 6 7 After calling your function, the tree should look like: 1 -> NULL / \ 2 -> 3 -> NULL / \ / \ 4->5->6->7 -> NULL

127.5.4 121 // LeetCode, Populating Next Right Pointers in Each Node // O(n) O(logn) class Solution { public: void connect(TreeLinkNode *root) { connect(root, NULL); } private: void connect(TreeLinkNode *root, TreeLinkNode *sibling) { if (root == nullptr) return; else root->next = sibling; connect(root->left, root->right); if (sibling) connect(root->right, sibling->left); else connect(root->right, nullptr); } }; 题 • Populating Next Right Pointers in Each Node II §5.1.12 5.4.7 Sum Root to Leaf Numbers Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path 1->2->3 which represents the number 123. Find the total sum of all root-to-leaf numbers. For example, 1 / \ 2 3 The root-to-leaf path 1->2 represents the number 12. The root-to-leaf path 1->3 represents the number 13. Return the sum = 12 + 13 = 25.

128.122 5 // LeetCode, Decode Ways // O(n) O(logn) class Solution { public: int sumNumbers(TreeNode *root) { return dfs(root, 0); } private: int dfs(TreeNode *root, int sum) { if (root == nullptr) return 0; if (root->left == nullptr && root->right == nullptr) return sum * 10 + root->val; return dfs(root->left, sum * 10 + root->val) + dfs(root->right, sum * 10 + root->val); } }; 题 •

129. 6 6.1 Merge Sorted Array Given two sorted integer arrays A and B, merge B into A as one sorted array. Note: You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively. //LeetCode, Merge Sorted Array // O(m+n) O(1) class Solution { public: void merge(vector<int>& A, int m, vector<int>& B, int n) { int ia = m - 1, ib = n - 1, icur = m + n - 1; while(ia >= 0 && ib >= 0) { A[icur--] = A[ia] >= B[ib] ? A[ia--] : B[ib--]; } while(ib >= 0) { A[icur--] = B[ib--]; } } }; 题 • Merge Two Sorted Lists §6.2 • Merge k Sorted Lists §6.3 123

130.124 6 6.2 Merge Two Sorted Lists Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. //LeetCode, Merge Two Sorted Lists // O(min(m,n)) O(1) class Solution { public: ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) { if (l1 == nullptr) return l2; if (l2 == nullptr) return l1; ListNode dummy(-1); ListNode *p = &dummy; for (; l1 != nullptr && l2 != nullptr; p = p->next) { if (l1->val > l2->val) { p->next = l2; l2 = l2->next; } else { p->next = l1; l1 = l1->next; } } p->next = l1 != nullptr ? l1 : l2; return dummy.next; } }; 题 • Merge Sorted Array §6.1 • Merge k Sorted Lists §6.3 6.3 Merge k Sorted Lists Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Merge Two Sorted Lists §6.2

131.6.4 Insertion Sort List 125 //LeetCode, Merge k Sorted Lists // O(n1+n2+...) O(1) // TODO: class Solution { public: ListNode *mergeKLists(vector<ListNode *> &lists) { if (lists.size() == 0) return nullptr; ListNode *p = lists[0]; for (int i = 1; i < lists.size(); i++) { p = mergeTwoLists(p, lists[i]); } return p; } // Merge Two Sorted Lists ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) { ListNode head(-1); for (ListNode* p = &head; l1 != nullptr || l2 != nullptr; p = p->next) { int val1 = l1 == nullptr ? INT_MAX : l1->val; int val2 = l2 == nullptr ? INT_MAX : l2->val; if (val1 <= val2) { p->next = l1; l1 = l1->next; } else { p->next = l2; l2 = l2->next; } } return head.next; } }; 题 • Merge Sorted Array §6.1 • Merge Two Sorted Lists §6.2 6.4 Insertion Sort List Sort a linked list using insertion sort.

132.126 6 // LeetCode, Insertion Sort List // O(n^2) O(1) class Solution { public: ListNode *insertionSortList(ListNode *head) { ListNode dummy(INT_MIN); //dummy.next = head; for (ListNode *cur = head; cur != nullptr;) { auto pos = findInsertPos(&dummy, cur->val); ListNode *tmp = cur->next; cur->next = pos->next; pos->next = cur; cur = tmp; } return dummy.next; } ListNode* findInsertPos(ListNode *head, int x) { ListNode *pre = nullptr; for (ListNode *cur = head; cur != nullptr && cur->val <= x; pre = cur, cur = cur->next) ; return pre; } }; 题 • Sort List, §6.5 6.5 Sort List Sort a linked list in O(nlogn) time using constant space complexity. O(nlogn) 题 ”Merge Two Sorted Lists” // LeetCode, Sort List // O(nlogn) O(1) class Solution {

133.6.6 First Missing Positive 127 public: ListNode *sortList(ListNode *head) { if (head == NULL || head->next == NULL)return head; // ListNode *fast = head, *slow = head; while (fast->next != NULL && fast->next->next != NULL) { fast = fast->next->next; slow = slow->next; } // fast = slow; slow = slow->next; fast->next = NULL; ListNode *l1 = sortList(head); // ListNode *l2 = sortList(slow); // return mergeTwoLists(l1, l2); } // Merge Two Sorted Lists ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) { ListNode dummy(-1); for (ListNode* p = &dummy; l1 != nullptr || l2 != nullptr; p = p->next) { int val1 = l1 == nullptr ? INT_MAX : l1->val; int val2 = l2 == nullptr ? INT_MAX : l2->val; if (val1 <= val2) { p->next = l1; l1 = l1->next; } else { p->next = l2; l2 = l2->next; } } return dummy.next; } }; 题 • Insertion Sort List §6.4 6.6 First Missing Positive Given an unsorted integer array, find the first missing positive integer. For example, Given [1,2,0] return 3, and [3,4,-1,1] return 2. Your algorithm should run in O(n) time and uses constant space.

134.128 6 (bucket sort) A[i]!= i+1 A[i] A[A[i]-1] A[i]== A[A[i]-1] // LeetCode, First Missing Positive // O(n) O(1) class Solution { public: int firstMissingPositive(vector<int>& nums) { bucket_sort(nums); for (int i = 0; i < nums.size(); ++i) if (nums[i] != (i + 1)) return i + 1; return nums.size() + 1; } private: static void bucket_sort(vector<int>& A) { const int n = A.size(); for (int i = 0; i < n; i++) { while (A[i] != i + 1) { if (A[i] <= 0 || A[i] > n || A[i] == A[A[i] - 1]) break; swap(A[i], A[A[i] - 1]); } } } }; 题 • Sort Colors, §6.7 6.7 Sort Colors Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. Note: You are not suppose to use the library’s sort function for this problem. Follow up: A rather straight forward solution is a two-pass algorithm using counting sort.

135.6.7 Sort Colors 129 First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s. Could you come up with an one-pass algorithm using only constant space? 0, 1, 2 (counting sort) 题 index red index blue index O(n) O(1) 3 partition 0 1 n 1 // LeetCode, Sort Colors // Counting Sort // O(n) O(1) class Solution { public: void sortColors(vector<int>& A) { int counts[3] = { 0 }; // for (int i = 0; i < A.size(); i++) counts[A[i]]++; for (int i = 0, index = 0; i < 3; i++) for (int j = 0; j < counts[i]; j++) A[index++] = i; } }; 2 // LeetCode, Sort Colors // O(n) O(1) class Solution { public: void sortColors(vector<int>& A) { // red index blue index int red = 0, blue = A.size() - 1; for (int i = 0; i < blue + 1;) { if (A[i] == 0) swap(A[i++], A[red++]); else if (A[i] == 2) swap(A[i], A[blue--]); else

136.130 6 i++; } } }; 3 // LeetCode, Sort Colors // use partition() // O(n) O(1) class Solution { public: void sortColors(vector<int>& nums) { partition(partition(nums.begin(), nums.end(), bind1st(equal_to<int>(), 0)), nums.end(), bind1st(equal_to<int>(), 1)); } }; 4 // LeetCode, Sort Colors // partition() // O(n) O(1) class Solution { public: void sortColors(vector<int>& nums) { partition(partition(nums.begin(), nums.end(), bind1st(equal_to<int>(), 0)), nums.end(), bind1st(equal_to<int>(), 1)); } private: template<typename ForwardIterator, typename UnaryPredicate> ForwardIterator partition(ForwardIterator first, ForwardIterator last, UnaryPredicate pred) { auto pos = first; for (; first != last; ++first) if (pred(*first)) swap(*first, *pos++); return pos; } }; 题 • First Missing Positive, §6.6

137. 7 7.1 Search for a Range Given a sorted array of integers, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1]. For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4]. STL // LeetCode, Search for a Range // STL // O(logn) O(1) class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { const int l = distance(nums.begin(), lower_bound(nums.begin(), nums.end(), target)); const int u = distance(nums.begin(), prev(upper_bound(nums.begin(), nums.end(), target if (nums[l] != target) // not found return vector<int> { -1, -1 }; else return vector<int> { l, u }; } }; lower_bound upper_bound // LeetCode, Search for a Range // lower_bound upper_bound // O(logn) O(1) class Solution { 131

138.132 7 public: vector<int> searchRange (vector<int>& nums, int target) { auto lower = lower_bound(nums.begin(), nums.end(), target); auto uppper = upper_bound(lower, nums.end(), target); if (lower == nums.end() || *lower != target) return vector<int> { -1, -1 }; else return vector<int> {distance(nums.begin(), lower), distance(nums.begin(), prev(upp } template<typename ForwardIterator, typename T> ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, T value) { while (first != last) { auto mid = next(first, distance(first, last) / 2); if (value > *mid) first = ++mid; else last = mid; } return first; } template<typename ForwardIterator, typename T> ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, T value) { while (first != last) { auto mid = next(first, distance (first, last) / 2); if (value >= *mid) first = ++mid; // lower_bound else last = mid; } return first; } }; 题 • Search Insert Position, §7.2 7.2 Search Insert Position Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array.

139.7.3 Search a 2D Matrix 133 Here are few examples. [1,3,5,6], 5 → 2 [1,3,5,6], 2 → 1 [1,3,5,6], 7 → 4 [1,3,5,6], 0 → 0 std::lower_bound() // LeetCode, Search Insert Position // lower_bound // O(logn) O(1) class Solution { public: int searchInsert(vector<int>& nums, int target) { return distance(nums.begin(), lower_bound(nums.begin(), nums.end(), target)); } template<typename ForwardIterator, typename T> ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, T value) { while (first != last) { auto mid = next(first, distance(first, last) / 2); if (value > *mid) first = ++mid; else last = mid; } return first; } }; 题 • Search for a Range, §7.1 7.3 Search a 2D Matrix Write an efficient algorithm that searches for a value in an m × n matrix. This matrix has the following properties: • Integers in each row are sorted from left to right. • The first integer of each row is greater than the last integer of the previous row.

140.134 7 For example, Consider the following matrix: [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] Given target = 3, return true. // LeetCode, Search a 2D Matrix // O(logn) O(1) class Solution { public: bool searchMatrix(const vector<vector<int>>& matrix, int target) { if (matrix.empty()) return false; const size_t m = matrix.size(); const size_t n = matrix.front().size(); int first = 0; int last = m * n; while (first < last) { int mid = first + (last - first) / 2; int value = matrix[mid / n][mid % n]; if (value == target) return true; else if (value < target) first = mid + 1; else last = mid; } return false; } }; 题 •

141. 8 8.1 Subsets Given a set of distinct integers, S, return all possible subsets. Note: • Elements in a subset must be in non-descending order. • The solution set must not contain duplicate subsets. For example, If S = [1,2,3], a solution is: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] 8.1.1 // LeetCode, Subsets // O(2^n) O(n) class Solution { public: vector<vector<int> > subsets(vector<int> &S) { sort(S.begin(), S.end()); // vector<vector<int> > result; vector<int> path; subsets(S, path, 0, result); return result; 135

142.136 8 } private: static void subsets(const vector<int> &S, vector<int> &path, int step, vector<vector<int> > &result) { if (step == S.size()) { result.push_back(path); return; } // S[step] subsets(S, path, step + 1, result); // S[step] path.push_back(S[step]); subsets(S, path, step + 1, result); path.pop_back(); } }; bool selected[n] // LeetCode, Subsets // O(2^n) O(n) class Solution { public: vector<vector<int> > subsets(vector<int> &S) { sort(S.begin(), S.end()); // vector<vector<int> > result; vector<bool> selected(S.size(), false); subsets(S, selected, 0, result); return result; } private: static void subsets(const vector<int> &S, vector<bool> &selected, int step, vector<vector<int> > &result) { if (step == S.size()) { vector<int> subset; for (int i = 0; i < S.size(); i++) { if (selected[i]) subset.push_back(S[i]); } result.push_back(subset); return; } // S[step] selected[step] = false; subsets(S, selected, step + 1, result); // S[step] selected[step] = true; subsets(S, selected, step + 1, result);

143.8.1 Subsets 137 } }; 8.1.2 // LeetCode, Subsets // O(2^n) O(1) class Solution { public: vector<vector<int> > subsets(vector<int> &S) { sort(S.begin(), S.end()); // vector<vector<int> > result(1); for (auto elem : S) { result.reserve(result.size() * 2); auto half = result.begin() + result.size(); copy(result.begin(), half, back_inserter(result)); for_each(half, result.end(), [&elem](decltype(result[0]) &e){ e.push_back(elem); }); } return result; } }; int int i 1 S[i] 0 S={A,B,C,D} 0110=6 {B,C} B1 B2 B1 ∪ B2 , B1 ∩ B2 , B1 △B2 // LeetCode, Subsets // O(2^n) O(1) class Solution { public: vector<vector<int> > subsets(vector<int> &S) { sort(S.begin(), S.end()); // vector<vector<int> > result; const size_t n = S.size(); vector<int> v; for (size_t i = 0; i < 1 << n; i++) { for (size_t j = 0; j < n; j++) { if (i & 1 << j) v.push_back(S[j]); } result.push_back(v); v.clear();

144.138 8 } return result; } }; 题 • Subsets II §8.2 8.2 Subsets II Given a collection of integers that might contain duplicates, S, return all possible subsets. Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets. For example, If S = [1,2,2], a solution is: [ [2], [1], [1,2,2], [2,2], [1,2], [] ] 题 题 题 0 1 0 8.2.1 // LeetCode, Subsets II // 1 O(2^n) O(n) class Solution { public: vector<vector<int> > subsetsWithDup(vector<int> &S) { sort(S.begin(), S.end()); // vector<vector<int> > result; vector<int> path; dfs(S, S.begin(), path, result);

145.8.2 Subsets II 139 return result; } private: static void dfs(const vector<int> &S, vector<int>::iterator start, vector<int> &path, vector<vector<int> > &result) { result.push_back(path); for (auto i = start; i < S.end(); i++) { if (i != start && *i == *(i-1)) continue; path.push_back(*i); dfs(S, i + 1, path, result); path.pop_back(); } } }; // LeetCode, Subsets II // 2 O(2^n) O(n) class Solution { public: vector<vector<int> > subsetsWithDup(vector<int> &S) { vector<vector<int> > result; sort(S.begin(), S.end()); // unordered_map<int, int> count_map; // for_each(S.begin(), S.end(), [&count_map](int e) { if (count_map.find(e) != count_map.end()) count_map[e]++; else count_map[e] = 1; }); // map pair vector vector<pair<int, int> > elems; for_each(count_map.begin(), count_map.end(), [&elems](const pair<int, int> &e) { elems.push_back(e); }); sort(elems.begin(), elems.end()); vector<int> path; // subsets(elems, 0, path, result); return result; } private: static void subsets(const vector<pair<int, int> > &elems, size_t step, vector<int> &path, vector<vector<int> > &result) { if (step == elems.size()) { result.push_back(path); return; }

146.140 8 for (int i = 0; i <= elems[step].second; i++) { for (int j = 0; j < i; ++j) { path.push_back(elems[step].first); } subsets(elems, step + 1, path, result); for (int j = 0; j < i; ++j) { path.pop_back(); } } } }; // LeetCode, Subsets II // O(2^n) O(n) class Solution { public: vector<vector<int> > subsetsWithDup(vector<int> &S) { vector<vector<int> > result; // sort(S.begin(), S.end()); vector<int> count(S.back() - S.front() + 1, 0); // for (auto i : S) { count[i - S[0]]++; } // vector<int> selected(S.back() - S.front() + 1, -1); subsets(S, count, selected, 0, result); return result; } private: static void subsets(const vector<int> &S, vector<int> &count, vector<int> &selected, size_t step, vector<vector<int> > &result) { if (step == count.size()) { vector<int> subset; for(size_t i = 0; i < selected.size(); i++) { for (int j = 0; j < selected[i]; j++) { subset.push_back(i+S[0]); } } result.push_back(subset); return; } for (int i = 0; i <= count[step]; i++) { selected[step] = i; subsets(S, count, selected, step + 1, result); } }

147.8.2 Subsets II 141 }; 8.2.2 // LeetCode, Subsets II // // O(2^n) O(1) class Solution { public: vector<vector<int> > subsetsWithDup(vector<int> &S) { sort(S.begin(), S.end()); // vector<vector<int> > result(1); size_t previous_size = 0; for (size_t i = 0; i < S.size(); ++i) { const size_t size = result.size(); for (size_t j = 0; j < size; ++j) { if (i == 0 || S[i] != S[i-1] || j >= previous_size) { result.push_back(result[j]); result.back().push_back(S[i]); } } previous_size = size; } return result; } }; // LeetCode, Subsets II // O(2^n) O(1) class Solution { public: vector<vector<int> > subsetsWithDup(vector<int> &S) { sort(S.begin(), S.end()); // // set unordered_set set<vector<int> > result; const size_t n = S.size(); vector<int> v; for (size_t i = 0; i < 1U << n; ++i) { for (size_t j = 0; j < n; ++j) { if (i & 1 << j) v.push_back(S[j]); } result.insert(v); v.clear(); } vector<vector<int> > real_result;

148.142 8 copy(result.begin(), result.end(), back_inserter(real_result)); return real_result; } }; 题 • Subsets §8.1 8.3 Permutations Given a collection of numbers, return all possible permutations. For example, [1,2,3] have the following permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1]. 8.3.1 next_permutation() std::next_permutation() OJ API // LeetCode, Permutations // O(n!) O(1) class Solution { public: vector<vector<int> > permute(vector<int> &num) { vector<vector<int> > result; sort(num.begin(), num.end()); do { result.push_back(num); } while(next_permutation(num.begin(), num.end())); return result; } }; 8.3.2 next_permutation() §2.1.12

149.8.3 Permutations 143 // LeetCode, Permutations // next_permutation() // O(n!) O(1) class Solution { public: vector<vector<int> > permute(vector<int> &num) { vector<vector<int> > result; sort(num.begin(), num.end()); do { result.push_back(num); // 2.1.12 next_permutation() // std::next_permutation() } while(next_permutation(num.begin(), num.end())); return result; } }; 8.3.3 题 解 题 // LeetCode, Permutations // // O(n!) O(n) class Solution { public: vector<vector<int> > permute(vector<int>& num) { sort(num.begin(), num.end()); vector<vector<int>> result; vector<int> path; // dfs(num, path, result); return result; } private: void dfs(const vector<int>& num, vector<int> &path, vector<vector<int> > &result) { if (path.size() == num.size()) { // result.push_back(path); return; }

150.144 8 // for (auto i : num) { // i path auto pos = find(path.begin(), path.end(), i); if (pos == path.end()) { path.push_back(i); dfs(num, path, result); path.pop_back(); } } } }; 题 • Next Permutation, §2.1.12 • Permutation Sequence, §2.1.13 • Permutations II, §8.4 • Combinations, §8.5 8.4 Permutations II Given a collection of numbers that might contain duplicates, return all possible unique permutations. For example, [1,1,2] have the following unique permutations: [1,1,2], [1,2,1], and [2,1,1]. 8.4.1 next_permutation() std::next_permutation() 题 8.4.2 next_permutation() std::next_permutation() 题 8.4.3 permute() p 题

151.8.4 Permutations II 145 // LeetCode, Permutations II // O(n!) O(n) class Solution { public: vector<vector<int> > permuteUnique(vector<int>& num) { sort(num.begin(), num.end()); unordered_map<int, int> count_map; // for_each(num.begin(), num.end(), [&count_map](int e) { if (count_map.find(e) != count_map.end()) count_map[e]++; else count_map[e] = 1; }); // map pair vector vector<pair<int, int> > elems; for_each(count_map.begin(), count_map.end(), [&elems](const pair<int, int> &e) { elems.push_back(e); }); vector<vector<int>> result; // vector<int> p; // n = num.size(); permute(elems.begin(), elems.end(), p, result); return result; } private: size_t n; typedef vector<pair<int, int> >::const_iterator Iter; void permute(Iter first, Iter last, vector<int> &p, vector<vector<int> > &result) { if (n == p.size()) { // result.push_back(p); } // for (auto i = first; i != last; i++) { int count = 0; // *i p for (auto j = p.begin(); j != p.end(); j++) { if (i->first == *j) { count ++; } } if (count < i->second) { p.push_back(i->first); permute(first, last, p, result);

152.146 8 p.pop_back(); // } } } }; 题 • Next Permutation, §2.1.12 • Permutation Sequence, §2.1.13 • Permutations, §8.3 • Combinations, §8.5 8.5 Combinations Given two integers n and k, return all possible combinations of k numbers out of 1...n. For example, If n = 4 and k = 2, a solution is: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] 8.5.1 // LeetCode, Combinations // // O(n!) O(n) class Solution { public: vector<vector<int> > combine(int n, int k) { vector<vector<int> > result; vector<int> path; dfs(n, k, 1, 0, path, result); return result; } private: // start , cur static void dfs(int n, int k, int start, int cur, vector<int> &path, vector<vector<int> > &result) { if (cur == k) { result.push_back(path);

153.8.6 Letter Combinations of a Phone Number 147 } for (int i = start; i <= n; ++i) { path.push_back(i); dfs(n, k, i + 1, cur + 1, path, result); path.pop_back(); } } }; 8.5.2 // LeetCode, Combinations // use prev_permutation() // O((n-k)!) O(n) class Solution { public: vector<vector<int> > combine(int n, int k) { vector<int> values(n); iota(values.begin(), values.end(), 1); vector<bool> select(n, false); fill_n(select.begin(), k, true); vector<vector<int> > result; do{ vector<int> one(k); for (int i = 0, index = 0; i < n; ++i) if (select[i]) one[index++] = values[i]; result.push_back(one); } while(prev_permutation(select.begin(), select.end())); return result; } }; 题 • Next Permutation, §2.1.12 • Permutation Sequence, §2.1.13 • Permutations, §8.3 • Permutations II, §8.4 8.6 Letter Combinations of a Phone Number Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below.

154.148 8 8-1 Phone Keyboard Input:Digit string "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. Note: Although the above answer is in lexicographical order, your answer could be in any order you want. 8.6.1 // LeetCode, Letter Combinations of a Phone Number // O(3^n) O(n) class Solution { public: const vector<string> keyboard { " ", "", "abc", "def", // '0','1','2',... "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" }; vector<string> letterCombinations (const string &digits) { vector<string> result; if (digits.empty()) return result; dfs(digits, 0, "", result); return result; } void dfs(const string &digits, size_t cur, string path, vector<string> &result) { if (cur == digits.size()) { result.push_back(path); return; } for (auto c : keyboard[digits[cur] - '0']) { dfs(digits, cur + 1, path + c, result); }

155.8.6 Letter Combinations of a Phone Number 149 } }; 8.6.2 // LeetCode, Letter Combinations of a Phone Number // O(3^n) O(1) class Solution { public: const vector<string> keyboard { " ", "", "abc", "def", // '0','1','2',... "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" }; vector<string> letterCombinations (const string &digits) { if (digits.empty()) return vector<string>(); vector<string> result(1, ""); for (auto d : digits) { const size_t n = result.size(); const size_t m = keyboard[d - '0'].size(); result.resize(n * m); for (size_t i = 0; i < m; ++i) copy(result.begin(), result.begin() + n, result.begin() + n * i); for (size_t i = 0; i < m; ++i) { auto begin = result.begin(); for_each(begin + n * i, begin + n * (i+1), [&](string &s) { s += keyboard[d - '0'][i]; }); } } return result; } }; 题 •

156. 9 题 A* 解 题 题 解 9.1 Word Ladder Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that: • Only one letter can be changed at a time • Each intermediate word must exist in the dictionary For example, Given: start = "hit" end = "cog" dict = ["hot","dot","dog","lot","log"] As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5. Note: • Return 0 if there is no such transformation sequence. • All words have the same length. • All words contain only lowercase alphabetic characters. 150

157.9.1 Word Ladder 151 //LeetCode, Word Ladder // O(n) O(n) struct state_t { string word; int level; state_t() { word = ""; level = 0; } state_t(const string& word, int level) { this->word = word; this->level = level; } bool operator==(const state_t &other) const { return this->word == other.word; } }; namespace std { template<> struct hash<state_t> { public: size_t operator()(const state_t& s) const { return str_hash(s.word); } private: std::hash<std::string> str_hash; }; } class Solution { public: int ladderLength(const string& start, const string &end, const unordered_set<string> &dict) { queue<state_t> q; unordered_set<state_t> visited; // auto state_is_valid = [&](const state_t& s) { return dict.find(s.word) != dict.end() || s.word == end; }; auto state_is_target = [&](const state_t &s) {return s.word == end; }; auto state_extend = [&](const state_t &s) { unordered_set<state_t> result; for (size_t i = 0; i < s.word.size(); ++i) { state_t new_state(s.word, s.level + 1); for (char c = 'a'; c <= 'z'; c++) { // if (c == new_state.word[i]) continue; swap(c, new_state.word[i]);

158.152 9 if (state_is_valid(new_state) && visited.find(new_state) == visited.end()) { result.insert(new_state); } swap(c, new_state.word[i]); // } } return result; }; state_t start_state(start, 0); q.push(start_state); visited.insert(start_state); while (!q.empty()) { // const auto& pop() // const auto state = q.front(); q.pop(); if (state_is_target(state)) { return state.level + 1; } const auto& new_states = state_extend(state); for (const auto& new_state : new_states) { q.push(new_state); visited.insert(new_state); } } return 0; } }; //LeetCode, Word Ladder // O(n) O(n) class Solution { public: int ladderLength(const string& start, const string &end, const unordered_set<string> &dict) { queue<string> current, next; // unordered_set<string> visited; // int level = -1; // auto state_is_valid = [&](const string& s) { return dict.find(s) != dict.end() || s == end; }; auto state_is_target = [&](const string &s) {return s == end;}; auto state_extend = [&](const string &s) { unordered_set<string> result;

159.9.1 Word Ladder 153 for (size_t i = 0; i < s.size(); ++i) { string new_word(s); for (char c = 'a'; c <= 'z'; c++) { // if (c == new_word[i]) continue; swap(c, new_word[i]); if (state_is_valid(new_word) && visited.find(new_word) == visited.end()) { result.insert(new_word); } swap(c, new_word[i]); // } } return result; }; current.push(start); visited.insert(start); while (!current.empty()) { ++level; while (!current.empty()) { // const auto& pop() // const auto state = current.front(); current.pop(); if (state_is_target(state)) { return level + 1; } const auto& new_states = state_extend(state); for (const auto& new_state : new_states) { next.push(new_state); visited.insert(new_state); } } swap(next, current); } return 0; } }; 题 • Word Ladder II §9.2

160.154 9 9.2 Word Ladder II Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that: • Only one letter can be changed at a time • Each intermediate word must exist in the dictionary For example, Given: start = "hit" end = "cog" dict = ["hot","dot","dog","lot","log"] Return [ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ] Note: • All words have the same length. • All words contain only lowercase alphabetic characters. Word Ladder 题 BFS //LeetCode, Word Ladder II // O(n) O(n) struct state_t { string word; int level; state_t() { word = ""; level = 0; } state_t(const string& word, int level) { this->word = word; this->level = level; }

161.9.2 Word Ladder II 155 bool operator==(const state_t &other) const { return this->word == other.word; } }; namespace std { template<> struct hash<state_t> { public: size_t operator()(const state_t& s) const { return str_hash(s.word); } private: std::hash<std::string> str_hash; }; } class Solution { public: vector<vector<string> > findLadders(const string& start, const string& end, const unordered_set<string> &dict) { queue<state_t> q; unordered_set<state_t> visited; // unordered_map<state_t, vector<state_t> > father; // DAG auto state_is_valid = [&](const state_t& s) { return dict.find(s.word) != dict.end() || s.word == end; }; auto state_is_target = [&](const state_t &s) {return s.word == end; }; auto state_extend = [&](const state_t &s) { unordered_set<state_t> result; for (size_t i = 0; i < s.word.size(); ++i) { state_t new_state(s.word, s.level + 1); for (char c = 'a'; c <= 'z'; c++) { // if (c == new_state.word[i]) continue; swap(c, new_state.word[i]); if (state_is_valid(new_state)) { auto visited_iter = visited.find(new_state); if (visited_iter != visited.end()) { if (visited_iter->level < new_state.level) { // do nothing } else if (visited_iter->level == new_state.level) { result.insert(new_state); } else { // not possible throw std::logic_error("not possible to get here"); } } else { result.insert(new_state);

162.156 9 } } swap(c, new_state.word[i]); // } } return result; }; vector<vector<string>> result; state_t start_state(start, 0); q.push(start_state); visited.insert(start_state); while (!q.empty()) { // const auto& pop() // const auto state = q.front(); q.pop(); // // if (!result.empty() && state.level + 1 > result[0].size()) break; if (state_is_target(state)) { vector<string> path; gen_path(father, start_state, state, path, result); continue; } // A B // q // visited.insert(state); // const auto& new_states = state_extend(state); for (const auto& new_state : new_states) { if (visited.find(new_state) == visited.end()) { q.push(new_state); } visited.insert(new_state); father[new_state].push_back(state); } } return result; } private: void gen_path(unordered_map<state_t, vector<state_t> > &father, const state_t &start, const state_t &state, vector<string> &path, vector<vector<string> > &result) { path.push_back(state.word); if (state == start) { if (!result.empty()) { if (path.size() < result[0].size()) {

163.9.2 Word Ladder II 157 result.clear(); result.push_back(path); reverse(result.back().begin(), result.back().end()); } else if (path.size() == result[0].size()) { result.push_back(path); reverse(result.back().begin(), result.back().end()); } else { // not possible throw std::logic_error("not possible to get here "); } } else { result.push_back(path); reverse(result.back().begin(), result.back().end()); } } else { for (const auto& f : father[state]) { gen_path(father, start, f, path, result); } } path.pop_back(); } }; //LeetCode, Word Ladder II // O(n) O(n) class Solution { public: vector<vector<string> > findLadders(const string& start, const string& end, const unordered_set<string> &dict) { // unordered_set // vector, next // father next unordered_set<string> current, next; unordered_set<string> visited; // unordered_map<string, vector<string> > father; // DAG int level = -1; // auto state_is_valid = [&](const string& s) { return dict.find(s) != dict.end() || s == end; }; auto state_is_target = [&](const string &s) {return s == end;}; auto state_extend = [&](const string &s) { unordered_set<string> result; for (size_t i = 0; i < s.size(); ++i) { string new_word(s); for (char c = 'a'; c <= 'z'; c++) { // if (c == new_word[i]) continue;

164.158 9 swap(c, new_word[i]); if (state_is_valid(new_word) && visited.find(new_word) == visited.end()) { result.insert(new_word); } swap(c, new_word[i]); // } } return result; }; vector<vector<string> > result; current.insert(start); while (!current.empty()) { ++ level; // // if (!result.empty() && level+1 > result[0].size()) break; // 1. visited, // 2. current visited, // for (const auto& state : current) visited.insert(state); for (const auto& state : current) { if (state_is_target(state)) { vector<string> path; gen_path(father, path, start, state, result); continue; } const auto new_states = state_extend(state); for (const auto& new_state : new_states) { next.insert(new_state); father[new_state].push_back(state); } } current.clear(); swap(current, next); } return result; } private: void gen_path(unordered_map<string, vector<string> > &father, vector<string> &path, const string &start, const string &word, vector<vector<string> > &result) { path.push_back(word); if (word == start) { if (!result.empty()) {

165.9.2 Word Ladder II 159 if (path.size() < result[0].size()) { result.clear(); result.push_back(path); } else if(path.size() == result[0].size()) { result.push_back(path); } else { // not possible throw std::logic_error("not possible to get here"); } } else { result.push_back(path); } reverse(result.back().begin(), result.back().end()); } else { for (const auto& f : father[word]) { gen_path(father, path, start, f, result); } } path.pop_back(); } }; 题 dict 题 //LeetCode, Word Ladder II // O(n) O(n) class Solution { public: vector<vector<string> > findLadders(const string& start, const string &end, const unordered_set<string> &dict) { const auto& g = build_graph(dict); vector<state_t*> pool; queue<state_t*> q; // // value unordered_map<string, int> visited; auto state_is_target = [&](const state_t *s) {return s->word == end; }; vector<vector<string>> result; q.push(create_state(nullptr, start, 0, pool)); while (!q.empty()) { state_t* state = q.front(); q.pop(); // // if (!result.empty() && state->level+1 > result[0].size()) break; if (state_is_target(state)) {

166.160 9 const auto& path = gen_path(state); if (result.empty()) { result.push_back(path); } else { if (path.size() < result[0].size()) { result.clear(); result.push_back(path); } else if (path.size() == result[0].size()) { result.push_back(path); } else { // not possible throw std::logic_error("not possible to get here"); } } continue; } visited[state->word] = state->level; // auto iter = g.find(state->word); if (iter == g.end()) continue; for (const auto& neighbor : iter->second) { auto visited_iter = visited.find(neighbor); if (visited_iter != visited.end() && visited_iter->second < state->level + 1) { continue; } q.push(create_state(state, neighbor, state->level + 1, pool)); } } // release all states for (auto state : pool) { delete state; } return result; } private: struct state_t { state_t* father; string word; int level; // 0 state_t(state_t* father_, const string& word_, int level_) : father(father_), word(word_), level(level_) {} }; state_t* create_state(state_t* parent, const string& value, int length, vector<state_t*>& pool) {

167.9.2 Word Ladder II 161 state_t* node = new state_t(parent, value, length); pool.push_back(node); return node; } vector<string> gen_path(const state_t* node) { vector<string> path; while(node != nullptr) { path.push_back(node->word); node = node->father; } reverse(path.begin(), path.end()); return path; } unordered_map<string, unordered_set<string> > build_graph( const unordered_set<string>& dict) { unordered_map<string, unordered_set<string> > adjacency_list; for (const auto& word : dict) { for (size_t i = 0; i < word.size(); ++i) { string new_word(word); for (char c = 'a'; c <= 'z'; c++) { // if (c == new_word[i]) continue; swap(c, new_word[i]); if ((dict.find(new_word) != dict.end())) { auto iter = adjacency_list.find(word); if (iter != adjacency_list.end()) { iter->second.insert(new_word); } else { adjacency_list.insert(pair<string, unordered_set<string>>(word, unordered_set<string>())); adjacency_list[word].insert(new_word); } } swap(c, new_word[i]); // } } } return adjacency_list; } }; 题 • Word Ladder §9.1

168.162 9 9.3 Surrounded Regions Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region . For example, X X X X X O O X X X O X X O X X After running your function, the board should be: X X X X X X X X X X X X X O X X 'O' // LeetCode, Surrounded Regions // BFS O(n) O(n) class Solution { public: void solve(vector<vector<char>> &board) { if (board.empty()) return; const int m = board.size(); const int n = board[0].size(); for (int i = 0; i < n; i++) { bfs(board, 0, i); bfs(board, m - 1, i); } for (int j = 1; j < m - 1; j++) { bfs(board, j, 0); bfs(board, j, n - 1); } for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (board[i][j] == 'O') board[i][j] = 'X'; else if (board[i][j] == '+') board[i][j] = 'O'; } private: void bfs(vector<vector<char>> &board, int i, int j) {

169.9.3 Surrounded Regions 163 typedef pair<int, int> state_t; queue<state_t> q; const int m = board.size(); const int n = board[0].size(); auto state_is_valid = [&](const state_t &s) { const int x = s.first; const int y = s.second; if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O') return false; return true; }; auto state_extend = [&](const state_t &s) { vector<state_t> result; const int x = s.first; const int y = s.second; // const state_t new_states[4] = {{x-1,y}, {x+1,y}, {x,y-1}, {x,y+1}}; for (int k = 0; k < 4; ++k) { if (state_is_valid(new_states[k])) { // board[new_states[k].first][new_states[k].second] = '+'; result.push_back(new_states[k]); } } return result; }; state_t start = { i, j }; if (state_is_valid(start)) { board[i][j] = '+'; q.push(start); } while (!q.empty()) { auto cur = q.front(); q.pop(); auto new_states = state_extend(cur); for (auto s : new_states) q.push(s); } } }; 题 •

170.164 9 9.4 9.4.1 DAG 解 9.4.2 1. (a) + (b) i. ii. 4 2. 3. 2 题 1 4. BFS (a) (b) DAG visited visited (c) i. ii. unordered_- set head next §?? 2

171.9.4 165 iii. 5. 题 9.4.3 hashset queue vector 1. state_t level level A* queue priority_queue 2. current, next level level level hashset (bool visited[STATE_MAX] vector<bool> visited(STATE_MAX, false)) STL set unordered_set STL unordered_map<state_t, state_t > father STATE_MAX (state_t nodes[STATE_- MAX]) bfs_common.h /** */ struct state_t { int data1; /** . */ int data2; /** . */ // dataN; /** */ int action; /** . */ int level; /** 0 -1 */ bool operator==(const state_t &other) const { return true; // 题 } }; // hash // 1 hash namespace std { template<> struct hash<state_t> {

172.166 9 size_t operator()(const state_t & x) const { return 0; // 题 } }; } // 2 hash class Hasher { public: Hasher(int _m) : m(_m) {}; size_t operator()(const state_t &s) const { return 0; // 题 } private: int m; // }; /** * @brief . * @param[in] father * @param[in] target * @return target */ vector<state_t> gen_path(const unordered_map<state_t, state_t> &father, const state_t &target) { vector<state_t> path; path.push_back(target); for (state_t cur = target; father.find(cur) != father.end(); cur = father.at(cur)) path.push_back(cur); reverse(path.begin(), path.end()); return path; } /** * . * @param[in] father * @param[in] start * @param[in] state * @return */ void gen_path(unordered_map<state_t, vector<state_t> > &father, const string &start, const state_t& state, vector<state_t> &path, vector<vector<state_t> > &result) { path.push_back(state); if (state == start) { if (!result.empty()) { if (path.size() < result[0].size()) { result.clear(); result.push_back(path);

173.9.4 167 } else if(path.size() == result[0].size()) { result.push_back(path); } else { // not possible throw std::logic_error("not possible to get here"); } } else { result.push_back(path); } reverse(result.back().begin(), result.back().end()); } else { for (const auto& f : father[state]) { gen_path(father, start, f, path, result); } } path.pop_back(); } bfs_common.h bfs_template.cpp #include "bfs_common.h" /** * @brief . * @param[in] start * @param[in] data * @return */ vector<state_t> bfs(state_t &start, const vector<vector<int>> &grid) { queue<state_t> q; // unordered_set<state_t> visited; // unordered_map<state_t, state_t> father; // // auto state_is_valid = [&](const state_t &s) { /*...*/ }; // auto state_is_target = [&](const state_t &s) { /*...*/ }; // auto state_extend = [&](const state_t &s) { unordered_set<state_t> result; for (/*...*/) { const state_t new_state = /*...*/; if (state_is_valid(new_state) && visited.find(new_state) != visited.end()) { result.insert(new_state); } }

174.168 9 return result; }; assert (start.level == 0); q.push(start); while (!q.empty()) { // const auto& pop() // const state_t state = q.front(); q.pop(); visited.insert(state); // if (state_is_target(state)) { return return gen_path(father, target); // // return state.level + 1; // } // vector<state_t> new_states = state_extend(state); for (const auto& new_state : new_states) { q.push(new_state); father[new_state] = state; // // visited.insert(state); // visited // q // visited while // , visited.insert(start) } } return vector<state_t>(); //return 0; } bfs_template.cpp bfs_template1.cpp #include "bfs_common.h" /** * @brief . * @param[in] start * @param[in] data * @return */ vector<state_t> bfs(const state_t &start, const type& data) { queue<state_t> next, current; // unordered_set<state_t> visited; // unordered_map<state_t, state_t> father; // int level = -1; // //

175.9.4 169 auto state_is_valid = [&](const state_t &s) { /*...*/ }; // auto state_is_target = [&](const state_t &s) { /*...*/ }; // auto state_extend = [&](const state_t &s) { unordered_set<state_t> result; for (/*...*/) { const state_t new_state = /*...*/; if (state_is_valid(new_state) && visited.find(new_state) != visited.end()) { result.insert(new_state); } } return result; }; current.push(start); while (!current.empty()) { ++level; while (!current.empty()) { // const auto& pop() // const auto state = current.front(); current.pop(); visited.insert(state); if (state_is_target(state)) { return return gen_path(father, state); // // return state.level + 1; // } const auto& new_states = state_extend(state); for (const auto& new_state : new_states) { next.push(new_state); father[new_state] = state; // visited.insert(state); // visited // current // visited while // , visited.insert(start) } } swap(next, current); //!!! } return vector<state_t>(); // return 0; } bfs_template1.cpp

176.170 9 bfs_template.cpp /** * @brief . * @param[in] start * @param[in] data * @return */ vector<vector<state_t> > bfs(const state_t &start, const type& data) { queue<state_t> q; unordered_set<state_t> visited; // unordered_map<state_t, vector<state_t> > father; // DAG auto state_is_valid = [&](const state_t& s) { /*...*/ }; auto state_is_target = [&](const state_t &s) { /*...*/ }; auto state_extend = [&](const state_t &s) { unordered_set<state_t> result; for (/*...*/) { const state_t new_state = /*...*/; if (state_is_valid(new_state)) { auto visited_iter = visited.find(new_state); if (visited_iter != visited.end()) { if (visited_iter->level < new_state.level) { // do nothing } else if (visited_iter->level == new_state.level) { result.insert(new_state); } else { // not possible throw std::logic_error("not possible to get here"); } } else { result.insert(new_state); } } } return result; }; vector<vector<string>> result; state_t start_state(start, 0); q.push(start_state); visited.insert(start_state); while (!q.empty()) { // const auto& pop() // const auto state = q.front(); q.pop(); // //

177.9.4 171 if (!result.empty() && state.level + 1 > result[0].size()) break; if (state_is_target(state)) { vector<string> path; gen_path(father, start_state, state, path, result); continue; } // A B // q // visited.insert(state); // const auto& new_states = state_extend(state); for (const auto& new_state : new_states) { if (visited.find(new_state) == visited.end()) { q.push(new_state); } visited.insert(new_state); father[new_state].push_back(state); } } return result; } bfs_template.cpp bfs_template.cpp #include "bfs_common.h" /** * @brief . * @param[in] start * @param[in] data * @return */ vector<vector<state_t> > bfs(const state_t &start, const type& data) { // unordered_set // vector, next // father next unordered_set<string> current, next; unordered_set<state_t> visited; // unordered_map<state_t, vector<state_t> > father; // DAG int level = -1; // // auto state_is_valid = [&](const state_t &s) { /*...*/ }; // auto state_is_target = [&](const state_t &s) { /*...*/ }; //

178.172 9 auto state_extend = [&](const state_t &s) { unordered_set<state_t> result; for (/*...*/) { const state_t new_state = /*...*/; if (state_is_valid(new_state) && visited.find(new_state) != visited.end()) { result.insert(new_state); } } return result; }; vector<vector<state_t> > result; current.insert(start); while (!current.empty()) { ++ level; // // if (!result.empty() && level+1 > result[0].size()) break; // 1. visited, // 2. current visited, // for (const auto& state : current) visited.insert(state); for (const auto& state : current) { if (state_is_target(state)) { vector<string> path; gen_path(father, path, start, state, result); continue; } const auto new_states = state_extend(state); for (const auto& new_state : new_states) { next.insert(new_state); father[new_state].push_back(state); } } current.clear(); swap(current, next); } return result; } bfs_template.cpp

179. 10 10.1 Palindrome Partitioning Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. For example, given s = "aab", Return [ ["aa","b"], ["a","a","b"] ] n n−1 O(2n−1 ) 1 //LeetCode, Palindrome Partitioning // O(2^n) O(n) class Solution { public: vector<vector<string>> partition(string s) { vector<vector<string>> result; vector<string> path; // partition dfs(s, path, result, 0, 1); return result; } // prev , start void dfs(string &s, vector<string>& path, vector<vector<string>> &result, size_t prev, size_t start) { if (start == s.size()) { // if (isPalindrome(s, prev, start - 1)) { // path.push_back(s.substr(prev, start - prev)); 173

180.174 10 result.push_back(path); path.pop_back(); } return; } // dfs(s, path, result, prev, start + 1); // [prev, start-1] if (isPalindrome(s, prev, start - 1)) { // path.push_back(s.substr(prev, start - prev)); dfs(s, path, result, start, start + 1); path.pop_back(); } } bool isPalindrome(const string &s, int start, int end) { while (start < end && s[start] == s[end]) { ++start; --end; } return start >= end; } }; 2 Combination Sum, Combination Sum II //LeetCode, Palindrome Partitioning // O(2^n) O(n) class Solution { public: vector<vector<string>> partition(string s) { vector<vector<string>> result; vector<string> path; // partition DFS(s, path, result, 0); return result; } // s[start] partition void DFS(string &s, vector<string>& path, vector<vector<string>> &result, int start) { if (start == s.size()) { result.push_back(path); return; } for (int i = start; i < s.size(); i++) { if (isPalindrome(s, start, i)) { // i path.push_back(s.substr(start, i - start + 1)); DFS(s, path, result, i + 1); // path.pop_back(); // } }

181.10.1 Palindrome Partitioning 175 } bool isPalindrome(const string &s, int start, int end) { while (start < end && s[start] == s[end]) { ++start; --end; } return start >= end; } }; // LeetCode, Palindrome Partitioning // O(n^2) O(1) class Solution { public: vector<vector<string> > partition(string s) { const int n = s.size(); bool p[n][n]; // whether s[i,j] is palindrome fill_n(&p[0][0], n * n, false); for (int i = n - 1; i >= 0; --i) for (int j = i; j < n; ++j) p[i][j] = s[i] == s[j] && ((j - i < 2) || p[i + 1][j - 1]); vector<vector<string> > sub_palins[n]; // sub palindromes of s[0,i] for (int i = n - 1; i >= 0; --i) { for (int j = i; j < n; ++j) if (p[i][j]) { const string palindrome = s.substr(i, j - i + 1); if (j + 1 < n) { for (auto v : sub_palins[j + 1]) { v.insert(v.begin(), palindrome); sub_palins[i].push_back(v); } } else { sub_palins[i].push_back(vector<string> { palindrome }); } } } return sub_palins[0]; } }; 题 • Palindrome Partitioning II §13.3

182.176 10 10.2 Unique Paths A robot is located at the top-left corner of a m × n grid (marked ’Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ’Finish’ in the diagram below). How many possible unique paths are there? 10-1 Above is a 3 × 7 grid. How many possible unique paths are there? Note: m and n will be at most 100. 10.2.1 // LeetCode, Unique Paths // // O(n^4) O(n) class Solution { public: int uniquePaths(int m, int n) { if (m < 1 || n < 1) return 0; // if (m == 1 && n == 1) return 1; // return uniquePaths(m - 1, n) + uniquePaths(m, n - 1); } }; 10.2.2

183.10.2 Unique Paths 177 // LeetCode, Unique Paths // + // O(n^2) O(n^2) class Solution { public: int uniquePaths(int m, int n) { // f[x][y] (0,0) (x,y) f = vector<vector<int> >(m, vector<int>(n, 0)); f[0][0] = 1; return dfs(m - 1, n - 1); } private: vector<vector<int> > f; // int dfs(int x, int y) { if (x < 0 || y < 0) return 0; // if (x == 0 && y == 0) return f[0][0]; // if (f[x][y] > 0) { return f[x][y]; } else { return f[x][y] = dfs(x - 1, y) + dfs(x, y - 1); } } }; 10.2.3 解 解 f[i][j] (1, 1) (i, j) f[i][j]=f[i-1][j]+f[i][j-1] // LeetCode, Unique Paths // // O(n^2) O(n) class Solution { public: int uniquePaths(int m, int n) { vector<int> f(n, 0); f[0] = 1; for (int i = 0; i < m; i++) { for (int j = 1; j < n; j++) { // f[j] f[j] f[i][j] // f[j] f[j] f[i-1][j] f[j] = f[j] + f[j - 1]; }

184.178 10 } return f[n - 1]; } }; 10.2.4 m n m+n−2 m−1 题 m+n−2 m–1 m−1 Cm+n−2 // LeetCode, Unique Paths // class Solution { public: typedef long long int64_t; // , n!/(start-1)! n*(n-1)...start n >= 1 static int64_t factor(int n, int start = 1) { int64_t ret = 1; for(int i = start; i <= n; ++i) ret *= i; return ret; } // C_n^k static int64_t combination(int n, int k) { // if (k == 0) return 1; if (k == 1) return n; int64_t ret = factor(n, k+1); ret /= factor(n - k); return ret; } int uniquePaths(int m, int n) { // max n k combination() return combination(m+n-2, max(m-1, n-1)); } }; 题 • Unique Paths II §10.3 • Minimum Path Sum, §13.8

185.10.3 Unique Paths II 179 10.3 Unique Paths II Follow up for ”Unique Paths”: Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as 1 and 0 respectively in the grid. For example, There is one obstacle in the middle of a 3 × 3 grid as illustrated below. [ [0,0,0], [0,1,0], [0,0,0] ] The total number of unique paths is 2. Note: m and n will be at most 100. 10.3.1 题 // LeetCode, Unique Paths II // + class Solution { public: int uniquePathsWithObstacles(const vector<vector<int> >& obstacleGrid) { const int m = obstacleGrid.size(); const int n = obstacleGrid[0].size(); if (obstacleGrid[0][0] || obstacleGrid[m - 1][n - 1]) return 0; f = vector<vector<int> >(m, vector<int>(n, 0)); f[0][0] = obstacleGrid[0][0] ? 0 : 1; return dfs(obstacleGrid, m - 1, n - 1); } private: vector<vector<int> > f; // // @return (0, 0) (x, y) int dfs(const vector<vector<int> >& obstacleGrid, int x, int y) { if (x < 0 || y < 0) return 0; // // (x,y) if (obstacleGrid[x][y]) return 0; if (x == 0 and y == 0) return f[0][0]; //

186.180 10 if (f[x][y] > 0) { return f[x][y]; } else { return f[x][y] = dfs(obstacleGrid, x - 1, y) + dfs(obstacleGrid, x, y - 1); } } }; 10.3.2 题 题 1 题 0 // LeetCode, Unique Paths II // // O(n^2) O(n) class Solution { public: int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) { const int m = obstacleGrid.size(); const int n = obstacleGrid[0].size(); if (obstacleGrid[0][0] || obstacleGrid[m-1][n-1]) return 0; vector<int> f(n, 0); f[0] = obstacleGrid[0][0] ? 0 : 1; for (int i = 0; i < m; i++) { f[0] = f[0] == 0 ? 0 : (obstacleGrid[i][0] ? 0 : 1); for (int j = 1; j < n; j++) f[j] = obstacleGrid[i][j] ? 0 : (f[j] + f[j - 1]); } return f[n - 1]; } }; 题 • Unique Paths §10.2 • Minimum Path Sum, §13.8

187.10.4 N-Queens 181 10.4 N-Queens The n-queens puzzle is the problem of placing n queens on an n × n chessboard such that no two queens attack each other. 10-2 Eight Queens Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space respectively. For example, There exist two distinct solutions to the 4-queens puzzle: [ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ] 题

188.182 10 vector<int> C(n, 0), C[i] i (i, C[i]) 1 // LeetCode, N-Queens // + // O(n!*n) O(n) class Solution { public: vector<vector<string> > solveNQueens(int n) { vector<vector<string> > result; vector<int> C(n, -1); // C[i] i dfs(C, result, 0); return result; } private: void dfs(vector<int> &C, vector<vector<string> > &result, int row) { const int N = C.size(); if (row == N) { // 解 vector<string> solution; for (int i = 0; i < N; ++i) { string s(N, '.'); for (int j = 0; j < N; ++j) { if (j == C[i]) s[j] = 'Q'; } solution.push_back(s); } result.push_back(solution); return; } for (int j = 0; j < N; ++j) { // const bool ok = isValid(C, row, j); if (!ok) continue; // // C[row] = j; dfs(C, result, row + 1); // // C[row] = -1; } } /** * (row, col) . * * @param C * @param row * @param col * @return */ bool isValid(const vector<int> &C, int row, int col) {

189.10.4 N-Queens 183 for (int i = 0; i < row; ++i) { // if (C[i] == col) return false; // if (abs(i - row) == abs(C[i] - col)) return false; } return true; } }; 2 // LeetCode, N-Queens // + // O(n!) O(n) class Solution { public: vector<vector<string> > solveNQueens(int n) { this->columns = vector<bool>(n, false); this->main_diag = vector<bool>(2 * n - 1, false); this->anti_diag = vector<bool>(2 * n - 1, false); vector<vector<string> > result; vector<int> C(n, -1); // C[i] i dfs(C, result, 0); return result; } private: // vector<bool> columns; // vector<bool> main_diag; // vector<bool> anti_diag; // void dfs(vector<int> &C, vector<vector<string> > &result, int row) { const int N = C.size(); if (row == N) { // 解 vector<string> solution; for (int i = 0; i < N; ++i) { string s(N, '.'); for (int j = 0; j < N; ++j) { if (j == C[i]) s[j] = 'Q'; } solution.push_back(s); } result.push_back(solution); return; } for (int j = 0; j < N; ++j) { // const bool ok = !columns[j] && !main_diag[row - j + N - 1] && !anti_diag[row + j]; if (!ok) continue; // //

190.184 10 C[row] = j; columns[j] = main_diag[row - j + N - 1] = anti_diag[row + j] = true; dfs(C, result, row + 1); // // C[row] = -1; columns[j] = main_diag[row - j + N - 1] = anti_diag[row + j] = false; } } }; 题 • N-Queens II §10.5 10.5 N-Queens II Follow up for N-Queens problem. Now, instead outputting board configurations, return the total number of distinct solutions. 解 解 题 解 1 1 // LeetCode, N-Queens II // + // O(n!*n) O(n) class Solution { public: int totalNQueens(int n) { this->count = 0; vector<int> C(n, 0); // C[i] i dfs(C, 0); return this->count; } private: int count; // 解 void dfs(vector<int> &C, int row) { const int N = C.size(); if (row == N) { // 解 ++this->count; return;

191.10.5 N-Queens II 185 } for (int j = 0; j < N; ++j) { // const bool ok = isValid(C, row, j); if (!ok) continue; // // C[row] = j; dfs(C, row + 1); // // C[row] = -1; } } /** * (row, col) . * * @param C * @param row * @param col * @return */ bool isValid(const vector<int> &C, int row, int col) { for (int i = 0; i < row; ++i) { // if (C[i] == col) return false; // if (abs(i - row) == abs(C[i] - col)) return false; } return true; } }; 2 // LeetCode, N-Queens II // + // O(n!) O(n) class Solution { public: int totalNQueens(int n) { this->count = 0; this->columns = vector<bool>(n, false); this->main_diag = vector<bool>(2 * n - 1, false); this->anti_diag = vector<bool>(2 * n - 1, false); vector<int> C(n, 0); // C[i] i dfs(C, 0); return this->count; } private: int count; // 解 // vector<bool> columns; // vector<bool> main_diag; //

192.186 10 vector<bool> anti_diag; // void dfs(vector<int> &C, int row) { const int N = C.size(); if (row == N) { // 解 ++this->count; return; } for (int j = 0; j < N; ++j) { // const bool ok = !columns[j] && !main_diag[row - j + N] && !anti_diag[row + j]; if (!ok) continue; // // C[row] = j; columns[j] = main_diag[row - j + N] = anti_diag[row + j] = true; dfs(C, row + 1); // // C[row] = -1; columns[j] = main_diag[row - j + N] = anti_diag[row + j] = false; } } }; 题 • N-Queens §10.4 10.6 Restore IP Addresses Given a string containing only digits, restore it by returning all possible valid IP address combinations. For example: Given "25525511135", return ["255.255.11.135", "255.255.111.35"]. (Order does not matter) 解 // LeetCode, Restore IP Addresses // O(n^4) O(n) class Solution {

193.10.6 Restore IP Addresses 187 public: vector<string> restoreIpAddresses(const string& s) { vector<string> result; vector<string> ip; // dfs(s, ip, result, 0); return result; } /** * @brief 解 * @param[in] s * @param[out] ip * @param[out] result IP * @param[in] start index * @return */ void dfs(string s, vector<string>& ip, vector<string> &result, size_t start) { if (ip.size() == 4 && start == s.size()) { // 解 result.push_back(ip[0] + '.' + ip[1] + '.' + ip[2] + '.' + ip[3]); return; } if (s.size() - start > (4 - ip.size()) * 3) return; // if (s.size() - start < (4 - ip.size())) return; // int num = 0; for (size_t i = start; i < start + 3; i++) { num = num * 10 + (s[i] - '0'); if (num < 0 || num > 255) continue; // ip.push_back(s.substr(start, i - start + 1)); dfs(s, ip, result, i + 1); ip.pop_back(); if (num == 0) break; // 0 0 } } }; 题 •

194.188 10 10.7 Combination Sum Given a set of candidate numbers (C) and a target number (T ), find all unique combinations in C where the candidate numbers sums to T . The same repeated number may be chosen from C unlimited number of times. Note: • All numbers (including target) will be positive integers. • Elements in a combination (a1 , a2 , ..., ak ) must be in non-descending order. (ie, a1 ≤ a2 ≤ ... ≤ ak ). • The solution set must not contain duplicate combinations. For example, given candidate set 2,3,6,7 and target 7, A solution set is: [7] [2, 2, 3] // LeetCode, Combination Sum // O(n!) O(n) class Solution { public: vector<vector<int> > combinationSum(vector<int> &nums, int target) { sort(nums.begin(), nums.end()); vector<vector<int> > result; // vector<int> path; // dfs(nums, path, result, target, 0); return result; } private: void dfs(vector<int>& nums, vector<int>& path, vector<vector<int> > &result, int gap, int start) { if (gap == 0) { // 解 result.push_back(path); return; } for (size_t i = start; i < nums.size(); i++) { // if (gap < nums[i]) return; // path.push_back(nums[i]); // dfs(nums, path, result, gap - nums[i], i); path.pop_back(); // }

195.10.8 Combination Sum II 189 } }; 题 • Combination Sum II §10.8 10.8 Combination Sum II Given a collection of candidate numbers (C) and a target number (T ), find all unique combinations in C where the candidate numbers sums to T . Each number in C may only be used once in the combination. Note: • All numbers (including target) will be positive integers. • Elements in a combination (a1 , a2 , ..., ak ) must be in non-descending order. (ie, a1 > a2 > ... > ak ). • The solution set must not contain duplicate combinations. For example, given candidate set 10,1,2,7,6,1,5 and target 8, A solution set is: [1, 7] [1, 2, 5] [2, 6] [1, 1, 6] // LeetCode, Combination Sum II // O(n!) O(n) class Solution { public: vector<vector<int> > combinationSum2(vector<int> &nums, int target) { sort(nums.begin(), nums.end()); // 50 // vector<vector<int> > result; vector<int> path; dfs(nums, path, result, target, 0); return result; } private: // nums[start, nums.size()) 解

196.190 10 static void dfs(const vector<int> &nums, vector<int> &path, vector<vector<int> > &result, int gap, int start) { if (gap == 0) { // 解 result.push_back(path); return; } int previous = -1; for (size_t i = start; i < nums.size(); i++) { // nums[i] nums[i] // nums[i] if (previous == nums[i]) continue; if (gap < nums[i]) return; // previous = nums[i]; path.push_back(nums[i]); dfs(nums, path, result, gap - nums[i], i + 1); path.pop_back(); // } } }; 题 • Combination Sum §10.7 10.9 Generate Parentheses Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: "((()))", "(()())", "(())()", "()(())", "()()()" <n 1 // LeetCode, Generate Parentheses // O(TODO) O(n) class Solution {

197.10.9 Generate Parentheses 191 public: vector<string> generateParenthesis(int n) { vector<string> result; string path; if (n > 0) generate(n, path, result, 0, 0); return result; } // l ( , r ) void generate(int n, string& path, vector<string> &result, int l, int r) { if (l == n) { string s(path); result.push_back(s.append(n - r, ')')); return; } path.push_back('('); generate(n, path, result, l + 1, r); path.pop_back(); if (l > r) { path.push_back(')'); generate(n, path, result, l, r + 1); path.pop_back(); } } }; 2 // LeetCode, Generate Parentheses // @author (http://weibo.com/lianchengzju) class Solution { public: vector<string> generateParenthesis (int n) { if (n == 0) return vector<string>(1, ""); if (n == 1) return vector<string> (1, "()"); vector<string> result; for (int i = 0; i < n; ++i) for (auto inner : generateParenthesis (i)) for (auto outer : generateParenthesis (n - 1 - i)) result.push_back ("(" + inner + ")" + outer); return result; } }; 题 • Valid Parentheses, §4.1.1

198.192 10 • Longest Valid Parentheses, §4.1.2 10.10 Sudoku Solver Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells are indicated by the character '.'. You may assume that there will be only one unique solution. 10-3 A sudoku puzzle... 10-4 ...and its solution numbers marked in red

199.10.11 Word Search 193 // LeetCode, Sudoku Solver // O(9^4) O(1) class Solution { public: bool solveSudoku(vector<vector<char> > &board) { for (int i = 0; i < 9; ++i) for (int j = 0; j < 9; ++j) { if (board[i][j] == '.') { for (int k = 0; k < 9; ++k) { board[i][j] = '1' + k; if (isValid(board, i, j) && solveSudoku(board)) return true; board[i][j] = '.'; } return false; } } return true; } private: // (x, y) bool isValid(const vector<vector<char> > &board, int x, int y) { int i, j; for (i = 0; i < 9; i++) // y if (i != x && board[i][y] == board[x][y]) return false; for (j = 0; j < 9; j++) // x if (j != y && board[x][j] == board[x][y]) return false; for (i = 3 * (x / 3); i < 3 * (x / 3 + 1); i++) for (j = 3 * (y / 3); j < 3 * (y / 3 + 1); j++) if ((i != x || j != y) && board[i][j] == board[x][y]) return false; return true; } }; 题 • Valid Sudoku, §2.1.14 10.11 Word Search Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighbouring. The same letter cell may not be used more than once.

200.194 10 For example, Given board = [ ["ABCE"], ["SFCS"], ["ADEE"] ] word = "ABCCED", -> returns true, word = "SEE", -> returns true, word = "ABCB", -> returns false. // LeetCode, Word Search // // O(n^2*m^2) O(n^2) class Solution { public: bool exist(const vector<vector<char> > &board, const string& word) { const int m = board.size(); const int n = board[0].size(); vector<vector<bool> > visited(m, vector<bool>(n, false)); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (dfs(board, word, 0, i, j, visited)) return true; return false; } private: static bool dfs(const vector<vector<char> > &board, const string &word, int index, int x, int y, vector<vector<bool> > &visited) { if (index == word.size()) return true; // if (x < 0 || y < 0 || x >= board.size() || y >= board[0].size()) return false; // if (visited[x][y]) return false; // if (board[x][y] != word[index]) return false; // visited[x][y] = true; bool ret = dfs(board, word, index + 1, x - 1, y, visited) || // dfs(board, word, index + 1, x + 1, y, visited) || // dfs(board, word, index + 1, x, y - 1, visited) || // dfs(board, word, index + 1, x, y + 1, visited); // visited[x][y] = false;

201.10.12 195 return ret; } }; 题 • 10.12 10.12.1 解 解 10.12.2 1. 题 解 解 解 (a) (b) path[] 2. 解 解 解 解 解 题 解 解 题 3. struct struct 4. 题 1

202.196 10 5. 0 6. 解 解 解 解 解 path[] 解 7. (a) DAG BFS BFS DAG (b) §9.4 DAG 题 8 8. (a) 题 (b) i. DAG DAG=> 题 => 题 解 题 ii. HashMap HashMap C++ map C++ 11 unordered_map map 题 解 8 题 5 8 题 题 题

203.10.12 197 10.12.3 dfs_template.cpp /** * dfs . * @param[in] input * @param[out] path * @param[out] result * @param[inout] cur or gap * @return */ void dfs(type &input, type &path, type &result, int cur or gap) { if ( ) return 0; // if (cur == input.size()) { // // if (gap == 0) { path result } if ( ) return; for(...) { // path dfs(input, step + 1 or gap--, result); path } } dfs_template.cpp 10.12.4 (Depth-first search, DFS) http://en.wikipedia.org/wiki/Depth_first_search (backtrack- ing) http://en.wikipedia.org/wiki/Backtracking = + (recursion) 10.12.5 (recursion) (iteration) (prunning)

204.198 10 + memorization memorization §?? ”top-down with cache” + Donald Michie 1968 top-down memorization (iterative) memo- rization memorization memorization memorization

205. 11 11.1 Pow(x,n) Implement pow(x, n). xn = xn/2 × xn/2 × xn%2 //LeetCode, Pow(x, n) // $x^n = x^{n/2} * x^{n/2} * x^{n\%2}$ // O(logn) O(1) class Solution { public: double myPow(double x, int n) { if (n < 0) return 1.0 / power(x, -n); else return power(x, n); } private: double power(double x, int n) { if (n == 0) return 1; double v = power(x, n / 2); if (n % 2 == 0) return v * v; else return v * v * x; } }; 题 • Sqrt(x) §11.2 199

206.200 11 11.2 Sqrt(x) Implement int sqrt(int x). Compute and return the square root of x. // LeetCode, Sqrt(x) // // O(logn) O(1) class Solution { public: int mySqrt(int x) { int left = 1, right = x / 2; int last_mid; // mid if (x < 2) return x; while(left <= right) { const int mid = left + (right - left) / 2; if(x / mid > mid) { // x > mid * mid left = mid + 1; last_mid = mid; } else if(x / mid < mid) { right = mid - 1; } else { return mid; } } return last_mid; } }; 题 • Pow(x) §11.1

207. 12 12.1 Jump Game Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. For example: A = [2,3,1,1,4], return true. A = [3,2,1,0,4], return false. A[i] 0 1 0 0 f[i] 0 A[i] f [i] = max(f [i − 1], A[i − 1]) − 1, i > 0 1 // LeetCode, Jump Game // 1 O(n) O(1) class Solution { public: bool canJump(const vector<int>& nums) { int reach = 1; // for (int i = 0; i < reach && reach < nums.size(); ++i) reach = max(reach, i + 1 + nums[i]); 201

208.202 12 return reach >= nums.size(); } }; 2 // LeetCode, Jump Game // 2 O(n) O(1) class Solution { public: bool canJump (const vector<int>& nums) { if (nums.empty()) return true; // int left_most = nums.size() - 1; for (int i = nums.size() - 2; i >= 0; --i) if (i + nums[i] >= left_most) left_most = i; return left_most == 0; } }; 3 // LeetCode, Jump Game // O(n) O(n) class Solution { public: bool canJump(const vector<int>& nums) { vector<int> f(nums.size(), 0); f[0] = 0; for (int i = 1; i < nums.size(); i++) { f[i] = max(f[i - 1], nums[i - 1]) - 1; if (f[i] < 0) return false;; } return f[nums.size() - 1] >= 0; } }; 题 • Jump Game II §12.2 12.2 Jump Game II Given an array of non-negative integers, you are initially positioned at the first index of the array.

209.12.2 Jump Game II 203 Each element in the array represents your maximum jump length at that position. Your goal is to reach the last index in the minimum number of jumps. For example: Given array A = [2,3,1,1,4] The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.) 1 // LeetCode, Jump Game II // O(n) O(1) class Solution { public: int jump(const vector<int>& nums) { int step = 0; // int left = 0; int right = 0; // [left, right] if (nums.size() == 1) return 0; while (left <= right) { // ++step; const int old_right = right; for (int i = left; i <= old_right; ++i) { int new_right = i + nums[i]; if (new_right >= nums.size() - 1) return step; if (new_right > right) right = new_right; } left = old_right + 1; } return 0; } }; 2 // LeetCode, Jump Game II // O(n) O(1) class Solution { public: int jump(const vector<int>& nums) { int result = 0; // the maximum distance that has been reached int last = 0; // the maximum distance that can be reached by using "ret+1" steps int cur = 0;

210.204 12 for (int i = 0; i < nums.size(); ++i) { if (i > last) { last = cur; ++result; } cur = max(cur, i + nums[i]); } return result; } }; 题 • Jump Game §12.1 12.3 Best Time to Buy and Sell Stock Say you have an array for which the i-th element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit. 题 m m=1 // LeetCode, Best Time to Buy and Sell Stock // O(n) O(1) class Solution { public: int maxProfit(vector<int> &prices) { if (prices.size() < 2) return 0; int profit = 0; // int cur_min = prices[0]; // for (int i = 1; i < prices.size(); i++) { profit = max(profit, prices[i] - cur_min); cur_min = min(cur_min, prices[i]); } return profit; } };

211.12.4 Best Time to Buy and Sell Stock II 205 题 • Best Time to Buy and Sell Stock II §12.4 • Best Time to Buy and Sell Stock III §13.5 12.4 Best Time to Buy and Sell Stock II Say you have an array for which the i-th element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). 题 m m= // LeetCode, Best Time to Buy and Sell Stock II // O(n) O(1) class Solution { public: int maxProfit(vector<int> &prices) { int sum = 0; for (int i = 1; i < prices.size(); i++) { int diff = prices[i] - prices[i - 1]; if (diff > 0) sum += diff; } return sum; } }; 题 • Best Time to Buy and Sell Stock §12.3 • Best Time to Buy and Sell Stock III §13.5

212.206 12 12.5 Longest Substring Without Repeating Characters Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1. 题 题 题 题 题 index+1 O(n) 12-1 12-1 // LeetCode, Longest Substring Without Repeating Characters // O(n) O(1) // class Solution { public: int lengthOfLongestSubstring(string s) { const int ASCII_MAX = 255; int last[ASCII_MAX]; // int start = 0; // fill(last, last + ASCII_MAX, -1); // 0 -1 int max_len = 0; for (int i = 0; i < s.size(); i++) { if (last[s[i]] >= start) { max_len = max(i - start, max_len); start = last[s[i]] + 1; } last[s[i]] = i; }

213.12.6 Container With Most Water 207 return max((int)s.size() - start, max_len); // "abcd" } }; 题 • 12.6 Container With Most Water Given n non-negative integers a1 , a2 , ..., an , where each represents a point at coordinate (i, ai ). n verti- cal lines are drawn such that the two endpoints of line i is at (i, ai ) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water. Note: You may not slant the container. // LeetCode, Container With Most Water // O(n) O(1) class Solution { public: int maxArea(vector<int> &height) { int start = 0; int end = height.size() - 1; int result = INT_MIN; while (start < end) { int area = min(height[end], height[start]) * (end - start); result = max(result, area); if (height[start] <= height[end]) { start++; } else { end--; } } return result; } }; 题 • Trapping Rain Water, §2.1.15

214.208 12 • Largest Rectangle in Histogram, §4.1.3

215. 13 13.1 Triangle Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle [ [2], [3,4], [6,5,7], [4,1,8,3] ] The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11). Note: Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle. f (i, j) (i, j) f (i, j) = min {f (i + 1, j), f (i + 1, j + 1)} + (i, j) // LeetCode, Triangle // O(n^2) O(1) class Solution { public: int minimumTotal (vector<vector<int>>& triangle) { for (int i = triangle.size() - 2; i >= 0; --i) for (int j = 0; j < i + 1; ++j) triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]); 209

216.210 13 return triangle [0][0]; } }; 题 • 13.2 Maximum Subarray Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has the largest sum = 6. 题 1 SubArray 2. SubArray SubArray 0 SubArray SubArray 0 0 0 SubArray f[j] S[j] f [j] = max {f [j − 1] + S[j], S[j]} , 1≤j≤n target = max {f [j]} , 1≤j≤n 解 • S[j] f [j − 1] + S[j] • S[j] S[j] S[j] • 2 i j O(n3 ) • 3 O(n2 ) • 4 O(n log n) • 5 2O(n2 ) O(n) • 6 M=1 M

217.13.2 Maximum Subarray 211 // LeetCode, Maximum Subarray // O(n) O(1) class Solution { public: int maxSubArray(vector<int>& nums) { int result = INT_MIN, f = 0; for (int i = 0; i < nums.size(); ++i) { f = max(f + nums[i], nums[i]); result = max(result, f); } return result; } }; 5 // LeetCode, Maximum Subarray // O(n) O(n) class Solution { public: int maxSubArray(vector<int>& A) { return mcss(A.begin(), A.end()); } private: // 5 template <typename Iter> static int mcss(Iter begin, Iter end) { int result, cur_min; const int n = distance(begin, end); int *sum = new int[n + 1]; // n sum[0] = 0; result = INT_MIN; cur_min = sum[0]; for (int i = 1; i <= n; i++) { sum[i] = sum[i - 1] + *(begin + i - 1); } for (int i = 1; i <= n; i++) { result = max(result, sum[i] - cur_min); cur_min = min(cur_min, sum[i]); } delete[] sum; return result; } }; 题 • Binary Tree Maximum Path Sum §5.4.5

218.212 13 13.3 Palindrome Partitioning II Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s. For example, given s = "aab", Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut. f(i,j) [i,j] cut f (i, j) = min {f (i, k) + f (k + 1, j)} , i ≤ k ≤ j, 0 ≤ i ≤ j < n DP i DP f(i)= [i, n-1] cut n f (i) = min {f (j + 1) + 1} , i ≤ j < n 题 [i,j] i j DP 题 P[i][j] = true if [i,j] P[i][j] = str[i] == str[j] && P[i+1][j-1] // LeetCode, Palindrome Partitioning II // O(n^2) O(n^2) class Solution { public: int minCut(const string& s) { const int n = s.size(); int f[n+1]; bool p[n][n]; fill_n(&p[0][0], n * n, false); //the worst case is cutting by each char for (int i = 0; i <= n; i++) f[i] = n - 1 - i; // f[n]=-1 for (int i = n - 1; i >= 0; i--) { for (int j = i; j < n; j++) { if (s[i] == s[j] && (j - i < 2 || p[i + 1][j - 1])) { p[i][j] = true; f[i] = min(f[i], f[j + 1] + 1); } }

219.13.4 Maximal Rectangle 213 } return f[0]; } }; 题 • Palindrome Partitioning §10.1 13.4 Maximal Rectangle Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area. // LeetCode, Maximal Rectangle // O(n^2) O(n) class Solution { public: int maximalRectangle(vector<vector<char> > &matrix) { if (matrix.empty()) return 0; const int m = matrix.size(); const int n = matrix[0].size(); vector<int> H(n, 0); vector<int> L(n, 0); vector<int> R(n, n); int ret = 0; for (int i = 0; i < m; ++i) { int left = 0, right = n; // calculate L(i, j) from left to right for (int j = 0; j < n; ++j) { if (matrix[i][j] == '1') { ++H[j]; L[j] = max(L[j], left); } else { left = j+1; H[j] = 0; L[j] = 0; R[j] = n; } }

220.214 13 // calculate R(i, j) from right to left for (int j = n-1; j >= 0; --j) { if (matrix[i][j] == '1') { R[j] = min(R[j], right); ret = max(ret, H[j]*(R[j]-L[j])); } else { right = j; } } } return ret; } }; 题 • 13.5 Best Time to Buy and Sell Stock III Say you have an array for which the i-th element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). f (i) [0, i](0 ≤ i ≤ n−1) g(i) [i, n−1](0 ≤ i ≤ n−1) max {f (i) + g(i)} , 0 ≤ i ≤ n − 1 题 题 m m = 2 https://gist.github.com/soulmachine/5906637 // LeetCode, Best Time to Buy and Sell Stock III // O(n) O(n) class Solution { public: int maxProfit(vector<int>& prices) { if (prices.size() < 2) return 0; const int n = prices.size(); vector<int> f(n, 0);

221.13.6 Interleaving String 215 vector<int> g(n, 0); for (int i = 1, valley = prices[0]; i < n; ++i) { valley = min(valley, prices[i]); f[i] = max(f[i - 1], prices[i] - valley); } for (int i = n - 2, peak = prices[n - 1]; i >= 0; --i) { peak = max(peak, prices[i]); g[i] = max(g[i], peak - prices[i]); } int max_profit = 0; for (int i = 0; i < n; ++i) max_profit = max(max_profit, f[i] + g[i]); return max_profit; } }; 题 • Best Time to Buy and Sell Stock §12.3 • Best Time to Buy and Sell Stock II §12.4 13.6 Interleaving String Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2. For example, Given: s1 = "aabcc", s2 = "dbbca", When s3 = "aadbbcbcac", return true. When s3 = "aadbbbaccc", return false. f[i][j] s1[0,i] s2[0,j] s3[0, i+j] s1 s3 f[i][j]=f[i-1][j] s2 s3 f[i][j]=f[i][j-1] f[i][j] = (s1[i - 1] == s3 [i + j - 1] && f[i - 1][j]) || (s2[j - 1] == s3 [i + j - 1] && f[i][j - 1]); // LeetCode, Interleaving String // 解

222.216 13 class Solution { public: bool isInterleave(const string& s1, const string& s2, const string& s3) { if (s3.length() != s1.length() + s2.length()) return false; return isInterleave(begin(s1), end(s1), begin(s2), end(s2), begin(s3), end(s3)); } template<typename InIt> bool isInterleave(InIt first1, InIt last1, InIt first2, InIt last2, InIt first3, InIt last3) { if (first3 == last3) return first1 == last1 && first2 == last2; return (*first1 == *first3 && isInterleave(next(first1), last1, first2, last2, next(first3), last3)) || (*first2 == *first3 && isInterleave(first1, last1, next(first2), last2, next(first3), last3)); } }; // LeetCode, Interleaving String // O(n^2) O(n^2) class Solution { public: bool isInterleave(const string& s1, const string& s2, const string& s3) { if (s3.length() != s1.length() + s2.length()) return false; vector<vector<bool>> f(s1.length() + 1, vector<bool>(s2.length() + 1, true)); for (size_t i = 1; i <= s1.length(); ++i) f[i][0] = f[i - 1][0] && s1[i - 1] == s3[i - 1]; for (size_t i = 1; i <= s2.length(); ++i) f[0][i] = f[0][i - 1] && s2[i - 1] == s3[i - 1]; for (size_t i = 1; i <= s1.length(); ++i) for (size_t j = 1; j <= s2.length(); ++j) f[i][j] = (s1[i - 1] == s3[i + j - 1] && f[i - 1][j]) || (s2[j - 1] == s3[i + j - 1] && f[i][j - 1]); return f[s1.length()][s2.length()]; } };

223.13.7 Scramble String 217 + // LeetCode, Interleaving String // + O(n^2) O(n) class Solution { public: bool isInterleave(const string& s1, const string& s2, const string& s3) { if (s1.length() + s2.length() != s3.length()) return false; if (s1.length() < s2.length()) return isInterleave(s2, s1, s3); vector<bool> f(s2.length() + 1, true); for (size_t i = 1; i <= s2.length(); ++i) f[i] = s2[i - 1] == s3[i - 1] && f[i - 1]; for (size_t i = 1; i <= s1.length(); ++i) { f[0] = s1[i - 1] == s3[i - 1] && f[0]; for (size_t j = 1; j <= s2.length(); ++j) f[j] = (s1[i - 1] == s3[i + j - 1] && f[j]) || (s2[j - 1] == s3[i + j - 1] && f[j - 1]); } return f[s2.length()]; } }; 题 • 13.7 Scramble String Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively. Below is one possible representation of s1 = "great": great / \ gr eat / \ / \ g r e at / \ a t

224.218 13 To scramble the string, we may choose any non-leaf node and swap its two children. For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat". rgeat / \ rg eat / \ / \ r g e at / \ a t We say that "rgeat" is a scrambled string of "great". Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae". rgtae / \ rg tae / \ / \ r g ta e / \ t a We say that "rgtae" is a scrambled string of "great". Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1. string memorization scamble false HashMap 题 HashMap map unordered_map 题 f[n][i][j] n s1[i] s2[j] scramble f[n][i][j]} = (f[k][i][j] && f[n-k][i+k][j+k]) || (f[k][i][j+n-k] && f[n-k][i+k][j]) // LeetCode, Scramble String // 解 // O(n^6) O(1) class Solution {

225.13.7 Scramble String 219 public: bool isScramble(const string& s1, const string& s2) { return isScramble(s1.begin(), s1.end(), s2.begin()); } private: typedef string::iterator Iterator; bool isScramble(Iterator first1, Iterator last1, Iterator first2) { auto length = distance(first1, last1); auto last2 = next(first2, length); if (length == 1) return *first1 == *first2; for (int i = 1; i < length; ++i) if ((isScramble(first1, first1 + i, first2) && isScramble(first1 + i, last1, first2 + i)) || (isScramble(first1, first1 + i, last2 - i) && isScramble(first1 + i, last1, first2))) return true; return false; } }; // LeetCode, Scramble String // O(n^3) O(n^3) class Solution { public: bool isScramble(const string& s1, const string& s2) { const int N = s1.size(); if (N != s2.size()) return false; // f[n][i][j] n s1[i] // s2[j] scramble bool f[N + 1][N][N]; fill_n(&f[0][0][0], (N + 1) * N * N, false); for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) f[1][i][j] = s1[i] == s2[j]; for (int n = 1; n <= N; ++n) { for (int i = 0; i + n <= N; ++i) { for (int j = 0; j + n <= N; ++j) { for (int k = 1; k < n; ++k) { if ((f[k][i][j] && f[n - k][i + k][j + k]) || (f[k][i][j + n - k] && f[n - k][i + k][j])) { f[n][i][j] = true; break; } } }

226.220 13 } } return f[N][0][0]; } }; + // LeetCode, Scramble String // + // O(n^6) O(1) class Solution { public: bool isScramble(const string& s1, const string& s2) { return isScramble(s1.begin(), s1.end(), s2.begin()); } private: typedef string::const_iterator Iterator; bool isScramble(Iterator first1, Iterator last1, Iterator first2) { auto length = distance(first1, last1); auto last2 = next(first2, length); if (length == 1) return *first1 == *first2; // int A[26]; // fill(A, A + 26, 0); for(int i = 0; i < length; i++) A[*(first1+i)-'a']++; for(int i = 0; i < length; i++) A[*(first2+i)-'a']--; for(int i = 0; i < 26; i++) if (A[i] != 0) return false; for (int i = 1; i < length; ++i) if ((isScramble(first1, first1 + i, first2) && isScramble(first1 + i, last1, first2 + i)) || (isScramble(first1, first1 + i, last2 - i) && isScramble(first1 + i, last1, first2))) return true; return false; } }; // LeetCode, Scramble String // +map cache // O(n^3) O(n^3), TLE class Solution { public: bool isScramble(const string& s1, const string& s2) { cache.clear(); return isScramble(s1.begin(), s1.end(), s2.begin()); }

227.13.7 Scramble String 221 private: typedef string::const_iterator Iterator; map<tuple<Iterator, Iterator, Iterator>, bool> cache; bool isScramble(Iterator first1, Iterator last1, Iterator first2) { auto length = distance(first1, last1); auto last2 = next(first2, length); if (length == 1) return *first1 == *first2; for (int i = 1; i < length; ++i) if ((getOrUpdate(first1, first1 + i, first2) && getOrUpdate(first1 + i, last1, first2 + i)) || (getOrUpdate(first1, first1 + i, last2 - i) && getOrUpdate(first1 + i, last1, first2))) return true; return false; } bool getOrUpdate(Iterator first1, Iterator last1, Iterator first2) { auto key = make_tuple(first1, last1, first2); auto pos = cache.find(key); return (pos != cache.end()) ? pos->second : (cache[key] = isScramble(first1, last1, first2)); } }; typedef string::const_iterator Iterator; typedef tuple<Iterator, Iterator, Iterator> Key; // namespace std { template<> struct hash<Key> { size_t operator()(const Key & x) const { Iterator first1, last1, first2; tie(first1, last1, first2) = x; int result = *first1; result = result * 31 + *last1; result = result * 31 + *first2; result = result * 31 + *(next(first2, distance(first1, last1)-1)); return result; } }; } // LeetCode, Scramble String // +unordered_map cache map // O(n^3) O(n^3) class Solution {

228.222 13 public: unordered_map<Key, bool> cache; bool isScramble(const string& s1, const string& s2) { cache.clear(); return isScramble(s1.begin(), s1.end(), s2.begin()); } bool isScramble(Iterator first1, Iterator last1, Iterator first2) { auto length = distance(first1, last1); auto last2 = next(first2, length); if (length == 1) return *first1 == *first2; for (int i = 1; i < length; ++i) if ((getOrUpdate(first1, first1 + i, first2) && getOrUpdate(first1 + i, last1, first2 + i)) || (getOrUpdate(first1, first1 + i, last2 - i) && getOrUpdate(first1 + i, last1, first2))) return true; return false; } bool getOrUpdate(Iterator first1, Iterator last1, Iterator first2) { auto key = make_tuple(first1, last1, first2); auto pos = cache.find(key); return (pos != cache.end()) ? pos->second : (cache[key] = isScramble(first1, last1, first2)); } }; 题 • 13.8 Minimum Path Sum Given a m × n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time Unique Paths ( §10.2)

229.13.8 Minimum Path Sum 223 f[i][j] (0, 0) (i, j) f[i][j]=min(f[i-1][j], f[i][j-1])+grid[i][j] // LeetCode, Minimum Path Sum // class Solution { public: int minPathSum(vector<vector<int> > &grid) { const int m = grid.size(); const int n = grid[0].size(); this->f = vector<vector<int> >(m, vector<int>(n, -1)); return dfs(grid, m-1, n-1); } private: vector<vector<int> > f; // int dfs(const vector<vector<int> > &grid, int x, int y) { if (x < 0 || y < 0) return INT_MAX; // 0 if (x == 0 && y == 0) return grid[0][0]; // return min(getOrUpdate(grid, x - 1, y), getOrUpdate(grid, x, y - 1)) + grid[x][y]; } int getOrUpdate(const vector<vector<int> > &grid, int x, int y) { if (x < 0 || y < 0) return INT_MAX; // 0 if (f[x][y] >= 0) return f[x][y]; else return f[x][y] = dfs(grid, x, y); } }; // LeetCode, Minimum Path Sum // class Solution { public: int minPathSum(vector<vector<int> > &grid) { if (grid.size() == 0) return 0; const int m = grid.size(); const int n = grid[0].size(); int f[m][n]; f[0][0] = grid[0][0]; for (int i = 1; i < m; i++) { f[i][0] = f[i - 1][0] + grid[i][0]; } for (int i = 1; i < n; i++) { f[0][i] = f[0][i - 1] + grid[0][i];

230.224 13 } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { f[i][j] = min(f[i - 1][j], f[i][j - 1]) + grid[i][j]; } } return f[m - 1][n - 1]; } }; + // LeetCode, Minimum Path Sum // + class Solution { public: int minPathSum(vector<vector<int> > &grid) { const int m = grid.size(); const int n = grid[0].size(); int f[n]; fill(f, f+n, INT_MAX); // INT_MAX min f[0] = 0; for (int i = 0; i < m; i++) { f[0] += grid[i][0]; for (int j = 1; j < n; j++) { // f[j] f[j] f[i[[j] // f[j] f[j] f[i-1][j] f[j] = min(f[j - 1], f[j]) + grid[i][j]; } } return f[n - 1]; } }; 题 • Unique Paths, §10.2 • Unique Paths II, §10.3 13.9 Edit Distance Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.) You have the following 3 operations permitted on a word:

231.13.9 Edit Distance 225 • Insert a character • Delete a character • Replace a character f[i][j] A[0,i] B[0,j] A[0,i] str1c B[0,j] str2d 1. c==d f[i][j]=f[i-1][j-1] 2. c!=d (a) c d f[i][j]=f[i-1][j-1]+1 (b) c d f[i][j]=f[i][j-1]+1 (c) c f[i][j]=f[i-1][j]+1 // LeetCode, Edit Distance // O(n*m) O(n*m) class Solution { public: int minDistance(const string &word1, const string &word2) { const size_t n = word1.size(); const size_t m = word2.size(); // n n+1 int f[n + 1][m + 1]; for (size_t i = 0; i <= n; i++) f[i][0] = i; for (size_t j = 0; j <= m; j++) f[0][j] = j; for (size_t i = 1; i <= n; i++) { for (size_t j = 1; j <= m; j++) { if (word1[i - 1] == word2[j - 1]) f[i][j] = f[i - 1][j - 1]; else { int mn = min(f[i - 1][j], f[i][j - 1]); f[i][j] = 1 + min(f[i - 1][j - 1], mn); } } } return f[n][m]; } };

232.226 13 + // LeetCode, Edit Distance // + // O(n*m) O(n) class Solution { public: int minDistance(const string &word1, const string &word2) { if (word1.length() < word2.length()) return minDistance(word2, word1); int f[word2.length() + 1]; int upper_left = 0; // f[i-1][j-1] for (size_t i = 0; i <= word2.size(); ++i) f[i] = i; for (size_t i = 1; i <= word1.size(); ++i) { upper_left = f[0]; f[0] = i; for (size_t j = 1; j <= word2.size(); ++j) { int upper = f[j]; if (word1[i - 1] == word2[j - 1]) f[j] = upper_left; else f[j] = 1 + min(upper_left, min(f[j], f[j - 1])); upper_left = upper; } } return f[word2.length()]; } }; 题 • 13.10 Decode Ways A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26

233.13.11 Distinct Subsequences 227 Given an encoded message containing digits, determine the total number of ways to decode it. For example, Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12). The number of ways decoding "12" is 2. Climbing Stairs ( §2.1.18) // LeetCode, Decode Ways // O(n) O(1) class Solution { public: int numDecodings(const string &s) { if (s.empty() || s[0] == '0') return 0; int prev = 0; int cur = 1; // n n+1 for (size_t i = 1; i <= s.size(); ++i) { if (s[i-1] == '0') cur = 0; if (i < 2 || !(s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6'))) prev = 0; int tmp = cur; cur = prev + cur; prev = tmp; } return cur; } }; 题 • Climbing Stairs, §2.1.18 13.11 Distinct Subsequences Given a string S and a string T , count the number of distinct subsequences of T in S. A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

234.228 13 Here is an example: S = "rabbbit", T = "rabbit" Return 3. f (i, j) T[0,j] S[0,i] S[i] T[j] S[i] f (i, j) = f (i − 1, j) S[i]==T[j] S[i] f (i, j) = f (i − 1, j) + f (i − 1, j − 1) // LeetCode, Distinct Subsequences // + // O(m*n) O(n) class Solution { public: int numDistinct(const string &S, const string &T) { vector<int> f(T.size() + 1); f[0] = 1; for (int i = 0; i < S.size(); ++i) { for (int j = T.size() - 1; j >= 0; --j) { f[j + 1] += S[i] == T[j] ? f[j] : 0; } } return f[T.size()]; } }; 题 • 13.12 Word Break Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words. For example, given s = "leetcode", dict = ["leet", "code"]. Return true because "leetcode" can be segmented as "leet code".

235.13.12 Word Break 229 f (i) s[0,i] f (i) = any_of (f (j)&&s[j + 1, i] ∈ dict), 0 ≤ j < i // LeetCode, Word Break // // O(2^n) O(n) class Solution { public: bool wordBreak(string s, unordered_set<string> &dict) { return dfs(s, dict, 0, 0); } private: static bool dfs(const string &s, unordered_set<string> &dict, size_t start, size_t cur) { if (cur == s.size()) { return dict.find(s.substr(start, cur-start+1)) != dict.end(); } if (dfs(s, dict, start, cur+1)) return true; if (dict.find(s.substr(start, cur-start+1)) != dict.end()) if (dfs(s, dict, cur+1, cur+1)) return true; return false; } }; // LeetCode, Word Break // O(n^2) O(n) class Solution { public: bool wordBreak(string s, unordered_set<string> &dict) { // n n+1 vector<bool> f(s.size() + 1, false); f[0] = true; // for (int i = 1; i <= s.size(); ++i) { for (int j = i - 1; j >= 0; --j) { if (f[j] && dict.find(s.substr(j, i - j)) != dict.end()) { f[i] = true; break; } } } return f[s.size()]; } };

236.230 13 题 • Word Break II, §13.13 13.13 Word Break II Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences. For example, given s = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"]. A solution is ["cats and dog", "cat sand dog"]. 题 解 // LeetCode, Word Break II // O(n^2) O(n^2) class Solution { public: vector<string> wordBreak(string s, unordered_set<string> &dict) { // n n+1 vector<bool> f(s.length() + 1, false); // prev[i][j] true s[j, i) j // vector<vector<bool> > prev(s.length() + 1, vector<bool>(s.length())); f[0] = true; for (size_t i = 1; i <= s.length(); ++i) { for (int j = i - 1; j >= 0; --j) { if (f[j] && dict.find(s.substr(j, i - j)) != dict.end()) { f[i] = true; prev[i][j] = true; } } } vector<string> result; vector<string> path; gen_path(s, prev, s.length(), path, result); return result; }

237.13.13 Word Break II 231 private: // DFS void gen_path(const string &s, const vector<vector<bool> > &prev, int cur, vector<string> &path, vector<string> &result) { if (cur == 0) { string tmp; for (auto iter = path.crbegin(); iter != path.crend(); ++iter) tmp += *iter + " "; tmp.erase(tmp.end() - 1); result.push_back(tmp); } for (size_t i = 0; i < s.size(); ++i) { if (prev[cur][i]) { path.push_back(s.substr(i, cur - i)); gen_path(s, prev, i, path, result); path.pop_back(); } } } }; 题 • Word Break, §13.12

238. 14 // struct UndirectedGraphNode { int label; vector<UndirectedGraphNode *> neighbors; UndirectedGraphNode(int x) : label(x) {}; }; 14.1 Clone Graph Clone an undirected graph. Each node in the graph contains a label and a list of its neighbours. OJ’s undirected graph serialization: Nodes are labeled uniquely. We use # as a separator for each node, and , as a separator for node label and each neighbour of the node. As an example, consider the serialized graph {0,1,2#1,2#2,2}. The graph has a total of three nodes, and therefore contains three parts as separated by #. 1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2. 2. Second node is labeled as 1. Connect node 1 to node 2. 3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle. Visually, the graph looks like the following: 1 / \ / \ 0 --- 2 / \ \_/ 232

239.14.1 Clone Graph 233 DFS // LeetCode, Clone Graph // DFS O(n) O(n) class Solution { public: UndirectedGraphNode *cloneGraph(const UndirectedGraphNode *node) { if(node == nullptr) return nullptr; // key is original node value is copied node unordered_map<const UndirectedGraphNode *, UndirectedGraphNode *> copied; clone(node, copied); return copied[node]; } private: // DFS static UndirectedGraphNode* clone(const UndirectedGraphNode *node, unordered_map<const UndirectedGraphNode *, UndirectedGraphNode *> &copied) { // a copy already exists if (copied.find(node) != copied.end()) return copied[node]; UndirectedGraphNode *new_node = new UndirectedGraphNode(node->label); copied[node] = new_node; for (auto nbr : node->neighbors) new_node->neighbors.push_back(clone(nbr, copied)); return new_node; } }; BFS // LeetCode, Clone Graph // BFS O(n) O(n) class Solution { public: UndirectedGraphNode *cloneGraph(const UndirectedGraphNode *node) { if (node == nullptr) return nullptr; // key is original node value is copied node unordered_map<const UndirectedGraphNode *, UndirectedGraphNode *> copied; // each node in queue is already copied itself // but neighbors are not copied yet queue<const UndirectedGraphNode *> q; q.push(node); copied[node] = new UndirectedGraphNode(node->label); while (!q.empty()) { const UndirectedGraphNode *cur = q.front(); q.pop(); for (auto nbr : cur->neighbors) { // a copy already exists if (copied.find(nbr) != copied.end()) { copied[cur]->neighbors.push_back(copied[nbr]);

240.234 14 } else { UndirectedGraphNode *new_node = new UndirectedGraphNode(nbr->label); copied[nbr] = new_node; copied[cur]->neighbors.push_back(new_node); q.push(nbr); } } } return copied[node]; } }; 题 •

241. 15 题 题 15.1 Reverse Integer Reverse digits of an integer. Example1: x = 123, return 321 Example2: x = -123, return -321 Have you thought about this? Here are some good questions to ask before coding. Bonus points for you if you have already thought through this! If the integer’s last digit is 0, what should the output be? ie, cases such as 10, 100. Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases? Throw an exception? Good, but what if throwing an exception is not an option? You would then have to re-design the function (ie, add an extra parameter). 题 //LeetCode, Reverse Integer // O(logn) O(1) // 1. 2. ( && x = -2147483648( -2^31) ) class Solution { public: int reverse (int x) { long long r = 0; long long t = x; t = t > 0 ? t : -t; 235

242.236 15 题 for (; t; t /= 10) r = r * 10 + t % 10; bool sign = x > 0 ? false: true; if (r > 2147483647 || (sign && r > 2147483648)) { return 0; } else { if (sign) { return -r; } else { return r; } } } }; 题 • Palindrome Number, §15.2 15.2 Palindrome Number Determine whether an integer is a palindrome. Do this without extra space. Some hints: Could negative integers be palindromes? (ie, -1) If you are thinking of converting the integer to string, note the restriction of using extra space. You could also try reversing an integer. However, if you have solved the problem ”Reverse Integer”, you know that the reversed integer might overflow. How would you handle such case? There is a more generic way of solving this problem. 题 Palindrome reverse() 解 10 //LeetCode, Palindrome Number // O(1) O(1) class Solution { public:

243.15.3 Insert Interval 237 bool isPalindrome(int x) { if (x < 0) return false; int d = 1; // divisor while (x / d >= 10) d *= 10; while (x > 0) { int q = x / d; // quotient int r = x % 10; // remainder if (q != r) return false; x = x % d / 10; d /= 100; } return true; } }; 题 • Reverse Integer, §15.1 • Valid Palindrome, §3.1 15.3 Insert Interval Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times. Example 1: Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9]. Example 2: Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16]. This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10]. struct Interval { int start; int end; Interval() : start(0), end(0) { } Interval(int s, int e) : start(s), end(e) { } }; //LeetCode, Insert Interval

244.238 15 题 // O(n) O(1) class Solution { public: vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) { vector<Interval>::iterator it = intervals.begin(); while (it != intervals.end()) { if (newInterval.end < it->start) { intervals.insert(it, newInterval); return intervals; } else if (newInterval.start > it->end) { it++; continue; } else { newInterval.start = min(newInterval.start, it->start); newInterval.end = max(newInterval.end, it->end); it = intervals.erase(it); } } intervals.insert(intervals.end(), newInterval); return intervals; } }; 题 • Merge Intervals §15.4 15.4 Merge Intervals Given a collection of intervals, merge all overlapping intervals. For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18] Insert Intervals 解 interval interval struct Interval { int start; int end; Interval() : start(0), end(0) { } Interval(int s, int e) : start(s), end(e) { } };

245.15.5 Minimum Window Substring 239 //LeetCode, Merge Interval // Insert Intervals 解 // O(n1+n2+...) O(1) class Solution { public: vector<Interval> merge(vector<Interval> &intervals) { vector<Interval> result; for (int i = 0; i < intervals.size(); i++) { insert(result, intervals[i]); } return result; } private: vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) { vector<Interval>::iterator it = intervals.begin(); while (it != intervals.end()) { if (newInterval.end < it->start) { intervals.insert(it, newInterval); return intervals; } else if (newInterval.start > it->end) { it++; continue; } else { newInterval.start = min(newInterval.start, it->start); newInterval.end = max(newInterval.end, it->end); it = intervals.erase(it); } } intervals.insert(intervals.end(), newInterval); return intervals; } }; 题 • Insert Interval §15.3 15.5 Minimum Window Substring Given a string S and a string T , find the minimum window in S which will contain all the characters in T in complexity O(n). For example, S = "ADOBECODEBANC", T = "ABC" Minimum window is "BANC". Note: • If there is no such window in S that covers all characters in T , return the emtpy string "".

246.240 15 题 • If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S. T // LeetCode, Minimum Window Substring // O(n) O(1) class Solution { public: string minWindow(string S, string T) { if (S.empty()) return ""; if (S.size() < T.size()) return ""; const int ASCII_MAX = 256; int appeared_count[ASCII_MAX]; int expected_count[ASCII_MAX]; fill(appeared_count, appeared_count + ASCII_MAX, 0); fill(expected_count, expected_count + ASCII_MAX, 0); for (size_t i = 0; i < T.size(); i++) expected_count[T[i]]++; int minWidth = INT_MAX, min_start = 0; // int wnd_start = 0; int appeared = 0; // T // for (size_t wnd_end = 0; wnd_end < S.size(); wnd_end++) { if (expected_count[S[wnd_end]] > 0) { // this char is a part of T appeared_count[S[wnd_end]]++; if (appeared_count[S[wnd_end]] <= expected_count[S[wnd_end]]) appeared++; } if (appeared == T.size()) { // T // while (appeared_count[S[wnd_start]] > expected_count[S[wnd_start]] || expected_count[S[wnd_start]] == 0) { appeared_count[S[wnd_start]]--; wnd_start++; } if (minWidth > (wnd_end - wnd_start + 1)) { minWidth = wnd_end - wnd_start + 1; min_start = wnd_start; } } } if (minWidth == INT_MAX) return "";

247.15.6 Multiply Strings 241 else return S.substr(min_start, minWidth); } }; 题 • 15.6 Multiply Strings Given two numbers represented as strings, return multiplication of the numbers as a string. Note: The numbers can be arbitrarily large and are non-negative. int int int32 2 31 − 1 = 2147483647 9 4 int64 9 1 // LeetCode, Multiply Strings // @author (http://weibo.com/lianchengzju) // int // O(n*m) O(n+m) typedef vector<int> bigint; bigint make_bigint(string const& repr) { bigint n; transform(repr.rbegin(), repr.rend(), back_inserter(n), [](char c) { return c - '0'; }); return n; } string to_string(bigint const& n) { string str; transform(find_if(n.rbegin(), prev(n.rend()), [](char c) { return c > '\0'; }), n.rend(), back_inserter(str), [](char c) { return c + '0'; }); return str; } bigint operator*(bigint const& x, bigint const& y) { bigint z(x.size() + y.size());

248.242 15 题 for (size_t i = 0; i < x.size(); ++i) for (size_t j = 0; j < y.size(); ++j) { z[i + j] += x[i] * y[j]; z[i + j + 1] += z[i + j] / 10; z[i + j] %= 10; } return z; } class Solution { public: string multiply(string num1, string num2) { return to_string(make_bigint(num1) * make_bigint(num2)); } }; 2 // LeetCode, Multiply Strings // 9 int64_t // O(n*m/81) O((n+m)/9) /** . */ class BigInt { public: /** * @brief . * @param[in] s * @return */ BigInt(string s) { vector<int64_t> result; result.reserve(s.size() / RADIX_LEN + 1); for (int i = s.size(); i > 0; i -= RADIX_LEN) { // [i-RADIX_LEN, i) int temp = 0; const int low = max(i - RADIX_LEN, 0); for (int j = low; j < i; j++) { temp = temp * 10 + s[j] - '0'; } result.push_back(temp); } elems = result; } /** * @brief . * @return */ string toString() { stringstream result; bool started = false; // 0 for (auto i = elems.rbegin(); i != elems.rend(); i++) {

249.15.6 Multiply Strings 243 if (started) { // 0 result << setw(RADIX_LEN) << setfill('0') << *i; } else { result << *i; started = true; // 0 0 } } if (!started) return "0"; // x 0 else return result.str(); } /** * @brief . * @param[in] x x * @param[in] y y * @return */ static BigInt multiply(const BigInt &x, const BigInt &y) { vector<int64_t> z(x.elems.size() + y.elems.size(), 0); for (size_t i = 0; i < y.elems.size(); i++) { for (size_t j = 0; j < x.elems.size(); j++) { // y[i] x // i, j i+j z[i + j] += y.elems[i] * x.elems[j]; if (z[i + j] >= BIGINT_RADIX) { // z[i + j + 1] += z[i + j] / BIGINT_RADIX; // z[i + j] %= BIGINT_RADIX; } } } while (z.back() == 0) z.pop_back(); // 0 return BigInt(z); } private: typedef long long int64_t; /** 9 * 1000000000 * 1000000000 2^63-1 */ const static int BIGINT_RADIX = 1000000000; const static int RADIX_LEN = 9; /** . */ vector<int64_t> elems; BigInt(const vector<int64_t> num) : elems(num) {} }; class Solution { public: string multiply(string num1, string num2) { BigInt x(num1);

250.244 15 题 BigInt y(num2); return BigInt::multiply(x, y).toString(); } }; 题 • 15.7 Substring with Concatenation of All Words You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters. For example, given: S: "barfoothefoobarman" L: ["foo", "bar"] You should return the indices: [0,9].(order does not matter). // LeetCode, Substring with Concatenation of All Words // O(n*m) O(m) class Solution { public: vector<int> findSubstring(string s, vector<string>& dict) { size_t wordLength = dict.front().length(); size_t catLength = wordLength * dict.size(); vector<int> result; if (s.length() < catLength) return result; unordered_map<string, int> wordCount; for (auto const& word : dict) ++wordCount[word]; for (auto i = begin(s); i <= prev(end(s), catLength); ++i) { unordered_map<string, int> unused(wordCount); for (auto j = i; j != next(i, catLength); j += wordLength) { auto pos = unused.find(string(j, next(j, wordLength)));

251.15.8 Pascal’s Triangle 245 if (pos == unused.end() || pos->second == 0) break; if (--pos->second == 0) unused.erase(pos); } if (unused.size() == 0) result.push_back(distance(begin(s), i)); } return result; } }; 题 • 15.8 Pascal’s Triangle Given numRows, generate the first numRows of Pascal’s triangle. For example, given numRows = 5, Return [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] 题 0 1 // LeetCode, Pascal's Triangle // O(n^2) O(n) class Solution { public: vector<vector<int> > generate(int numRows) { vector<vector<int> > result;

252.246 15 题 if(numRows == 0) return result; result.push_back(vector<int>(1,1)); //first row for(int i = 2; i <= numRows; ++i) { vector<int> current(i,1); // const vector<int> &prev = result[i-2]; // for(int j = 1; j < i - 1; ++j) { current[j] = prev[j-1] + prev[j]; // } result.push_back(current); } return result; } }; // LeetCode, Pascal's Triangle // O(n^2) O(n) class Solution { public: vector<vector<int> > generate(int numRows) { vector<vector<int> > result; vector<int> array; for (int i = 1; i <= numRows; i++) { for (int j = i - 2; j > 0; j--) { array[j] = array[j - 1] + array[j]; } array.push_back(1); result.push_back(array); } return result; } }; 题 • Pascal’s Triangle II §15.9 15.9 Pascal’s Triangle II Given an index k, return the kth row of the Pascal’s triangle. For example, given k = 3, Return [1,3,3,1]. Note: Could you optimize your algorithm to use only O(k) extra space?

253.15.10 Spiral Matrix 247 // LeetCode, Pascal's Triangle II // O(n^2) O(n) class Solution { public: vector<int> getRow(int rowIndex) { vector<int> array; for (int i = 0; i <= rowIndex; i++) { for (int j = i - 1; j > 0; j--){ array[j] = array[j - 1] + array[j]; } array.push_back(1); } return array; } }; 题 • Pascal’s Triangle §15.8 15.10 Spiral Matrix Given a matrix of m × n elements (m rows, n columns), return all elements of the matrix in spiral order. For example, Given the following matrix: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] You should return [1,2,3,6,9,8,7,4,5].

254.248 15 题 // LeetCode, Spiral Matrix // @author (http://weibo.com/luangong) // O(n^2) O(1) class Solution { public: vector<int> spiralOrder(vector<vector<int> >& matrix) { vector<int> result; if (matrix.empty()) return result; int beginX = 0, endX = matrix[0].size() - 1; int beginY = 0, endY = matrix.size() - 1; while (true) { // From left to right for (int j = beginX; j <= endX; ++j) result.push_back(matrix[beginY][j]); if (++beginY > endY) break; // From top to bottom for (int i = beginY; i <= endY; ++i) result.push_back(matrix[i][endX]); if (beginX > --endX) break; // From right to left for (int j = endX; j >= beginX; --j) result.push_back(matrix[endY][j]); if (beginY > --endY) break; // From bottom to top for (int i = endY; i >= beginY; --i) result.push_back(matrix[i][beginX]); if (++beginX > endX) break; } return result; } }; 题 • Spiral Matrix II §15.11 15.11 Spiral Matrix II Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order. For example, Given n = 3, You should return the following matrix: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

255.15.11 Spiral Matrix II 249 题 题 1 // LeetCode, Spiral Matrix II // O(n^2) O(n^2) class Solution { public: vector<vector<int> > generateMatrix(int n) { vector<vector<int> > matrix(n, vector<int>(n)); int begin = 0, end = n - 1; int num = 1; while (begin < end) { for (int j = begin; j < end; ++j) matrix[begin][j] = num++; for (int i = begin; i < end; ++i) matrix[i][end] = num++; for (int j = end; j > begin; --j) matrix[end][j] = num++; for (int i = end; i > begin; --i) matrix[i][begin] = num++; ++begin; --end; } if (begin == end) matrix[begin][begin] = num; return matrix; } }; 2 // LeetCode, Spiral Matrix II // @author (http://weibo.com/luangong) // O(n^2) O(n^2) class Solution { public: vector<vector<int> > generateMatrix(int n) { vector< vector<int> > matrix(n, vector<int>(n)); if (n == 0) return matrix; int beginX = 0, endX = n - 1; int beginY = 0, endY = n - 1; int num = 1; while (true) { for (int j = beginX; j <= endX; ++j) matrix[beginY][j] = num++; if (++beginY > endY) break; for (int i = beginY; i <= endY; ++i) matrix[i][endX] = num++; if (beginX > --endX) break; for (int j = endX; j >= beginX; --j) matrix[endY][j] = num++; if (beginY > --endY) break;

256.250 15 题 for (int i = endY; i >= beginY; --i) matrix[i][beginX] = num++; if (++beginX > endX) break; } return matrix; } }; 题 • Spiral Matrix, §15.10 15.12 ZigZag Conversion The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) P A H N A P L S I I G Y I R And then read line by line: "PAHNAPLSIIGYIR" Write the code that will take a string and make this conversion given a number of rows: string convert(string text, int nRows); convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR". 题 n=4: P I N A L S I G Y A H R P I n=5: P H A S I Y I R P L I G A N (i, j) = (j + 1) ∗ n + i (i, j) = (j + 1) ∗ n − i

257.15.13 Divide Two Integers 251 // LeetCode, ZigZag Conversion // O(n) O(1) class Solution { public: string convert(string s, int nRows) { if (nRows <= 1 || s.size() <= 1) return s; string result; for (int i = 0; i < nRows; i++) { for (int j = 0, index = i; index < s.size(); j++, index = (2 * nRows - 2) * j + i) { result.append(1, s[index]); // if (i == 0 || i == nRows - 1) continue; // if (index + (nRows - i - 1) * 2 < s.size()) result.append(1, s[index + (nRows - i - 1) * 2]); } } return result; } }; 题 • 15.13 Divide Two Integers Divide two integers without using multiplication, division and mod operator. 1 // LeetCode, Divide Two Integers // O(logn) O(1) class Solution { public: int divide(int dividend, int divisor) { // dividend = INT_MIN -dividend long long long long a = dividend >= 0 ? dividend : -(long long)dividend; long long b = divisor >= 0 ? divisor : -(long long)divisor;

258.252 15 题 // dividend = INT_MIN divisor = -1 long long long long result = 0; while (a >= b) { long long c = b; for (int i = 0; a >= c; ++i, c <<= 1) { a -= c; result += 1 << i; } } return ((dividend^divisor) >> 31) ? (-result) : (result); } }; 2 // LeetCode, Divide Two Integers // O(logn) O(1) class Solution { public: int divide(int dividend, int divisor) { int result = 0; // dividend = INT_MIN divisor = -1 const bool sign = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0); // // dividend = INT_MIN -dividend unsigned int unsigned int a = dividend >= 0 ? dividend : -dividend; unsigned int b = divisor >= 0 ? divisor : -divisor; while (a >= b) { int multi = 1; unsigned int bb = b; while (a >= bb) { a -= bb; result += multi; if (bb < INT_MAX >> 1) { // bb += bb; multi += multi; } } } if (sign) return -result; else return result; } }; 题 •

259.15.14 Text Justification 253 15.14 Text Justification Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified. You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters. Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right. For the last line of text, it should be left justified and no extra space is inserted between words. For example, words: ["This", "is", "an", "example", "of", "text", "justification."] L: 16. Return the formatted lines as: [ "This is an", "example of text", "justification. " ] Note: Each word is guaranteed not to exceed L in length. Corner Cases: • A line other than the last line might contain only one word. What should you do in this case? • In this case, that line should be left // LeetCode, Text Justification // O(n) O(1) class Solution { public: vector<string> fullJustify(vector<string> &words, int L) { vector<string> result; const int n = words.size(); int begin = 0, len = 0; // for (int i = 0; i < n; ++i) { if (len + words[i].size() + (i - begin) > L) { result.push_back(connect(words, begin, i - 1, len, L, false));

260.254 15 题 begin = i; len = 0; } len += words[i].size(); } // L result.push_back(connect(words, begin, n - 1, len, L, true)); return result; } /** * @brief words[begin, end] * @param[in] words * @param[in] begin * @param[in] end * @param[in] len words[begin, end] * @param[in] L 题 * @param[in] is_last * @return */ string connect(vector<string> &words, int begin, int end, int len, int L, bool is_last) { string s; int n = end - begin + 1; for (int i = 0; i < n; ++i) { s += words[begin + i]; addSpaces(s, i, n - 1, L - len, is_last); } if (s.size() < L) s.append(L - s.size(), ' '); return s; } /** * @brief . * @param[inout]s * @param[in] i * @param[in] n * @param[in] L * @param[in] is_last * @return */ void addSpaces(string &s, int i, int n, int L, bool is_last) { if (n < 1 || i > n - 1) return; int spaces = is_last ? 1 : (L / n + (i < (L % n) ? 1 : 0)); s.append(spaces, ' '); } }; 题 •

261.15.15 Max Points on a Line 255 15.15 Max Points on a Line Given n points on a 2D plane, find the maximum number of points that lie on the same straight line. 1 n n(n + 1) 2 n O(n3 ) key value O(n2 ) O(n) // LeetCode, Max Points on a Line // O(n^3) O(1) class Solution { public: int maxPoints(vector<Point> &points) { if (points.size() < 3) return points.size(); int result = 0; for (int i = 0; i < points.size() - 1; i++) { for (int j = i + 1; j < points.size(); j++) { int sign = 0; int a, b, c; if (points[i].x == points[j].x) sign = 1; else { a = points[j].x - points[i].x; b = points[j].y - points[i].y; c = a * points[i].y - b * points[i].x; } int count = 0; for (int k = 0; k < points.size(); k++) { if ((0 == sign && a * points[k].y == c + b * points[k].x) || (1 == sign&&points[k].x == points[j].x)) count++; } if (count > result) result = count; } } return result; } };

262.256 15 题 // LeetCode, Max Points on a Line // O(n^2) O(n) class Solution { public: int maxPoints(vector<Point> &points) { if (points.size() < 3) return points.size(); int result = 0; unordered_map<double, int> slope_count; for (int i = 0; i < points.size()-1; i++) { slope_count.clear(); int samePointNum = 0; // i int point_max = 1; // i for (int j = i + 1; j < points.size(); j++) { double slope; // if (points[i].x == points[j].x) { slope = std::numeric_limits<double>::infinity(); if (points[i].y == points[j].y) { ++ samePointNum; continue; } } else { slope = 1.0 * (points[i].y - points[j].y) / (points[i].x - points[j].x); } int count = 0; if (slope_count.find(slope) != slope_count.end()) count = ++slope_count[slope]; else { count = 2; slope_count[slope] = 2; } if (point_max < count) point_max = count; } result = max(result, point_max + samePointNum); } return result; } }; 题 •

user picture
  • 蓝色的海牛
  • 一个幽灵,共产主义的幽灵,在欧洲大陆徘徊。

相关Slides