最新LeetCodeC++题解[2014-12-08]

LeetCode

5星 · 超过95%的资源需积分: 50 116 浏览量更新于2023-06-05 评论收藏 1.03MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

LeetCode 题解

戴方勤 (soulmachine@gmail.com)

https://github.com/soulmachine/leetcode

最后更新 2014-12-8

本作品采用“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/

目录 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

剩余247页未读，继续阅读

mzg12345678

2020-04-10

不错的分享，学习中

DWcsdnNET

粉丝: 415
资源: 652

会员权益专享

最新 LeetCode C++ 题解 [2014-12-08]

评论2

会员权益专享

最新资源

最新 LeetCode C++ 题解 [2014-12-08]

评论2

leetcode的JavaScript实现代码

（C++）LeetCode刷题题解答案

c++-c++编程基础之leetcode题解第37题解数独.zip

leetcode c++题解

leetcode 102acm

LeetCode358用C语言实现

leetcode怎么样

c++ vector批量添加

谷歌工程师的 leetcode 算法笔记

leetcode如何刷

腾讯解压算法 c++

vector<pair(int,int)>

memset一个pair

如何对vector<pair<int,int>> 类型进行排序

多重背包二进制优化c++代码

leetcode题解c-leetcode-solution:leetcode-解决方案

leetcode中国-Awesome-Leetcode-Interviews-Collections:LeetCode题解与面试经验收集

c++-c++编程基础之leetcode题解第12题整数转罗马数字.zip

分类整理leetcode算法题解，代码语言采用c++与python实现.zip

leetcode题库-Interview-Notes:C++技术面试知识笔记—剑指offer题解C++版、Leetcode题解C++版、数据结

会员权益专享

最新资源