算法刷题LeetCode中文版(1)

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];