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/
AlgorithmsRobert Sedgewick, Addison-Wesley Professional, http://book.douban.com/subject/4854123/
i
1 1
2 2
2.1 . . . . . . . . . . . . . . . 2
2.1.1 Remove Duplicates
from Sorted Array . . . 2
2.1.2 Remove Duplicates
from Sorted Array II . . 3
2.1.3 Search in Rotated
Sorted Array . . . . . . 5
2.1.4 Search in Rotated
Sorted Array II . . . . . 6
2.1.5 Median of Two Sorted
Arrays . . . . . . . . . . 7
2.1.6 Longest Consecutive
Sequence . . . . . . . . 8
2.1.7 Two Sum . . . . . . . . 10
2.1.8 3Sum . . . . . . . . . . 12
2.1.9 3Sum Closest . . . . . . 13
2.1.10 4Sum . . . . . . . . . . 14
2.1.11 Remove Element . . . . 18
2.1.12 Next Permutation . . . . 19
2.1.13 Permutation Sequence . 21
2.1.14 Valid Sudoku . . . . . . 23
2.1.15 Trapping Rain Water . . 24
2.1.16 Rotate Image . . . . . . 27
2.1.17 Plus One . . . . . . . . 28
2.1.18 Climbing Stairs . . . . . 30
2.1.19 Gray Code . . . . . . . 31
2.1.20 Set Matrix Zeroes . . . . 33
2.1.21 Gas Station . . . . . . . 35
2.1.22 Candy . . . . . . . . . . 36
2.1.23 Single Number . . . . . 37
2.1.24 Single Number II . . . . 38
2.2 . . . . . . . . . . . . . 40
2.2.1 Add Two Numbers . . . 40
2.2.2 Reverse Linked List II . 41
2.2.3 Partition List . . . . . . 42
2.2.4 Remove Duplicates
from Sorted List . . . . 43
2.2.5 Remove Duplicates
from Sorted List II . . . 44
2.2.6 Rotate List . . . . . . . 46
2.2.7 Remove Nth Node
From End of List . . . . 47
2.2.8 Swap Nodes in Pairs . . 47
2.2.9 Reverse Nodes in k-Group 49
2.2.10 Copy List with Random
Pointer . . . . . . . . . 50
2.2.11 Linked List Cycle . . . . 51
2.2.12 Linked List Cycle II . . 52
2.2.13 Reorder List . . . . . . 53
2.2.14 LRU Cache . . . . . . . 55
3 57
3.1 Valid Palindrome . . . . . . . . 57
3.2 Implement strStr() . . . . . . . . 58
3.3 String to Integer (atoi) . . . . . 60
ii
iii
3.4 Add Binary . . . . . . . . . . . 61
3.5 Longest Palindromic Substring . 62
3.6 Regular Expression Matching . . 66
3.7 Wildcard Matching . . . . . . . 67
3.8 Longest Common Prefix . . . . 69
3.9 Valid Number . . . . . . . . . . 70
3.10 Integer to Roman . . . . . . . . 72
3.11 Roman to Integer . . . . . . . . 73
3.12 Count and Say . . . . . . . . . . 74
3.13 Anagrams . . . . . . . . . . . . 75
3.14 Simplify Path . . . . . . . . . . 76
3.15 Length of Last Word . . . . . . 77
4 79
4.1 . . . . . . . . . . . . . . . . 79
4.1.1 Valid Parentheses . . . . 79
4.1.2 Longest Valid Paren-
theses . . . . . . . . . . 80
4.1.3 Largest Rectangle in
Histogram . . . . . . . . 82
4.1.4 Evaluate Reverse Pol-
ish Notation . . . . . . . 84
4.2 . . . . . . . . . . . . . . . 85
5 86
5.1 . . . . . . . . . 86
5.1.1 Binary Tree Preorder
Traversal . . . . . . . . 86
5.1.2 Binary Tree Inorder
Traversal . . . . . . . . 88
5.1.3 Binary Tree Postorder
Traversal . . . . . . . . 90
5.1.4 Binary Tree Level Or-
der Traversal . . . . . . 92
5.1.5 Binary Tree Level Or-
der Traversal II . . . . . 94
5.1.6 Binary Tree Zigzag
Level Order Traversal . 96
5.1.7 Recover Binary Search
Tree . . . . . . . . . . . 98
5.1.8 Same Tree . . . . . . . 99
5.1.9 Symmetric Tree . . . . . 100
5.1.10 Balanced Binary Tree . . 102
5.1.11 Flatten Binary Tree to
Linked List . . . . . . . 103
5.1.12 Populating Next Right
Pointers in Each Node II 105
5.2 . . . . . . . . . 106
5.2.1 Construct Binary Tree
from Preorder and In-
order Traversal . . . . . 106
5.2.2 Construct Binary Tree
from Inorder and Pos-
torder Traversal . . . . . 107
5.3 . . . . . . . . . . . 108
5.3.1 Unique Binary Search
Trees . . . . . . . . . . 108
5.3.2 Unique Binary Search
Trees II . . . . . . . . . 110
5.3.3 Validate Binary Search
Tree . . . . . . . . . . . 111
5.3.4 Convert Sorted Array to
Binary Search Tree . . . 112
5.3.5 Convert Sorted List to
Binary Search Tree . . . 113
5.4 . . . . . . . . . 114
5.4.1 Minimum Depth of Bi-
nary Tree . . . . . . . . 115
iv
5.4.2 Maximum Depth of Bi-
nary Tree . . . . . . . . 116
5.4.3 Path Sum . . . . . . . . 117
5.4.4 Path Sum II . . . . . . . 118
5.4.5 Binary Tree Maximum
Path Sum . . . . . . . . 119
5.4.6 Populating Next Right
Pointers in Each Node . 120
5.4.7 Sum Root to Leaf Num-
bers . . . . . . . . . . . 121
6 123
6.1 Merge Sorted Array . . . . . . . 123
6.2 Merge Two Sorted Lists . . . . . 124
6.3 Merge k Sorted Lists . . . . . . 124
6.4 Insertion Sort List . . . . . . . . 125
6.5 Sort List . . . . . . . . . . . . . 126
6.6 First Missing Positive . . . . . . 127
6.7 Sort Colors . . . . . . . . . . . 128
7 131
7.1 Search for a Range . . . . . . . 131
7.2 Search Insert Position . . . . . . 132
7.3 Search a 2D Matrix . . . . . . . 133
8 135
8.1 Subsets . . . . . . . . . . . . . 135
8.1.1 . . . . . . . . . . 135
8.1.2 . . . . . . . . . . 137
8.2 Subsets II . . . . . . . . . . . . 138
8.2.1 . . . . . . . . . . 138
8.2.2 . . . . . . . . . . 141
8.3 Permutations . . . . . . . . . . 142
8.3.1 next_permutation() . . . 142
8.3.2 next_permu-
tation() . . . . . . . . . 142
8.3.3 . . . . . . . . . . 143
8.4 Permutations II . . . . . . . . . 144
8.4.1 next_permutation() . . . 144
8.4.2 next_permu-
tation() . . . . . . . . . 144
8.4.3 . . . . . . . . . . 144
8.5 Combinations . . . . . . . . . . 146
8.5.1 . . . . . . . . . . 146
8.5.2 . . . . . . . . . . 147
8.6 Letter Combinations of a Phone
Number . . . . . . . . . . . . . 147
8.6.1 . . . . . . . . . . 148
8.6.2 . . . . . . . . . . 149
9 150
9.1 Word Ladder . . . . . . . . . . 150
9.2 Word Ladder II . . . . . . . . . 154
9.3 Surrounded Regions . . . . . . . 162
9.4 . . . . . . . . . . . . . . . 164
9.4.1 . . . . . . . . 164
9.4.2 . . . . . . 164
9.4.3 . . . . . . . . 165
10 173
10.1 Palindrome Partitioning . . . . . 173
10.2 Unique Paths . . . . . . . . . . 176
10.2.1 . . . . . . . . . . 176
10.2.2 . . . . . . . . 176
10.2.3 . . . . . . . . . . 177
10.2.4 . . . . . . . . 178
10.3 Unique Paths II . . . . . . . . . 179
10.3.1 . . . . . . . . 179
10.3.2 . . . . . . . . . . 180
v
10.4 N-Queens . . . . . . . . . . . . 181
10.5 N-Queens II . . . . . . . . . . . 184
10.6 Restore IP Addresses . . . . . . 186
10.7 Combination Sum . . . . . . . . 188
10.8 Combination Sum II . . . . . . 189
10.9 Generate Parentheses . . . . . . 190
10.10 Sudoku Solver . . . . . . . . . 192
10.11 Word Search . . . . . . . . . . 193
10.12 . . . . . . . . . . . . . . 195
10.12.1 . . . . . . . 195
10.12.2 . . . . . . 195
10.12.3 . . . . . . . 197
10.12.4 . 197
10.12.5 . . 197
11 199
11.1 Pow(x,n) . . . . . . . . . . . . . 199
11.2 Sqrt(x) . . . . . . . . . . . . . . 200
12 201
12.1 Jump Game . . . . . . . . . . . 201
12.2 Jump Game II . . . . . . . . . . 202
12.3 Best Time to Buy and Sell Stock 204
12.4 Best Time to Buy and Sell Stock II205
12.5 Longest Substring Without Re-
peating Characters . . . . . . . 206
12.6 Container With Most Water . . . 207
13 209
13.1 Triangle . . . . . . . . . . . . . 209
13.2 Maximum Subarray . . . . . . . 210
13.3 Palindrome Partitioning II . . . 212
13.4 Maximal Rectangle . . . . . . . 213
13.5 Best Time to Buy and Sell Stock
III . . . . . . . . . . . . . . . . 214
13.6 Interleaving String . . . . . . . 215
13.7 Scramble String . . . . . . . . . 217
13.8 Minimum Path Sum . . . . . . . 222
13.9 Edit Distance . . . . . . . . . . 224
13.10 Decode Ways . . . . . . . . . 226
13.11 Distinct Subsequences . . . . . 227
13.12 Word Break . . . . . . . . . . 228
13.13 Word Break II . . . . . . . . . 230
14 232
14.1 Clone Graph . . . . . . . . . . . 232
15 题 235
15.1 Reverse Integer . . . . . . . . . 235
15.2 Palindrome Number . . . . . . . 236
15.3 Insert Interval . . . . . . . . . . 237
15.4 Merge Intervals . . . . . . . . . 238
15.5 Minimum Window Substring . . 239
15.6 Multiply Strings . . . . . . . . . 241
15.7 Substring with Concatenation
of All Words . . . . . . . . . . . 244
15.8 Pascal’s Triangle . . . . . . . . 245
15.9 Pascal’s Triangle II . . . . . . . 246
15.10 Spiral Matrix . . . . . . . . . . 247
15.11 Spiral Matrix II . . . . . . . . . 248
15.12 ZigZag Conversion . . . . . . 250
15.13 Divide Two Integers . . . . . . 251
15.14 Text Justification . . . . . . . . 253
15.15 Max Points on a Line . . . . . 255
