LeetCode 题解
灵魂机器 (soulmachine@gmail.com)
https://github.com/soulmachine/leetcode
最后更新 2015-8-24
版权声明
本作品采用“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
目录
第 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 . . . . . . 4
2.1.4 Search in Rotated
Sorted Array II . . . . . 5
2.1.5 Median of Two Sorted
Arrays . . . . . . . . . . 6
2.1.6 Longest Consecutive
Sequence . . . . . . . . 8
2.1.7 Two Sum . . . . . . . . 10
2.1.8 3Sum . . . . . . . . . . 11
2.1.9 3Sum Closest . . . . . . 13
2.1.10 4Sum . . . . . . . . . . 14
2.1.11 Remove Element . . . . 17
2.1.12 Next Permutation . . . . 18
2.1.13 Permutation Sequence . 20
2.1.14 Valid Sudoku . . . . . . 22
2.1.15 Trapping Rain Water . . 24
2.1.16 Rotate Image . . . . . . 27
2.1.17 Plus One . . . . . . . . 28
2.1.18 Climbing Stairs . . . . . 29
2.1.19 Gray Code . . . . . . . 30
2.1.20 Set Matrix Zeroes . . . . 33
2.1.21 Gas Station . . . . . . . 35
2.1.22 Candy . . . . . . . . . . 35
2.1.23 Single Number . . . . . 37
2.1.24 Single Number II . . . . 38
2.2 单链表 . . . . . . . . . . . . . 39
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 . . . . . . . 45
2.2.7 Remove Nth Node
From End of List . . . . 46
2.2.8 Swap Nodes in Pairs . . 47
2.2.9 Reverse Nodes in k-Group 48
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 . . . . . . . 54
第 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 . . . . . . 93
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 . . . . . 101
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 二叉树的构建 . . . . . . . . . 107
5.2.1 Construct Binary Tree
from Preorder and In-
order Traversal . . . . . 107
5.2.2 Construct Binary Tree
from Inorder and Pos-
torder Traversal . . . . . 108
5.3 二叉查找树 . . . . . . . . . . . 109
5.3.1 Unique Binary Search
Trees . . . . . . . . . . 109
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 二叉树的递归 . . . . . . . . . 115
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 . . . . . . . . . . . 122
第 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 . . . . . . . . . 152
9.3 Surrounded Regions . . . . . . . 154
9.4 小结 . . . . . . . . . . . . . . . 156
9.4.1 适用场景 . . . . . . . . 156
9.4.2 思考的步骤 . . . . . . 156
9.4.3 代码模板 . . . . . . . . 157
第 10 章 深度优先搜索 162
10.1 Palindrome Partitioning . . . . . 162
10.2 Unique Paths . . . . . . . . . . 165
10.2.1 深搜 . . . . . . . . . . 165
10.2.2 备忘录法 . . . . . . . . 165
10.2.3 动规 . . . . . . . . . . 166
10.2.4 数学公式 . . . . . . . . 167
10.3 Unique Paths II . . . . . . . . . 168
10.3.1 备忘录法 . . . . . . . . 168
10.3.2 动规 . . . . . . . . . . 169
目录 v
10.4 N-Queens . . . . . . . . . . . . 169
10.5 N-Queens II . . . . . . . . . . . 172
10.6 Restore IP Addresses . . . . . . 173
10.7 Combination Sum . . . . . . . . 174
10.8 Combination Sum II . . . . . . 175
10.9 Generate Parentheses . . . . . . 177
10.10 Sudoku Solver . . . . . . . . . 178
10.11 Word Search . . . . . . . . . . 180
10.12 小结 . . . . . . . . . . . . . . 181
10.12.1 适用场景 . . . . . . . 181
10.12.2 思考的步骤 . . . . . . 181
10.12.3 代码模板 . . . . . . . 183
10.12.4 深搜与回溯法的区别 . 184
10.12.5 深搜与递归的区别 . . 184
第 11 章 分治法 185
11.1 Pow(x,n) . . . . . . . . . . . . . 185
11.2 Sqrt(x) . . . . . . . . . . . . . . 186
第 12 章 贪心法 187
12.1 Jump Game . . . . . . . . . . . 187
12.2 Jump Game II . . . . . . . . . . 188
12.3 Best Time to Buy and Sell Stock 190
12.4 Best Time to Buy and Sell Stock II191
12.5 Longest Substring Without Re-
peating Characters . . . . . . . 192
12.6 Container With Most Water . . . 193
第 13 章 动态规划 195
13.1 Triangle . . . . . . . . . . . . . 195
13.2 Maximum Subarray . . . . . . . 196
13.3 Palindrome Partitioning II . . . 198
13.4 Maximal Rectangle . . . . . . . 199
13.5 Best Time to Buy and Sell Stock
III . . . . . . . . . . . . . . . . 200
13.6 Interleaving String . . . . . . . 201
13.7 Scramble String . . . . . . . . . 203
13.8 Minimum Path Sum . . . . . . . 208
13.9 Edit Distance . . . . . . . . . . 210
13.10 Decode Ways . . . . . . . . . 212
13.11 Distinct Subsequences . . . . . 213
13.12 Word Break . . . . . . . . . . 214
13.13 Word Break II . . . . . . . . . 216
第 14 章 图 218
14.1 Clone Graph . . . . . . . . . . . 218
第 15 章 细节实现题 221
15.1 Reverse Integer . . . . . . . . . 221
15.2 Palindrome Number . . . . . . . 222
15.3 Insert Interval . . . . . . . . . . 223
15.4 Merge Intervals . . . . . . . . . 224
15.5 Minimum Window Substring . . 225
15.6 Multiply Strings . . . . . . . . . 227
15.7 Substring with Concatenation
of All Words . . . . . . . . . . . 230
15.8 Pascal’s Triangle . . . . . . . . 231
15.9 Pascal’s Triangle II . . . . . . . 232
15.10 Spiral Matrix . . . . . . . . . . 233
15.11 Spiral Matrix II . . . . . . . . . 234
15.12 ZigZag Conversion . . . . . . 236
15.13 Divide Two Integers . . . . . . 237
15.14 Text Justification . . . . . . . . 238
15.15 Max Points on a Line . . . . . 240
