没有合适的资源?快使用搜索试试~ 我知道了~
首页lintcode题解详细完整版C++实现
lintcode题解详细完整版C++实现
需积分: 17 10 下载量 197 浏览量
更新于2023-03-16
评论 2
收藏 1.03MB PDF 举报
本书的目标读者是准备去北美找工作的码农,也适用于在国内找工作的码农,以及刚接触 ACM 算法竞赛的新手。 本书包含了 LintCode Online Judge(http://www.lintcode.com/) 所有题目的答案,所有代码经过精心编写,编码规范良好,适合读者反复揣摩,模仿,甚至在纸上默写。全书的代码,使用 C++ 编写,并测试通过。希望对大家提升代码能力有较大的帮助。
资源详情
资源评论
资源推荐
LintCode 题解
灵魂机器 (soulmachine@gmail.com)
https://github.com/soulmachine/lintcode
最后更新 2015-5-3
版权声明
本作品采用“Creative Commons 署名 -非商业性使用 -相同方式共享 3.0 Unported 许可协议
(cc by-nc-sa)”进行许可。http://creativecommons.org/licenses/by-nc-sa/3.0/
内容简介
本书的目标读者是准备去北美找工作的码农,也适用于在国内找工作的码农,以及刚
接触 ACM 算法竞赛的新手。
本书包含了 LintCode Online Judge(http://www.lintcode.com/) 所有题目的答案,所有代码
经过精心编写,编码规范良好,适合读者反复揣摩,模仿,甚至在纸上默写。
全书的代码,使用 C++ 11 的编写,并在 LintCode Online Judge 上测试通过。本书中的
代码规范,跟在公司中的工程规范略有不同,为了使代码短(方便迅速实现):
• 所有代码都是单一文件。这是因为一般 OJ 网站,提交代码的时候只有一个文本框,
如果还是按照标准做法,比如分为头文件.h 和源代码.cpp,无法在网站上提交;
• Shorter is better。能递归则一定不用栈;能用 STL 则一定不自己实现。
• 不提倡防御式编程。不需要检查 malloc()/new 返回的指针是否为 nullptr;不需要检查
内部函数入口参数的有效性。
本手册假定读者已经学过《数据结构》
¬
,《算法》
这两门课,熟练掌握 C++ 或 Java。
GitHub 地址
本书是开源的,GitHub 地址:https://github.com/soulmachine/lintcode
北美求职微博群
我和我的小伙伴们在这里: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 . . . . . . . . . . 36
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 . . 41
2.2.3 Reverse Linked List II . 42
2.2.4 Partition List . . . . . . 43
2.2.5 Remove Duplicates
from Sorted List . . . . 44
2.2.6 Remove Duplicates
from Sorted List II . . . 45
2.2.7 Rotate List . . . . . . . 46
2.2.8 Remove Nth Node
From End of List . . . . 47
2.2.9 Swap Nodes in Pairs . . 48
2.2.10 Reverse Nodes in k-Group 49
2.2.11 Copy List with Random
Pointer . . . . . . . . . 51
2.2.12 Linked List Cycle . . . . 52
2.2.13 Linked List Cycle II . . 53
2.2.14 Reorder List . . . . . . 54
2.2.15 LRU Cache . . . . . . . 55
第 3 章 字符串 58
3.1 Valid Palindrome . . . . . . . . 58
3.2 Implement strStr() . . . . . . . . 59
ii
目录 iii
3.3 String to Integer (atoi) . . . . . 61
3.4 Add Binary . . . . . . . . . . . 62
3.5 Longest Palindromic Substring . 63
3.6 Regular Expression Matching . . 67
3.7 Wildcard Matching . . . . . . . 68
3.8 Longest Common Prefix . . . . 70
3.9 Valid Number . . . . . . . . . . 71
3.10 Integer to Roman . . . . . . . . 73
3.11 Roman to Integer . . . . . . . . 74
3.12 Count and Say . . . . . . . . . . 75
3.13 Anagrams . . . . . . . . . . . . 76
3.14 Simplify Path . . . . . . . . . . 77
3.15 Length of Last Word . . . . . . 78
第 4 章 栈和队列 80
4.1 栈 . . . . . . . . . . . . . . . . 80
4.1.1 Valid Parentheses . . . . 80
4.1.2 Longest Valid Paren-
theses . . . . . . . . . . 81
4.1.3 Largest Rectangle in
Histogram . . . . . . . . 83
4.1.4 Evaluate Reverse Pol-
ish Notation . . . . . . . 85
4.2 队列 . . . . . . . . . . . . . . . 86
第 5 章 树 87
5.1 二叉树的遍历 . . . . . . . . . 87
5.1.1 Binary Tree Preorder
Traversal . . . . . . . . 87
5.1.2 Binary Tree Inorder
Traversal . . . . . . . . 89
5.1.3 Binary Tree Postorder
Traversal . . . . . . . . 91
5.1.4 Binary Tree Level Or-
der Traversal . . . . . . 94
5.1.5 Binary Tree Level Or-
der Traversal II . . . . . 95
5.1.6 Binary Tree Zigzag
Level Order Traversal . 97
5.1.7 Recover Binary Search
Tree . . . . . . . . . . . 99
5.1.8 Same Tree . . . . . . . 100
5.1.9 Symmetric Tree . . . . . 102
5.1.10 Balanced Binary Tree . . 103
5.1.11 Flatten Binary Tree to
Linked List . . . . . . . 104
5.1.12 Populating Next Right
Pointers in Each Node II 106
5.2 二叉树的构建 . . . . . . . . . 108
5.2.1 Construct Binary Tree
from Preorder and In-
order Traversal . . . . . 108
5.2.2 Construct Binary Tree
from Inorder and Pos-
torder Traversal . . . . . 109
5.3 二叉查找树 . . . . . . . . . . . 110
5.3.1 Unique Binary Search
Trees . . . . . . . . . . 110
5.3.2 Unique Binary Search
Trees II . . . . . . . . . 111
5.3.3 Validate Binary Search
Tree . . . . . . . . . . . 112
5.3.4 Convert Sorted Array to
Binary Search Tree . . . 113
5.3.5 Convert Sorted List to
Binary Search Tree . . . 114
5.4 二叉树的递归 . . . . . . . . . 116
5.4.1 Minimum Depth of Bi-
nary Tree . . . . . . . . 116
iv 目录
5.4.2 Maximum Depth of Bi-
nary Tree . . . . . . . . 117
5.4.3 Path Sum . . . . . . . . 118
5.4.4 Path Sum II . . . . . . . 119
5.4.5 Binary Tree Maximum
Path Sum . . . . . . . . 120
5.4.6 Populating Next Right
Pointers in Each Node . 121
5.4.7 Sum Root to Leaf Num-
bers . . . . . . . . . . . 123
第 6 章 排序 124
6.1 Merge Sorted Array . . . . . . . 124
6.2 Merge Two Sorted Lists . . . . . 125
6.3 Merge k Sorted Lists . . . . . . 125
6.4 Insertion Sort List . . . . . . . . 126
6.5 Sort List . . . . . . . . . . . . . 127
6.6 First Missing Positive . . . . . . 129
6.7 Sort Colors . . . . . . . . . . . 130
第 7 章 查找 133
7.1 Search for a Range . . . . . . . 133
7.2 Search Insert Position . . . . . . 134
7.3 Search a 2D Matrix . . . . . . . 135
第 8 章 暴力枚举法 137
8.1 Subsets . . . . . . . . . . . . . 137
8.1.1 递归 . . . . . . . . . . 137
8.1.2 迭代 . . . . . . . . . . 139
8.2 Subsets II . . . . . . . . . . . . 140
8.2.1 递归 . . . . . . . . . . 140
8.2.2 迭代 . . . . . . . . . . 143
8.3 Permutations . . . . . . . . . . 144
8.3.1 next_permutation() . . . 144
8.3.2 解 法 2: 重 新 实 现
next_permutation() . . . 144
8.3.3 递归 . . . . . . . . . . 145
8.4 Permutations II . . . . . . . . . 146
8.4.1 next_permutation() . . . 146
8.4.2 重新实现 next_permu-
tation() . . . . . . . . . 146
8.4.3 递归 . . . . . . . . . . 146
8.5 Combinations . . . . . . . . . . 148
8.5.1 递归 . . . . . . . . . . 148
8.5.2 迭代 . . . . . . . . . . 149
8.6 Letter Combinations of a Phone
Number . . . . . . . . . . . . . 149
8.6.1 递归 . . . . . . . . . . 150
8.6.2 迭代 . . . . . . . . . . 151
第 9 章 广度优先搜索 152
9.1 Word Ladder . . . . . . . . . . 152
9.2 Word Ladder II . . . . . . . . . 154
9.3 Surrounded Regions . . . . . . . 156
9.4 小结 . . . . . . . . . . . . . . . 158
9.4.1 适用场景 . . . . . . . . 158
9.4.2 思考的步骤 . . . . . . 158
9.4.3 代码模板 . . . . . . . . 159
第 10 章 深度优先搜索 164
10.1 Palindrome Partitioning . . . . . 164
10.2 Unique Paths . . . . . . . . . . 167
10.2.1 深搜 . . . . . . . . . . 167
10.2.2 备忘录法 . . . . . . . . 167
10.2.3 动规 . . . . . . . . . . 168
10.2.4 数学公式 . . . . . . . . 169
10.3 Unique Paths II . . . . . . . . . 170
10.3.1 备忘录法 . . . . . . . . 170
10.3.2 动规 . . . . . . . . . . 171
目录 v
10.4 N-Queens . . . . . . . . . . . . 171
10.5 N-Queens II . . . . . . . . . . . 174
10.6 Restore IP Addresses . . . . . . 175
10.7 Combination Sum . . . . . . . . 176
10.8 Combination Sum II . . . . . . 177
10.9 Generate Parentheses . . . . . . 179
10.10 Sudoku Solver . . . . . . . . . 180
10.11 Word Search . . . . . . . . . . 182
10.12 小结 . . . . . . . . . . . . . . 183
10.12.1 适用场景 . . . . . . . 183
10.12.2 思考的步骤 . . . . . . 183
10.12.3 代码模板 . . . . . . . 185
10.12.4 深搜与回溯法的区别 . 186
10.12.5 深搜与递归的区别 . . 186
第 11 章 分治法 187
11.1 Pow(x,n) . . . . . . . . . . . . . 187
11.2 Sqrt(x) . . . . . . . . . . . . . . 188
第 12 章 贪心法 189
12.1 Jump Game . . . . . . . . . . . 189
12.2 Jump Game II . . . . . . . . . . 191
12.3 Best Time to Buy and Sell Stock 192
12.4 Best Time to Buy and Sell Stock II193
12.5 Longest Substring Without Re-
peating Characters . . . . . . . 194
12.6 Container With Most Water . . . 195
第 13 章 动态规划 197
13.1 Triangle . . . . . . . . . . . . . 197
13.2 Maximum Subarray . . . . . . . 198
13.3 Palindrome Partitioning II . . . 200
13.4 Maximal Rectangle . . . . . . . 201
13.5 Best Time to Buy and Sell Stock
III . . . . . . . . . . . . . . . . 202
13.6 Interleaving String . . . . . . . 203
13.7 Scramble String . . . . . . . . . 205
13.8 Minimum Path Sum . . . . . . . 210
13.9 Edit Distance . . . . . . . . . . 212
13.10 Decode Ways . . . . . . . . . 214
13.11 Distinct Subsequences . . . . . 215
13.12 Word Break . . . . . . . . . . 216
13.13 Word Break II . . . . . . . . . 218
第 14 章 图 220
14.1 Clone Graph . . . . . . . . . . . 220
第 15 章 细节实现题 223
15.1 Reverse Integer . . . . . . . . . 223
15.2 Palindrome Number . . . . . . . 224
15.3 Insert Interval . . . . . . . . . . 225
15.4 Merge Intervals . . . . . . . . . 226
15.5 Minimum Window Substring . . 227
15.6 Multiply Strings . . . . . . . . . 229
15.7 Substring with Concatenation
of All Words . . . . . . . . . . . 232
15.8 Pascal’s Triangle . . . . . . . . 233
15.9 Pascal’s Triangle II . . . . . . . 234
15.10 Spiral Matrix . . . . . . . . . . 235
15.11 Spiral Matrix II . . . . . . . . . 236
15.12 ZigZag Conversion . . . . . . 238
15.13 Divide Two Integers . . . . . . 239
15.14 Text Justification . . . . . . . . 240
15.15 Max Points on a Line . . . . . 242
剩余249页未读,继续阅读
yuj48849157
- 粉丝: 0
- 资源: 4
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- ExcelVBA中的Range和Cells用法说明.pdf
- 基于单片机的电梯控制模型设计.doc
- 主成分分析和因子分析.pptx
- 共享笔记服务系统论文.doc
- 基于数据治理体系的数据中台实践分享.pptx
- 变压器的铭牌和额定值.pptx
- 计算机网络课程设计报告--用winsock设计Ping应用程序.doc
- 高电压技术课件:第03章 液体和固体介质的电气特性.pdf
- Oracle商务智能精华介绍.pptx
- 基于单片机的输液滴速控制系统设计文档.doc
- dw考试题 5套.pdf
- 学生档案管理系统详细设计说明书.doc
- 操作系统PPT课件.pptx
- 智慧路边停车管理系统方案.pptx
- 【企业内控系列】企业内部控制之人力资源管理控制(17页).doc
- 温度传感器分类与特点.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0