第1页 / 共248页
第2页 / 共248页
第3页 / 共248页
第4页 / 共248页
第5页 / 共248页
第6页 / 共248页
第7页 / 共248页
第8页 / 共248页
LeetCode全部题目和详细解答 数据结构算法 程序员面试求职必备.pdf
第1章 编程技巧
第2章 线性表
2.1 数组
2.1.1 Remove Duplicates from Sorted Array
2.1.2 Remove Duplicates from Sorted Array II
2.1.3 Search in Rotated Sorted Array
2.1.4 Search in Rotated Sorted Array II
2.1.5 Median of Two Sorted Arrays
2.1.6 Longest Consecutive Sequence
2.1.7 Two Sum
2.1.8 3Sum
2.1.9 3Sum Closest
2.1.10 4Sum
2.1.11 Remove Element
2.1.12 Next Permutation
2.1.13 Permutation Sequence
2.1.14 Valid Sudoku
2.1.15 Trapping Rain Water
2.1.16 Rotate Image
2.1.17 Plus One
2.1.18 Climbing Stairs
2.1.19 Gray Code
2.1.20 Set Matrix Zeroes
2.1.21 Gas Station
2.1.22 Candy
2.1.23 Single Number
2.1.24 Single Number II
2.2 单链表
2.2.1 Add Two Numbers
2.2.2 Reverse Linked List II
2.2.3 Partition List
2.2.4 Remove Duplicates from Sorted List
2.2.5 Remove Duplicates from Sorted List II
2.2.6 Rotate List
2.2.7 Remove Nth Node From End of List
2.2.8 Swap Nodes in Pairs
2.2.9 Reverse Nodes in k-Group
2.2.10 Copy List with Random Pointer
2.2.11 Linked List Cycle
2.2.12 Linked List Cycle II
2.2.13 Reorder List
2.2.14 LRU Cache
第3章 字符串
3.1 Valid Palindrome
3.2 Implement strStr()
3.3 String to Integer (atoi)
3.4 Add Binary
3.5 Longest Palindromic Substring
3.6 Regular Expression Matching
3.7 Wildcard Matching
3.8 Longest Common Prefix
3.9 Valid Number
3.10 Integer to Roman
3.11 Roman to Integer
3.12 Count and Say
3.13 Anagrams
3.14 Simplify Path
3.15 Length of Last Word
第4章 栈和队列
4.1 栈
4.1.1 Valid Parentheses
4.1.2 Longest Valid Parentheses
4.1.3 Largest Rectangle in Histogram
4.1.4 Evaluate Reverse Polish Notation
4.2 队列
第5章 树
5.1 二叉树的遍历
5.1.1 Binary Tree Preorder Traversal
5.1.2 Binary Tree Inorder Traversal
5.1.3 Binary Tree Postorder Traversal
5.1.4 Binary Tree Level Order Traversal
5.1.5 Binary Tree Level Order Traversal II
5.1.6 Binary Tree Zigzag Level Order Traversal
5.1.7 Recover Binary Search Tree
5.1.8 Same Tree
5.1.9 Symmetric Tree
5.1.10 Balanced Binary Tree
5.1.11 Flatten Binary Tree to Linked List
5.1.12 Populating Next Right Pointers in Each Node II
5.2 二叉树的构建
5.2.1 Construct Binary Tree from Preorder and Inorder Traversal
5.2.2 Construct Binary Tree from Inorder and Postorder Traversal
5.3 二叉查找树
5.3.1 Unique Binary Search Trees
5.3.2 Unique Binary Search Trees II
5.3.3 Validate Binary Search Tree
5.3.4 Convert Sorted Array to Binary Search Tree
5.3.5 Convert Sorted List to Binary Search Tree
5.4 二叉树的递归
5.4.1 Minimum Depth of Binary Tree
5.4.2 Maximum Depth of Binary Tree
5.4.3 Path Sum
5.4.4 Path Sum II
5.4.5 Binary Tree Maximum Path Sum
5.4.6 Populating Next Right Pointers in Each Node
5.4.7 Sum Root to Leaf Numbers
第6章 排序
6.1 Merge Sorted Array
6.2 Merge Two Sorted Lists
6.3 Merge k Sorted Lists
6.4 Insertion Sort List
6.5 Sort List
6.6 First Missing Positive
6.7 Sort Colors
第7章 查找
7.1 Search for a Range
7.2 Search Insert Position
7.3 Search a 2D Matrix
第8章 暴力枚举法
8.1 Subsets
8.1.1 递归
8.1.2 迭代
8.2 Subsets II
8.2.1 递归
8.2.2 迭代
8.3 Permutations
8.3.1 next_permutation()
8.3.2 重新实现next_permutation()
8.3.3 递归
8.4 Permutations II
8.4.1 next_permutation()
8.4.2 重新实现next_permutation()
8.4.3 递归
8.5 Combinations
8.5.1 递归
8.5.2 迭代
8.6 Letter Combinations of a Phone Number
8.6.1 递归
8.6.2 迭代
第9章 广度优先搜索
9.1 Word Ladder
9.2 Word Ladder II
9.3 Surrounded Regions
9.4 小结
9.4.1 适用场景
9.4.2 思考的步骤
9.4.3 代码模板
第10章 深度优先搜索
10.1 Palindrome Partitioning
10.2 Unique Paths
10.2.1 深搜
10.2.2 备忘录法
10.2.3 动规
10.2.4 数学公式
10.3 Unique Paths II
10.3.1 备忘录法
10.3.2 动规
10.4 N-Queens
10.5 N-Queens II
10.6 Restore IP Addresses
10.7 Combination Sum
10.8 Combination Sum II
10.9 Generate Parentheses
10.10 Sudoku Solver
10.11 Word Search
10.12 小结
10.12.1 适用场景
10.12.2 思考的步骤
10.12.3 代码模板
10.12.4 深搜与回溯法的区别
10.12.5 深搜与递归的区别
第11章 分治法
11.1 Pow(x,n)
11.2 Sqrt(x)
第12章 贪心法
12.1 Jump Game
12.2 Jump Game II
12.3 Best Time to Buy and Sell Stock
12.4 Best Time to Buy and Sell Stock II
12.5 Longest Substring Without Repeating Characters
12.6 Container With Most Water
第13章 动态规划
13.1 Triangle
13.2 Maximum Subarray
13.3 Palindrome Partitioning II
13.4 Maximal Rectangle
13.5 Best Time to Buy and Sell Stock III
13.6 Interleaving String
13.7 Scramble String
13.8 Minimum Path Sum
13.9 Edit Distance
13.10 Decode Ways
13.11 Distinct Subsequences
13.12 Word Break
13.13 Word Break II
第14章 图
14.1 Clone Graph
第15章 细节实现题
15.1 Reverse Integer
15.2 Palindrome Number
15.3 Insert Interval
15.4 Merge Intervals
15.5 Minimum Window Substring
15.6 Multiply Strings
15.7 Substring with Concatenation of All Words
15.8 Pascal's Triangle
15.9 Pascal's Triangle II
15.10 Spiral Matrix
15.11 Spiral Matrix II
15.12 ZigZag Conversion
15.13 Divide Two Integers
15.14 Text Justification
15.15 Max Points on a Line
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/
i
第 1 章 编程技巧
第 2 章 线性表
2.1 数组 . .
1
2
2
2
3
4
5
6
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
in
in
2.1.4
2.1.3
Arrays .
2.1.2 Remove
from Sorted Array .
.
2.1.1 Remove
from Sorted Array II
Search
Sorted Array . .
Search
Sorted Array II .
.
.
Duplicates
.
Duplicates
. .
Rotated
.
Rotated
.
2.1.5 Median of Two Sorted
.
2.1.6 Longest Consecutive
.
.
.
.
.
.
.
8
.
.
.
Sequence . .
10
.
.
.
2.1.7 Two Sum . .
11
.
.
3Sum .
.
2.1.8
.
13
.
.
3Sum Closest . .
2.1.9
. 14
.
2.1.10 4Sum .
.
. 17
2.1.11 Remove Element
.
2.1.12 Next Permutation .
. 18
2.1.13 Permutation Sequence . 20
22
2.1.14 Valid Sudoku . .
.
24
2.1.15 Trapping Rain Water . .
2.1.16 Rotate Image . .
.
27
.
2.1.17 Plus One . .
28
.
. 29
2.1.18 Climbing Stairs .
2.1.19 Gray Code
.
.
30
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. .
.
.
.
.
.
.
.
.
.
.
.
.
.
目录
2.2 单链表 . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2.1.20 Set Matrix Zeroes . .
.
2.1.21 Gas Station . .
.
2.1.22 Candy .
.
.
2.1.23 Single Number
.
2.1.24 Single Number II . .
.
.
.
.
.
.
.
2.2.1 Add Two Numbers . .
2.2.2 Reverse Linked List II
2.2.3
.
.
Duplicates
2.2.4 Remove
.
Duplicates
. .
2.2.6 Rotate List
.
.
2.2.7 Remove Nth Node
.
from Sorted List II
.
.
from Sorted List
2.2.5 Remove
Partition List
. .
. .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
33
35
35
37
38
39
40
41
42
43
44
45
. .
.
From End of List
Swap Nodes in Pairs . .
46
2.2.8
47
2.2.9 Reverse Nodes in k-Group 48
2.2.10 Copy List with Random
.
.
.
.
. .
.
.
.
.
.
2.2.11 Linked List Cycle . .
2.2.12 Linked List Cycle II
.
2.2.13 Reorder List
.
2.2.14 LRU Cache . .
.
50
51
52
53
54
Pointer
. .
.
.
.
.
.
.
.
.
第 3 章 字符串
3.1 Valid Palindrome . .
3.2
Implement strStr() . .
3.3 String to Integer (atoi)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
57
57
58
60
ii
目录
.
.
.
.
.
.
.
.
.
.
3.4 Add Binary . .
61
3.5 Longest Palindromic Substring . 62
66
3.6 Regular Expression Matching . .
.
3.7 Wildcard Matching . .
.
67
3.8 Longest Common Prefix .
. 69
.
. 70
.
3.9 Valid Number .
.
.
72
.
.
3.10 Integer to Roman . .
.
3.11 Roman to Integer
. .
.
.
73
.
. 74
.
.
.
.
3.12 Count and Say .
.
.
.
.
.
.
3.13 Anagrams . .
.
75
.
3.14 Simplify Path .
.
.
.
.
. 76
77
.
.
3.15 Length of Last Word . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
第 4 章 栈和队列
4.1 栈 . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
theses .
.
.
4.1.1 Valid Parentheses .
.
4.1.2 Longest Valid Paren-
.
4.1.3 Largest Rectangle in
.
4.1.4 Evaluate Reverse Pol-
.
.
ish Notation . .
.
Histogram . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4.2 队列 . .
第 5 章 树
5.1 二叉树的遍历 .
.
.
.
.
.
.
.
.
.
Traversal
. .
5.1.2 Binary Tree
. .
.
5.1.1 Binary Tree Preorder
.
.
Inorder
.
.
5.1.3 Binary Tree Postorder
.
5.1.4 Binary Tree Level Or-
.
der Traversal
Traversal
Traversal
. .
. .
.
.
.
.
.
.
.
.
.
79
79
.
. 79
. 80
.
82
.
84
. 85
86
. 86
.
.
.
.
86
88
90
93
iii
94
96
.
.
.
.
der Traversal II .
5.1.5 Binary Tree Level Or-
.
5.1.6 Binary Tree Zigzag
Level Order Traversal
5.1.7 Recover Binary Search
.
.
.
98
.
.
99
5.1.8
5.1.9
. 101
5.1.10 Balanced Binary Tree . . 102
5.1.11 Flatten Binary Tree to
.
5.1.12 Populating Next Right
.
Tree .
.
Same Tree
.
Symmetric Tree .
Linked List
. 103
.
.
. .
. .
.
.
.
.
.
.
.
.
.
.
.
5.2 二叉树的构建 . .
Pointers in Each Node II 105
. 107
.
.
.
5.3 二叉查找树 .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Trees
.
5.2.1 Construct Binary Tree
from Preorder and In-
order Traversal
.
5.2.2 Construct Binary Tree
from Inorder and Pos-
.
torder Traversal .
.
.
5.3.1 Unique Binary Search
.
5.3.2 Unique Binary Search
.
5.3.3 Validate Binary Search
.
5.3.4 Convert Sorted Array to
Binary Search Tree . .
5.3.5 Convert Sorted List to
Binary Search Tree . .
.
5.4.1 Minimum Depth of Bi-
.
nary Tree . .
Trees II . .
Tree .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. 107
. 108
. 109
. 109
. 110
. 111
. 112
. 113
. 115
. 115
5.4 二叉树的递归 . .
iv
.
.
.
.
.
.
.
.
.
. 116
. 117
. 118
.
nary Tree . .
Path Sum . .
.
Path Sum II . .
5.4.2 Maximum Depth of Bi-
.
.
5.4.3
5.4.4
.
5.4.5 Binary Tree Maximum
Path Sum . .
.
Populating Next Right
Pointers in Each Node . 120
Sum Root to Leaf Num-
bers . .
.
. 119
. 122
5.4.6
5.4.7
.
.
.
.
.
.
.
.
.
.
.
第 6 章 排序
6.1 Merge Sorted Array . .
.
6.2 Merge Two Sorted Lists .
6.3 Merge k Sorted Lists
. .
.
.
Insertion Sort List . .
6.4
6.5 Sort List . .
.
.
.
6.6 First Missing Positive . .
.
6.7 Sort Colors
. .
.
.
.
.
.
.
.
.
第 7 章 查找
7.1 Search for a Range . .
.
7.2 Search Insert Position . .
7.3 Search a 2D Matrix . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
第 8 章 暴力枚举法
. .
8.1 Subsets
8.2 Subsets II
.
. .
.
8.1.1 递归 .
8.1.2 迭代 .
.
8.2.1 递归 .
8.2.2 迭代 .
.
.
.
.
.
.
.
.
next_permutation() .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
8.3.1
8.3 Permutations
123
. 123
. 124
. 124
. 125
. 126
. 127
. 128
131
. 131
. 132
. 133
135
. 135
. 135
. 137
. 138
. 138
. 141
. 142
. 142
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. .
.
.
. .
tation()
8.3.3 递归 .
8.4 Permutations II
8.3.2 重新实现 next_permu-
.
.
.
8.4.1
next_permutation() . .
8.4.2 重新实现 next_permu-
.
.
.
.
.
8.6 Letter Combinations of a Phone
.
.
.
tation()
8.4.3 递归 .
8.5 Combinations .
8.5.1 递归 .
8.5.2 迭代 .
Number
.
8.6.1 递归 .
8.6.2 迭代 .
. .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
第 9 章 广度优先搜索
.
.
.
.
.
. .
9.1 Word Ladder
.
9.2 Word Ladder II
.
9.3 Surrounded Regions . .
.
9.4 小结 .
.
.
9.4.1 适用场景 . .
9.4.2 思考的步骤 .
9.4.3 代码模板 . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
第 10 章 深度优先搜索
.
.
.
.
10.1 Palindrome Partitioning .
.
10.2 Unique Paths
.
.
.
.
.
.
.
.
.
10.2.1 深搜 .
.
10.2.2 备忘录法 . .
10.2.3 动规 .
.
10.2.4 数学公式 . .
.
10.3.1 备忘录法 . .
10.3.2 动规 .
.
10.3 Unique Paths II
.
.
.
.
.
.
.
.
. .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
目录
. 142
. 143
. 144
. 144
. 144
. 144
. 146
. 146
. 147
. 147
. 148
. 149
150
. 150
. 152
. 154
. 156
. 156
. 156
. 157
162
. 162
. 165
. 165
. 165
. 166
. 167
. 168
. 168
. 169
目录
.
.
.
.
.
.
.
.
.
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 章 分治法
11.1 Pow(x,n) . .
11.2 Sqrt(x) .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
185
. 185
. 186
第 12 章 贪心法
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
187
. 187
12.1 Jump Game . .
. 188
12.2 Jump Game II .
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-
.
.
.
12.6 Container With Most Water .
peating Characters
. 192
. 193
. .
.
.
第 13 章 动态规划
.
13.1 Triangle . .
.
13.2 Maximum Subarray . .
.
13.3 Palindrome Partitioning II
.
.
.
.
.
195
. 195
. 196
. 198
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
III
13.4 Maximal Rectangle . .
.
13.5 Best Time to Buy and Sell Stock
.
.
.
.
.
.
.
.
.
.
.
.
13.6 Interleaving String . .
.
13.7 Scramble String . .
.
.
13.8 Minimum Path Sum . .
.
.
13.9 Edit Distance .
13.10 Decode Ways
.
.
13.11 Distinct Subsequences .
.
13.12 Word Break .
13.13 Word Break II
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. .
.
.
. .
.
.
.
.
.
.
.
第 14 章 图
14.1 Clone Graph .
.
.
.
.
.
.
.
.
.
v
. 199
. 200
. 201
. 203
. 208
. 210
. 212
. 213
. 214
. 216
218
. 218
第 15 章 细节实现题
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
221
. 221
15.1 Reverse Integer . .
.
. 222
15.2 Palindrome Number . .
. 223
.
15.3 Insert Interval
.
15.4 Merge Intervals . .
. 224
.
15.5 Minimum Window Substring . . 225
.
15.6 Multiply Strings . .
. 227
15.7 Substring with Concatenation
.
.
.
.
.
.
.
.
.
.
.
.
15.8 Pascal’s Triangle . .
. .
15.9 Pascal’s Triangle II
.
.
15.10 Spiral Matrix .
.
.
15.11 Spiral Matrix II . .
.
.
15.12 ZigZag Conversion .
15.13 Divide Two Integers .
15.14 Text Justification . .
.
15.15 Max Points on a Line
. 230
. 231
. 232
. 233
. 234
. 236
. 237
. 238
. 240
of All Words .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
vi
目录
第 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 > ary(row_num, vector(col_num, 0));
使用 reserve 来避免不必要的重新分配
1
第 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(int A[], int n) {
if (n == 0) return 0;
int index = 0;
for (int i = 1; i < n; i++) {
if (A[index] != A[i])
A[++index] = A[i];
}
return index + 1;
}
};
2
