Leetcode CPP

LeetCode

([email protected])
https://github.com/soulmachine/leetcode
2016-1-28

Creative Commons

3.0 Unported
http://creativecommons.org/licenses/by-nc-sa/3.0/
(cc by-nc-sa)
ACM
LeetCode Online Judge(http://leetcode.com/onlinejudge)
C++ 11
LeetCode Online Judge

:
OJ
.h
Shorter is better
.cpp
STL
malloc()/new
nullptr
C++
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/
Java
2.1
. . . . . . . . . . . . . . .
2.1.1
Remove
Duplicates
from Sorted Array . . .

2.1.2
Remove
Search
in
Search
in
35
2.1.22 Candy . . . . . . . . . .
36
2.1.23 Single Number . . . . .
37
2.1.24 Single Number II . . . .
38
. . . . . . . . . . . . .
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
Longest
Duplicates
from Sorted List . . . .

6
2.2.5
Median of Two Sorted

Arrays . . . . . . . . . .
2.1.6
2.1.21 Gas Station . . . . . . .
Rotated
Sorted Array II . . . . .
2.1.5
33
2.2
Rotated
Sorted Array . . . . . .
2.1.4
Duplicates
from Sorted Array II . .

2.1.3
2.1.20 Set Matrix Zeroes . . . .
Consecutive
Sequence . . . . . . . .
2.1.7
Two Sum . . . . . . . .
10
2.1.8
3Sum . . . . . . . . . . 12
2.1.9
3Sum Closest . . . . . .
13
Remove
43
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
2.1.10 4Sum . . . . . . . . . . 14
2.1.11 Remove Element . . . . 18
2.1.12 Next Permutation . . . . 19
2.1.13 Permutation Sequence . 21
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
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
3.1
Valid Palindrome . . . . . . . .
57
2.1.18 Climbing Stairs . . . . . 30
3.2
Implement strStr() . . . . . . . .
58
2.1.19 Gray Code . . . . . . .
3.3
String to Integer (atoi) . . . . .
60
31
ii
57
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
5.1.5
Binary Tree Level Order Traversal II . . . . .
5.1.6
Binary
Tree
Zigzag
Level Order Traversal .

5.1.7
94
96
Recover Binary Search

Tree . . . . . . . . . . .
98
99
3.10 Integer to Roman . . . . . . . .
72
5.1.8
Same Tree . . . . . . .
3.11 Roman to Integer . . . . . . . .
73
5.1.9
Symmetric Tree . . . . . 100
3.12 Count and Say . . . . . . . . . . 74
5.1.10 Balanced Binary Tree . . 102
3.13 Anagrams . . . . . . . . . . . .
5.1.11 Flatten Binary Tree to
75
Linked List . . . . . . . 103
3.14 Simplify Path . . . . . . . . . . 76

3.15 Length of Last Word . . . . . .
5.1.12 Populating Next Right
77
Pointers in Each Node II 105

4
4.1
79
. . . . . . . . . . . . . . . .
5.2
. . . . . . . . . 106
5.2.1
79
Construct Binary Tree
4.1.1
Valid Parentheses . . . . 79
from Preorder and In-
4.1.2
Longest Valid Paren-
order Traversal . . . . . 106

5.2.2
theses . . . . . . . . . . 80
4.1.3
4.1.4
torder Traversal . . . . . 107
82
5.3
Evaluate Reverse Polish Notation . . . . . . .
4.2
from Inorder and Pos-
Largest Rectangle in
Histogram . . . . . . . .
. . . . . . . . . . . 108
5.3.1
84
5.3.2
86
5.1
5.1.2
5.3.4
Convert Sorted Array to
Tree . . . . . . . . . . . 111
86
Binary Search Tree . . . 112

88
5.3.5
Binary Tree Postorder

Traversal . . . . . . . .
5.1.4
Validate Binary Search
Binary Tree Inorder

Traversal . . . . . . . .
5.1.3
5.3.3
Binary Tree Preorder

Traversal . . . . . . . .
Convert Sorted List to

Binary Search Tree . . . 113
90
Binary Tree Level Order Traversal . . . . . .
Unique Binary Search

Trees II . . . . . . . . . 110
. . . . . . . . . 86
5.1.1
Unique Binary Search

Trees . . . . . . . . . . 108
. . . . . . . . . . . . . . . 85
Construct Binary Tree
5.4
. . . . . . . . . 114
5.4.1
92
Minimum Depth of Binary Tree . . . . . . . . 115
iv
5.4.2
Maximum Depth of Bi-
8.3.2
next_permu-
nary Tree . . . . . . . . 116
tation() . . . . . . . . . 142
8.3.3
5.4.3
Path Sum . . . . . . . . 117
5.4.4
Path Sum II . . . . . . . 118
5.4.5
Binary Tree Maximum
8.4.1
Path Sum . . . . . . . . 119
8.4.2
5.4.6
8.4
next_permutation() . . . 144
next_permutation() . . . . . . . . . 144
8.4.3
8.5
Sum Root to Leaf Numbers . . . . . . . . . . . 121
Permutations II . . . . . . . . . 144
Populating Next Right

Pointers in Each Node . 120
5.4.7
. . . . . . . . . . 143
123
8.6
. . . . . . . . . . 144
Combinations . . . . . . . . . . 146
8.5.1
. . . . . . . . . . 146
8.5.2
. . . . . . . . . . 147
Letter Combinations of a Phone
6.1
Merge Sorted Array . . . . . . . 123
Number . . . . . . . . . . . . . 147
6.2
Merge Two Sorted Lists . . . . . 124
8.6.1
. . . . . . . . . . 148
6.3
Merge k Sorted Lists . . . . . . 124
8.6.2
. . . . . . . . . . 149
6.4
Insertion Sort List . . . . . . . . 125
6.5
Sort List . . . . . . . . . . . . . 126
6.6
First Missing Positive . . . . . . 127
6.7
Sort Colors . . . . . . . . . . . 128
131
7.1
Search for a Range . . . . . . . 131
7.2
Search Insert Position . . . . . . 132
7.3
Search a 2D Matrix . . . . . . . 133
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
8
8.1
8.2
8.3
135
Subsets . . . . . . . . . . . . . 135
173
10.1 Palindrome Partitioning . . . . . 173

10.2 Unique Paths . . . . . . . . . . 176
8.1.1
. . . . . . . . . . 135
10.2.1
8.1.2
. . . . . . . . . . 137
10.2.2
. . . . . . . . 176
Subsets II . . . . . . . . . . . . 138
10.2.3
. . . . . . . . . . 177
8.2.1
. . . . . . . . . . 138
10.2.4
. . . . . . . . 178
8.2.2
. . . . . . . . . . 141
. . . . . . . . . . 176
10.3 Unique Paths II . . . . . . . . . 179
Permutations . . . . . . . . . . 142
10.3.1
. . . . . . . . 179
8.3.1
10.3.2
. . . . . . . . . . 180
next_permutation() . . . 142
v
10.4 N-Queens . . . . . . . . . . . . 181
13.4 Maximal Rectangle . . . . . . . 213
10.5 N-Queens II . . . . . . . . . . . 184
13.5 Best Time to Buy and Sell Stock
10.6 Restore IP Addresses . . . . . . 186
III . . . . . . . . . . . . . . . . 214
10.7 Combination Sum . . . . . . . . 188
13.6 Interleaving String . . . . . . . 215
10.8 Combination Sum II . . . . . . 189
13.7 Scramble String . . . . . . . . . 217
10.9 Generate Parentheses . . . . . . 190
13.8 Minimum Path Sum . . . . . . . 222
10.10 Sudoku Solver . . . . . . . . . 192
13.9 Edit Distance . . . . . . . . . . 224
10.11 Word Search . . . . . . . . . . 193
13.10 Decode Ways . . . . . . . . . 226
10.12
. . . . . . . . . . . . . . 195
13.11 Distinct Subsequences . . . . . 227
10.12.1
. . . . . . . 195
13.12 Word Break . . . . . . . . . . 228
10.12.2
. . . . . . 195
13.13 Word Break II . . . . . . . . . 230
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
14
232
14.1 Clone Graph . . . . . . . . . . . 232

15
235
15.1 Reverse Integer . . . . . . . . . 235

15.2 Palindrome Number . . . . . . . 236
15.3 Insert Interval . . . . . . . . . . 237
201
15.4 Merge Intervals . . . . . . . . . 238
12.1 Jump Game . . . . . . . . . . . 201
15.5 Minimum Window Substring . . 239
12.2 Jump Game II . . . . . . . . . . 202
15.6 Multiply Strings . . . . . . . . . 241
12.3 Best Time to Buy and Sell Stock 204
15.7 Substring with Concatenation
12
12.4 Best Time to Buy and Sell Stock II205
of All Words . . . . . . . . . . . 244

15.8 Pascals Triangle . . . . . . . . 245
12.5 Longest Substring Without Repeating Characters . . . . . . . 206
15.9 Pascals Triangle II . . . . . . . 246
12.6 Container With Most Water . . . 207
15.10 Spiral Matrix . . . . . . . . . . 247

15.11 Spiral Matrix II . . . . . . . . . 248
13
209
15.12 ZigZag Conversion . . . . . . 250
13.1 Triangle . . . . . . . . . . . . . 209
15.13 Divide Two Integers . . . . . . 251
13.2 Maximum Subarray . . . . . . . 210
15.14 Text Justification . . . . . . . . 253
13.3 Palindrome Partitioning II . . . 212
15.15 Max Points on a Line . . . . . 255
vi
a==b
fabs(a-b)
1e-9
x % 2 != 0
x % 2 == 1
char
char
unsigned int
unsigned char
STL
vector
C++
Effective STL
string
vector
new
delete
delete
new
int** ary = new int*[row_num];
for(int i = 0; i < row_num; ++i)
ary[i] = new int[col_num];
vector
vector<vector<int> > ary(row_num, vector<int>(col_num, 0));
reserve
BUG
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(vector<int>& nums) {
if (nums.empty()) return 0;
int index = 0;
for (int i = 1; i < nums.size(); i++) {
if (nums[index] != nums[i])
nums[++index] = nums[i];
}
return index + 1;
}
};
2.1
2
//
STL
O(n)
O(1)
class Solution {
public:
return distance(nums.begin(), unique(nums.begin(), nums.end()));
}
};

//
STL
O(n)
O(1)
class Solution {
public:
return distance(nums.begin(), removeDuplicates(nums.begin(), nums.end(), nums.begin())
}
template<typename InIt, typename OutIt>
OutIt removeDuplicates(InIt first, InIt last, OutIt output) {
while (first != last) {
*output++ = *first;
first = upper_bound(first, last, *first);
}
return output;
}
};
Remove Duplicates from Sorted Array II
2.1.2
2.1.2 Remove Duplicates from Sorted Array II
Follow up for Remove Duplicates: What if duplicates are allowed at most twice?
For example, Given sorted array A = [1,1,1,2,2,3],
Your function should return length = 5, and A is now [1,1,2,2,3]
hashmap
1
// LeetCode, Remove Duplicates from Sorted Array II
//
O(n)
O(1)
// @author hex108 (https://github.com/hex108)
class Solution {
public:
if (nums.size() <= 2) return nums.size();
int index = 2;
for (int i = 2; i < nums.size(); i++){
if (nums[i] != nums[index - 2])
nums[index++] = nums[i];
}
return index;
}
};
2
occur < 2
< 3
occur
// LeetCode, Remove Duplicates from Sorted Array II

// @author
(http://weibo.com/u/1666779725)
//
O(n)
O(1)
class Solution {
public:
const int n = nums.size();
int index = 0;
for (int i = 0; i < n; ++i) {
if (i > 0 && i < n - 1 && nums[i] == nums[i - 1] && nums[i] == nums[i + 1])
continue;
}
return index;
}
};
Remove Duplicates from Sorted Array
2.1.1
2.1
2.1.3 Search in Rotated Sorted Array
Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
// LeetCode, Search in Rotated Sorted Array

//
O(log n)
O(1)
class Solution {
public:
int search(const vector<int>& nums, int target)
int first = 0, last = nums.size();
const int mid = first + (last - first)
if (nums[mid] == target)
return mid;
if (nums[first] <= nums[mid]) {
if (nums[first] <= target && target
last = mid;
else
first = mid + 1;
} else {
if (nums[mid] < target && target <=
first = mid + 1;
else
last = mid;
}
}
return -1;
}
};
Search in Rotated Sorted Array II
2.1.4
{
/ 2;
< nums[mid])
nums[last-1])
2.1.4 Search in Rotated Sorted Array II
Follow up for Search in Rotated Sorted Array: What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
A[m]>=A[l],
[l,m]
[1,3,1,1,1]
A[m]>=A[l]
A[m]>A[l]
A[m]==A[l]
[l,m]
l++
// LeetCode, Search in Rotated Sorted Array II

//
O(n)
O(1)
class Solution {
public:
bool search(const vector<int>& nums, int target) {
int first = 0, last = nums.size();
const int mid = first + (last - first) / 2;
if (nums[mid] == target)
return true;
if (nums[first] < nums[mid]) {
if (nums[first] <= target && target < nums[mid])
last = mid;
else
first = mid + 1;
} else if (nums[first] > nums[mid]) {
if (nums[mid] < target && target <= nums[last-1])
first = mid + 1;
else
last = mid;
} else
//skip duplicate one
first++;
}
return false;
}
};
2.1
Search in Rotated Sorted Array
2.1.3
2.1.5 Median of Two Sorted Arrays
There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted
arrays. The overall run time complexity should be O(log(m + n)).
O(m + n)
merge
k
pA
m
merge sort
B
pB++
O(1)
pB
pA++
A
m++
m++
O(k)
m+n
O(m + n)
k
k
A
A
k/2
k/2
B[k/2-1]
A[k/2-1]
k/2
k
A[k/2-1] == B[k/2-1]
A[k/2-1] > B[k/2-1]
A[k/2-1] < B[k/2-1]
A[k/2-1] < B[k/2-1]
A
B
A[k/2-1]
AB
top k
k
A[k/2-1] > B[k/2-1]
k/2
k/2
A[k/2-1] == B[k/2-1]
A[0]
AB
A[k/2-1]
A[k/2-1]
A
B
B[k-1]
A[k-1]
k=1
min(A[0], B[0])
A[k/2-1] == B[k/2-1]
A[k/2-1]
B[k/2-1]
B[k/2-1]
// LeetCode, Median of Two Sorted Arrays

//
O(log(m+n))
O(log(m+n))
class Solution {
public:
double findMedianSortedArrays(const vector<int>& A, const vector<int>& B) {
const int m = A.size();
const int n = B.size();
int total = m + n;
if (total & 0x1)
return find_kth(A.begin(), m, B.begin(), n, total / 2 + 1);
else
return (find_kth(A.begin(), m, B.begin(), n, total / 2)
+ find_kth(A.begin(), m, B.begin(), n, total / 2 + 1)) / 2.0;
}
private:
static int find_kth(std::vector<int>::const_iterator A, int m,
std::vector<int>::const_iterator B, int n, int k) {
//always assume that m is equal or smaller than n
if (m > n) return find_kth(B, n, A, m, k);
if (m == 0) return *(B + k - 1);
if (k == 1) return min(*A, *B);
//divide k into two parts
int ia = min(k / 2, m), ib = k - ia;
if (*(A + ia - 1) < *(B + ib - 1))
return find_kth(A + ia, m - ia, B, n, k - ia);
else if (*(A + ia - 1) > *(B + ib - 1))
return find_kth(A, m, B + ib, n - ib, k - ib);
else
return A[ia - 1];
}
};
2.1.6 Longest Consecutive Sequence
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example, Given [100, 4, 200, 1, 3, 2], The longest consecutive elements sequence is [1,
2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.
2.1
O(n log n)
O(n)
O(n)
unordered_map<int, bool> used
// Leet Code, Longest Consecutive Sequence

//
O(n)
O(n)
class Solution {
public:
int longestConsecutive(const vector<int> &nums) {
unordered_map<int, bool> used;
for (auto i : nums) used[i] = false;
int longest = 0;
for (auto i : nums) {
if (used[i]) continue;
int length = 1;
used[i] = true;
for (int j = i + 1; used.find(j) != used.end(); ++j) {
used[j] = true;
++length;
}
for (int j = i - 1; used.find(j) != used.end(); --j) {
used[j] = true;
++length;
}
longest = max(longest, length);
}
return longest;
}
};
2
,
.
map<int, int> map
,
.
union,find
.
,
unordered_-
http://discuss.leetcode.com/questions/1070/
10
longest-consecutive-sequence
// Leet Code, Longest Consecutive Sequence

//
O(n)
O(n)
// Author: @advancedxy
class Solution {
public:
int longestConsecutive(vector<int> &nums) {
unordered_map<int, int> map;
int size = nums.size();
int l = 1;
for (int i = 0; i < size; i++) {
if (map.find(nums[i]) != map.end()) continue;
map[nums[i]] = 1;
if (map.find(nums[i] - 1) != map.end()) {
l = max(l, mergeCluster(map, nums[i] - 1, nums[i]));
}
if (map.find(nums[i] + 1) != map.end()) {
l = max(l, mergeCluster(map, nums[i], nums[i] + 1));
}
}
return size == 0 ? 0 : l;
}
private:
int mergeCluster(unordered_map<int, int> &map, int left, int right) {
int upper = right + map[right] - 1;
int lower = left - map[left] + 1;
int length = upper - lower + 1;
map[upper] = length;
map[lower] = length;
return length;
}
};
2.1.7 Two Sum
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where
index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not
zero-based.
11
2.1
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
O(n2 )
1
2
O(n).
hash
O(n log n)
O(n)
O(n log n)
//LeetCode, Two Sum

//
2 hash
//
O(n)
O(n)
class Solution {
public:
vector<int> twoSum(vector<int> &nums, int target) {
unordered_map<int, int> mapping;
vector<int> result;
mapping[nums[i]] = i;
}
const int gap = target - nums[i];
if (mapping.find(gap) != mapping.end() && mapping[gap] > i) {
result.push_back(i + 1);
result.push_back(mapping[gap] + 1);
break;
}
}
return result;
}
};
3Sum,
2.1.8
3Sum Closest,
4Sum,
2.1.10
2.1.9
12
2.1.8 3Sum
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique
triplets in the array which gives the sum of zero.
Note:
Elements in a triplet (a, b, c) must be in non-descending order. (ie, a b c)
The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4}.
A solution set is:
(-1, 0, 1)
(-1, -1, 2)
O(n2 )
k-sum
O(max{n log n, n
k1
k2
})
// LeetCode, 3Sum
//
O(n^2)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
if (nums.size() < 3) return result;
sort(nums.begin(), nums.end());
const int target = 0;
auto last = nums.end();
for (auto i = nums.begin(); i < last-2; ++i) {
auto j = i+1;
if (i > nums.begin() && *i == *(i-1)) continue;
auto k = last-1;
while (j < k) {
if (*i + *j + *k < target) {
++j;
while(*j == *(j - 1) && j < k) ++j;
} else if (*i + *j + *k > target) {
--k;
while(*k == *(k + 1) && j < k) --k;
} else {
result.push_back({ *i, *j, *k });
++j;
O(1)
13
2.1
--k;
while(*j == *(j - 1) && *k == *(k + 1) && j < k) ++j;
}
}
}
return result;
}
};
Two sum,
2.1.7
3Sum Closest,
4Sum,
2.1.9
2.1.10
2.1.9 3Sum Closest
Given an array S of n integers, find three integers in S such that the sum is closest to a given number,
target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
O(n2 )
// LeetCode, 3Sum Closest

//
O(n^2)
O(1)
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int result = 0;
int min_gap = INT_MAX;
for (auto a = nums.begin(); a != prev(nums.end(), 2); ++a) {
auto b = next(a);
auto c = prev(nums.end());
while (b < c) {
const int sum = *a + *b + *c;
const int gap = abs(sum - target);
14
if (gap < min_gap) {

result = sum;
min_gap = gap;
}
if (sum < target) ++b;
else
--c;
}
}
return result;
}
};
Two sum,
2.1.7
3Sum,
2.1.8
4Sum,
2.1.10
2.1.10 4Sum
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target?
Find all unique quadruplets in the array which gives the sum of target.
Note:
Elements in a quadruplet (a, b, c, d) must be in non-descending order. (ie, a b c d)
The solution set must not contain duplicate quadruplets.
For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
A solution set is:
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)
O(n3 )
hashmap
O(n3 )
3Sum
15
2.1
// LeetCode, 4Sum
//
O(n^3)
O(1)
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
for (auto a = nums.begin(); a < prev(last, 3); ++a) {
for (auto b = next(a); b < prev(last, 2); ++b) {
auto c = next(b);
auto d = prev(last);
while (c < d) {
if (*a + *b + *c + *d < target) {
++c;
} else if (*a + *b + *c + *d > target) {
--d;
} else {
result.push_back({ *a, *b, *c, *d });
++c;
--d;
}
}
}
}
sort(result.begin(), result.end());
result.erase(unique(result.begin(), result.end()), result.end());
return result;
}
};
map
// LeetCode, 4Sum
//
hashmap
//
O(n^2)
O(n^4)
O(n^2)
class Solution {
public:
vector<vector<int> > fourSum(vector<int> &nums, int target) {
unordered_map<int, vector<pair<int, int> > > cache;
for (size_t a = 0; a < nums.size(); ++a) {
for (size_t b = a + 1; b < nums.size(); ++b) {
cache[nums[a] + nums[b]].push_back(pair<int, int>(a, b));
}
}
16
for (int c = 0; c < nums.size(); ++c) {

for (size_t d = c + 1; d < nums.size(); ++d) {
const int key = target - nums[c] - nums[d];
if (cache.find(key) == cache.end()) continue;
const auto& vec = cache[key];
for (size_t k = 0; k < vec.size(); ++k) {
if (c <= vec[k].second)
continue; //
result.push_back( { nums[vec[k].first],
nums[vec[k].second], nums[c], nums[d] });
}
}
}
return result;
}
};
multimap
// LeetCode, 4Sum
//
hashmap
//
O(n^2)
O(n^2)
// @author
(http://weibo.com/luangong)
class Solution {
public:
unordered_multimap<int, pair<int, int>> cache;
for (int i = 0; i + 1 < nums.size(); ++i)
for (int j = i + 1; j < nums.size(); ++j)
cache.insert(make_pair(nums[i] + nums[j], make_pair(i, j)));
for (auto i = cache.begin(); i != cache.end(); ++i) {
int x = target - i->first;
auto range = cache.equal_range(x);
for (auto j = range.first; j != range.second; ++j) {
auto a = i->second.first;
auto b = i->second.second;
auto c = j->second.first;
auto d = j->second.second;
if (a != c && a != d && b != c && b != d) {
vector<int> vec = { nums[a], nums[b], nums[c], nums[d] };
sort(vec.begin(), vec.end());
result.push_back(vec);
}
17
2.1
}
}
return result;
}
};
4
// LeetCode, 4Sum
//
O(n^3logn)
O(1)
//
1
class Solution {
public:
for (auto a = nums.begin(); a < prev(last, 3);
a = upper_bound(a, prev(last, 3), *a)) {
for (auto b = next(a); b < prev(last, 2);
b = upper_bound(b, prev(last, 2), *b)) {
auto c = next(b);
auto d = prev(last);
while (c < d) {
if (*a + *b + *c + *d < target) {
c = upper_bound(c, d, *c);
} else if (*a + *b + *c + *d > target) {
d = prev(lower_bound(c, d, *d));
} else {
result.push_back({ *a, *b, *c, *d });
c = upper_bound(c, d, *c);
d = prev(lower_bound(c, d, *d));
}
}
}
}
return result;
}
};
Two sum,
3Sum,
2.1.7
2.1.8
3Sum Closest,
2.1.9
18
2.1.11 Remove Element
Given an array and a value, remove all instances of that value in place and return the new length.
The order of elements can be changed. It doesnt matter what you leave beyond the new length.
1
// LeetCode, Remove Element
//
O(n)
O(1)
class Solution {
public:
int removeElement(vector<int>& nums, int target) {
int index = 0;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] != target) {
}
}
return index;
}
};
2
// LeetCode, Remove Element
//
remove()
O(n)
O(1)
class Solution {
public:
int removeElement(vector<int>& nums, int target) {
return distance(nums.begin(), remove(nums.begin(), nums.end(), target));
}
};
19
2.1
2.1.12 Next Permutation
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the
right-hand column.
1,2,3 1,3,2
3,2,1 1,2,3
1,1,5 1,5,1
2-1
http://sherlei.blogspot.com/2012/12/leetcode-next-permutation.html
2-1
20
// LeetCode, Next Permutation

//
O(n)
O(1)
class Solution {
public:
void nextPermutation(vector<int> &nums) {
next_permutation(nums.begin(), nums.end());
}
template<typename BidiIt>
bool next_permutation(BidiIt first, BidiIt last) {
// Get a reversed range to simplify reversed traversal.
const auto rfirst = reverse_iterator<BidiIt>(last);
const auto rlast = reverse_iterator<BidiIt>(first);
// Begin from the second last element to the first element.
auto pivot = next(rfirst);
// Find `pivot`, which is the first element that is no less than its
// successor. `Prev` is used since `pivort` is a `reversed_iterator`.
while (pivot != rlast && *pivot >= *prev(pivot))
++pivot;
// No such elemenet found, current sequence is already the largest
// permutation, then rearrange to the first permutation and return false.
if (pivot == rlast) {
reverse(rfirst, rlast);
return false;
}
// Scan from right to left, find the first element that is greater than
// `pivot`.
auto change = find_if(rfirst, pivot, bind1st(less<int>(), *pivot));
swap(*change, *pivot);
reverse(rfirst, pivot);
return true;
}
};
Permutation Sequence,
Permutations,
Permutations II,
Combinations,
8.3
8.4
8.5
2.1.13
21
2.1
2.1.13 Permutation Sequence
The set [1,2,3,
,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3):
"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
k1
next_permutation()
k
n
a1
k
a2 , a3 , ..., an ,
a1 , a2 , a3 , ..., an
n1
a1 = k/(n 1)!
a2 , a3 , ..., an
k2
k%(n 1)!
a2
k2 /(n 2)!
kn1
kn2 %2!
an1
kn1 /1!
an
next_permutation()
// LeetCode, Permutation Sequence
//
next_permutation() TLE
class Solution {
public:
string getPermutation(int n, int k) {
string s(n, '0');
for (int i = 0; i < n; ++i)
n1
a1
(n 1)!
22
s[i] += i+1;
for (int i = 0; i < k-1; ++i)
next_permutation(s.begin(), s.end());
return s;
}
bool next_permutation(BidiIt first, BidiIt last) {
//
Next Permutation
}
};
// LeetCode, Permutation Sequence

//
O(n)
O(1)
class Solution {
public:
string getPermutation(int n, int k) {
string s(n, '0');
string result;
for (int i = 0; i < n; ++i)
s[i] += i + 1;
return kth_permutation(s, k);
}
private:
int factorial(int n) {
int result = 1;
for (int i = 1; i <= n; ++i)
result *= i;
return result;
}
// seq
template<typename Sequence>
Sequence kth_permutation(const Sequence &seq, int k) {
const int n = seq.size();
Sequence S(seq);
Sequence result;
int base = factorial(n - 1);
--k; //
0
for (int i = n - 1; i > 0; k %= base, base /= i, --i) {
auto a = next(S.begin(), k / base);
result.push_back(*a);
S.erase(a);
}
result.push_back(S[0]); //
return result;
}
23
2.1
};
Next Permutation,
Permutations,
2.1.12
8.3
Permutations II,
Combinations,
8.4
8.5
2.1.14 Valid Sudoku
Determine
if
Sudoku
is
valid,
according
to:
Sudoku
Puzzles
The
http://sudoku.com.au/TheRules.aspx .
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
2-2 A partially filled sudoku which is valid
// LeetCode, Valid Sudoku

//
O(n^2)
O(1)
class Solution {
public:
bool isValidSudoku(const vector<vector<char>>& board) {
bool used[9];
Rules
24
for (int i = 0; i < 9; ++i) {

fill(used, used + 9, false);
for (int j = 0; j < 9; ++j) //
if (!check(board[i][j], used))
return false;
for (int j = 0; j < 9; ++j) //
if (!check(board[j][i], used))
return false;
}
for (int r = 0; r < 3; ++r) //
9
for (int c = 0; c < 3; ++c) {
for (int i = r * 3; i < r * 3 + 3; ++i)
for (int j = c * 3; j < c * 3 + 3; ++j)
if (!check(board[i][j], used))
return false;
}
return true;
}
bool check(char ch, bool used[9]) {
if (ch == '.') return true;
if (used[ch - '1']) return false;
return used[ch - '1'] = true;
}
};
Sudoku Solver,
10.10
2.1.15 Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute
how much water it is able to trap after raining.
For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
25
2.1
2-3
Trapping Rain Water
min(max_left, max_right) - height

1.
2.
3.
1.
2.
3.
1
// LeetCode, Trapping Rain Water
//
1
O(n)
O(n)
class Solution {
public:
int trap(const vector<int>& A) {
const int n = A.size();
int *max_left = new int[n]();
int *max_right = new int[n]();
for (int i = 1; i < n; i++) {
max_left[i] = max(max_left[i - 1], A[i - 1]);
max_right[n - 1 - i] = max(max_right[n - i], A[n - i]);
}
int sum = 0;
for (int i = 0; i < n; i++) {
26
int height = min(max_left[i], max_right[i]);

if (height > A[i]) {
sum += height - A[i];
}
}
delete[] max_left;
delete[] max_right;
return sum;
}
};
2
//
2
O(n)
O(1)
class Solution {
public:
int max = 0; //
for (int i = 0; i < n; i++)
if (A[i] > A[max]) max = i;
int water = 0;
for (int i = 0, peak = 0; i < max; i++)
if (A[i] > peak) peak = A[i];
else water += peak - A[i];
for (int i = n - 1, top = 0; i > max; i--)
if (A[i] > top) top = A[i];
else water += top - A[i];
return water;
}
};

//
//
//
O(n)
O(n)
class Solution {
public:
stack<pair<int, int>> s;
int water = 0;
for (int i = 0; i < n; ++i) {
27
2.1
int height = 0;
while (!s.empty()) { //
int bar = s.top().first;
int pos = s.top().second;
// bar, height, A[i]
water += (min(bar, A[i]) - height) * (i - pos - 1);
height = bar;
if (A[i] < bar) //
break;
else
s.pop(); //
}
s.push(make_pair(A[i], i));
}
return water;
}
};
Container With Most Water,
12.6
Largest Rectangle in Histogram,
4.1.3
2.1.16 Rotate Image
You are given an n n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).
Follow up: Could you do this in-place?
2-4 Rotate Image
28
1
// LeetCode, Rotate Image
//
1
O(n^2)
O(1)
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
const int n = matrix.size();
for (int i = 0; i < n; ++i) //
for (int j = 0; j < n - i; ++j)
swap(matrix[i][j], matrix[n - 1 - j][n - 1 - i]);
for (int i = 0; i < n / 2; ++i) //
for (int j = 0; j < n; ++j)
swap(matrix[i][j], matrix[n - 1 - i][j]);
}
};
2
// LeetCode, Rotate Image
//
2
O(n^2)
O(1)
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
const int n = matrix.size();
for (int i = 0; i < n / 2; ++i) //
for (int j = 0; j < n; ++j)
swap(matrix[i][j], matrix[n - 1 - i][j]);
for (int i = 0; i < n; ++i) //
for (int j = i + 1; j < n; ++j)
swap(matrix[i][j], matrix[j][i]);
}
};
2.1.17 Plus One
Given a number represented as an array of digits, plus one to the number.
29
2.1
1
// LeetCode, Plus One
//
O(n)
O(1)
class Solution {
public:
vector<int> plusOne(vector<int> &digits) {
add(digits, 1);
return digits;
}
private:
// 0 <= digit <= 9
void add(vector<int> &digits, int digit) {
int c = digit; // carry,
for (auto it = digits.rbegin(); it != digits.rend(); ++it) {
*it += c;
c = *it / 10;
*it %= 10;
}
if (c > 0) digits.insert(digits.begin(), 1);
}
};
2
// LeetCode, Plus One
//
O(n)
O(1)
class Solution {
public:
vector<int> plusOne(vector<int> &digits) {
add(digits, 1);
return digits;
}
private:
// 0 <= digit <= 9
void add(vector<int> &digits, int digit) {
int c = digit; // carry,
for_each(digits.rbegin(), digits.rend(), [&c](int &d){
d += c;
c = d / 10;
d %= 10;
});
if (c > 0) digits.insert(digits.begin(), 1);
30
}
};
2.1.18 Climbing Stairs
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
f (n)
n1
n1
f (n) = f (n 1) + f (n 2)
1
// LeetCode, Climbing Stairs

//
O(n)
O(1)
class Solution {
public:
int climbStairs(int n) {
int prev = 0;
int cur = 1;
for(int i = 1; i <= n ; ++i){
int tmp = cur;
cur += prev;
prev = tmp;
}
return cur;
}
};
1
an =
5
[(
)n (
)n ]
1+ 5
1 5
2
2
31
2.1
// LeetCode, Climbing Stairs

//
O(1)
O(1)
class Solution {
public:
int climbStairs(int n) {
const double s = sqrt(5);
return floor((pow((1+s)/2, n+1) + pow((1-s)/2, n+1))/s + 0.5);
}
};
Decode Ways,
13.10
2.1.19 Gray Code
The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of
gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
00
01
11
10
0
1
3
2
Note:
For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.
http://en.wikipedia.org/wiki/Gray_code
(Gray Code)
g0 = b0 , gi = bi bi1
1001
1
0
4
0
3
1
3
2
0
1101
b0 = g0 , bi = gi bi1
2
1
32
1000
1
3
4
n (n/2)
0 2n 1
n1
2-5
2-5
The first few steps of the reflect-and-prefix method.
// LeetCode, Gray Code

//
O(2^n)
O(1)
class Solution {
public:
vector<int> grayCode(int n) {
vector<int> result;
const size_t size = 1 << n; // 2^n
result.reserve(size);
for (size_t i = 0; i < size; ++i)
result.push_back(binary_to_gray(i));
return result;
}
private:
static unsigned int binary_to_gray(unsigned int n) {
return n ^ (n >> 1);
}
};
1
1
n
1
1111
n
33
2.1
Reflect-and-prefix method
// LeetCode, Gray Code
// reflect-and-prefix method
//
O(2^n)
O(1)
class Solution {
public:
vector<int> grayCode(int n) {
vector<int> result;
result.reserve(1<<n);
result.push_back(0);
for (int i = 0; i < n; i++) {
const int highest_bit = 1 << i;
for (int j = result.size() - 1; j >= 0; j--) //
result.push_back(highest_bit | result[j]);
}
return result;
}
};
2.1.20 Set Matrix Zeroes
Given a m n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
Follow up: Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
O(m + n)
bool
1
// LeetCode, Set Matrix Zeroes
//
O(m*n)
O(m+n)
class Solution {
public:
void setZeroes(vector<vector<int> > &matrix) {
const size_t m = matrix.size();
const size_t n = matrix[0].size();
34
vector<bool> row(m, false); //

vector<bool> col(n, false); //
0
0
for (size_t i = 0; i < m; ++i) {

for (size_t j = 0; j < n; ++j) {
if (matrix[i][j] == 0) {
row[i] = col[j] = true;
}
}
}
for (size_t i = 0; i < m; ++i) {
if (row[i])
fill(&matrix[i][0], &matrix[i][0] + n, 0);
}
for (size_t j = 0; j < n; ++j) {
if (col[j]) {
for (size_t i = 0; i < m; ++i) {
matrix[i][j] = 0;
}
}
}
}
};
2
// LeetCode, Set Matrix Zeroes
//
O(m*n)
O(1)
class Solution {
public:
void setZeroes(vector<vector<int> > &matrix) {
const size_t n = matrix[0].size();
bool row_has_zero = false; //
bool col_has_zero = false; //
for (size_t i = 0; i < n; i++)
if (matrix[0][i] == 0) {
row_has_zero = true;
break;
}
for (size_t i = 0; i < m; i++)
if (matrix[i][0] == 0) {
col_has_zero = true;
break;
}
for (size_t j = 1; j < n; j++)
if (matrix[i][j] == 0) {
matrix[0][j] = 0;
0
0
35
2.1
matrix[i][0] = 0;
}
for (size_t j = 1; j < n; j++)
if (matrix[i][0] == 0 || matrix[0][j] == 0)
matrix[i][j] = 0;
if (row_has_zero)
for (size_t i = 0; i < n; i++)
matrix[0][i] = 0;
if (col_has_zero)
matrix[i][0] = 0;
}
};
2.1.21 Gas Station
There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next
station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas stations index if you can travel around the circuit once, otherwise return -1.
Note: The solution is guaranteed to be unique.
O(N 2 )
O(N )
sum
sum
total
-1
// LeetCode, Gas Station

//
O(n)
O(1)
class Solution {
public:
int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
int total = 0;
int j = -1;
for (int i = 0, sum = 0; i < gas.size(); ++i) {
sum += gas[i] - cost[i];
total += gas[i] - cost[i];
36
if (sum < 0) {
j = i;
sum = 0;
}
}
return total >= 0 ? j + 1 : -1;
}
};
2.1.22 Candy
There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?
// LeetCode, Candy
//
O(n)
O(n)
class Solution {
public:
int candy(vector<int> &ratings) {
const int n = ratings.size();
vector<int> increment(n);
//
for (int i = 1, inc = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1])
increment[i] = max(inc++, increment[i]);
else
inc = 1;
}
for (int i = n - 2, inc = 1; i >= 0; i--) {
if (ratings[i] > ratings[i + 1])
37
2.1
increment[i] = max(inc++, increment[i]);

else
inc = 1;
}
//
n
return accumulate(&increment[0], &increment[0]+n, n);
}
};
// LeetCode, Candy
//
O(n)
O(n)
// @author fancymouse (http://weibo.com/u/1928162822)
class Solution {
public:
int candy(const vector<int>& ratings) {
vector<int> f(ratings.size());
int sum = 0;
for (int i = 0; i < ratings.size(); ++i)
sum += solve(ratings, f, i);
return sum;
}
int solve(const vector<int>& ratings, vector<int>&
if (f[i] == 0) {
f[i] = 1;
if (i > 0 && ratings[i] > ratings[i - 1])
f[i] = max(f[i], solve(ratings, f, i if (i < ratings.size() - 1 && ratings[i] >
f[i] = max(f[i], solve(ratings, f, i +
}
return f[i];
}
};
f, int i) {
1) + 1);
ratings[i + 1])
1) + 1);
2.1.23 Single Number
Given an array of integers, every element appears twice except for one. Find that single one.
Note: Your algorithm should have a linear runtime complexity. Could you implement it without using
extra memory?
38
1
// LeetCode, Single Number
//
O(n)
O(1)
class Solution {
public:
int singleNumber(vector<int>& nums) {
int x = 0;
x ^= i;
}
return x;
}
};
2
// LeetCode, Single Number
//
O(n)
O(1)
class Solution {
public:
return accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());
}
};
Single Number II,
2.1.24
2.1.24 Single Number II
Given an array of integers, every element appears three times except for one. Find that single one.
Note: Your algorithm should have a linear runtime complexity. Could you implement it without using
extra memory?
Single Number
1
sizeof(int)
count[i]
count[sizeof(int)] count[i]
39
2.1
one
two
one
1
two
mod 3
mod 3
one
1
// LeetCode, Single Number II
//
1
O(n)
O(1)
class Solution {
public:
const int W = sizeof(int) * 8; //
int count[W]; // count[i]
i
fill_n(&count[0], W, 0);
for (int j = 0; j < W; j++) {
count[j] += (nums[i] >> j) & 1;
count[j] %= 3;
}
}
int result = 0;
for (int i = 0; i < W; i++) {
result += (count[i] << i);
}
return result;
}
};
2
// LeetCode, Single Number II
//
2
O(n)
O(1)
class Solution {
public:
int one = 0, two = 0, three = 0;
two |= (one & i);
one ^= i;
three = ~(one & two);
one &= three;
two &= three;
}
return one;
}
};
bit
1
40
Single Number,
2.1.23
2.2
//
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) { }
};
2.2.1 Add Two Numbers
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse
order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Add Binary
3.4
// LeetCode, Add Two Numbers

//
Add Binary
//
O(m+n)
O(1)
class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
ListNode dummy(-1); //
int carry = 0;
ListNode *prev = &dummy;
for (ListNode *pa = l1, *pb = l2;
pa != nullptr || pb != nullptr;
pa = pa == nullptr ? nullptr : pa->next,
pb = pb == nullptr ? nullptr : pb->next,
prev = prev->next) {
const int ai = pa == nullptr ? 0 : pa->val;
const int bi = pb == nullptr ? 0 : pb->val;
const int value = (ai + bi + carry) % 10;
carry = (ai + bi + carry) / 10;
41
2.2
prev->next = new ListNode(value); //

}
if (carry > 0)
prev->next = new ListNode(carry);
return dummy.next;
}
};
Add Binary,
3.4
2.2.2 Reverse Linked List II
Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example: Given 1->2->3->4->5->nullptr, m = 2 and n = 4,
return 1->4->3->2->5->nullptr.
Note: Given m, n satisfy the following condition: 1 m n length of list.
15
bug free
// LeetCode, Reverse Linked List II

//
O(n)
O(1)
class Solution {
public:
ListNode *reverseBetween(ListNode *head, int m, int n) {
ListNode dummy(-1);
dummy.next = head;
ListNode *prev = &dummy;
for (int i = 0; i < m-1; ++i)
prev = prev->next;
ListNode* const head2 = prev;
prev = head2->next;
ListNode *cur = prev->next;
for (int i = m; i < n; ++i) {
prev->next = cur->next;
cur->next = head2->next;
head2->next = cur; //
cur = prev->next;
}
42
return dummy.next;
}
};
2.2.3 Partition List
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater
than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example, Given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5.
// LeetCode, Partition List

//
O(n)
O(1)
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode left_dummy(-1); //
ListNode right_dummy(-1); //
auto left_cur = &left_dummy;
auto right_cur = &right_dummy;
for (ListNode *cur = head; cur; cur = cur->next) {
if (cur->val < x) {
left_cur->next = cur;
left_cur = cur;
} else {
right_cur->next = cur;
right_cur = cur;
}
}
left_cur->next = right_dummy.next;
right_cur->next = nullptr;
43
2.2
return left_dummy.next;
}
};
2.2.4 Remove Duplicates from Sorted List
Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
// LeetCode, Remove Duplicates from Sorted List

//
O(n)
O(1)
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {
if (!head) return head;
ListNode dummy(head->val + 1); //
dummy.next = head;
head
recur(&dummy, head);
return dummy.next;
}
private:
static void recur(ListNode *prev, ListNode *cur) {
if (cur == nullptr) return;
if (prev->val == cur->val) { //
delete cur;
recur(prev, prev->next);
} else {
recur(prev->next, cur->next);
}
}
};
head
44
// LeetCode, Remove Duplicates from Sorted List

//
O(n)
O(1)
class Solution {
public:
if (head == nullptr) return nullptr;
for (ListNode *prev = head, *cur = head->next; cur; cur = prev->next) {
if (prev->val == cur->val) {
delete cur;
} else {
prev = cur;
}
}
return head;
}
};
Remove Duplicates from Sorted List II
2.2.5
2.2.5 Remove Duplicates from Sorted List II
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers
from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.
// LeetCode, Remove Duplicates from Sorted List II

//
O(n)
O(1)
class Solution {
public:
if (!head || !head->next) return head;
45
2.2
ListNode *p = head->next;
if (head->val == p->val) {
while (p && head->val == p->val) {
ListNode *tmp = p;
p = p->next;
delete tmp;
}
delete head;
return deleteDuplicates(p);
} else {
head->next = deleteDuplicates(head->next);
return head;
}
}
};
// LeetCode, Remove Duplicates from Sorted List II

//
O(n)
O(1)
class Solution {
public:
if (head == nullptr) return head;
ListNode dummy(INT_MIN); //
dummy.next = head;
ListNode *prev = &dummy, *cur = head;
while (cur != nullptr) {
bool duplicated = false;
while (cur->next != nullptr && cur->val == cur->next->val) {
duplicated = true;
ListNode *temp = cur;
cur = cur->next;
delete temp;
}
if (duplicated) { //
ListNode *temp = cur;
cur = cur->next;
delete temp;
continue;
}
prev->next = cur;
prev = prev->next;
cur = cur->next;
}
prev->next = cur;
return dummy.next;
}
};
46
Remove Duplicates from Sorted List
2.2.4
2.2.6 Rotate List
Given a list, rotate the list to the right by k places, where k is non-negative.
For example: Given 1->2->3->4->5->nullptr and k = 2, return 4->5->1->2->3->nullptr.
len
len
len k
// LeetCode, Remove Rotate List

//
O(n)
O(1)
class Solution {
public:
ListNode *rotateRight(ListNode *head, int k) {
if (head == nullptr || k == 0) return head;
int len = 1;
ListNode* p = head;
while (p->next) { //
len++;
p = p->next;
}
k = len - k % len;
p->next = head; //
for(int step = 0; step < k; step++) {
p = p->next; //
}
head = p->next; //
p->next = nullptr; //
return head;
}
};
k% = len
next
47
2.2
2.2.7 Remove Nth Node From End of List
Given a linked list, remove the nth node from the end of list and return its head.
For example, Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.
p, q
// LeetCode, Remove Nth Node From End of List

//
O(n)
O(1)
class Solution {
public:
ListNode *removeNthFromEnd(ListNode *head, int n) {
ListNode dummy{-1, head};
ListNode *p = &dummy, *q = &dummy;
for (int i = 0; i < n; i++)
q = q->next;
// q
while(q->next) { //
p = p->next;
q = q->next;
}
ListNode *tmp = p->next;
p->next = p->next->next;
delete tmp;
return dummy.next;
}
};
2.2.8 Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head.
p->next
48
For example, Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes
itself can be changed.
// LeetCode, Swap Nodes in Pairs

//
O(n)
O(1)
class Solution {
public:
ListNode *swapPairs(ListNode *head) {
if (head == nullptr || head->next == nullptr) return head;
ListNode dummy(-1);
dummy.next = head;
for(ListNode *prev = &dummy, *cur = prev->next, *next = cur->next;
next;
prev = cur, cur = cur->next, next = cur ? cur->next: nullptr) {
prev->next = next;
cur->next = next->next;
next->next = cur;
}
return dummy.next;
}
};
// LeetCode, Swap Nodes in Pairs

//
O(n)
O(1)
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* p = head;
while (p && p->next) {
swap(p->val, p->next->val);
p = p->next->next;
}
return head;
}
};
Reverse Nodes in k-Group,
2.2.9
49
2.2
2.2.9 Reverse Nodes in k-Group
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example, Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
// LeetCode, Reverse Nodes in k-Group

//
O(n)
O(1)
class Solution {
public:
ListNode *reverseKGroup(ListNode *head, int k) {
if (head == nullptr || head->next == nullptr || k < 2)
return head;
ListNode *next_group = head;
for (int i = 0; i < k; ++i) {
if (next_group)
next_group = next_group->next;
else
return head;
}
// next_group is the head of next group
// new_next_group is the new head of next group after reversion
ListNode *new_next_group = reverseKGroup(next_group, k);
ListNode *prev = NULL, *cur = head;
while (cur != next_group) {
ListNode *next = cur->next;
cur->next = prev ? prev : new_next_group;
prev = cur;
cur = next;
}
return prev; // prev will be the new head of this group
}
};
50
// LeetCode, Reverse Nodes in k-Group

//
O(n)
O(1)
class Solution {
public:
ListNode *reverseKGroup(ListNode *head, int k) {
if (head == nullptr || head->next == nullptr || k < 2) return head;
ListNode dummy(-1);
dummy.next = head;
for(ListNode *prev = &dummy, *end = head; end; end = prev->next) {
for (int i = 1; i < k && end; i++)
end = end->next;
if (end == nullptr) break; //
k
prev = reverse(prev, prev->next, end);
}
return dummy.next;
}
// prev
first
, [begin, end]
null
//
1
ListNode* reverse(ListNode *prev, ListNode *begin, ListNode *end) {
ListNode *end_next = end->next;
for (ListNode *p = begin, *cur = p->next, *next = cur->next;
cur != end_next;
p = cur, cur = next, next = next ? next->next : nullptr) {
cur->next = p;
}
begin->next = end_next;
prev->next = end;
return begin;
}
};
Swap Nodes in Pairs,
2.2.8
2.2.10 Copy List with Random Pointer
A linked list is given such that each node contains an additional random pointer which could point to
any node in the list or null.
Return a deep copy of the list.
51
2.2
// LeetCode, Copy List with Random Pointer

//
O(n)
O(1)
class Solution {
public:
RandomListNode *copyRandomList(RandomListNode *head) {
for (RandomListNode* cur = head; cur != nullptr; ) {
RandomListNode* node = new RandomListNode(cur->label);
node->next = cur->next;
cur->next = node;
cur = node->next;
}
for (RandomListNode* cur = head; cur != nullptr; ) {
if (cur->random != NULL)
cur->next->random = cur->random->next;
cur = cur->next->next;
}
//
RandomListNode dummy(-1);
for (RandomListNode* cur = head, *new_cur = &dummy;
cur != nullptr; ) {
new_cur->next = cur->next;
new_cur = new_cur->next;
cur->next = cur->next->next;
cur = cur->next;
}
return dummy.next;
}
};
2.2.11 Linked List Cycle
Given a linked list, determine if it has a cycle in it.

Follow up: Can you solve it without using extra space?
52
unordered_map<int, bool> visited

O(n)
O(n)
O(N )
O(1)
http://leetcode.com/2010/09/detecting-loop-in-singly-linked-list.html
//LeetCode, Linked List Cycle

//
O(n)
O(1)
class Solution {
public:
bool hasCycle(ListNode *head) {
//
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
};
Linked List Cycle II,
2.2.12
2.2.12 Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up: Can you solve it without using extra space?
fast
slow
slow
s
slow
fast
2s
fast
s
fast
2s
s + nr
nr
(1 n)
r
53
2.2
x+a
nr = (n1)r + r = (n 1)r + L x
(n 1)r + (Lxa)
n1
Lxa
head
slow2
//LeetCode, Linked List Cycle II

//
O(n)
O(1)
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
slow = slow->next;
if (slow == fast) {
ListNode *slow2 = head;
while (slow2 != slow) {
slow2 = slow2->next;
slow = slow->next;
}
return slow2;
}
}
return nullptr;
}
};
Linked List Cycle,
2.2.11
2.2.13 Reorder List
Given a singly linked list L : L0 L1 Ln1 Ln , reorder it to: L0 Ln L1

Ln1 L2 Ln2
You must do this in-place without altering the nodes values.
For example, Given {1,2,3,4}, reorder it to {1,4,2,3}.
54
in-place
O(1)
reverse
// LeetCode, Reorder List

//
O(n)
O(1)
class Solution {
public:
void reorderList(ListNode *head) {
if (head == nullptr || head->next == nullptr) return;
ListNode *slow = head, *fast = head, *prev = nullptr;
prev = slow;
slow = slow->next;
}
prev->next = nullptr; // cut at middle
slow = reverse(slow);
// merge two lists
ListNode *curr = head;
while (curr->next) {
ListNode *tmp = curr->next;
curr->next = slow;
slow = slow->next;
curr->next->next = tmp;
curr = tmp;
}
curr->next = slow;
}
ListNode* reverse(ListNode *head) {
if (head == nullptr || head->next == nullptr) return head;
ListNode *prev = head;
for (ListNode *curr = head->next, *next = curr->next; curr;
prev = curr, curr = next, next = next ? next->next : nullptr) {
curr->next = prev;
}
head->next = nullptr;
return prev;
}
};
55
2.2
2.2.14 LRU Cache
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the
following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise
return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its
capacity, it should invalidate the least recently used item before inserting a new item.
(std::list)
(std::unordered_map)
O(1)
hash
cache
size
capacity
// LeetCode, LRU Cache

//
O(logn)
O(n)
class LRUCache{
private:
struct CacheNode {
int key;
int value;
CacheNode(int k, int v) :key(k), value(v){}
};
public:
LRUCache(int capacity) {
this->capacity = capacity;
}
hash
56
int get(int key) {

if (cacheMap.find(key) == cacheMap.end()) return -1;
//
map
cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
cacheMap[key] = cacheList.begin();
return cacheMap[key]->value;
}
void set(int key, int value) {
if (cacheMap.find(key) == cacheMap.end()) {
if (cacheList.size() == capacity) { //
cacheMap.erase(cacheList.back().key);
cacheList.pop_back();
}
//
,
map
cacheList.push_front(CacheNode(key, value));
} else {
//
,
map
cacheMap[key]->value = value;
cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
}
}
private:
list<CacheNode> cacheList;
unordered_map<int, list<CacheNode>::iterator> cacheMap;
int capacity;
};
3.1 Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring
cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
Note: Have you consider that the string might be empty? This is a good question to ask during an
interview.
For the purpose of this problem, we define empty string as valid palindrome.
// Leet Code, Valid Palindrome

//
O(n)
O(1)
class Solution {
public:
bool isPalindrome(string s) {
transform(s.begin(), s.end(), s.begin(), ::tolower);
auto left = s.begin(), right = prev(s.end());
while (left < right) {
if (!::isalnum(*left)) ++left;
else if (!::isalnum(*right)) --right;
else if (*left != *right) return false;
else { left++, right--; }
}
return true;
}
};
57
58
Palindrome Number,
15.2
3.2 Implement strStr()

Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
O(m n)
Rabin-Karp
KMP
Boyer-Mooer
BUG
// LeetCode, Implement strStr()

//
O(N*M)
O(1)
class Solution {
public:
int strStr(const string& haystack, const string& needle) {
if (needle.empty()) return 0;
const int N = haystack.size() - needle.size() + 1;
for (int i = 0; i < N; i++) {
int j = i;
int k = 0;
while (j < haystack.size() && k < needle.size() && haystack[j] == needle[k]) {
j++;
k++;
}
if (k == needle.size()) return i;
}
return -1;
}
};
KMP
// LeetCode, Implement strStr()
// KMP
O(N+M)
O(M)
class Solution {
public:
int strStr(const string& haystack, const string& needle) {
return kmp(haystack.c_str(), needle.c_str());
}
3.2 Implement strStr()
private:
/*
* @brief
next
.
*
* @param[in] pattern
* @param[out] next next
* @return
*/
static void compute_prefix(const char *pattern, int next[]) {
int i;
int j = -1;
const int m = strlen(pattern);
next[0] = j;
for (i = 1; i < m; i++) {
while (j > -1 && pattern[j + 1] != pattern[i]) j = next[j];
if (pattern[i] == pattern[j + 1]) j++;
next[i] = j;
}
}
/*
* @brief KMP
.
*
* @param[in] text
* @param[in] pattern
* @return
-1
*/
static int kmp(const char *text, const char *pattern) {
int i;
int j = -1;
const int n = strlen(text);
const int m = strlen(pattern);
if (n == 0 && m == 0) return 0; /* "","" */
if (m == 0) return 0; /* "a","" */
int *next = (int*)malloc(sizeof(int) * m);
compute_prefix(pattern, next);
for (i = 0; i < n; i++) {
while (j > -1 && pattern[j + 1] != text[i]) j = next[j];
if (text[i] == pattern[j + 1]) j++;
if (j == m - 1) {
free(next);
return i-j;
}
}
free(next);
return -1;
}
59
60
};
String to Integer (atoi)
3.3
3.3 String to Integer (atoi)

Implement atoi to convert a string to an integer.
Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and
ask yourself what are the possible input cases.
Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.
Requirements for atoi:
The function first discards as many whitespace characters as necessary until the first non-whitespace
character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by
as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored
and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such
sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
If no valid conversion could be performed, a zero value is returned. If the correct value is out of the
range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.
1.
-3924x8fc
2.
++c, ++1
3.
2147483648
+ 413,
// LeetCode, String to Integer (atoi)

//
O(n)
O(1)
class Solution {
61
3.4 Add Binary
public:
int myAtoi(const string &str) {
int num = 0;
int sign = 1;
const int n = str.length();
int i = 0;
while (str[i] == ' ' && i < n) i++;
if (str[i] == '+') {
i++;
} else if (str[i] == '-') {
sign = -1;
i++;
}
for (; i < n; i++) {
if (str[i] < '0' || str[i] > '9')
break;
if (num > INT_MAX / 10 ||
(num == INT_MAX / 10 &&
(str[i] - '0') > INT_MAX % 10)) {
return sign == -1 ? INT_MIN : INT_MAX;
}
num = num * 10 + str[i] - '0';
}
return num * sign;
}
};
Implement strStr()
3.2
3.4 Add Binary

Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".
62
//LeetCode, Add Binary

//
O(n)
O(1)
class Solution {
public:
string addBinary(string a, string b) {
string result;
const size_t n = a.size() > b.size() ? a.size() : b.size();
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
int carry = 0;
for (size_t i = 0; i < n; i++) {
const int ai = i < a.size() ? a[i] - '0' : 0;
const int bi = i < b.size() ? b[i] - '0' : 0;
const int val = (ai + bi + carry) % 2;
carry = (ai + bi + carry) / 2;
result.insert(result.begin(), val + '0');
}
if (carry == 1) {
result.insert(result.begin(), '1');
}
return result;
}
};
Add Two Numbers,
2.2.1
3.5 Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length
of S is 1000, and there exists one unique longest palindromic substring.
O(n2 )
O(n2 )
f[i][j]
[i,j]
f[i][j] = if (i == j) S[i]
if (S[i] == S[j] && f[i+1][j-1] == S[i+1][j-1]) S[i][j]
else max(f[i+1][j-1], f[i][j-1], f[i+1][j])
63

O(n2 )
f(i,j)
[i,j]
true
f (i, j) = S[i] = S[j]
S[i] = S[j] and f (i + 1, j 1)

Manacher s Algorithm,
O(n)
,i = j
,j = i + 1
,j > i + 1
http://leetcode.com/2011/11/longest-
palindromic-substring-part-ii.html
// LeetCode, Longest Palindromic Substring

//
//
O(n^2)
O(n^2)
typedef string::const_iterator Iterator;
namespace std {
template<>
struct hash<pair<Iterator, Iterator>> {
size_t operator()(pair<Iterator, Iterator> const& p) const {
return ((size_t) &(*p.first)) ^ ((size_t) &(*p.second));
}
};
}
class Solution {
public:
string longestPalindrome(string const& s) {
cache.clear();
return cachedLongestPalindrome(s.begin(), s.end());
}
private:
unordered_map<pair<Iterator, Iterator>, string> cache;
string longestPalindrome(Iterator first, Iterator last) {
size_t length = distance(first, last);
if (length < 2) return string(first, last);
auto s = cachedLongestPalindrome(next(first), prev(last));
if (s.length() == length - 2 && *first == *prev(last))
return string(first, last);
auto s1 = cachedLongestPalindrome(next(first), last);
auto s2 = cachedLongestPalindrome(first, prev(last));
// return max(s, s1, s2)
if (s.size() > s1.size()) return s.size() > s2.size() ? s : s2;
64
else return s1.size() > s2.size() ? s1 : s2;

}
string cachedLongestPalindrome(Iterator first, Iterator last) {
auto key = make_pair(first, last);
auto pos = cache.find(key);
if (pos != cache.end()) return pos->second;
else return cache[key] = longestPalindrome(first, last);
}
};

//
O(n^2)
O(n^2)
class Solution {
public:
string longestPalindrome(const string& s) {
const int n = s.size();
bool f[n][n];
fill_n(&f[0][0], n * n, false);
//
vector
//vector<vector<bool> > f(n, vector<bool>(n, false));
size_t max_len = 1, start = 0; //
for (size_t i = 0; i < s.size(); i++)
f[i][i] = true;
for (size_t j = 0; j < i; j++) {
f[j][i] = (s[j] == s[i] && (i
if (f[j][i] && max_len < (i max_len = i - j + 1;
start = j;
}
}
}
return s.substr(start, max_len);
{
// [j, i]
- j < 2 || f[j + 1][i - 1]));
j + 1)) {
}
};
Manacher s Algorithm
// Manacher s Algorithm
//
O(n)
O(n)
class Solution {
public:
// Transform S into T.
// For example, S = "abba", T = "^#a#b#b#a#$".
// ^ and $ signs are sentinels appended to each end to avoid bounds checking
string preProcess(const string& s) {
int n = s.length();
65
if (n == 0) return "^$";
string ret = "^";
for (int i = 0; i < n; i++) ret += "#" + s.substr(i, 1);
ret += "#$";
return ret;
}
string longestPalindrome(string s) {
string T = preProcess(s);
const int n = T.length();
//
T[i]
/
//
P[i]
int P[n];
int C = 0, R = 0;
T[i]
for (int i = 1; i < n - 1; i++) {

int i_mirror = 2 * C - i; // equals to i' = C - (i-C)
P[i] = (R > i) ? min(R - i, P[i_mirror]) : 0;
// Attempt to expand palindrome centered at i
while (T[i + 1 + P[i]] == T[i - 1 - P[i]])
P[i]++;
// If palindrome centered at i expand past R,
// adjust center based on expanded palindrome.
if (i + P[i] > R) {
C = i;
R = i + P[i];
}
}
// Find the maximum element in P.
int max_len = 0;
int center_index = 0;
for (int i = 1; i < n - 1; i++) {
if (P[i] > max_len) {
max_len = P[i];
center_index = i;
}
}
return s.substr((center_index - 1 - max_len) / 2, max_len);
}
};
66
3.6 Regular Expression Matching

Implement regular expression matching with support for '.' and '*'.
'.' Matches any single character. '*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") false
isMatch("aa","aa") true
isMatch("aaa","aa") false
isMatch("aa", "a*") true
isMatch("aa", ".*") true
isMatch("ab", ".*") true
isMatch("aab", "c*a*b") true
// LeetCode, Regular Expression Matching

//
O(n)
O(1)
class Solution {
public:
bool isMatch(const string& s, const string& p) {
return isMatch(s.c_str(), p.c_str());
}
private:
bool isMatch(const char *s, const char *p) {
if (*p == '\0') return *s == '\0';
// next char is not '*', then must match current character
if (*(p + 1) != '*') {
if (*p == *s || (*p == '.' && *s != '\0'))
return isMatch(s + 1, p + 1);
else
return false;
} else { // next char is '*'
while (*p == *s || (*p == '.' && *s != '\0')) {
if (isMatch(s, p + 2))
return true;
s++;
}
return isMatch(s, p + 2);
67
3.7 Wildcard Matching
}
}
};
Wildcard Matching,
3.7
3.7 Wildcard Matching

Implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") false
isMatch("aa","aa") true
isMatch("aaa","aa") false
isMatch("aa", "*") true
isMatch("aa", "a*") true
isMatch("ab", "?*") true
isMatch("aab", "c*a*b") false
'*'
'*'
s++
// LeetCode, Wildcard Matching

//
//
O(n!*m!)
class Solution {
public:
O(n)
'*'
68

}
private:
if (*p == '*') {
while (*p == '*') ++p; //skip continuous '*'
if (*p == '\0') return true;
while (*s != '\0' && !isMatch(s, p)) ++s;
return *s != '\0';
}
else if (*p == '\0' || *s == '\0') return *p == *s;
else if (*p == *s || *p == '?') return isMatch(++s, ++p);
else return false;
}
};
// LeetCode, Wildcard Matching

//
O(n*m)
O(1)
class Solution {
public:
}
private:
bool star = false;
const char *str, *ptr;
for (str = s, ptr = p; *str != '\0'; str++, ptr++) {
switch (*ptr) {
case '?':
break;
case '*':
star = true;
s = str, p = ptr;
while (*p == '*') p++; //skip continuous '*'
if (*p == '\0') return true;
str = s - 1;
ptr = p - 1;
break;
default:
if (*str != *ptr) {
//
'*'
if (!star) return false;
s++;
str = s - 1;
ptr = p - 1;
}
}
}
69
3.8 Longest Common Prefix
while (*ptr == '*') ptr++;

return (*ptr == '\0');
}
};
Regular Expression Matching,
3.6
3.8 Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.
// LeetCode, Longest Common Prefix

//
0
//
O(n1+n2+...)
// @author
(http://weibo.com/zhouditty)
class Solution {
public:
string longestCommonPrefix(vector<string> &strs) {
if (strs.empty()) return "";
for (int idx = 0; idx < strs[0].size(); ++idx) { //
for (int i = 1; i < strs.size(); ++i) {
if (strs[i][idx] != strs[0][idx]) return strs[0].substr(0,idx);
}
}
return strs[0];
}
};
// LeetCode, Longest Common Prefix

//
0
//
//
O(n1+n2+...)
class Solution {
public:
string longestCommonPrefix(vector<string> &strs) {
70
if (strs.empty()) return "";

int right_most = strs[0].size() - 1;
for (size_t i = 1; i < strs.size(); i++)
for (int j = 0; j <= right_most; j++)
if (strs[i][j] != strs[0][j]) //
right_most = j - 1;
string::[]
return strs[0].substr(0, right_most + 1);

}
};
3.9 Valid Number

Validate if a given string is numeric.
Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up
front before implementing one.
strtod()
// LeetCode, Valid Number

// @author
// finite automata
O(n)
class Solution {
public:
bool isNumber(const string& s) {
enum InputType {
INVALID,
// 0
SPACE,
// 1
O(n)
71
3.9 Valid Number
SIGN,
DIGIT,
DOT,
EXPONENT,
NUM_INPUTS
//
//
//
//
//
2
3
4
5
6
};
const int transitionTable[][NUM_INPUTS] = {
-1, 0, 3, 1, 2, -1, // next states for state 0
-1, 8, -1, 1, 4, 5,
// next states for state 1
-1, -1, -1, 4, -1, -1,
-1, -1, -1, 1, 2, -1,
-1, 8, -1, 4, -1, 5,
-1, -1, 6, 7, -1, -1,
-1, -1, -1, 7, -1, -1,
-1, 8, -1, 7, -1, -1,
-1, 8, -1, -1, -1, -1,
};
int state = 0;
for (auto ch : s) {
InputType inputType = INVALID;
if (isspace(ch))
inputType = SPACE;
else if (ch == '+' || ch == '-')
inputType = SIGN;
else if (isdigit(ch))
inputType = DIGIT;
else if (ch == '.')
inputType = DOT;
else if (ch == 'e' || ch == 'E')
inputType = EXPONENT;
// Get next state from current state and input symbol
state = transitionTable[state][inputType];
// Invalid input
if (state == -1) return false;
}
// If the current state belongs to one of the accepting (final) states,
// then the number is valid
return state == 1 || state == 4 || state == 7 || state == 8;
}
};
strtod()
// LeetCode, Valid Number
// @author
(http://weibo.com/lianchengzju)
//
strtod()
O(n)
class Solution {
public:
bool isNumber (const string& s) {
72
return isNumber(s.c_str());
}
private:
bool isNumber (char const* s) {
char* endptr;
strtod (s, &endptr);
if (endptr == s) return false;
for (; *endptr; ++endptr)
if (!isspace (*endptr)) return false;
return true;
}
};
3.10 Integer to Roman

Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.
// LeetCode, Integer to Roman

//
O(num)
O(1)
class Solution {
public:
string intToRoman(int num) {
const int radix[] = {1000, 900, 500, 400, 100, 90,
50, 40, 10, 9, 5, 4, 1};
const string symbol[] = {"M", "CM", "D", "CD", "C", "XC",
"L", "XL", "X", "IX", "V", "IV", "I"};
string roman;
for (size_t i = 0; num > 0; ++i) {
int count = num / radix[i];
num %= radix[i];
for (; count > 0; --count) roman += symbol[i];
73
3.11 Roman to Integer
}
return roman;
}
};
Roman to Integer,
3.11
3.11 Roman to Integer

Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
IV = 5 1
VI = 5 + 1, II=1+1
// LeetCode, Roman to Integer

//
O(n)
O(1)
class Solution {
public:
inline int map(const char c) {
switch (c) {
case 'I': return 1;
case 'V': return 5;
case 'X': return 10;
case 'L': return 50;
case 'C': return 100;
case 'D': return 500;
case 'M': return 1000;
default: return 0;
}
}
int romanToInt(const string& s) {
int result = 0;
for (size_t i = 0; i < s.size(); i++) {
if (i > 0 && map(s[i]) > map(s[i - 1])) {
result += (map(s[i]) - 2 * map(s[i - 1]));
} else {
74
result += map(s[i]);
}
}
return result;
}
};
Integer to Roman,
3.10
3.12 Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2", then "one 1" or 1211.
Given an integer n, generate the nth sequence.
Note: The sequence of integers will be represented as a string.
// LeetCode, Count and Say

// @author
//
O(n^2)
O(n)
class Solution {
public:
string countAndSay(int n) {
string s("1");
while (--n)
s = getNext(s);
return s;
}
string getNext(const string &s) {
stringstream ss;
75
3.13 Anagrams
for (auto i = s.begin(); i != s.end(); ) {

auto j = find_if(i, s.end(), bind1st(not_equal_to<char>(), *i));
ss << distance(i, j) << *i;
i = j;
}
return ss.str();
}
};
3.13 Anagrams
Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
"dormitory"
Anagram
"dirty room"
"tea"
"eat"
anagrams
// LeetCode, Anagrams
//
O(n)
O(n)
class Solution {
public:
vector<string> anagrams(vector<string> &strs) {
unordered_map<string, vector<string> > group;
for (const auto &s : strs) {
string key = s;
sort(key.begin(), key.end());
group[key].push_back(s);
}
vector<string> result;
for (auto it = group.cbegin(); it != group.cend(); it++) {
if (it->second.size() > 1)
result.insert(result.end(), it->second.begin(), it->second.end());
}
76
return result;
}
};
3.14 Simplify Path

Given an absolute path for a file (Unix-style), simplify it.
For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
Corner Cases:
Did you consider the case where path = "/../"? In this case, you should return "/".
Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
In this case, you should ignore redundant slashes and return "/home/foo".
// LeetCode, Simplify Path

//
O(n)
O(n)
class Solution {
public:
string simplifyPath(const string& path) {
vector<string> dirs; //
for (auto i = path.begin(); i != path.end();) {
++i;
auto j = find(i, path.end(), '/');
auto dir = string(i, j);
if (!dir.empty() && dir != ".") {//
if (dir == "..") {
if (!dirs.empty())
dirs.pop_back();
'///'
dir
3.15 Length of Last Word
77
} else
dirs.push_back(dir);
}
i = j;
}
stringstream out;
if (dirs.empty()) {
out << "/";
} else {
for (auto dir : dirs)
out << '/' << dir;
}
return out.str();
}
};
3.15 Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length
of last word in the string.
If the last word does not exist, return 0.
Note: A word is defined as a character sequence consists of non-space characters only.
For example, Given s = "Hello World", return 5.
STL
// LeetCode, Length of Last Word
//
STL
//
O(n)
O(1)
class Solution {
public:
int lengthOfLastWord(const string& s) {
auto first = find_if(s.rbegin(), s.rend(), ::isalpha);
auto last = find_if_not(first, s.rend(), ::isalpha);
78
return distance(first, last);

}
};
// LeetCode, Length of Last Word

//
word
//
O(n)
O(1)
class Solution {
public:
int lengthOfLastWord(const string& s) {
return lengthOfLastWord(s.c_str());
}
private:
int lengthOfLastWord(const char *s) {
int len = 0;
while (*s) {
if (*s++ != ' ')
++len;
else if (*s && *s != ' ')
len = 0;
}
return len;
}
};
4.1
4.1.1 Valid Parentheses
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the
input string is valid.
The brackets must close in the correct order, "()" and "()[]" are all valid but "(]" and "([)]" are
not.
// LeetCode, Valid Parentheses

//
O(n)
O(n)
class Solution {
public:
bool isValid (string const& s) {
string left = "([{";
string right = ")]}";
stack<char> stk;
for (auto c : s) {
if (left.find(c) != string::npos) {
stk.push (c);
} else {
if (stk.empty () || stk.top () != left[right.find (c)])
return false;
else
stk.pop ();
}
}
79
80
return stk.empty();
}
};
Generate Parentheses,
10.9
Longest Valid Parentheses,
4.1.2
4.1.2 Longest Valid Parentheses
Given a string containing just the characters '(' and ')', find the length of the longest valid (wellformed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has
length = 4.
// LeetCode, Longest Valid Parenthese

//
O(n)
O(n)
class Solution {
public:
int longestValidParentheses(const string& s) {
int max_len = 0, last = -1; // the position of the last ')'
stack<int> lefts; // keep track of the positions of non-matching '('s
for (int i = 0; i < s.size(); ++i) {
if (s[i] =='(') {
lefts.push(i);
} else {
if (lefts.empty()) {
// no matching left
last = i;
} else {
// find a matching pair
lefts.pop();
if (lefts.empty()) {
max_len = max(max_len, i-last);
} else {
max_len = max(max_len, i-lefts.top());
81
4.1
}
}
}
}
return max_len;
}
};
Dynamic Programming, One Pass

//
O(n)
O(n)
// @author
(http://weibo.com/wjson)
class Solution {
public:
vector<int> f(s.size(), 0);
int ret = 0;
for (int i = s.size() - 2; i >= 0; --i) {
int match = i + f[i + 1] + 1;
// case: "((...))"
if (s[i] == '(' && match < s.size() && s[match] == ')') {
f[i] = f[i + 1] + 2;
// if a valid sequence exist afterwards "((...))()"
if (match + 1 < s.size()) f[i] += f[match + 1];
}
ret = max(ret, f[i]);
}
return ret;
}
};

//
O(n)
O(1)
// @author
(http://weibo.com/cpcs)
class Solution {
public:
int answer = 0, depth = 0, start = -1;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '(') {
++depth;
} else {
--depth;
if (depth < 0) {
start = i;
depth = 0;
} else if (depth == 0) {
answer = max(answer, i - start);
}
82
}
}
depth = 0;
start = s.size();
for (int i = s.size() - 1; i >= 0; --i) {
if (s[i] == ')') {
++depth;
} else {
--depth;
if (depth < 0) {
start = i;
depth = 0;
} else if (depth == 0) {
answer = max(answer, start - i);
}
}
}
return answer;
}
};
Valid Parentheses,
Generate Parentheses,
4.1.1
10.9
4.1.3 Largest Rectangle in Histogram
Given n non-negative integers representing the histograms bar height where the width of each bar is 1,
find the area of largest rectangle in the histogram.
4-1
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
83
4.1
4-2
The largest rectangle is shown in the shaded area, which has area = 10 unit.
For example, Given height = [2,1,5,6,2,3], return 10.
Container With Most Water(12.6)

O(n2 )
4-2
i=4
3
3
3
4
// LeetCode, Largest Rectangle in Histogram

//
O(n)
O(n)
class Solution {
public:
int largestRectangleArea(vector<int> &height) {
stack<int> s;
height.push_back(0);
int result = 0;
for (int i = 0; i < height.size(); ) {
if (s.empty() || height[i] > height[s.top()])
s.push(i++);
else {
int tmp = s.top();
s.pop();
result = max(result,
height[tmp] * (s.empty() ? i : i - s.top() - 1));
}
}
return result;
84
}
};
Trapping Rain Water, 2.1.15

Container With Most Water, 12.6
4.1.4 Evaluate Reverse Polish Notation
Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
// LeetCode, Evaluate Reverse Polish Notation

//
O(n)
O(logn)
class Solution {
public:
int evalRPN(vector<string> &tokens) {
int x, y;
auto token = tokens.back(); tokens.pop_back();
if (is_operator(token)) {
y = evalRPN(tokens);
x = evalRPN(tokens);
if (token[0] == '+')
x += y;
else if (token[0] == '-') x -= y;
else if (token[0] == '*') x *= y;
else
x /= y;
} else {
size_t i;
x = stoi(token, &i);
}
return x;
}
private:
bool is_operator(const string &op) {
return op.size() == 1 && string("+-*/").find(op) != string::npos;
}
};
85
4.2
// LeetCode, Max Points on a Line

//
O(n)
O(logn)
class Solution {
public:
int evalRPN(vector<string> &tokens) {
stack<string> s;
for (auto token : tokens) {
if (!is_operator(token)) {
s.push(token);
} else {
int y = stoi(s.top());
s.pop();
int x = stoi(s.top());
s.pop();
if (token[0] == '+')
x += y;
else if (token[0] == '-') x -= y;
else if (token[0] == '*') x *= y;
else
x /= y;
s.push(to_string(x));
}
}
return stoi(s.top());
}
private:
bool is_operator(const string &op) {
return op.size() == 1 && string("+-*/").find(op) != string::npos;
}
};
4.2
LeetCode
//
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) { }
};
5.1
(root->left->right) root->right->left
>right->root) right->left->root
(left(left->root->right)
5.1.1 Binary Tree Preorder Traversal
Given a binary tree, return the preorder traversal of its nodes values.
For example: Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?
86
87
5.1
Morris
// LeetCode, Binary Tree Preorder Traversal

//
O(n)
O(n)
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
vector<int> result;
stack<const TreeNode *> s;
if (root != nullptr) s.push(root);
while (!s.empty()) {
const TreeNode *p = s.top();
s.pop();
result.push_back(p->val);
if (p->right != nullptr) s.push(p->right);
if (p->left != nullptr) s.push(p->left);
}
return result;
}
};
Morris
// LeetCode, Binary Tree Preorder Traversal
// Morris
O(n)
O(1)
class Solution {
public:
vector<int> preorderTraversal(TreeNode *root) {
vector<int> result;
TreeNode *cur = root, *prev = nullptr;
if (cur->left == nullptr) {
result.push_back(cur->val);
prev = cur; /* cur
*/
cur = cur->right;
} else {
/*
*/
TreeNode *node = cur->left;
while (node->right != nullptr && node->right != cur)
node = node->right;
if (node->right == nullptr) { /*
result.push_back(cur->val); /*
node->right = cur;
prev = cur; /* cur
*/
*/
*/
88
cur = cur->left;
} else {
/*
node->right = nullptr;
/* prev = cur;
cur = cur->right;
}
*/
cur
}
}
return result;
}
};
Binary Tree Inorder Traversal

Binary Tree Postorder Traversal
Recover Binary Search Tree
5.1.2
5.1.3
5.1.7
5.1.2 Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes values.
1
\
2
/
3
return [1,3,2].
Morris
// LeetCode, Binary Tree Inorder Traversal

//
O(n)
O(n)
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> result;
const TreeNode *p = root;
*/
89
5.1
while (!s.empty() || p != nullptr) {

if (p != nullptr) {
s.push(p);
p = p->left;
} else {
p = s.top();
s.pop();
p = p->right;
}
}
return result;
}
};
Morris
// LeetCode, Binary Tree Inorder Traversal
// Morris
O(n)
O(1)
class Solution {
public:
vector<int> inorderTraversal(TreeNode *root) {
vector<int> result;
TreeNode *cur = root, *prev = nullptr;
prev = cur;
cur = cur->right;
} else {
/*
*/
node = node->right;
node->right = cur;
/* prev = cur;
cur
cur = cur->left;
} else {
/*
prev = cur;
cur = cur->right;
}
}
}
return result;
}
};
*/
*/
*/
90
Binary Tree Preorder Traversal

Binary Tree Postorder Traversal
5.1.1
5.1.3
5.1.7
5.1.3 Binary Tree Postorder Traversal
Given a binary tree, return the postorder traversal of its nodes values.
1
\
2
/
3
return [3,2,1].
Morris
// LeetCode, Binary Tree Postorder Traversal

//
O(n)
O(n)
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
vector<int> result;
/* p
q
*/
const TreeNode *p = root, *q = nullptr;
do {
while (p != nullptr) { /*
s.push(p);
p = p->left;
}
q = nullptr;
p = s.top();
s.pop();
/*
if (p->right == q) {
*/
*/
91
5.1
q = p; /*
} else {
/*
s.push(p);
/*
*/
p = p->right;
break;
}
*/
*/
}
} while (!s.empty());
return result;
}
};
Morris
// LeetCode, Binary Tree Postorder Traversal
// Morris
O(n)
O(1)
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
vector<int> result;
TreeNode dummy(-1);
TreeNode *cur, *prev = nullptr;
std::function < void(const TreeNode*)> visit =
[&result](const TreeNode *node){
result.push_back(node->val);
};
dummy.left = root;
cur = &dummy;
prev = cur; /*
*/
cur = cur->right;
} else {
node = node->right;
node->right = cur;
prev = cur; /*
*/
cur = cur->left;
} else { /*
visit_reverse(cur->left, prev, visit);
prev->right = nullptr;
prev = cur; /*
*/
cur = cur->right;
}
}
*/
*/
92
}
return result;
}
private:
//
static void reverse(TreeNode *from, TreeNode *to) {
TreeNode *x = from, *y = from->right, *z;
if (from == to) return;
while (x != to) {
z = y->right;
y->right = x;
x = y;
y = z;
}
}
//
static void visit_reverse(TreeNode* from, TreeNode *to,
std::function< void(const TreeNode*) >& visit) {
TreeNode *p = to;
reverse(from, to);
while (true) {
visit(p);
if (p == from)
break;
p = p->right;
}
reverse(to, from);
}
};
Binary Tree Preorder Traversal

5.1.1
5.1.2
5.1.7
5.1.4 Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes values. (ie, from left to right, level by
level).
For example: Given binary tree {3,9,20,#,#,15,7},
93
5.1
3
/ \
9 20
/ \
15
7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
// LeetCode, Binary Tree Level Order Traversal

//
O(n)
O(n)
class Solution {
public:
vector<vector<int> > levelOrder(TreeNode *root) {
traverse(root, 1, result);
return result;
}
void traverse(TreeNode *root, size_t level, vector<vector<int>> &result) {
if (!root) return;
if (level > result.size())
result.push_back(vector<int>());
result[level-1].push_back(root->val);
traverse(root->left, level+1, result);
traverse(root->right, level+1, result);
}
};
// LeetCode, Binary Tree Level Order Traversal

//
O(n)
O(1)
class Solution {
public:
vector<vector<int> > levelOrder(TreeNode *root) {
vector<vector<int> > result;
queue<TreeNode*> current, next;
94
if(root == nullptr) {
return result;
} else {
current.push(root);
}
while (!current.empty()) {
vector<int> level; // elments in one level
TreeNode* node = current.front();
current.pop();
level.push_back(node->val);
if (node->left != nullptr) next.push(node->left);
if (node->right != nullptr) next.push(node->right);
}
result.push_back(level);
swap(next, current);
}
return result;
}
};
Binary Tree Level Order Traversal II

Binary Tree Zigzag Level Order Traversal
5.1.5
5.1.6
5.1.5 Binary Tree Level Order Traversal II
Given a binary tree, return the bottom-up level order traversal of its nodes values. (ie, from left to right,
level by level from leaf to root).
For example: Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15
7
return its bottom-up level order traversal as:
[
[15,7]
[9,20],
[3],
]
95
5.1
5.1.4
reverse()
// LeetCode, Binary Tree Level Order Traversal II

//
O(n)
O(n)
class Solution {
public:
vector<vector<int> > levelOrderBottom(TreeNode *root) {
traverse(root, 1, result);
std::reverse(result.begin(), result.end()); //
return result;
}
void traverse(TreeNode *root, size_t level, vector<vector<int>> &result) {
if (!root) return;
traverse(root->left, level+1, result);
traverse(root->right, level+1, result);
}
};
// LeetCode, Binary Tree Level Order Traversal II

//
O(n)
O(1)
class Solution {
public:
vector<vector<int> > levelOrderBottom(TreeNode *root) {
if(root == nullptr) return result;
vector<int> level; // elments in level level
current.push(root);
current.pop();
}
96
level.clear();
}
reverse(result.begin(), result.end()); //
return result;
}
};
Binary Tree Level Order Traversal
5.1.4
Binary Tree Zigzag Level Order Traversal
5.1.6
5.1.6 Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes values. (ie, from left to right,
then right to left for the next level and alternate between).
For example: Given binary tree 3,9,20,#,#,15,7,
3
/ \
9 20
/ \
15
7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
bool
// LeetCode, Binary Tree Zigzag Level Order Traversal

//
O(n)
O(n)
class Solution {
public:
vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
traverse(root, 1, result, true);
return result;
97
5.1
}
void traverse(TreeNode *root, size_t level, vector<vector<int>> &result,
bool left_to_right) {
if (!root) return;
if (left_to_right)
else
result[level-1].insert(result[level-1].begin(), root->val);
traverse(root->left, level+1, result, !left_to_right);
traverse(root->right, level+1, result, !left_to_right);
}
};
//LeetCode, Binary Tree Zigzag Level Order Traversal

//
bool
//
O(n)
O(n)
class Solution {
public:
vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
bool left_to_right = true;
if(root == nullptr) {
return result;
} else {
current.push(root);
}
vector<int> level; // elments in one level
current.pop();
}
if (!left_to_right) reverse(level.begin(), level.end());
left_to_right = !left_to_right;
}
return result;
}
98
};
Binary Tree Level Order Traversal

Binary Tree Level Order Traversal II
5.1.4
5.1.5
5.1.7 Recover Binary Search Tree
Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.
Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
O(n)
O(n)
// LeetCode, Recover Binary Search Tree

// Morris
O(n)
class Solution {
public:
void recoverTree(TreeNode* root) {
pair<TreeNode*, TreeNode*> broken;
TreeNode* prev = nullptr;
TreeNode* cur = root;
Morris
O(1)

detect(broken, prev, cur);
prev = cur;
cur = cur->right;
} else {
auto node = cur->left;
node = node->right;
if (node->right == nullptr) {
node->right = cur;
//prev = cur;
cur
99
5.1
cur = cur->left;
} else {
detect(broken, prev, cur);
prev = cur;
cur = cur->right;
}
}
}
swap(broken.first->val, broken.second->val);
}
void detect(pair<TreeNode*, TreeNode*>& broken, TreeNode* prev,
TreeNode* current) {
if (prev != nullptr && prev->val > current->val) {
if (broken.first == nullptr) {
broken.first = prev;
} //
else
{0,1}
swap
second
nullptr
//
Runtime Error
broken.second = current;
}
}
};
5.1.2
5.1.8 Same Tree
Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
// LeetCode, Same Tree

//
O(n)
O(logn)
class Solution {
public:
bool isSameTree(TreeNode *p, TreeNode *q) {
100
if (!p && !q) return true;

//
if (!p || !q) return false; //
return p->val == q->val
//
&& isSameTree(p->left, q->left)
&& isSameTree(p->right, q->right);
}
};
// LeetCode, Same Tree

//
O(n)
O(logn)
class Solution {
public:
bool isSameTree(TreeNode *p, TreeNode *q) {
stack<TreeNode*> s;
s.push(p);
s.push(q);
while(!s.empty()) {
p = s.top(); s.pop();
q = s.top(); s.pop();
if (!p && !q) continue;
if (!p || !q) return false;
if (p->val != q->val) return false;
s.push(p->left);
s.push(q->left);
s.push(p->right);
s.push(q->right);
}
return true;
}
};
Symmetric Tree
5.1.9
5.1.9 Symmetric Tree
Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
101
5.1
// LeetCode, Symmetric Tree

//
O(n)
O(logn)
class Solution {
public:
bool isSymmetric(TreeNode *root) {
if (root == nullptr) return true;
return isSymmetric(root->left, root->right);
}
bool isSymmetric(TreeNode *p, TreeNode *q) {
if (p == nullptr && q == nullptr) return true;
if (p == nullptr || q == nullptr) return false;
return p->val == q->val
//
&& isSymmetric(p->left, q->right)
&& isSymmetric(p->right, q->left);
}
};
// LeetCode, Symmetric Tree

//
O(n)
O(logn)
class Solution {
public:
bool isSymmetric (TreeNode* root) {
if (!root) return true;
stack<TreeNode*> s;
s.push(root->left);
s.push(root->right);
while (!s.empty ()) {
auto p = s.top (); s.pop();
auto q = s.top (); s.pop();
if (!p && !q) continue;
if (!p || !q) return false;
if (p->val != q->val) return false;
s.push(p->left);
s.push(q->right);
s.push(p->right);
s.push(q->left);
}
return true;
//
//
102
}
};
Same Tree
5.1.8
5.1.10 Balanced Binary Tree
Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two
subtrees of every node never differ by more than 1.
// LeetCode, Balanced Binary Tree

//
O(n)
O(logn)
class Solution {
public:
bool isBalanced (TreeNode* root) {
return balancedHeight (root) >= 0;
}
/**
* Returns the height of `root` if `root` is a balanced tree,
* otherwise, returns `-1`.
*/
int balancedHeight (TreeNode* root) {
if (root == nullptr) return 0; //
int left = balancedHeight (root->left);
int right = balancedHeight (root->right);
if (left < 0 || right < 0 || abs(left - right) > 1) return -1;
return max(left, right) + 1; //
}
};
//
103
5.1
5.1.11 Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.

For example, Given
1
/ \
2
5
/ \
\
3
4
6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
1
// LeetCode, Flatten Binary Tree to Linked List
//
1
O(n)
O(logn)
class Solution {
public:
void flatten(TreeNode *root) {
if (root == nullptr) return; //
flatten(root->left);
flatten(root->right);
if (nullptr == root->left) return;
//
TreeNode *p = root->left;
while(p->right) p = p->right; //
p->right = root->right;
root->right = root->left;
root->left = nullptr;
}
};
root
root->right
104
2
//
2
// @author
(http://weibo.com/u/1234984145)
//
O(n)
O(logn)
class Solution {
public:
void flatten(TreeNode *root) {
flatten(root, NULL);
}
private:
//
root
tail
TreeNode *flatten(TreeNode *root, TreeNode *tail) {
if (NULL == root) return tail;
root->right = flatten(root->left, flatten(root->right, tail));
root->left = NULL;
return root;
}
};

//
O(n)
O(logn)
class Solution {
public:
void flatten(TreeNode* root) {
if (root == nullptr) return;
stack<TreeNode*> s;
s.push(root);
auto p = s.top();
s.pop();
if (p->right)
s.push(p->right);
if (p->left)
s.push(p->left);
p->left = nullptr;
if (!s.empty())
p->right = s.top();
}
}
};
105
5.1
5.1.12 Populating Next Right Pointers in Each Node II
Follow up for problem Populating Next Right Pointers in Each Node.

What if the given tree could be any binary tree? Would your previous solution still work?
Note: You may only use constant extra space.
For example, Given the following binary tree,
1
/ \
2
3
/ \
\
4
5
7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \
\
4-> 5 -> 7 -> NULL
Populating Next Right Pointers in Each Node I.
// LeetCode, Populating Next Right Pointers in Each Node II

//
O(n)
O(1)
class Solution {
public:
void connect(TreeLinkNode *root) {
TreeLinkNode dummy(-1);
for (TreeLinkNode *curr = root, *prev = &dummy;
curr; curr = curr->next) {
if (curr->left != nullptr){
prev->next = curr->left;
prev = prev->next;
}
if (curr->right != nullptr){
106
prev->next = curr->right;
prev = prev->next;
}
}
connect(dummy.next);
}
};
// LeetCode, Populating Next Right Pointers in Each Node II

//
O(n)
O(1)
class Solution {
public:
while (root) {
TreeLinkNode * next = nullptr; // the first node of next level
TreeLinkNode * prev = nullptr; // previous node on the same level
for (; root; root = root->next) {
if (!next) next = root->left ? root->left : root->right;
if (root->left) {
if (prev) prev->next = root->left;
prev = root->left;
}
if (root->right) {
if (prev) prev->next = root->right;
prev = root->right;
}
}
root = next; // turn to next level
}
}
};
Populating Next Right Pointers in Each Node
5.4.6
5.2
5.2.1 Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.
107
5.2
// LeetCode, Construct Binary Tree from Preorder and Inorder Traversal

//
O(n)
O(\logn)
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return buildTree(begin(preorder), end(preorder),
begin(inorder), end(inorder));
}
template<typename InputIterator>
TreeNode* buildTree(InputIterator pre_first, InputIterator pre_last,
InputIterator in_first, InputIterator in_last) {
if (pre_first == pre_last) return nullptr;
if (in_first == in_last) return nullptr;
auto root = new TreeNode(*pre_first);
auto inRootPos = find(in_first, in_last, *pre_first);
auto leftSize = distance(in_first, inRootPos);
root->left = buildTree(next(pre_first), next(pre_first,
leftSize + 1), in_first, next(in_first, leftSize));
root->right = buildTree(next(pre_first, leftSize + 1), pre_last,
next(inRootPos), in_last);
return root;
}
};
Construct Binary Tree from Inorder and Postorder Traversal
5.2.2
5.2.2 Construct Binary Tree from Inorder and Postorder Traversal
Given inorder and postorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.
108
// LeetCode, Construct Binary Tree from Inorder and Postorder Traversal

//
O(n)
O(\logn)
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
return buildTree(begin(inorder), end(inorder),
begin(postorder), end(postorder));
}
TreeNode* buildTree(BidiIt in_first, BidiIt in_last,
BidiIt post_first, BidiIt post_last) {
if (in_first ==in_last) return nullptr;
if (post_first == post_last) return nullptr;
const auto val = *prev(post_last);
TreeNode* root = new TreeNode(val);
auto in_root_pos = find(in_first, in_last, val);
auto left_size = distance(in_first, in_root_pos);
auto post_left_last = next(post_first, left_size);
root->left = buildTree(in_first, in_root_pos, post_first, post_left_last);
root->right = buildTree(next(in_root_pos), in_last, post_left_last,
prev(post_last));
return root;
}
};
Construct Binary Tree from Preorder and Inorder Traversal
5.2.1
5.3
5.3.1 Unique Binary Search Trees
Given n, how many structurally unique BSTs (binary search trees) that store values 1...n?
For example, Given n = 3, there are a total of 5 unique BSTs.
1
3
\
/
3
2
/
/
2
3
/
1
\
2
2
/ \
1
3
1
\
2
\
3
109
5.3
1
\
\
3
/
2
/ \
2
3
3
3
/
/
1
/
1
\
2
1
1, 2, 3, ..., n
BST
[1, i-1]
[i+1, n]
f (i)
[1, i]
Unique Binary Search Tree

f (0) = 1
BST
1
f (1) = 1
BST
1,2
1
2
/
\
2
f (2)
f (0) f (1)
f (1) f (0)
BST
f (3)
f (0) f (2)
f (1) f (1)
f (2) f (0)
f
f (i) =
f (k 1) f (i k)
k=1
// LeetCode, Unique Binary Search Trees

//
O(n^2)
O(n)
class Solution {
110
public:
int numTrees(int n) {
vector<int> f(n + 1, 0);
f[0] = 1;
f[1] = 1;
for (int i = 2; i <= n; ++i) {
for (int k = 1; k <= i; ++k)
f[i] += f[k-1] * f[i - k];
}
return f[n];
}
};
Unique Binary Search Trees II
5.3.2
5.3.2 Unique Binary Search Trees II
Given n, generate all structurally unique BSTs (binary search trees) that store values 1...n.
For example, Given n = 3, your program should return all 5 unique BSTs shown below.
1
3
3
2
1
\
/
/
/ \
\
3
2
1
1
3
2
/
/
\
\
2
1
2
3
// LeetCode, Unique Binary Search Trees II

//
TODO
TODO
class Solution {
public:
vector<TreeNode *> generateTrees(int n) {
if (n == 0) return generate(1, 0);
return generate(1, n);
}
private:
vector<TreeNode *> generate(int start, int end) {
vector<TreeNode*> subTree;
if (start > end) {
111
5.3
subTree.push_back(nullptr);
return subTree;
}
for (int k = start; k <= end; k++) {
vector<TreeNode*> leftSubs = generate(start, k - 1);
vector<TreeNode*> rightSubs = generate(k + 1, end);
for (auto i : leftSubs) {
for (auto j : rightSubs) {
TreeNode *node = new TreeNode(k);
node->left = i;
node->right = j;
subTree.push_back(node);
}
}
}
return subTree;
}
};
Unique Binary Search Trees
5.3.1
5.3.3 Validate Binary Search Tree
Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the nodes key.
The right subtree of a node contains only nodes with keys greater than the nodes key.
Both the left and right subtrees must also be binary search trees.
// LeetCode, Validate Binary Search Tree

//
O(n)
O(\logn)
class Solution {
public:
bool isValidBST(TreeNode* root) {
return isValidBST(root, INT_MIN, INT_MAX);
}
bool isValidBST(TreeNode* root, int lower, int upper) {
if (root == nullptr) return true;
112
return root->val > lower && root->val < upper

&& isValidBST(root->left, lower, root->val)
&& isValidBST(root->right, root->val, upper);
}
};
Validate Binary Search Tree
5.3.3
5.3.4 Convert Sorted Array to Binary Search Tree
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
// LeetCode, Convert Sorted Array to Binary Search Tree

//
O(n)
O(logn)
class Solution {
public:
TreeNode* sortedArrayToBST (vector<int>& num) {
return sortedArrayToBST(num.begin(), num.end());
}
template<typename RandomAccessIterator>
TreeNode* sortedArrayToBST (RandomAccessIterator first,
RandomAccessIterator last) {
const auto length = distance(first, last);
if (length <= 0) return nullptr;
//
//
auto mid = first + length / 2;
TreeNode* root = new TreeNode (*mid);
root->left = sortedArrayToBST(first, mid);
root->right = sortedArrayToBST(mid + 1, last);
return root;
}
};
113
5.3
Convert Sorted List to Binary Search Tree
5.3.5
5.3.5 Convert Sorted List to Binary Search Tree
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced
BST.
RandomAccessIt
erator
(bottom-up)
http://leetcode.com/2010/11/convert-sorted-list-to-balanced-
binary.html
Convert Sorted Array to Binary Search Tree
O(n log n)
// LeetCode, Convert Sorted List to Binary Search Tree

//
//
O(n^2)
O(logn)
class Solution {
public:
TreeNode* sortedListToBST (ListNode* head) {
return sortedListToBST (head, listLength (head));
}
TreeNode* sortedListToBST (ListNode* head, int len) {
if (len == 0) return nullptr;
if (len == 1) return new TreeNode (head->val);
TreeNode* root = new TreeNode (nth_node (head, len / 2 + 1)->val);
root->left = sortedListToBST (head, len / 2);
root->right = sortedListToBST (nth_node (head, len / 2 + 2),
(len - 1) / 2);
return root;
}
int listLength (ListNode* node) {
int n = 0;
while(node) {
++n;
node = node->next;
114
}
return n;
}
ListNode* nth_node (ListNode* node, int n) {
while (--n)
node = node->next;
return node;
}
};
// LeetCode, Convert Sorted List to Binary Search Tree

// bottom-up
O(n)
O(logn)
class Solution {
public:
TreeNode *sortedListToBST(ListNode *head) {
int len = 0;
ListNode *p = head;
while (p) {
len++;
p = p->next;
}
return sortedListToBST(head, 0, len - 1);
}
private:
TreeNode* sortedListToBST(ListNode*& list, int start, int end) {
if (start > end) return nullptr;
int mid = start + (end - start) / 2;
TreeNode *leftChild = sortedListToBST(list, start, mid - 1);
TreeNode *parent = new TreeNode(list->val);
parent->left = leftChild;
list = list->next;
parent->right = sortedListToBST(list, mid + 1, end);
return parent;
}
};
5.4
5.3.4
115
5.4
10.12.5
DFS
3! = 6
root->r->l
r->root->l, r->l->root
5.4.1 Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest
leaf node.
// LeetCode, Minimum Depth of Binary Tree

//
O(n)
O(logn)
class Solution {
public:
int minDepth(const TreeNode *root) {
return minDepth(root, false);
}
private:
static int minDepth(const TreeNode *root, bool hasbrother) {
if (!root) return hasbrother ? INT_MAX : 0;
return 1 + min(minDepth(root->left, root->right != NULL),
minDepth(root->right, root->left != NULL));
}
};
// LeetCode, Minimum Depth of Binary Tree

//
O(n)
O(logn)
class Solution {
public:
int minDepth(TreeNode* root) {
if (root == nullptr)
return 0;
int result = INT_MAX;
stack<pair<TreeNode*, int>> s;
116
s.push(make_pair(root, 1));
auto node = s.top().first;
auto depth = s.top().second;
s.pop();
if (node->left == nullptr && node->right == nullptr)
result = min(result, depth);
if (node->left && result > depth) //
s.push(make_pair(node->left, depth + 1));
if (node->right && result > depth) //
s.push(make_pair(node->right, depth + 1));
}
return result;
}
};
Maximum Depth of Binary Tree
5.4.2
5.4.2 Maximum Depth of Binary Tree
Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the
farthest leaf node.
// LeetCode, Maximum Depth of Binary Tree

//
O(n)
O(logn)
class Solution {
public:
int maxDepth(TreeNode *root) {
if (root == nullptr) return 0;
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
};
117
5.4
Minimum Depth of Binary Tree
5.4.1
5.4.3 Path Sum
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the
values along the path equals the given sum.
For example: Given the below binary tree and sum = 22,
5
/ \
4
8
/
/ \
11 13 4
/ \
\
7
2
1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
true
false
return
// LeetCode, Path Sum

//
O(n)
O(logn)
class Solution {
public:
bool hasPathSum(TreeNode *root, int sum) {
if (root == nullptr) return false;
if (root->left == nullptr && root->right == nullptr) // leaf
return sum == root->val;
return hasPathSum(root->left, sum - root->val)
|| hasPathSum(root->right, sum - root->val);
}
};
Path Sum II
5.4.4
118
5.4.4 Path Sum II
Given a binary tree and a sum, find all root-to-leaf paths where each paths sum equals the given sum.
For example: Given the below binary tree and sum = 22,
5
/ \
4
8
/
/ \
11 13 4
/ \
/ \
7
2 5
1
return
[
[5,4,11,2],
[5,8,4,5]
]
// LeetCode, Path Sum II

//
O(n)
O(logn)
class Solution {
public:
vector<vector<int> > pathSum(TreeNode *root, int sum) {
vector<int> cur; //
pathSum(root, sum, cur, result);
return result;
}
private:
void pathSum(TreeNode *root, int gap, vector<int> &cur,
vector<vector<int> > &result) {
cur.push_back(root->val);
if (root->left == nullptr && root->right == nullptr) { // leaf
if (gap == root->val)
result.push_back(cur);
}
pathSum(root->left, gap - root->val, cur, result);
pathSum(root->right, gap - root->val, cur, result);
return
119
5.4
cur.pop_back();
}
};
Path Sum
5.4.3
5.4.5 Binary Tree Maximum Path Sum
Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree. For example: Given the below binary tree,
1
/ \
2
3
Return 6.
13.2
Array
Binary Tree
Array
Binary Tree
dfs
L
L
R
// LeetCode, Binary Tree Maximum Path Sum

//
O(n)
O(logn)
class Solution {
public:
int maxPathSum(TreeNode *root) {
max_sum = INT_MIN;
dfs(root);
return max_sum;
}
private:
int max_sum;
int dfs(const TreeNode *root) {
int l = dfs(root->left);
int r = dfs(root->right);
Binary Tree
L
0
R
120
int sum = root->val;

if (l > 0) sum += l;
if (r > 0) sum += r;
max_sum = max(max_sum, sum);
return max(r, l) > 0 ? max(r, l) + root->val : root->val;
}
};
return
L->root->R
L->root
R->root
Maximum Subarray
13.2
5.4.6 Populating Next Right Pointers in Each Node
Given a binary tree

struct TreeLinkNode {
int val;
TreeLinkNode *left, *right, *next;
TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
};
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer
should be set to NULL.
Initially, all next pointers are set to NULL.
Note:
You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent
has two children).
For example, Given the following perfect binary tree,
1
\
2
3
/ \ / \
4 5 6 7
/
After calling your function, the tree should look like:

1 -> NULL
/ \
2 -> 3 -> NULL
/ \ / \
4->5->6->7 -> NULL
121
5.4
// LeetCode, Populating Next Right Pointers in Each Node

//
O(n)
O(logn)
class Solution {
public:
connect(root, NULL);
}
private:
void connect(TreeLinkNode *root, TreeLinkNode *sibling) {
if (root == nullptr)
return;
else
root->next = sibling;
connect(root->left, root->right);
if (sibling)
connect(root->right, sibling->left);
else
connect(root->right, nullptr);
}
};
Populating Next Right Pointers in Each Node II
5.1.12
5.4.7 Sum Root to Leaf Numbers
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,
1
/ \
2
3
The root-to-leaf path 1->2 represents the number 12. The root-to-leaf path 1->3 represents the number
13.
Return the sum = 12 + 13 = 25.
122
// LeetCode, Decode Ways

//
O(n)
O(logn)
class Solution {
public:
int sumNumbers(TreeNode *root) {
return dfs(root, 0);
}
private:
int dfs(TreeNode *root, int sum) {
if (root->left == nullptr && root->right == nullptr)
return sum * 10 + root->val;
return dfs(root->left, sum * 10 + root->val) +
dfs(root->right, sum * 10 + root->val);
}
};
6.1 Merge Sorted Array

Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note: You may assume that A has enough space to hold additional elements from B. The number of
elements initialized in A and B are m and n respectively.
//LeetCode, Merge Sorted Array

//
O(m+n)
O(1)
class Solution {
public:
void merge(vector<int>& A, int m, vector<int>& B, int n) {
int ia = m - 1, ib = n - 1, icur = m + n - 1;
while(ia >= 0 && ib >= 0) {
A[icur--] = A[ia] >= B[ib] ? A[ia--] : B[ib--];
}
while(ib >= 0) {
A[icur--] = B[ib--];
}
}
};
Merge Two Sorted Lists

Merge k Sorted Lists
6.2
6.3
123
124
6.2 Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together
the nodes of the first two lists.
//LeetCode, Merge Two Sorted Lists

//
O(min(m,n))
O(1)
class Solution {
public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
if (l1 == nullptr) return l2;
if (l2 == nullptr) return l1;
ListNode dummy(-1);
ListNode *p = &dummy;
for (; l1 != nullptr && l2 != nullptr; p = p->next) {
if (l1->val > l2->val) { p->next = l2; l2 = l2->next; }
else { p->next = l1; l1 = l1->next; }
}
p->next = l1 != nullptr ? l1 : l2;
return dummy.next;
}
};
Merge Sorted Array 6.1

Merge k Sorted Lists
6.3
6.3 Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
6.2
125
6.4 Insertion Sort List
//LeetCode, Merge k Sorted Lists

//
O(n1+n2+...)
O(1)
// TODO:
class Solution {
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
if (lists.size() == 0) return nullptr;
ListNode *p = lists[0];
for (int i = 1; i < lists.size(); i++) {
p = mergeTwoLists(p, lists[i]);
}
return p;
}
// Merge Two Sorted Lists
ListNode *mergeTwoLists(ListNode
ListNode head(-1);
for (ListNode* p = &head; l1
int val1 = l1 == nullptr
int val2 = l2 == nullptr
if (val1 <= val2) {
p->next = l1;
l1 = l1->next;
} else {
p->next = l2;
l2 = l2->next;
}
}
return head.next;
}
};
Merge Sorted Array 6.1

6.2
6.4 Insertion Sort List

Sort a linked list using insertion sort.
*l1, ListNode *l2) {

!= nullptr || l2 != nullptr; p = p->next) {
? INT_MAX : l1->val;
? INT_MAX : l2->val;
126
// LeetCode, Insertion Sort List

//
O(n^2)
O(1)
class Solution {
public:
ListNode *insertionSortList(ListNode *head) {
ListNode dummy(INT_MIN);
//dummy.next = head;
for (ListNode *cur = head; cur != nullptr;) {
auto pos = findInsertPos(&dummy, cur->val);
ListNode *tmp = cur->next;
cur->next = pos->next;
pos->next = cur;
cur = tmp;
}
return dummy.next;
}
ListNode* findInsertPos(ListNode *head, int x) {
ListNode *pre = nullptr;
for (ListNode *cur = head; cur != nullptr && cur->val <= x;
pre = cur, cur = cur->next)
;
return pre;
}
};
Sort List,
6.5
6.5 Sort List

Sort a linked list in O(nlogn) time using constant space complexity.
O(nlogn)
Two Sorted Lists
// LeetCode, Sort List

//
O(nlogn)
class Solution {
O(1)
Merge
127
6.6 First Missing Positive
public:
ListNode *sortList(ListNode *head) {
if (head == NULL || head->next == NULL)return head;
//
ListNode *fast = head, *slow = head;
while (fast->next != NULL && fast->next->next != NULL) {
slow = slow->next;
}
//
fast = slow;
slow = slow->next;
fast->next = NULL;
ListNode *l1 = sortList(head);
ListNode *l2 = sortList(slow);
return mergeTwoLists(l1, l2);
//
//
}
// Merge Two Sorted Lists
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
ListNode dummy(-1);
for (ListNode* p = &dummy; l1 != nullptr || l2 != nullptr; p = p->next) {
int val1 = l1 == nullptr ? INT_MAX : l1->val;
int val2 = l2 == nullptr ? INT_MAX : l2->val;
if (val1 <= val2) {
p->next = l1;
l1 = l1->next;
} else {
p->next = l2;
l2 = l2->next;
}
}
return dummy.next;
}
};
Insertion Sort List
6.4
6.6 First Missing Positive

Given an unsorted integer array, find the first missing positive integer.
For example, Given [1,2,0] return 3, and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
128
(bucket sort)
A[i]!= i+1
A[i]
A[A[i]-1]
A[i]== A[A[i]-1]
// LeetCode, First Missing Positive

//
O(n)
O(1)
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
bucket_sort(nums);
for (int i = 0; i < nums.size(); ++i)
if (nums[i] != (i + 1))
return i + 1;
return nums.size() + 1;
}
private:
static void bucket_sort(vector<int>& A) {
for (int i = 0; i < n; i++) {
while (A[i] != i + 1) {
if (A[i] <= 0 || A[i] > n || A[i] == A[A[i] - 1])
break;
swap(A[i], A[A[i] - 1]);
}
}
}
};
Sort Colors,
6.7
6.7 Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are
adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note: You are not suppose to use the librarys sort function for this problem.
Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
129
6.7 Sort Colors
First, iterate the array counting number of 0s, 1s, and 2s, then overwrite array with total number of 0s,
then 1s and followed by 2s.
Could you come up with an one-pass algorithm using only constant space?
0, 1, 2
(counting sort)
index
O(n)
red
index
blue
index
O(1)
partition
1
// LeetCode, Sort Colors
// Counting Sort
//
O(n)
O(1)
class Solution {
public:
void sortColors(vector<int>& A) {
int counts[3] = { 0 }; //
for (int i = 0; i < A.size(); i++)
counts[A[i]]++;
for (int i = 0, index = 0; i < 3; i++)
for (int j = 0; j < counts[i]; j++)
A[index++] = i;
}
};
2
//
O(n)
O(1)
class Solution {
public:
void sortColors(vector<int>& A) {
//
red
index
blue
int red = 0, blue = A.size() - 1;
for (int i = 0; i < blue + 1;) {
if (A[i] == 0)
swap(A[i++], A[red++]);
else if (A[i] == 2)
swap(A[i], A[blue--]);
else
index
130
i++;
}
}
};
3
// use partition()
//
O(n)
O(1)
class Solution {
public:
void sortColors(vector<int>& nums) {
partition(partition(nums.begin(), nums.end(), bind1st(equal_to<int>(), 0)),
nums.end(), bind1st(equal_to<int>(), 1));
}
};
4
//
partition()
//
O(n)
O(1)
class Solution {
public:
void sortColors(vector<int>& nums) {
partition(partition(nums.begin(), nums.end(), bind1st(equal_to<int>(), 0)),
nums.end(), bind1st(equal_to<int>(), 1));
}
private:
template<typename ForwardIterator, typename UnaryPredicate>
ForwardIterator partition(ForwardIterator first, ForwardIterator last,
UnaryPredicate pred) {
auto pos = first;
for (; first != last; ++first)
if (pred(*first))
swap(*first, *pos++);
return pos;
}
};
First Missing Positive,
6.6
7.1 Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithms runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4].
STL
// LeetCode, Search for a Range

//
STL
//
O(logn)
O(1)
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
const int l = distance(nums.begin(), lower_bound(nums.begin(), nums.end(), target));
const int u = distance(nums.begin(), prev(upper_bound(nums.begin(), nums.end(), target
if (nums[l] != target) // not found
return vector<int> { -1, -1 };
else
return vector<int> { l, u };
}
};
lower_bound
upper_bound
// LeetCode, Search for a Range

//
lower_bound
upper_bound
//
O(logn)
O(1)
class Solution {
131
132
public:
vector<int> searchRange (vector<int>& nums, int target) {
auto lower = lower_bound(nums.begin(), nums.end(), target);
auto uppper = upper_bound(lower, nums.end(), target);
if (lower == nums.end() || *lower != target)

return vector<int> { -1, -1 };
else
return vector<int> {distance(nums.begin(), lower), distance(nums.begin(), prev(upp
}
template<typename ForwardIterator, typename T>
ForwardIterator lower_bound (ForwardIterator first,
ForwardIterator last, T value) {
auto mid = next(first, distance(first, last) / 2);
if (value > *mid)
else
first = ++mid;
last = mid;
}
return first;
}
ForwardIterator upper_bound (ForwardIterator first,
auto mid = next(first, distance (first, last) / 2);
if (value >= *mid)
else
first = ++mid;
last = mid;
//
lower_bound
}
return first;
}
};
Search Insert Position,
7.2
7.2 Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index
where it would be if it were inserted in order.
You may assume no duplicates in the array.
133
7.3 Search a 2D Matrix
Here are few examples.

[1,3,5,6], 5 2
[1,3,5,6], 2 1
[1,3,5,6], 7 4
[1,3,5,6], 0 0
std::lower_bound()
// LeetCode, Search Insert Position

//
lower_bound
//
O(logn)
O(1)
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
return distance(nums.begin(), lower_bound(nums.begin(), nums.end(), target));
}
ForwardIterator lower_bound (ForwardIterator first,
auto mid = next(first, distance(first, last) / 2);
if (value > *mid)
else
first = ++mid;
last = mid;
}
return first;
}
};
Search for a Range,
7.1
7.3 Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m n matrix. This matrix has the following
properties:
Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
134
For example, Consider the following matrix:

[
[1,
3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3, return true.
// LeetCode, Search a 2D Matrix

//
O(logn)
O(1)
class Solution {
public:
bool searchMatrix(const vector<vector<int>>& matrix, int target) {
if (matrix.empty()) return false;
const size_t n = matrix.front().size();
int first = 0;
int last = m * n;
while (first < last) {
int mid = first + (last - first) / 2;
int value = matrix[mid / n][mid % n];
if (value == target)
return true;
else if (value < target)
first = mid + 1;
else
last = mid;
}
return false;
}
};
8.1 Subsets
Given a set of distinct integers, S, return all possible subsets.
Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example, If S = [1,2,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
8.1.1
// LeetCode, Subsets
//
O(2^n)
O(n)
class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
sort(S.begin(), S.end()); //
vector<int> path;
subsets(S, path, 0, result);
return result;
135
136
}
private:
static void subsets(const vector<int> &S, vector<int> &path, int step,
if (step == S.size()) {
result.push_back(path);
return;
}
//
S[step]
subsets(S, path, step + 1, result);
//
S[step]
path.push_back(S[step]);
subsets(S, path, step + 1, result);
path.pop_back();
}
};
bool selected[n]
//
O(2^n)
O(n)
class Solution {
public:
vector<bool> selected(S.size(), false);
subsets(S, selected, 0, result);
return result;
}
private:
static void subsets(const vector<int> &S, vector<bool> &selected, int step,
if (step == S.size()) {
vector<int> subset;
for (int i = 0; i < S.size(); i++) {
if (selected[i]) subset.push_back(S[i]);
}
result.push_back(subset);
return;
}
//
S[step]
selected[step] = false;
subsets(S, selected, step + 1, result);
//
S[step]
selected[step] = true;
subsets(S, selected, step + 1, result);
137
8.1 Subsets
}
};
8.1.2
//
O(2^n)
O(1)
class Solution {
public:
vector<vector<int> > result(1);
for (auto elem : S) {
result.reserve(result.size() * 2);
auto half = result.begin() + result.size();
copy(result.begin(), half, back_inserter(result));
for_each(half, result.end(), [&elem](decltype(result[0]) &e){
e.push_back(elem);
});
}
return result;
}
};
int
S[i]
S={A,B,C,D}
0
B1
B2
int
0110=6
B1 B2 , B1 B2 , B1 B2
//
O(2^n)
O(1)
class Solution {
public:
const size_t n = S.size();
vector<int> v;
for (size_t i = 0; i < 1 << n; i++) {
for (size_t j = 0; j < n; j++) {
if (i & 1 << j) v.push_back(S[j]);
}
result.push_back(v);
v.clear();
{B,C}
138
}
return result;
}
};
Subsets II
8.2
8.2 Subsets II
Given a collection of integers that might contain duplicates, S, return all possible subsets.
Note:
Elements in a subset must be in non-descending order. The solution set must not contain duplicate
subsets. For example, If S = [1,2,2], a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
8.2.1
// LeetCode, Subsets II
//
1
O(2^n)
O(n)
class Solution {
public:
vector<vector<int> > subsetsWithDup(vector<int> &S) {
vector<int> path;
dfs(S, S.begin(), path, result);
8.2 Subsets II
return result;
}
private:
static void dfs(const vector<int> &S, vector<int>::iterator start,
vector<int> &path, vector<vector<int> > &result) {
for (auto i = start; i < S.end(); i++) {
if (i != start && *i == *(i-1)) continue;
path.push_back(*i);
dfs(S, i + 1, path, result);
path.pop_back();
}
}
};
//
2
O(2^n)
O(n)
class Solution {
public:
unordered_map<int, int> count_map; //
for_each(S.begin(), S.end(), [&count_map](int e) {
if (count_map.find(e) != count_map.end())
count_map[e]++;
else
count_map[e] = 1;
});
//
map
pair
vector
vector<pair<int, int> > elems;
for_each(count_map.begin(), count_map.end(),
[&elems](const pair<int, int> &e) {
elems.push_back(e);
});
sort(elems.begin(), elems.end());
vector<int> path; //
subsets(elems, 0, path, result);
return result;
}
private:
static void subsets(const vector<pair<int, int> > &elems,
size_t step, vector<int> &path, vector<vector<int> > &result) {
if (step == elems.size()) {
return;
}
139
140
for (int i = 0; i <= elems[step].second; i++) {

for (int j = 0; j < i; ++j) {
path.push_back(elems[step].first);
}
subsets(elems, step + 1, path, result);
for (int j = 0; j < i; ++j) {
path.pop_back();
}
}
}
};
//
O(2^n)
O(n)
class Solution {
public:
vector<vector<int> > result; //
sort(S.begin(), S.end());
vector<int> count(S.back() - S.front() + 1, 0);
//
for (auto i : S) {
count[i - S[0]]++;
}
//
vector<int> selected(S.back() - S.front() + 1, -1);
subsets(S, count, selected, 0, result);
return result;
}
private:
static void subsets(const vector<int> &S, vector<int> &count,
vector<int> &selected, size_t step, vector<vector<int> > &result) {
if (step == count.size()) {
vector<int> subset;
for(size_t i = 0; i < selected.size(); i++) {
for (int j = 0; j < selected[i]; j++) {
subset.push_back(i+S[0]);
}
}
result.push_back(subset);
return;
}
for (int i = 0; i <= count[step]; i++) {
selected[step] = i;
subsets(S, count, selected, step + 1, result);
}
}
8.2 Subsets II
};
8.2.2
//
//
O(2^n)
O(1)
class Solution {
public:
vector<vector<int> > result(1);
size_t previous_size = 0;
for (size_t i = 0; i < S.size(); ++i) {
const size_t size = result.size();
for (size_t j = 0; j < size; ++j) {
if (i == 0 || S[i] != S[i-1] || j >= previous_size) {
result.push_back(result[j]);
result.back().push_back(S[i]);
}
}
previous_size = size;
}
return result;
}
};
//
O(2^n)
O(1)
class Solution {
public:
//
set
unordered_set
set<vector<int> > result;
const size_t n = S.size();
vector<int> v;
for (size_t i = 0; i < 1U << n; ++i) {
for (size_t j = 0; j < n; ++j) {
if (i & 1 << j)
v.push_back(S[j]);
}
result.insert(v);
v.clear();
}
vector<vector<int> > real_result;
141
142
copy(result.begin(), result.end(), back_inserter(real_result));

return real_result;
}
};
Subsets
8.1
8.3 Permutations
Given a collection of numbers, return all possible permutations.
For example, [1,2,3] have the following permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1],
[3,1,2], and [3,2,1].
8.3.1 next_permutation()
std::next_permutation()
OJ
// LeetCode, Permutations
//
O(n!)
O(1)
class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
sort(num.begin(), num.end());
do {
result.push_back(num);
} while(next_permutation(num.begin(), num.end()));
return result;
}
};
8.3.2
next_permutation()
2.1.12
API
143
8.3 Permutations
//
next_permutation()
//
O(n!)
O(1)
class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
do {
result.push_back(num);
//
2.1.12
next_permutation()
//
} while(next_permutation(num.begin(), num.end()));
return result;
}
};
8.3.3
//
//
O(n!)
O(n)
class Solution {
public:
vector<vector<int> > permute(vector<int>& num) {
dfs(num, path, result);
return result;
}
private:
void dfs(const vector<int>& num, vector<int> &path,
if (path.size() == num.size()) { //
return;
}
144
//
for (auto i : num) {
//
i
path
auto pos = find(path.begin(), path.end(), i);
if (pos == path.end()) {
path.push_back(i);
dfs(num, path, result);
path.pop_back();
}
}
}
};
Next Permutation,
2.1.12
Permutations II,
Combinations,
2.1.13
8.4
8.5
8.4 Permutations II
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example, [1,1,2] have the following unique permutations: [1,1,2], [1,2,1], and [2,1,1].
8.4.1 next_permutation()
8.4.2
next_permutation()
8.4.3
permute()
8.4 Permutations II
// LeetCode, Permutations II
//
O(n!)
O(n)
class Solution {
public:
vector<vector<int> > permuteUnique(vector<int>& num) {
unordered_map<int, int> count_map; //
for_each(num.begin(), num.end(), [&count_map](int e) {
if (count_map.find(e) != count_map.end())
count_map[e]++;
else
count_map[e] = 1;
});
//
map
pair
vector
vector<pair<int, int> > elems;
for_each(count_map.begin(), count_map.end(),
[&elems](const pair<int, int> &e) {
elems.push_back(e);
});
vector<vector<int>> result; //
vector<int> p; //
n = num.size();
permute(elems.begin(), elems.end(), p, result);
return result;
}
private:
size_t n;
typedef vector<pair<int, int> >::const_iterator Iter;
void permute(Iter first, Iter last, vector<int> &p,
if (n == p.size()) { //
result.push_back(p);
}
//
for (auto i = first; i != last; i++) {
int count = 0; //
*i
p
for (auto j = p.begin(); j != p.end(); j++) {
if (i->first == *j) {
count ++;
}
}
if (count < i->second) {
p.push_back(i->first);
permute(first, last, p, result);
145
146
p.pop_back(); //
}
}
}
};
Next Permutation,
2.1.12
Permutations,
Combinations,
2.1.13
8.3
8.5
8.5 Combinations
Given two integers n and k, return all possible combinations of k numbers out of 1...n.
For example, If n = 4 and k = 2, a solution is:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
8.5.1
// LeetCode, Combinations
//
//
O(n!)
O(n)
class Solution {
public:
vector<vector<int> > combine(int n, int k) {
vector<int> path;
dfs(n, k, 1, 0, path, result);
return result;
}
private:
// start
, cur
static void dfs(int n, int k, int start, int cur,
vector<int> &path, vector<vector<int> > &result) {
if (cur == k) {
8.6 Letter Combinations of a Phone Number
}
for (int i = start; i <= n; ++i) {
path.push_back(i);
dfs(n, k, i + 1, cur + 1, path, result);
path.pop_back();
}
}
};
8.5.2
// LeetCode, Combinations
// use prev_permutation()
//
O((n-k)!)
O(n)
class Solution {
public:
vector<vector<int> > combine(int n, int k) {
vector<int> values(n);
iota(values.begin(), values.end(), 1);
vector<bool> select(n, false);
fill_n(select.begin(), k, true);
do{
vector<int> one(k);
for (int i = 0, index = 0; i < n; ++i)
if (select[i])
one[index++] = values[i];
result.push_back(one);
} while(prev_permutation(select.begin(), select.end()));
return result;
}
};
Next Permutation,
2.1.12
Permutations,
Permutations II,
2.1.13
8.3
8.4

Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
147
148
8-1
Phone Keyboard
Input:Digit string "23"

Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note: Although the above answer is in lexicographical order, your answer could be in any order you
want.
8.6.1
// LeetCode, Letter Combinations of a Phone Number
//
O(3^n)
O(n)
class Solution {
public:
const vector<string> keyboard { " ", "", "abc", "def", // '0','1','2',...
"ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
vector<string> letterCombinations (const string &digits) {
if (digits.empty()) return result;
dfs(digits, 0, "", result);
return result;
}
void dfs(const string &digits, size_t cur, string path,
vector<string> &result) {
if (cur == digits.size()) {
return;
}
for (auto c : keyboard[digits[cur] - '0']) {
dfs(digits, cur + 1, path + c, result);
}
149
}
};
8.6.2
// LeetCode, Letter Combinations of a Phone Number
//
O(3^n)
O(1)
class Solution {
public:
const vector<string> keyboard { " ", "", "abc", "def", // '0','1','2',...
"ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
vector<string> letterCombinations (const string &digits) {
if (digits.empty()) return vector<string>();
vector<string> result(1, "");
for (auto d : digits) {
const size_t n = result.size();
const size_t m = keyboard[d - '0'].size();
result.resize(n * m);
for (size_t i = 0; i < m; ++i)
copy(result.begin(), result.begin() + n, result.begin() + n * i);
for (size_t i = 0; i < m; ++i) {
auto begin = result.begin();
for_each(begin + n * i, begin + n * (i+1), [&](string &s) {
s += keyboard[d - '0'][i];
});
}
}
return result;
}
};
A*
9.1 Word Ladder

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence
from start to end, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example, Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.
Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
150
151
9.1 Word Ladder
//LeetCode, Word Ladder

//
O(n)
struct state_t {
string word;
int level;
O(n)
state_t() { word = ""; level = 0; }

state_t(const string& word, int level) {
this->word = word;
this->level = level;
}
bool operator==(const state_t &other) const {
return this->word == other.word;
}
};
namespace std {
template<> struct hash<state_t> {
public:
size_t operator()(const state_t& s) const {
return str_hash(s.word);
}
private:
std::hash<std::string> str_hash;
};
}
class Solution {
public:
int ladderLength(const string& start, const string &end,
const unordered_set<string> &dict) {
queue<state_t> q;
unordered_set<state_t> visited; //
auto state_is_valid = [&](const state_t& s) {
return dict.find(s.word) != dict.end() || s.word == end;
};
auto state_is_target = [&](const state_t &s) {return s.word == end; };
auto state_extend = [&](const state_t &s) {
unordered_set<state_t> result;
for (size_t i = 0; i < s.word.size(); ++i) {
state_t new_state(s.word, s.level + 1);
for (char c = 'a'; c <= 'z'; c++) {
//
if (c == new_state.word[i]) continue;
swap(c, new_state.word[i]);
152
if (state_is_valid(new_state) &&
visited.find(new_state) == visited.end()) {
result.insert(new_state);
}
swap(c, new_state.word[i]); //
}
}
return result;
};
state_t start_state(start, 0);
q.push(start_state);
visited.insert(start_state);
while (!q.empty()) {
//
const auto& pop()
//
const auto state = q.front();
q.pop();
if (state_is_target(state)) {
return state.level + 1;
}
const auto& new_states = state_extend(state);
for (const auto& new_state : new_states) {
q.push(new_state);
visited.insert(new_state);
}
}
return 0;
}
};
//LeetCode, Word Ladder

//
O(n)
O(n)
class Solution {
public:
int ladderLength(const string& start, const string &end,
const unordered_set<string> &dict) {
queue<string> current, next;
//
unordered_set<string> visited; //
int level = -1;
//
auto state_is_valid = [&](const string& s) {

return dict.find(s) != dict.end() || s == end;
};
auto state_is_target = [&](const string &s) {return s == end;};
auto state_extend = [&](const string &s) {
unordered_set<string> result;
153
9.1 Word Ladder
for (size_t i = 0; i < s.size(); ++i) {

string new_word(s);
for (char c = 'a'; c <= 'z'; c++) {
//
if (c == new_word[i]) continue;
swap(c, new_word[i]);
if (state_is_valid(new_word) &&
visited.find(new_word) == visited.end()) {
result.insert(new_word);
}
swap(c, new_word[i]); //
}
}
return result;
};
current.push(start);
visited.insert(start);
++level;
//
const auto& pop()
//
const auto state = current.front();
current.pop();
return level + 1;
}
next.push(new_state);
}
}
}
return 0;
}
};
Word Ladder II
9.2
154
9.2 Word Ladder II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start
to end, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example, Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
Return
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
Note:
All words have the same length.
All words contain only lowercase alphabetic characters.
Word Ladder
//LeetCode, Word Ladder II

//
O(n)
struct state_t {
string word;
int level;
BFS
O(n)
state_t() { word = ""; level = 0; }

state_t(const string& word, int level) {
this->word = word;
this->level = level;
}
155
9.2 Word Ladder II

return this->word == other.word;
}
};
namespace std {
public:
size_t operator()(const state_t& s) const {
return str_hash(s.word);
}
private:
std::hash<std::string> str_hash;
};
}
class Solution {
public:
vector<vector<string> > findLadders(const string& start,
const string& end, const unordered_set<string> &dict) {
queue<state_t> q;
unordered_map<state_t, vector<state_t> > father; // DAG
auto state_is_valid = [&](const state_t& s) {
return dict.find(s.word) != dict.end() || s.word == end;
};
auto state_is_target = [&](const state_t &s) {return s.word == end; };
for (size_t i = 0; i < s.word.size(); ++i) {
state_t new_state(s.word, s.level + 1);
for (char c = 'a'; c <= 'z'; c++) {
//
if (c == new_state.word[i]) continue;
swap(c, new_state.word[i]);
if (state_is_valid(new_state)) {
auto visited_iter = visited.find(new_state);
if (visited_iter != visited.end()) {
if (visited_iter->level < new_state.level) {
// do nothing
} else if (visited_iter->level == new_state.level) {
} else { // not possible
throw std::logic_error("not possible to get here");
}
} else {
156
}
}
swap(c, new_state.word[i]); //
}
}
return result;
};
vector<vector<string>> result;
//
const auto& pop()
//
q.pop();
//
//
if (!result.empty() && state.level + 1 > result[0].size()) break;
vector<string> path;
gen_path(father, start_state, state, path, result);
continue;
}
//
A
B
//
q
// visited.insert(state);
//
if (visited.find(new_state) == visited.end()) {
q.push(new_state);
}
father[new_state].push_back(state);
}
}
return result;
}
private:
void gen_path(unordered_map<state_t, vector<state_t> > &father,
const state_t &start, const state_t &state, vector<string> &path,
vector<vector<string> > &result) {
path.push_back(state.word);
if (state == start) {
if (!result.empty()) {
if (path.size() < result[0].size()) {
157
9.2 Word Ladder II
result.clear();
reverse(result.back().begin(), result.back().end());
} else if (path.size() == result[0].size()) {
throw std::logic_error("not possible to get here ");
}
} else {
}
} else {
for (const auto& f : father[state]) {
gen_path(father, start, f, path, result);
}
}
path.pop_back();
}
};

//
O(n)
O(n)
class Solution {
public:
const string& end, const unordered_set<string> &dict) {
//
unordered_set
//
vector,
next
//
father
next
unordered_set<string> current, next;
unordered_set<string> visited; //
unordered_map<string, vector<string> > father; // DAG
int level = -1;
//
auto state_is_valid = [&](const string& s) {

return dict.find(s) != dict.end() || s == end;
};
auto state_is_target = [&](const string &s) {return s == end;};
auto state_extend = [&](const string &s) {
unordered_set<string> result;
string new_word(s);
for (char c = 'a'; c <= 'z'; c++) {
//
158
if (state_is_valid(new_word) &&
visited.find(new_word) == visited.end()) {
result.insert(new_word);
}
}
}
return result;
};
vector<vector<string> > result;
current.insert(start);
++ level;
//
//
if (!result.empty() && level+1 > result[0].size()) break;
// 1.
visited,
// 2.
current
visited,
//
for (const auto& state : current)
visited.insert(state);
for (const auto& state : current) {
gen_path(father, path, start, state, result);
continue;
}
const auto new_states = state_extend(state);
next.insert(new_state);
}
}
current.clear();
swap(current, next);
}
return result;
}
private:
void gen_path(unordered_map<string, vector<string> > &father,
vector<string> &path, const string &start, const string &word,
vector<vector<string> > &result) {
path.push_back(word);
if (word == start) {
159
9.2 Word Ladder II

result.clear();
} else if(path.size() == result[0].size()) {
} else {
// not possible
}
} else {
}
} else {
for (const auto& f : father[word]) {
gen_path(father, path, start, f, result);
}
}
path.pop_back();
}
};
dict

//
O(n)
O(n)
class Solution {
public:
const string &end, const unordered_set<string> &dict) {
const auto& g = build_graph(dict);
vector<state_t*> pool;
queue<state_t*> q; //
// value
unordered_map<string, int> visited;
auto state_is_target = [&](const state_t *s) {return s->word == end; };
q.push(create_state(nullptr, start, 0, pool));
state_t* state = q.front();
q.pop();
//
//
if (!result.empty() && state->level+1 > result[0].size()) break;
160
const auto& path = gen_path(state);

if (result.empty()) {
} else {
result.clear();
} else if (path.size() == result[0].size()) {
} else {
// not possible
}
}
continue;
}
visited[state->word] = state->level;
//
auto iter = g.find(state->word);
if (iter == g.end()) continue;
for (const auto& neighbor : iter->second) {
auto visited_iter = visited.find(neighbor);
if (visited_iter != visited.end() &&
visited_iter->second < state->level + 1) {
continue;
}
q.push(create_state(state, neighbor, state->level + 1, pool));
}
}
// release all states
for (auto state : pool) {
delete state;
}
return result;
}
private:
struct state_t {
state_t* father;
string word;
int level; //
state_t(state_t* father_, const string& word_, int level_) :

father(father_), word(word_), level(level_) {}
};
state_t* create_state(state_t* parent, const string& value,
int length, vector<state_t*>& pool) {
161
9.2 Word Ladder II
state_t* node = new state_t(parent, value, length);

pool.push_back(node);
return node;
}
vector<string> gen_path(const state_t* node) {
while(node != nullptr) {
path.push_back(node->word);
node = node->father;
}
reverse(path.begin(), path.end());
return path;
}
unordered_map<string, unordered_set<string> > build_graph(
const unordered_set<string>& dict) {
unordered_map<string, unordered_set<string> > adjacency_list;
for (const auto& word : dict) {
for (size_t i = 0; i < word.size(); ++i) {
string new_word(word);
for (char c = 'a'; c <= 'z'; c++) {
//
if ((dict.find(new_word) != dict.end())) {
auto iter = adjacency_list.find(word);
if (iter != adjacency_list.end()) {
iter->second.insert(new_word);
} else {
adjacency_list.insert(pair<string,
unordered_set<string>>(word, unordered_set<string>()));
adjacency_list[word].insert(new_word);
}
}
}
}
}
return adjacency_list;
}
};
Word Ladder
9.1
162
9.3 Surrounded Regions

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region .
For example,
X
X
X
X
X
O
X
O
X
O
O
X
X
X
X
X
After running your function, the board should be:

X
X
X
X
X
X
X
O
X
X
X
X
X
X
X
X
'O'
// LeetCode, Surrounded Regions

// BFS
O(n)
O(n)
class Solution {
public:
void solve(vector<vector<char>> &board) {
if (board.empty()) return;
const int m = board.size();
const int n = board[0].size();
for (int i = 0; i < n; i++) {
bfs(board, 0, i);
bfs(board, m - 1, i);
}
for (int j = 1; j < m - 1; j++) {
bfs(board, j, 0);
bfs(board, j, n - 1);
}
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (board[i][j] == 'O')
board[i][j] = 'X';
else if (board[i][j] == '+')
board[i][j] = 'O';
}
private:
void bfs(vector<vector<char>> &board, int i, int j) {
9.3 Surrounded Regions
typedef pair<int, int> state_t;

queue<state_t> q;
auto state_is_valid = [&](const state_t &s) {
const int x = s.first;
const int y = s.second;
if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] != 'O')
return false;
return true;
};
vector<state_t> result;
const int x = s.first;
const int y = s.second;
//
const state_t new_states[4] = {{x-1,y}, {x+1,y},
{x,y-1}, {x,y+1}};
for (int k = 0; k < 4; ++k) {
if (state_is_valid(new_states[k])) {
//
board[new_states[k].first][new_states[k].second] = '+';
result.push_back(new_states[k]);
}
}
return result;
};
state_t start = { i, j };
if (state_is_valid(start)) {
board[i][j] = '+';
q.push(start);
}
auto cur = q.front();
q.pop();
auto new_states = state_extend(cur);
for (auto s : new_states) q.push(s);
}
}
};
163
164
9.4
9.4.1
DAG
9.4.2
1.
(a)
(b)
i.
ii.
4
2.
3.
4.
BFS
(a)
(b)
DAG
visited
visited
(c)
i.
unordered_-
ii.
set
head
next
??
165
9.4
iii.
5.
9.4.3
hashset
queue
vector
state_t
1.
level
level
queue
A*
priority_queue
current, next
2.
level
level
level
(bool visited[STATE_MAX]
hashset
visited(STATE_MAX, false))
STL
STL
set
vector<bool>
unordered_set
unordered_map<state_t, state_t > father

(state_t nodes[STATE_-
STATE_MAX
MAX])
bfs_common.h
/**
*/
struct state_t {
int data1; /**
int data2; /**
// dataN;
/**
int action; /**
int level; /**
. */
. */
*/
. */
0
-1
*/

return true; //
}
};
//
hash
//
1
hash
namespace std {
166
size_t operator()(const state_t & x) const {

return 0; //
}
};
}
//
2
hash
class Hasher {
public:
Hasher(int _m) : m(_m) {};
size_t operator()(const state_t &s) const {
return 0; //
}
private:
int m; //
};
/**
* @brief
.
* @param[in] father
* @param[in] target
* @return
target
*/
vector<state_t> gen_path(const unordered_map<state_t, state_t> &father,
const state_t &target) {
vector<state_t> path;
path.push_back(target);
for (state_t cur = target; father.find(cur) != father.end();
cur = father.at(cur))
path.push_back(cur);
reverse(path.begin(), path.end());
return path;
}
/**
*
.
* @param[in] father
* @param[in] start
* @param[in] state
* @return
*/
void gen_path(unordered_map<state_t, vector<state_t> > &father,
const string &start, const state_t& state, vector<state_t> &path,
vector<vector<state_t> > &result) {
path.push_back(state);
if (state == start) {
result.clear();
167
9.4
} else if(path.size() == result[0].size()) {

} else {
// not possible
}
} else {
}
} else {
for (const auto& f : father[state]) {
gen_path(father, start, f, path, result);
}
}
path.pop_back();
}
bfs_common.h
bfs_template.cpp
#include "bfs_common.h"
/**
* @brief
.
* @param[in] start
* @param[in] data
* @return
*/
vector<state_t> bfs(state_t &start, const vector<vector<int>> &grid) {
queue<state_t> q; //
unordered_map<state_t, state_t> father; //
//
auto state_is_valid = [&](const state_t &s) { /*...*/ };
//
auto state_is_target = [&](const state_t &s) { /*...*/ };
//
for (/*...*/) {
const state_t new_state = /*...*/;
visited.find(new_state) != visited.end()) {
}
}
168
return result;
};
assert (start.level == 0);
q.push(start);
//
const auto& pop()
//
const state_t state = q.front();
q.pop();
//
return return gen_path(father, target); //
// return state.level + 1; //
}
//
vector<state_t> new_states = state_extend(state);
q.push(new_state);
father[new_state] = state; //
// visited.insert(state); //
//
q
//
visited
//
, visited.insert(start)
}
visited
while
}
return vector<state_t>();
//return 0;
}
bfs_template.cpp
bfs_template1.cpp
/**
* @brief
.
* @param[in] start
* @param[in] data
* @return
*/
vector<state_t> bfs(const state_t &start, const type& data) {
queue<state_t> next, current; //
unordered_map<state_t, state_t> father; //
int level = -1;
//
//
169
9.4

//
//
for (/*...*/) {
}
}
return result;
};
current.push(start);
++level;
//
const auto& pop()
//
const auto state = current.front();
current.pop();
return return gen_path(father, state); //
// return state.level + 1; //
}
next.push(new_state);
father[new_state] = state;
// visited.insert(state); //
visited
//
current
//
visited
//
, visited.insert(start)
}
while
}
swap(next, current); //!!!
}
return vector<state_t>();
// return 0;
}
bfs_template1.cpp
170
bfs_template.cpp
/**
* @brief
.
* @param[in] start
* @param[in] data
* @return
*/
vector<vector<state_t> > bfs(const state_t &start, const type& data) {
queue<state_t> q;
auto state_is_valid = [&](const state_t& s) { /*...*/ };
for (/*...*/) {
if (state_is_valid(new_state)) {
auto visited_iter = visited.find(new_state);
if (visited_iter != visited.end()) {
if (visited_iter->level < new_state.level) {
// do nothing
} else if (visited_iter->level == new_state.level) {
}
} else {
}
}
}
return result;
};
//
const auto& pop()
//
q.pop();
//
//
171
9.4
if (!result.empty() && state.level + 1 > result[0].size()) break;

gen_path(father, start_state, state, path, result);
continue;
}
//
A
B
//
q
// visited.insert(state);
//
if (visited.find(new_state) == visited.end()) {
q.push(new_state);
}
}
}
return result;
}
bfs_template.cpp
bfs_template.cpp
/**
* @brief
.
* @param[in] start
* @param[in] data
* @return
*/
vector<vector<state_t> > bfs(const state_t &start, const type& data) {
//
unordered_set
//
vector,
next
//
father
next
unordered_set<string> current, next;
int level = -1;
//
//
//
//
172

for (/*...*/) {
}
}
return result;
};
vector<vector<state_t> > result;
current.insert(start);
++ level;
//
//
if (!result.empty() && level+1 > result[0].size()) break;
// 1.
visited,
// 2.
current
visited,
//
for (const auto& state : current)
for (const auto& state : current) {
gen_path(father, path, start, state, result);
continue;
}
const auto new_states = state_extend(state);
next.insert(new_state);
}
}
current.clear();
swap(current, next);
}
return result;
}
bfs_template.cpp
10
10.1 Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab", Return
[
["aa","b"],
["a","a","b"]
]
n1
O(2n1 )
1
//LeetCode, Palindrome Partitioning
//
O(2^n)
O(n)
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<string> path; //
partition
dfs(s, path, result, 0, 1);
return result;
}
// prev
, start
void dfs(string &s, vector<string>& path,
vector<vector<string>> &result, size_t prev, size_t start) {
if (start == s.size()) { //
if (isPalindrome(s, prev, start - 1)) { //
path.push_back(s.substr(prev, start - prev));
173
174
10
path.pop_back();
}
return;
}
//
dfs(s, path, result, prev, start + 1);
//
[prev, start-1]
if (isPalindrome(s, prev, start - 1)) {
//
path.push_back(s.substr(prev, start - prev));
dfs(s, path, result, start, start + 1);
path.pop_back();
}
}
bool isPalindrome(const string &s, int start, int end) {
while (start < end && s[start] == s[end]) {
++start;
--end;
}
return start >= end;
}
};
2
Combination Sum, Combination Sum II
//LeetCode, Palindrome Partitioning
//
O(2^n)
O(n)
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<string> path; //
partition
DFS(s, path, result, 0);
return result;
}
//
s[start]
partition
void DFS(string &s, vector<string>& path,
vector<vector<string>> &result, int start) {
if (start == s.size()) {
return;
}
for (int i = start; i < s.size(); i++) {
if (isPalindrome(s, start, i)) { //
i
path.push_back(s.substr(start, i - start + 1));
DFS(s, path, result, i + 1); //
path.pop_back(); //
}
}
175
10.1 Palindrome Partitioning
}
bool isPalindrome(const string &s, int start, int end) {
while (start < end && s[start] == s[end]) {
++start;
--end;
}
return start >= end;
}
};
// LeetCode, Palindrome Partitioning

//
O(n^2)
O(1)
class Solution {
public:
vector<vector<string> > partition(string s) {
bool p[n][n]; // whether s[i,j] is palindrome
fill_n(&p[0][0], n * n, false);
for (int i = n - 1; i >= 0; --i)
for (int j = i; j < n; ++j)
p[i][j] = s[i] == s[j] && ((j - i < 2) || p[i + 1][j - 1]);
vector<vector<string> > sub_palins[n]; // sub palindromes of s[0,i]
for (int i = n - 1; i >= 0; --i) {
for (int j = i; j < n; ++j)
if (p[i][j]) {
const string palindrome = s.substr(i, j - i + 1);
if (j + 1 < n) {
for (auto v : sub_palins[j + 1]) {
v.insert(v.begin(), palindrome);
sub_palins[i].push_back(v);
}
} else {
sub_palins[i].push_back(vector<string> { palindrome });
}
}
}
return sub_palins[0];
}
};
Palindrome Partitioning II
13.3
176
10
10.2 Unique Paths

A robot is located at the top-left corner of a m n grid (marked Start in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the
bottom-right corner of the grid (marked Finish in the diagram below).
How many possible unique paths are there?
10-1 Above is a 3 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
10.2.1
// LeetCode, Unique Paths

//
//
O(n^4)
O(n)
class Solution {
public:
int uniquePaths(int m, int n) {
if (m < 1 || n < 1) return 0; //
if (m == 1 && n == 1) return 1; //
return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
}
};
10.2.2
177
10.2 Unique Paths

//
+
//
O(n^2)
O(n^2)
class Solution {
public:
// f[x][y]
(0,0)
(x,y)
f = vector<vector<int> >(m, vector<int>(n, 0));
f[0][0] = 1;
return dfs(m - 1, n - 1);
}
private:
vector<vector<int> > f; //
int dfs(int x, int y) {
if (x < 0 || y < 0) return 0; //
if (x == 0 && y == 0) return f[0][0]; //
if (f[x][y] > 0) {
return f[x][y];
} else {
return f[x][y] = dfs(x - 1, y) +
}
dfs(x, y - 1);
}
};
10.2.3
f[i][j]
(1, 1)
(i, j)
f[i][j]=f[i-1][j]+f[i][j-1]

//
//
O(n^2)
O(n)
class Solution {
public:
vector<int> f(n, 0);
f[0] = 1;
for (int i = 0; i < m; i++) {
for (int j = 1; j < n; j++) {
//
f[j]
f[j]
//
f[j]
f[j]
f[j] = f[j] + f[j - 1];
}
f[i][j]
f[i-1][j]
178
10
}
return f[n - 1];
}
};
10.2.4
m
m+n2
m1
m+n2
m1
m1
Cm+n2

//
class Solution {
public:
typedef long long int64_t;
//
, n!/(start-1)!
n*(n-1)...start
static int64_t factor(int n, int start = 1) {
int64_t ret = 1;
for(int i = start; i <= n; ++i)
ret *= i;
return ret;
}
//
C_n^k
static int64_t combination(int n, int k) {
//
if (k == 0) return 1;
if (k == 1) return n;
n >= 1
int64_t ret = factor(n, k+1);

ret /= factor(n - k);
return ret;
}
// max
n
k
combination()
return combination(m+n-2, max(m-1, n-1));
}
};
Unique Paths II
Minimum Path Sum,
10.3
13.8
179
10.3 Unique Paths II
10.3 Unique Paths II

Follow up for Unique Paths:
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
For example,
There is one obstacle in the middle of a 3 3 grid as illustrated below.
[
[0,0,0],
[0,1,0],
[0,0,0]
]
The total number of unique paths is 2.
Note: m and n will be at most 100.
10.3.1
// LeetCode, Unique Paths II

//
+
class Solution {
public:
int uniquePathsWithObstacles(const vector<vector<int> >& obstacleGrid) {
const int m = obstacleGrid.size();
const int n = obstacleGrid[0].size();
if (obstacleGrid[0][0] || obstacleGrid[m - 1][n - 1]) return 0;
f = vector<vector<int> >(m, vector<int>(n, 0));
f[0][0] = obstacleGrid[0][0] ? 0 : 1;
return dfs(obstacleGrid, m - 1, n - 1);
}
private:
vector<vector<int> > f;
//
// @return
(0, 0)
(x, y)
int dfs(const vector<vector<int> >& obstacleGrid,
int x, int y) {
if (x < 0 || y < 0) return 0; //
// (x,y)
if (obstacleGrid[x][y]) return 0;
if (x == 0 and y == 0) return f[0][0]; //
180
10
if (f[x][y] > 0) {
return f[x][y];
} else {
return f[x][y] = dfs(obstacleGrid, x - 1, y) +
dfs(obstacleGrid, x, y - 1);
}
}
};
10.3.2
// LeetCode, Unique Paths II

//
//
O(n^2)
O(n)
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
const int m = obstacleGrid.size();
const int n = obstacleGrid[0].size();
if (obstacleGrid[0][0] || obstacleGrid[m-1][n-1]) return 0;
f[0] = obstacleGrid[0][0] ? 0 : 1;
for (int i = 0; i < m; i++) {
f[0] = f[0] == 0 ? 0 : (obstacleGrid[i][0] ? 0 : 1);
for (int j = 1; j < n; j++)
f[j] = obstacleGrid[i][j] ? 0 : (f[j] + f[j - 1]);
}
return f[n - 1];
}
};
Unique Paths
10.2
Minimum Path Sum,
13.8
181
10.4 N-Queens
10.4 N-Queens
The n-queens puzzle is the problem of placing n queens on an n n chessboard such that no two queens
attack each other.
10-2 Eight Queens

Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens placement, where 'Q' and '.'
both indicate a queen and an empty space respectively.
For example, There exist two distinct solutions to the 4-queens puzzle:
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.",
"Q...",
"...Q",
".Q.."]
// Solution 2
182
10
vector<int> C(n, 0), C[i]
1
// LeetCode, N-Queens
//
+
//
O(n!*n)
O(n)
class Solution {
public:
vector<vector<string> > solveNQueens(int n) {
vector<int> C(n, -1); // C[i]
i
dfs(C, result, 0);
return result;
}
private:
void dfs(vector<int> &C, vector<vector<string> > &result, int row) {
const int N = C.size();
if (row == N) { //
vector<string> solution;
for (int i = 0; i < N; ++i) {
string s(N, '.');
for (int j = 0; j < N; ++j) {
if (j == C[i]) s[j] = 'Q';
}
solution.push_back(s);
}
result.push_back(solution);
return;
}
for (int j = 0; j < N; ++j) { //
const bool ok = isValid(C, row, j);
if (!ok) continue; //
//
C[row] = j;
dfs(C, result, row + 1);
//
// C[row] = -1;
}
}
/**
*
(row, col)
.
*
* @param C
* @param row
* @param col
* @return
*/
bool isValid(const vector<int> &C, int row, int col) {
(i, C[i])
183
10.4 N-Queens
for (int i = 0; i < row; ++i) {

//
if (C[i] == col) return false;
//
if (abs(i - row) == abs(C[i] - col)) return false;
}
return true;
}
};
2
// LeetCode, N-Queens
//
+
//
O(n!)
O(n)
class Solution {
public:
vector<vector<string> > solveNQueens(int n) {
this->columns = vector<bool>(n, false);
this->main_diag = vector<bool>(2 * n - 1, false);
this->anti_diag = vector<bool>(2 * n - 1, false);
vector<int> C(n, -1); // C[i]
dfs(C, result, 0);
return result;
}
private:
//
vector<bool> columns; //
vector<bool> main_diag; //
vector<bool> anti_diag; //
void dfs(vector<int> &C, vector<vector<string> > &result, int row) {
if (row == N) { //
vector<string> solution;
for (int i = 0; i < N; ++i) {
string s(N, '.');
for (int j = 0; j < N; ++j) {
if (j == C[i]) s[j] = 'Q';
}
solution.push_back(s);
}
result.push_back(solution);
return;
}
for (int j = 0; j < N; ++j) { //
const bool ok = !columns[j] && !main_diag[row - j + N - 1]
!anti_diag[row + j];
//
&&
184
10
C[row] = j;
columns[j] = main_diag[row - j + N - 1] = anti_diag[row + j] = true;
dfs(C, result, row + 1);
//
// C[row] = -1;
columns[j] = main_diag[row - j + N - 1] = anti_diag[row + j] = false;
}
}
};
N-Queens II
10.5
10.5 N-Queens II
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
1
// LeetCode, N-Queens II
//
+
//
O(n!*n)
class Solution {
public:
int totalNQueens(int n) {
this->count = 0;
vector<int> C(n, 0);
dfs(C, 0);
return this->count;
O(n)
// C[i]
}
private:
int count; //
void dfs(vector<int> &C, int row) {
if (row == N) { //
++this->count;
return;
185
10.5 N-Queens II
}
for (int j = 0; j < N; ++j) { //
const bool ok = isValid(C, row, j);
//
C[row] = j;
dfs(C, row + 1);
//
// C[row] = -1;
}
}
/**
*
(row, col)
.
*
* @param C
* @param row
* @param col
* @return
*/
bool isValid(const vector<int> &C, int row, int col) {
for (int i = 0; i < row; ++i) {
//
if (C[i] == col) return false;
//
if (abs(i - row) == abs(C[i] - col)) return false;
}
return true;
}
};
2
// LeetCode, N-Queens II
//
+
//
O(n!)
O(n)
class Solution {
public:
int totalNQueens(int n) {
this->count = 0;
this->columns = vector<bool>(n, false);
this->main_diag = vector<bool>(2 * n - 1, false);
this->anti_diag = vector<bool>(2 * n - 1, false);
vector<int> C(n, 0);
dfs(C, 0);
return this->count;
// C[i]
}
private:
int count; //
//
vector<bool> columns; //
vector<bool> main_diag; //
186
10
vector<bool> anti_diag;
//
void dfs(vector<int> &C, int row) {

if (row == N) { //
++this->count;
return;
}
for (int j = 0; j < N; ++j) { //

const bool ok = !columns[j] &&
!main_diag[row - j + N] &&
!anti_diag[row + j];
//
C[row] = j;
columns[j] = main_diag[row - j + N] =
anti_diag[row + j] = true;
dfs(C, row + 1);
//
// C[row] = -1;
columns[j] = main_diag[row - j + N] =
anti_diag[row + j] = false;
}
}
};
N-Queens
10.4
10.6 Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example: Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
// LeetCode, Restore IP Addresses

//
O(n^4)
O(n)
class Solution {
187
10.6 Restore IP Addresses
public:
vector<string> restoreIpAddresses(const string& s) {
vector<string> ip; //
dfs(s, ip, result, 0);
return result;
}
/**
* @brief
* @param[in] s
* @param[out] ip
* @param[out] result
IP
* @param[in] start
index
* @return
*/
void dfs(string s, vector<string>& ip, vector<string> &result,
size_t start) {
if (ip.size() == 4 && start == s.size()) { //
result.push_back(ip[0] + '.' + ip[1] + '.' + ip[2] + '.' + ip[3]);

return;
}
if (s.size()
return;
if (s.size()
return;
- start > (4 - ip.size()) * 3)

//
- start < (4 - ip.size()))
//
int num = 0;
for (size_t i = start; i < start + 3; i++) {
num = num * 10 + (s[i] - '0');
if (num < 0 || num > 255) continue;
//
ip.push_back(s.substr(start, i - start + 1));

dfs(s, ip, result, i + 1);
ip.pop_back();
if (num == 0) break;
}
}
};
//
188
10
10.7 Combination Sum

Given a set of candidate numbers (C) and a target number (T ), find all unique combinations in C where
the candidate numbers sums to T .
The same repeated number may be chosen from C unlimited number of times.
Note:
All numbers (including target) will be positive integers.
Elements in a combination (a1 , a2 , ..., ak ) must be in non-descending order. (ie, a1 a2 ... ak ).
The solution set must not contain duplicate combinations.
For example, given candidate set 2,3,6,7 and target 7, A solution set is:
[7]
[2, 2, 3]
// LeetCode, Combination Sum

//
O(n!)
O(n)
class Solution {
public:
vector<vector<int> > combinationSum(vector<int> &nums, int target) {
vector<vector<int> > result; //
dfs(nums, path, result, target, 0);
return result;
}
private:
void dfs(vector<int>& nums, vector<int>& path, vector<vector<int> > &result,
int gap, int start) {
if (gap == 0) { //
return;
}
for (size_t i = start; i < nums.size(); i++) { //
if (gap < nums[i]) return; //
path.push_back(nums[i]); //
dfs(nums, path, result, gap - nums[i], i);
path.pop_back(); //
}
189
10.8 Combination Sum II
}
};
Combination Sum II
10.8
10.8 Combination Sum II

Given a collection of candidate numbers (C) and a target number (T ), find all unique combinations in
C where the candidate numbers sums to T .
Each number in C may only be used once in the combination.
Note:
All numbers (including target) will be positive integers.
Elements in a combination (a1 , a2 , ..., ak ) must be in non-descending order. (ie, a1 > a2 > ... > ak ).
The solution set must not contain duplicate combinations.
For example, given candidate set 10,1,2,7,6,1,5 and target 8, A solution set is:
[1,
[1,
[2,
[1,
7]
2, 5]
6]
1, 6]
// LeetCode, Combination Sum II

//
O(n!)
O(n)
class Solution {
public:
vector<vector<int> > combinationSum2(vector<int> &nums, int target) {
sort(nums.begin(), nums.end()); //
50
//
vector<int> path;
dfs(nums, path, result, target, 0);
return result;
}
private:
//
nums[start, nums.size())
190
10
static void dfs(const vector<int> &nums, vector<int> &path,

vector<vector<int> > &result, int gap, int start) {
if (gap == 0) { //
return;
}
int previous = -1;
for (size_t i = start; i < nums.size(); i++) {
//
nums[i]
//
nums[i]
if (previous == nums[i]) continue;
if (gap < nums[i]) return;
nums[i]
//
previous = nums[i];
path.push_back(nums[i]);
dfs(nums, path, result, gap - nums[i], i + 1);
path.pop_back(); //
}
}
};
Combination Sum
10.7
10.9 Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"
<n
1
// LeetCode, Generate Parentheses
//
O(TODO)
O(n)
class Solution {
191
10.9 Generate Parentheses
public:
vector<string> generateParenthesis(int n) {
string path;
if (n > 0) generate(n, path, result, 0, 0);
return result;
}
// l
(
, r
)
void generate(int n, string& path, vector<string> &result, int l, int r) {
if (l == n) {
string s(path);
result.push_back(s.append(n - r, ')'));
return;
}
path.push_back('(');
generate(n, path, result, l + 1, r);
path.pop_back();
if (l > r) {
path.push_back(')');
generate(n, path, result, l, r + 1);
path.pop_back();
}
}
};
// LeetCode, Generate Parentheses

// @author
class Solution {
public:
vector<string> generateParenthesis (int n) {
if (n == 0) return vector<string>(1, "");
if (n == 1) return vector<string> (1, "()");
for (int i = 0; i < n; ++i)
for (auto inner : generateParenthesis (i))
for (auto outer : generateParenthesis (n - 1 - i))
result.push_back ("(" + inner + ")" + outer);
return result;
}
};
Valid Parentheses,
4.1.1
192
10
Longest Valid Parentheses,
4.1.2
10.10 Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.
10-3 A sudoku puzzle...
10-4 ...and its solution numbers marked in red
193
10.11 Word Search
// LeetCode, Sudoku Solver

//
O(9^4)
O(1)
class Solution {
public:
bool solveSudoku(vector<vector<char> > &board) {
for (int i = 0; i < 9; ++i)
for (int j = 0; j < 9; ++j) {
if (board[i][j] == '.') {
for (int k = 0; k < 9; ++k) {
board[i][j] = '1' + k;
if (isValid(board, i, j) && solveSudoku(board))
return true;
board[i][j] = '.';
}
return false;
}
}
return true;
}
private:
//
(x, y)
bool isValid(const vector<vector<char> > &board, int x, int y) {
int i, j;
for (i = 0; i < 9; i++) //
y
if (i != x && board[i][y] == board[x][y])
return false;
for (j = 0; j < 9; j++) //
x
if (j != y && board[x][j] == board[x][y])
return false;
for (i = 3 * (x / 3); i < 3 * (x / 3 + 1); i++)
for (j = 3 * (y / 3); j < 3 * (y / 3 + 1); j++)
if ((i != x || j != y) && board[i][j] == board[x][y])
return false;
return true;
}
};
Valid Sudoku,
2.1.14
10.11 Word Search

Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those
horizontally or vertically neighbouring. The same letter cell may not be used more than once.
194
10
For example, Given board =

[
["ABCE"],
["SFCS"],
["ADEE"]
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.
// LeetCode, Word Search

//
//
O(n^2*m^2)
O(n^2)
class Solution {
public:
bool exist(const vector<vector<char> > &board, const string& word) {
vector<vector<bool> > visited(m, vector<bool>(n, false));
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (dfs(board, word, 0, i, j, visited))
return true;
return false;
}
private:
static bool dfs(const vector<vector<char> > &board, const string &word,
int index, int x, int y, vector<vector<bool> > &visited) {
if (index == word.size())
return true; //
if (x < 0 || y < 0 || x >= board.size() || y >= board[0].size())
return false; //
if (visited[x][y]) return false; //
if (board[x][y] != word[index]) return false; //
visited[x][y] = true;
bool ret = dfs(board, word, index +
dfs(board, word, index + 1,
visited[x][y] = false;
1, x x + 1,
x, y x, y +
1,
y,
1,
1,
y, visited) || //
visited)
|| //
visited)
|| //
visited);
//
195
10.12
return ret;
}
};
10.12
10.12.1
10.12.2
1.
(a)
path[]
(b)
2.
3.
struct
struct
4.
196
10
5.
0
6.
path[]
7.
(a)
DAG
BFS
BFS
DAG
(b)
9.4
DAG
8
8.
(a)
(b)
i.
DAG
=>
DAG=>
ii.
HashMap
C++
map
HashMap
unordered_map
C++ 11
map
8
197
10.12
10.12.3
dfs_template.cpp
/**
* dfs
.
* @param[in] input
* @param[out] path
* @param[out] result
* @param[inout] cur or gap
* @return
*/
void dfs(type &input, type &path, type &result, int cur or gap) {
if (
) return 0;
//
if (cur == input.size()) { //
// if (gap == 0) {
path
result
}
if (
) return;
for(...) { //
path
dfs(input, step + 1 or gap--, result);
path
}
}
dfs_template.cpp
10.12.4
(Depth-first search, DFS)
http://en.wikipedia.org/wiki/Depth_rst_search
http://en.wikipedia.org/wiki/Backtracking
ing)
=
+
(recursion)
10.12.5
(recursion)
(iteration)
(prunning)
(backtrack-
198
10
memorization
memorization
Donald Michie
top-down with cache
??
1968
top-down
(iterative)
memorization
rization
memorization
memorization
memorization
memo-
11
11.1 Pow(x,n)
Implement pow(x, n).
xn = xn/2 xn/2 xn%2
//LeetCode, Pow(x, n)
//
$x^n = x^{n/2} * x^{n/2} * x^{n\%2}$
//
O(logn)
O(1)
class Solution {
public:
double myPow(double x, int n) {
if (n < 0) return 1.0 / power(x, -n);
else return power(x, n);
}
private:
double power(double x, int n) {
if (n == 0) return 1;
double v = power(x, n / 2);
if (n % 2 == 0) return v * v;
else return v * v * x;
}
};
Sqrt(x)
11.2
199
200
11
11.2 Sqrt(x)
Implement int sqrt(int x).
Compute and return the square root of x.
// LeetCode, Sqrt(x)
//
//
O(logn)
O(1)
class Solution {
public:
int mySqrt(int x) {
int left = 1, right = x / 2;
int last_mid; //
mid
if (x < 2) return x;
while(left <= right) {
const int mid = left + (right - left) / 2;
if(x / mid > mid) { //
x > mid * mid
left = mid + 1;
last_mid = mid;
} else if(x / mid < mid) {
right = mid - 1;
} else {
return mid;
}
}
return last_mid;
}
};
Pow(x)
11.1
12
12.1 Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
A[i]
0
0
f[i]
f [i] = max(f [i 1], A[i 1]) 1, i > 0
1
// LeetCode, Jump Game
//
1
O(n)
O(1)
class Solution {
public:
bool canJump(const vector<int>& nums) {
int reach = 1; //
for (int i = 0; i < reach && reach < nums.size(); ++i)
reach = max(reach, i + 1 + nums[i]);
201
A[i]
202
12
return reach >= nums.size();

}
};
2
//
2
O(n)
O(1)
class Solution {
public:
bool canJump (const vector<int>& nums) {
if (nums.empty()) return true;
//
int left_most = nums.size() - 1;
for (int i = nums.size() - 2; i >= 0; --i)
if (i + nums[i] >= left_most)
left_most = i;
return left_most == 0;
}
};
3
//
O(n)
O(n)
class Solution {
public:
bool canJump(const vector<int>& nums) {
vector<int> f(nums.size(), 0);
f[0] = 0;
f[i] = max(f[i - 1], nums[i - 1]) - 1;
if (f[i] < 0) return false;;
}
return f[nums.size() - 1] >= 0;
}
};
Jump Game II
12.2
12.2 Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.
12.2 Jump Game II
203
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example: Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps
to the last index.)
1
// LeetCode, Jump Game II
//
O(n)
O(1)
class Solution {
public:
int jump(const vector<int>& nums) {
int step = 0; //
int left = 0;
int right = 0; // [left, right]
if (nums.size() == 1) return 0;
while (left <= right) { //
++step;
const int old_right = right;
for (int i = left; i <= old_right; ++i) {
int new_right = i + nums[i];
if (new_right >= nums.size() - 1) return step;
if (new_right > right) right = new_right;
}
left = old_right + 1;
}
return 0;
}
};
2
// LeetCode, Jump Game II
//
O(n)
O(1)
class Solution {
public:
int jump(const vector<int>& nums) {
int result = 0;
// the maximum distance that has been reached
int last = 0;
// the maximum distance that can be reached by using "ret+1" steps
int cur = 0;
204
12

if (i > last) {
last = cur;
++result;
}
cur = max(cur, i + nums[i]);
}
return result;
}
};
Jump Game
12.1
12.3 Best Time to Buy and Sell Stock

Say you have an array for which the i-th element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the
stock), design an algorithm to find the maximum profit.
// LeetCode, Best Time to Buy and Sell Stock

//
O(n)
O(1)
class Solution {
public:
int maxProfit(vector<int> &prices) {
if (prices.size() < 2) return 0;
int profit = 0; //
int cur_min = prices[0]; //
for (int i = 1; i < prices.size(); i++) {
profit = max(profit, prices[i] - cur_min);
cur_min = min(cur_min, prices[i]);
}
return profit;
}
};
m=1
205
12.4 Best Time to Buy and Sell Stock II
Best Time to Buy and Sell Stock II
12.4
Best Time to Buy and Sell Stock III
13.5
12.4 Best Time to Buy and Sell Stock II

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie,
buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions
at the same time (ie, you must sell the stock before you buy again).
// LeetCode, Best Time to Buy and Sell Stock II

//
O(n)
O(1)
class Solution {
public:
int maxProfit(vector<int> &prices) {
int sum = 0;
for (int i = 1; i < prices.size(); i++) {
int diff = prices[i] - prices[i - 1];
if (diff > 0) sum += diff;
}
return sum;
}
};
Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock III
12.3
13.5
m=
206
12
12.5 Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the
longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the
longest substring is "b", with the length of 1.
index+1
O(n)
12-1
12-1
// LeetCode, Longest Substring Without Repeating Characters

//
O(n)
O(1)
//
class Solution {
public:
int lengthOfLongestSubstring(string s) {
const int ASCII_MAX = 255;
int last[ASCII_MAX]; //
int start = 0; //
fill(last, last + ASCII_MAX, -1); // 0
int max_len = 0;
for (int i = 0; i < s.size(); i++) {
if (last[s[i]] >= start) {
max_len = max(i - start, max_len);
start = last[s[i]] + 1;
}
last[s[i]] = i;
}
-1
207
12.6 Container With Most Water
return max((int)s.size() - start, max_len);
//
"abcd"
}
};
12.6 Container With Most Water

Given n non-negative integers a1 , a2 , ..., an , where each represents a point at coordinate (i, ai ). n vertical lines are drawn such that the two endpoints of line i is at (i, ai ) and (i, 0). Find two lines, which together
with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.
// LeetCode, Container With Most Water

//
O(n)
O(1)
class Solution {
public:
int maxArea(vector<int> &height) {
int start = 0;
int end = height.size() - 1;
int result = INT_MIN;
while (start < end) {
int area = min(height[end], height[start]) * (end - start);
result = max(result, area);
if (height[start] <= height[end]) {
start++;
} else {
end--;
}
}
return result;
}
};
Trapping Rain Water,
2.1.15
208
12
Largest Rectangle in Histogram,
4.1.3
13
13.1 Triangle
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent
numbers on the row below.
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note: Bonus point if you are able to do this using only O(n) extra space, where n is the total number of
rows in the triangle.
f (i, j)
(i, j)
f (i, j) = min {f (i + 1, j), f (i + 1, j + 1)} + (i, j)
// LeetCode, Triangle
//
O(n^2)
O(1)
class Solution {
public:
int minimumTotal (vector<vector<int>>& triangle) {
for (int i = triangle.size() - 2; i >= 0; --i)
for (int j = 0; j < i + 1; ++j)
triangle[i][j] += min(triangle[i + 1][j],
triangle[i + 1][j + 1]);
209
210
13
return triangle [0][0];

}
};
13.2 Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [2,1,3,4,1,2,1,5,4], the contiguous subarray [4,1,2,1] has
the largest sum = 6.
SubArray
2.
SubArray
SubArray
SubArray
SubArray
SubArray
f[j]
S[j]
f [j]
max {f [j 1] + S[j], S[j]} ,
target
max {f [j]} ,
1jn
1jn
f [j 1] +
S[j]
S[j]
S[j]
S[j]
S[j]
O(n3 )
O(n2 )
O(n log n)
2O(n2 )
M=1
O(n)
M
211
13.2 Maximum Subarray
// LeetCode, Maximum Subarray

//
O(n)
O(1)
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int result = INT_MIN, f = 0;
f = max(f + nums[i], nums[i]);
result = max(result, f);
}
return result;
}
};
5
// LeetCode, Maximum Subarray
//
O(n)
O(n)
class Solution {
public:
int maxSubArray(vector<int>& A) {
return mcss(A.begin(), A.end());
}
private:
//
5
template <typename Iter>
static int mcss(Iter begin, Iter end) {
int result, cur_min;
const int n = distance(begin, end);
int *sum = new int[n + 1]; //
n
sum[0] = 0;
result = INT_MIN;
cur_min = sum[0];
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + *(begin + i - 1);
}
for (int i = 1; i <= n; i++) {
result = max(result, sum[i] - cur_min);
cur_min = min(cur_min, sum[i]);
}
delete[] sum;
return result;
}
};
Binary Tree Maximum Path Sum
5.4.5
212
13
13.3 Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
f(i,j)
[i,j]
cut
f (i, j) = min {f (i, k) + f (k + 1, j)} , i k j, 0 i j < n
DP
f(i)=
[i, n-1]
DP
cut
f (i) = min {f (j + 1) + 1} , i j < n
[i,j]
DP
P[i][j] = true if [i,j]

P[i][j] = str[i] == str[j] && P[i+1][j-1]
// LeetCode, Palindrome Partitioning II

//
O(n^2)
O(n^2)
class Solution {
public:
int minCut(const string& s) {
int f[n+1];
bool p[n][n];
fill_n(&p[0][0], n * n, false);
//the worst case is cutting by each char
for (int i = 0; i <= n; i++)
f[i] = n - 1 - i; //
f[n]=-1
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (s[i] == s[j] && (j - i < 2 || p[i + 1][j - 1])) {
p[i][j] = true;
f[i] = min(f[i], f[j + 1] + 1);
}
}
213
13.4 Maximal Rectangle
}
return f[0];
}
};
Palindrome Partitioning
10.1
13.4 Maximal Rectangle

Given a 2D binary matrix filled with 0s and 1s, find the largest rectangle containing all ones and return
its area.
// LeetCode, Maximal Rectangle

//
O(n^2)
O(n)
class Solution {
public:
int maximalRectangle(vector<vector<char> > &matrix) {
if (matrix.empty()) return 0;
const int m
const int n
vector<int>
vector<int>
vector<int>
= matrix.size();
= matrix[0].size();
H(n, 0);
L(n, 0);
R(n, n);
int ret = 0;
for (int i = 0; i < m; ++i) {
int left = 0, right = n;
// calculate L(i, j) from left to right
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == '1') {
++H[j];
L[j] = max(L[j], left);
} else {
left = j+1;
H[j] = 0; L[j] = 0; R[j] = n;
}
}
214
13
// calculate R(i, j) from right to left

for (int j = n-1; j >= 0; --j) {
if (matrix[i][j] == '1') {
R[j] = min(R[j], right);
ret = max(ret, H[j]*(R[j]-L[j]));
} else {
right = j;
}
}
}
return ret;
}
};
13.5 Best Time to Buy and Sell Stock III

Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before
you buy again).
f (i)
[0, i](0 i n1)
[i, n1](0 i n1)
g(i)
max {f (i) + g(i)} , 0 i n 1
https://gist.github.com/soulmachine/5906637
// LeetCode, Best Time to Buy and Sell Stock III

//
O(n)
O(n)
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() < 2) return 0;
const int n = prices.size();
215
13.6 Interleaving String
vector<int> g(n, 0);

for (int i = 1, valley = prices[0]; i < n; ++i) {
valley = min(valley, prices[i]);
f[i] = max(f[i - 1], prices[i] - valley);
}
for (int i = n - 2, peak = prices[n - 1]; i >= 0; --i) {
peak = max(peak, prices[i]);
g[i] = max(g[i], peak - prices[i]);
}
int max_profit = 0;
for (int i = 0; i < n; ++i)
max_profit = max(max_profit, f[i] + g[i]);
return max_profit;
}
};
Best Time to Buy and Sell Stock
12.3
Best Time to Buy and Sell Stock II
12.4
13.6 Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example, Given: s1 = "aabcc", s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
f[i][j]
s3
s1[0,i]
s2[0,j]
f[i][j]=f[i-1][j]
s3[0, i+j]
s2
f[i][j]=f[i][j-1]
f[i][j] = (s1[i - 1] == s3 [i + j - 1] && f[i - 1][j])
|| (s2[j - 1] == s3 [i + j - 1] && f[i][j - 1]);
// LeetCode, Interleaving String

//
s1
s3
216
13
class Solution {
public:
bool isInterleave(const string& s1, const string& s2, const string& s3) {
if (s3.length() != s1.length() + s2.length())
return false;
return isInterleave(begin(s1), end(s1), begin(s2), end(s2),
begin(s3), end(s3));
}
template<typename InIt>
bool isInterleave(InIt first1, InIt last1, InIt first2, InIt last2,
InIt first3, InIt last3) {
if (first3 == last3)
return first1 == last1 && first2 == last2;
return (*first1 == *first3
&& isInterleave(next(first1), last1, first2, last2,
next(first3), last3))
|| (*first2 == *first3
&& isInterleave(first1, last1, next(first2), last2,
next(first3), last3));
}
};

//
O(n^2)
O(n^2)
class Solution {
public:
if (s3.length() != s1.length() + s2.length())
return false;
vector<vector<bool>> f(s1.length() + 1,
vector<bool>(s2.length() + 1, true));
for (size_t i = 1; i <= s1.length(); ++i)
f[i][0] = f[i - 1][0] && s1[i - 1] == s3[i - 1];
f[0][i] = f[0][i - 1] && s2[i - 1] == s3[i - 1];
for (size_t j = 1; j <= s2.length(); ++j)
f[i][j] = (s1[i - 1] == s3[i + j - 1] && f[i - 1][j])
|| (s2[j - 1] == s3[i + j - 1] && f[i][j - 1]);
return f[s1.length()][s2.length()];
}
};
13.7 Scramble String
217
+
//
+
O(n^2)
O(n)
class Solution {
public:
if (s1.length() + s2.length() != s3.length())
return false;
if (s1.length() < s2.length())
return isInterleave(s2, s1, s3);
vector<bool> f(s2.length() + 1, true);
f[i] = s2[i - 1] == s3[i - 1] && f[i - 1];
for (size_t i = 1; i <= s1.length(); ++i) {
f[0] = s1[i - 1] == s3[i - 1] && f[0];
for (size_t j = 1; j <= s2.length(); ++j)
f[j] = (s1[i - 1] == s3[i + j - 1] && f[j])
|| (s2[j - 1] == s3[i + j - 1] && f[j - 1]);
}
return f[s2.length()];
}
};

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings
recursively.
Below is one possible representation of s1 = "great":
great
/
\
gr
eat
/ \
/ \
g
r e
at
/ \
a
t
218
13
To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string
"rgeat".
rgeat
/
\
rg
eat
/ \
/ \
r
g e
at
/ \
a
t
We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string
"rgtae".
rgtae
/
\
rg
tae
/ \
/ \
r
g ta e
/ \
t
a
We say that "rgtae" is a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.
string
memorization
scamble
false
HashMap
HashMap
s1[i]
s2[j]
scramble
f[n][i][j]} = (f[k][i][j] && f[n-k][i+k][j+k])

|| (f[k][i][j+n-k] && f[n-k][i+k][j])
// LeetCode, Scramble String

//
//
O(n^6)
class Solution {
map
f[n][i][j]
O(1)
unordered_map
n
public:
bool isScramble(const string& s1, const string& s2) {
return isScramble(s1.begin(), s1.end(), s2.begin());
}
private:
typedef string::iterator Iterator;
bool isScramble(Iterator first1, Iterator last1, Iterator first2) {
auto length = distance(first1, last1);
auto last2 = next(first2, length);
if (length == 1) return *first1 == *first2;
for (int i = 1; i < length; ++i)
if ((isScramble(first1, first1 + i, first2)
&& isScramble(first1 + i, last1, first2 + i))
|| (isScramble(first1, first1 + i, last2 - i)
&& isScramble(first1 + i, last1, first2)))
return true;
return false;
}
};

//
O(n^3)
O(n^3)
class Solution {
public:
const int N = s1.size();
if (N != s2.size()) return false;
// f[n][i][j]
n
s1[i]
//
s2[j]
scramble
bool f[N + 1][N][N];
fill_n(&f[0][0][0], (N + 1) * N * N, false);
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
f[1][i][j] = s1[i] == s2[j];
for (int n = 1; n <= N; ++n) {
for (int i = 0; i + n <= N; ++i) {
for (int j = 0; j + n <= N; ++j) {
for (int k = 1; k < n; ++k) {
if ((f[k][i][j] && f[n - k][i + k][j + k]) ||
(f[k][i][j + n - k] && f[n - k][i + k][j])) {
f[n][i][j] = true;
break;
}
}
}
219
220
13
}
}
return f[N][0][0];
}
};
+
//
+
//
O(n^6)
O(1)
class Solution {
public:
}
private:
//
int A[26]; //
fill(A, A + 26, 0);
for(int i = 0; i < length; i++) A[*(first1+i)-'a']++;
for(int i = 0; i < length; i++) A[*(first2+i)-'a']--;
for(int i = 0; i < 26; i++) if (A[i] != 0) return false;
if ((isScramble(first1, first1 + i, first2)
&& isScramble(first1 + i, last1, first2 + i))
|| (isScramble(first1, first1 + i, last2 - i)
&& isScramble(first1 + i, last1, first2)))
return true;
return false;
}
};

//
+map
cache
//
O(n^3)
O(n^3), TLE
class Solution {
public:
cache.clear();
}
221
private:
map<tuple<Iterator, Iterator, Iterator>, bool> cache;
if ((getOrUpdate(first1, first1 + i, first2)
&& getOrUpdate(first1 + i, last1, first2 + i))
|| (getOrUpdate(first1, first1 + i, last2 - i)
&& getOrUpdate(first1 + i, last1, first2)))
return true;
return false;
}
bool getOrUpdate(Iterator first1, Iterator last1, Iterator first2) {
auto key = make_tuple(first1, last1, first2);
return (pos != cache.end()) ?
pos->second : (cache[key] = isScramble(first1, last1, first2));
}
};

typedef tuple<Iterator, Iterator, Iterator> Key;
//
namespace std {
template<> struct hash<Key> {
size_t operator()(const Key & x) const {
Iterator first1, last1, first2;
tie(first1, last1, first2) = x;
int result = *first1;
result = result * 31 + *last1;
result = result * 31 + *first2;
result = result * 31 + *(next(first2, distance(first1, last1)-1));
return result;
}
};
}
//
+unordered_map
cache
map
//
O(n^3)
O(n^3)
class Solution {
222
13
public:
unordered_map<Key, bool> cache;
cache.clear();
}
if (length == 1)
return *first1 == *first2;
if ((getOrUpdate(first1, first1 + i, first2)
&& getOrUpdate(first1 + i, last1, first2 + i))
|| (getOrUpdate(first1, first1 + i, last2 - i)
&& getOrUpdate(first1 + i, last1, first2)))
return true;
return false;
}
bool getOrUpdate(Iterator first1, Iterator last1, Iterator first2) {
auto key = make_tuple(first1, last1, first2);
return (pos != cache.end()) ?
pos->second : (cache[key] = isScramble(first1, last1, first2));
}
};
13.8 Minimum Path Sum

Given a m n grid filled with non-negative numbers, find a path from top left to bottom right which
minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time
Unique Paths (
10.2)
223
13.8 Minimum Path Sum
f[i][j]
(0, 0)
(i, j)
f[i][j]=min(f[i-1][j], f[i][j-1])+grid[i][j]
// LeetCode, Minimum Path Sum

//
class Solution {
public:
int minPathSum(vector<vector<int> > &grid) {
const int m = grid.size();
const int n = grid[0].size();
this->f = vector<vector<int> >(m, vector<int>(n, -1));
return dfs(grid, m-1, n-1);
}
private:
vector<vector<int> > f; //
int dfs(const vector<vector<int> > &grid, int x, int y) {
if (x < 0 || y < 0) return INT_MAX; //
if (x == 0 && y == 0) return grid[0][0]; //
return min(getOrUpdate(grid, x - 1, y),
getOrUpdate(grid, x, y - 1)) + grid[x][y];
}
int getOrUpdate(const vector<vector<int> > &grid, int x, int y) {
if (x < 0 || y < 0) return INT_MAX; //
0
if (f[x][y] >= 0) return f[x][y];
else return f[x][y] = dfs(grid, x, y);
}
};

//
class Solution {
public:
if (grid.size() == 0) return 0;
int f[m][n];
f[0][0] = grid[0][0];
for (int i = 1; i < m; i++)
f[i][0] = f[i - 1][0] +
}
for (int i = 1; i < n; i++)
f[0][i] = f[0][i - 1] +
{
grid[i][0];
{
grid[0][i];
224
13
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
f[i][j] = min(f[i - 1][j], f[i][j - 1]) + grid[i][j];
}
}
return f[m - 1][n - 1];
}
};
+
//
+
class Solution {
public:
int f[n];
fill(f, f+n, INT_MAX); //
f[0] = 0;
INT_MAX
min
for (int i = 0; i < m; i++) {

f[0] += grid[i][0];
for (int j = 1; j < n; j++) {
//
f[j]
f[j]
f[i[[j]
//
f[j]
f[j]
f[i-1][j]
f[j] = min(f[j - 1], f[j]) + grid[i][j];
}
}
return f[n - 1];
}
};
Unique Paths,
Unique Paths II,
10.2
10.3
13.9 Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to
word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
225
13.9 Edit Distance
Insert a character
Delete a character
Replace a character
f[i][j]
B[0,j]
A[0,i]
B[0,j]
A[0,i]
str2d
1.
c==d
2.
c!=d
f[i][j]=f[i-1][j-1]
(a)
(b)
(c)
f[i][j]=f[i-1][j-1]+1
d
f[i][j]=f[i][j-1]+1
f[i][j]=f[i-1][j]+1
// LeetCode, Edit Distance

//
O(n*m)
O(n*m)
class Solution {
public:
int minDistance(const string &word1, const string &word2) {
const size_t n = word1.size();
const size_t m = word2.size();
//
n
n+1
int f[n + 1][m + 1];
for (size_t i = 0; i <= n; i++)
f[i][0] = i;
for (size_t j = 0; j <= m; j++)
f[0][j] = j;
for (size_t i = 1; i <= n; i++) {
for (size_t j = 1; j <= m; j++) {
if (word1[i - 1] == word2[j - 1])
f[i][j] = f[i - 1][j - 1];
else {
int mn = min(f[i - 1][j], f[i][j - 1]);
f[i][j] = 1 + min(f[i - 1][j - 1], mn);
}
}
}
return f[n][m];
}
};
str1c
226
13
+
// LeetCode, Edit Distance
//
+
//
O(n*m)
O(n)
class Solution {
public:
int minDistance(const string &word1, const string &word2) {
if (word1.length() < word2.length())
return minDistance(word2, word1);
int f[word2.length() + 1];
int upper_left = 0; //
f[i-1][j-1]
for (size_t i = 0; i <= word2.size(); ++i)

f[i] = i;
for (size_t i = 1; i <= word1.size(); ++i) {
upper_left = f[0];
f[0] = i;
for (size_t j = 1; j <= word2.size(); ++j) {
int upper = f[j];
if (word1[i - 1] == word2[j - 1])
f[j] = upper_left;
else
f[j] = 1 + min(upper_left, min(f[j], f[j - 1]));
upper_left = upper;
}
}
return f[word2.length()];
}
};
13.10 Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
13.11 Distinct Subsequences
227
Given an encoded message containing digits, determine the total number of ways to decode it.
For example, Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.
Climbing Stairs (
2.1.18)
// LeetCode, Decode Ways

//
O(n)
O(1)
class Solution {
public:
int numDecodings(const string &s) {
if (s.empty() || s[0] == '0') return 0;
int prev = 0;
int cur = 1;
//
n
n+1
for (size_t i = 1; i <= s.size(); ++i) {
if (s[i-1] == '0') cur = 0;
if (i < 2 || !(s[i - 2] == '1' ||
(s[i - 2] == '2' && s[i - 1] <= '6')))
prev = 0;
int tmp = cur;
cur = prev + cur;
prev = tmp;
}
return cur;
}
};
Climbing Stairs,
2.1.18
13.11 Distinct Subsequences

Given a string S and a string T , count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can
be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is
a subsequence of "ABCDE" while "AEC" is not).
228
13
Here is an example: S = "rabbbit", T = "rabbit"

Return 3.
T[0,j]
f (i, j)
S[i]
S[0,i]
f (i, j) = f (i 1, j)
S[i]
S[i]==T[j]
S[i]
T[j]
f (i, j) =
f (i 1, j) + f (i 1, j 1)
// LeetCode, Distinct Subsequences

//
+
//
O(m*n)
O(n)
class Solution {
public:
int numDistinct(const string &S, const string &T) {
vector<int> f(T.size() + 1);
f[0] = 1;
for (int i = 0; i < S.size(); ++i) {
for (int j = T.size() - 1; j >= 0; --j) {
f[j + 1] += S[i] == T[j] ? f[j] : 0;
}
}
return f[T.size()];
}
};
13.12 Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated
sequence of one or more dictionary words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
229
13.12 Word Break
f (i)
s[0,i]
f (i) = any_of (f (j)&&s[j + 1, i] dict), 0 j < i
// LeetCode, Word Break

//
//
O(2^n)
O(n)
class Solution {
public:
bool wordBreak(string s, unordered_set<string> &dict) {
return dfs(s, dict, 0, 0);
}
private:
static bool dfs(const string &s, unordered_set<string> &dict,
size_t start, size_t cur) {
if (cur == s.size()) {
return dict.find(s.substr(start, cur-start+1)) != dict.end();
}
if (dfs(s, dict, start, cur+1)) return true;
if (dict.find(s.substr(start, cur-start+1)) != dict.end())
if (dfs(s, dict, cur+1, cur+1)) return true;
return false;
}
};
// LeetCode, Word Break

//
O(n^2)
O(n)
class Solution {
public:
bool wordBreak(string s, unordered_set<string> &dict) {
//
n
n+1
vector<bool> f(s.size() + 1, false);
f[0] = true; //
for (int i = 1; i <= s.size(); ++i) {
for (int j = i - 1; j >= 0; --j) {
if (f[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
f[i] = true;
break;
}
}
}
return f[s.size()];
}
};
230
13
Word Break II,
13.13
13.13 Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word
is a valid dictionary word.
Return all such possible sentences.
For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].
// LeetCode, Word Break II

//
O(n^2)
O(n^2)
class Solution {
public:
vector<string> wordBreak(string s, unordered_set<string> &dict) {
//
n
n+1
vector<bool> f(s.length() + 1, false);
// prev[i][j]
true
s[j, i)
j
//
vector<vector<bool> > prev(s.length() + 1, vector<bool>(s.length()));
f[0] = true;
for (size_t i = 1; i <= s.length(); ++i) {
for (int j = i - 1; j >= 0; --j) {
if (f[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
f[i] = true;
prev[i][j] = true;
}
}
}
gen_path(s, prev, s.length(), path, result);
return result;
}
231
13.13 Word Break II
private:
// DFS
void gen_path(const string &s, const vector<vector<bool> > &prev,
int cur, vector<string> &path, vector<string> &result) {
if (cur == 0) {
string tmp;
for (auto iter = path.crbegin(); iter != path.crend(); ++iter)
tmp += *iter + " ";
tmp.erase(tmp.end() - 1);
result.push_back(tmp);
}
if (prev[cur][i]) {
path.push_back(s.substr(i, cur - i));
gen_path(s, prev, i, path, result);
path.pop_back();
}
}
}
};
Word Break,
13.12
14
//
struct UndirectedGraphNode {
int label;
vector<UndirectedGraphNode *> neighbors;
UndirectedGraphNode(int x) : label(x) {};
};
14.1 Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbours.
OJs undirected graph serialization: Nodes are labeled uniquely.
We use # as a separator for each node, and , as a separator for node label and each neighbour of the
node. As an example, consider the serialized graph {0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.
1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:
1
/ \
/
\
0 --- 2
/ \
\_/
232
14.1 Clone Graph
DFS
// LeetCode, Clone Graph
// DFS
O(n)
O(n)
class Solution {
public:
UndirectedGraphNode *cloneGraph(const UndirectedGraphNode *node) {
if(node == nullptr) return nullptr;
// key is original node value is copied node
unordered_map<const UndirectedGraphNode *,
UndirectedGraphNode *> copied;
clone(node, copied);
return copied[node];
}
private:
// DFS
static UndirectedGraphNode* clone(const UndirectedGraphNode *node,
UndirectedGraphNode *> &copied) {
// a copy already exists
if (copied.find(node) != copied.end()) return copied[node];
UndirectedGraphNode *new_node = new UndirectedGraphNode(node->label);
copied[node] = new_node;
for (auto nbr : node->neighbors)
new_node->neighbors.push_back(clone(nbr, copied));
return new_node;
}
};
BFS
// LeetCode, Clone Graph
// BFS
O(n)
O(n)
class Solution {
public:
UndirectedGraphNode *cloneGraph(const UndirectedGraphNode *node) {
if (node == nullptr) return nullptr;
// key is original node value is copied node
UndirectedGraphNode *> copied;
// each node in queue is already copied itself
// but neighbors are not copied yet
queue<const UndirectedGraphNode *> q;
q.push(node);
copied[node] = new UndirectedGraphNode(node->label);
const UndirectedGraphNode *cur = q.front();
q.pop();
for (auto nbr : cur->neighbors) {
// a copy already exists
if (copied.find(nbr) != copied.end()) {
copied[cur]->neighbors.push_back(copied[nbr]);
233
234
14
} else {
UndirectedGraphNode *new_node =
new UndirectedGraphNode(nbr->label);
copied[nbr] = new_node;
copied[cur]->neighbors.push_back(new_node);
q.push(nbr);
}
}
}
return copied[node];
}
};
15
15.1 Reverse Integer

Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321
Have you thought about this?
Here are some good questions to ask before coding. Bonus points for you if you have already thought
through this!
If the integers last digit is 0, what should the output be? ie, cases such as 10, 100.
Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the
reverse of 1000000003 overflows. How should you handle such cases?
Throw an exception? Good, but what if throwing an exception is not an option? You would then have
to re-design the function (ie, add an extra parameter).
//LeetCode, Reverse Integer

//
O(logn)
//
1.
2.
class Solution {
public:
int reverse (int x) {
long long r = 0;
long long t = x;
t = t > 0 ? t : -t;
O(1)
(
&&
235
x = -2147483648(
-2^31) )
236
15
for (; t; t /= 10)
r = r * 10 + t % 10;
bool sign = x > 0 ? false: true;
if (r > 2147483647 || (sign && r > 2147483648)) {
return 0;
} else {
if (sign) {
return -r;
} else {
return r;
}
}
}
};
Palindrome Number,
15.2
15.2 Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.
Some hints:
Could negative integers be palindromes? (ie, -1)
If you are thinking of converting the integer to string, note the restriction of using extra space.
You could also try reversing an integer. However, if you have solved the problem Reverse Integer,
you know that the reversed integer might overflow. How would you handle such case?
There is a more generic way of solving this problem.
Palindrome
reverse()
//LeetCode, Palindrome Number

//
O(1)
O(1)
class Solution {
public:
10
237
15.3 Insert Interval
bool isPalindrome(int x) {
if (x < 0) return false;
int d = 1; // divisor
while (x / d >= 10) d *= 10;
while (x > 0) {
int q = x /
int r = x %
if (q != r)
x = x % d /
d /= 100;
}
return true;
d; // quotient
10;
// remainder
return false;
10;
}
};
Reverse Integer,
Valid Palindrome,
15.1
3.1
15.3 Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1: Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as
[1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
struct Interval {
int start;
int end;
Interval() : start(0), end(0) { }
Interval(int s, int e) : start(s), end(e) { }
};
//LeetCode, Insert Interval
238
15
//
O(n)
O(1)
class Solution {
public:
vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
vector<Interval>::iterator it = intervals.begin();
while (it != intervals.end()) {
if (newInterval.end < it->start) {
intervals.insert(it, newInterval);
return intervals;
} else if (newInterval.start > it->end) {
it++;
continue;
} else {
newInterval.start = min(newInterval.start, it->start);
newInterval.end = max(newInterval.end, it->end);
it = intervals.erase(it);
}
}
intervals.insert(intervals.end(), newInterval);
return intervals;
}
};
Merge Intervals
15.4
15.4 Merge Intervals

Given a collection of intervals, merge all overlapping intervals.
For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18]
Insert Intervals
interval
interval
struct Interval {
int start;
int end;
Interval() : start(0), end(0) { }
Interval(int s, int e) : start(s), end(e) { }
};
15.5 Minimum Window Substring
239
//LeetCode, Merge Interval

//
Insert Intervals
//
O(n1+n2+...)
O(1)
class Solution {
public:
vector<Interval> merge(vector<Interval> &intervals) {
vector<Interval> result;
for (int i = 0; i < intervals.size(); i++) {
insert(result, intervals[i]);
}
return result;
}
private:
vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
vector<Interval>::iterator it = intervals.begin();
while (it != intervals.end()) {
if (newInterval.end < it->start) {
intervals.insert(it, newInterval);
return intervals;
} else if (newInterval.start > it->end) {
it++;
continue;
} else {
newInterval.start = min(newInterval.start, it->start);
newInterval.end = max(newInterval.end, it->end);
it = intervals.erase(it);
}
}
intervals.insert(intervals.end(), newInterval);
return intervals;
}
};
Insert Interval
15.3
15.5 Minimum Window Substring

Given a string S and a string T , find the minimum window in S which will contain all the characters in
T in complexity O(n).
For example, S = "ADOBECODEBANC", T = "ABC"
Minimum window is "BANC".
Note:
If there is no such window in S that covers all characters in T , return the emtpy string "".
240
15
If there are multiple such windows, you are guaranteed that there will always be only one unique
minimum window in S.
// LeetCode, Minimum Window Substring

//
O(n)
O(1)
class Solution {
public:
string minWindow(string S, string T) {
if (S.empty()) return "";
if (S.size() < T.size()) return "";
const int ASCII_MAX = 256;
int appeared_count[ASCII_MAX];
int expected_count[ASCII_MAX];
fill(appeared_count, appeared_count + ASCII_MAX, 0);
fill(expected_count, expected_count + ASCII_MAX, 0);
for (size_t i = 0; i < T.size(); i++) expected_count[T[i]]++;
int
int
int
//
for
minWidth = INT_MAX, min_start = 0;

wnd_start = 0;
appeared = 0; //
T
//
(size_t wnd_end = 0; wnd_end < S.size(); wnd_end++) {

if (expected_count[S[wnd_end]] > 0) { // this char is a part of T
appeared_count[S[wnd_end]]++;
if (appeared_count[S[wnd_end]] <= expected_count[S[wnd_end]])
appeared++;
}
if (appeared == T.size()) { //
T
//
while (appeared_count[S[wnd_start]] > expected_count[S[wnd_start]]
|| expected_count[S[wnd_start]] == 0) {
appeared_count[S[wnd_start]]--;
wnd_start++;
}
if (minWidth > (wnd_end - wnd_start + 1)) {
minWidth = wnd_end - wnd_start + 1;
min_start = wnd_start;
}
}
}
if (minWidth == INT_MAX) return "";
241
15.6 Multiply Strings
else return S.substr(min_start, minWidth);

}
};

Given two numbers represented as strings, return multiplication of the numbers as a string.
Note: The numbers can be arbitrarily large and are non-negative.
int
2
int32
4
31
int
1 = 2147483647
int64
1
// LeetCode, Multiply Strings
// @author
//
int
//
O(n*m)
O(n+m)
typedef vector<int> bigint;
bigint make_bigint(string const& repr) {
bigint n;
transform(repr.rbegin(), repr.rend(), back_inserter(n),
[](char c) { return c - '0'; });
return n;
}
string to_string(bigint const& n)
string str;
transform(find_if(n.rbegin(),
[](char c) { return c
[](char c) { return c
return str;
}
{
prev(n.rend()),
> '\0'; }), n.rend(), back_inserter(str),
+ '0'; });
bigint operator*(bigint const& x, bigint const& y) {

bigint z(x.size() + y.size());
242
15
for (size_t i = 0; i < x.size(); ++i)

for (size_t j = 0; j < y.size(); ++j) {
z[i + j] += x[i] * y[j];
z[i + j + 1] += z[i + j] / 10;
z[i + j] %= 10;
}
return z;
}
class Solution {
public:
string multiply(string num1, string num2) {
return to_string(make_bigint(num1) * make_bigint(num2));
}
};
2
// LeetCode, Multiply Strings
// 9
int64_t
//
O(n*m/81)
O((n+m)/9)
/**
. */
class BigInt {
public:
/**
* @brief
.
* @param[in] s
* @return
*/
BigInt(string s) {
vector<int64_t> result;
result.reserve(s.size() / RADIX_LEN + 1);
for (int i = s.size(); i > 0; i -= RADIX_LEN) {
int temp = 0;
const int low = max(i - RADIX_LEN, 0);
for (int j = low; j < i; j++) {
temp = temp * 10 + s[j] - '0';
}
result.push_back(temp);
}
elems = result;
// [i-RADIX_LEN, i)
}
/**
* @brief
.
* @return
*/
string toString() {
stringstream result;
bool started = false; //
0
for (auto i = elems.rbegin(); i != elems.rend(); i++) {
243
if (started) { //
0
result << setw(RADIX_LEN) << setfill('0') << *i;
} else {
result << *i;
started = true; //
0
}
}
if (!started) return "0"; //
else return result.str();
}
/**
* @brief
.
* @param[in] x x
* @param[in] y y
* @return
*/
static BigInt multiply(const BigInt &x, const BigInt &y) {
vector<int64_t> z(x.elems.size() + y.elems.size(), 0);
for (size_t i = 0; i < y.elems.size(); i++) {
for (size_t j = 0; j < x.elems.size(); j++) { //
//
i, j
i+j
z[i + j] += y.elems[i] * x.elems[j];
y[i]
if (z[i + j] >= BIGINT_RADIX) { //

z[i + j + 1] += z[i + j] / BIGINT_RADIX; //
z[i + j] %= BIGINT_RADIX;
}
}
}
while (z.back() == 0) z.pop_back();
return BigInt(z);
//
}
private:
typedef long long int64_t;
/**
9
*
1000000000 * 1000000000
2^63-1
*/
const static int BIGINT_RADIX = 1000000000;
const static int RADIX_LEN = 9;
/**
. */
vector<int64_t> elems;
BigInt(const vector<int64_t> num) : elems(num) {}
};
class Solution {
public:
string multiply(string num1, string num2) {
BigInt x(num1);
244
15
BigInt y(num2);
return BigInt::multiply(x, y).toString();
}
};
15.7 Substring with Concatenation of All Words

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of
substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]
You should return the indices: [0,9].(order does not matter).
// LeetCode, Substring with Concatenation of All Words

//
O(n*m)
O(m)
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& dict) {
size_t wordLength = dict.front().length();
size_t catLength = wordLength * dict.size();
vector<int> result;
if (s.length() < catLength) return result;
unordered_map<string, int> wordCount;
for (auto const& word : dict) ++wordCount[word];
for (auto i = begin(s); i <= prev(end(s), catLength); ++i) {
unordered_map<string, int> unused(wordCount);
for (auto j = i; j != next(i, catLength); j += wordLength) {
auto pos = unused.find(string(j, next(j, wordLength)));
245
15.8 Pascals Triangle
if (pos == unused.end() || pos->second == 0) break;

if (--pos->second == 0) unused.erase(pos);
}
if (unused.size() == 0) result.push_back(distance(begin(s), i));
}
return result;
}
};
15.8 Pascals Triangle

Given numRows, generate the first numRows of Pascals triangle.
For example, given numRows = 5,
Return
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
0
1
// LeetCode, Pascal's Triangle

//
O(n^2)
O(n)
class Solution {
public:
vector<vector<int> > generate(int numRows) {
246
15
if(numRows == 0) return result;

result.push_back(vector<int>(1,1)); //first row
for(int i = 2; i <= numRows; ++i) {
vector<int> current(i,1); //
const vector<int> &prev = result[i-2];
//
for(int j = 1; j < i - 1; ++j) {

current[j] = prev[j-1] + prev[j]; //
}
result.push_back(current);
}
return result;
}
};
// LeetCode, Pascal's Triangle

//
O(n^2)
O(n)
class Solution {
public:
vector<vector<int> > generate(int numRows) {
vector<int> array;
for (int i = 1; i <= numRows; i++) {
for (int j = i - 2; j > 0; j--) {
array[j] = array[j - 1] + array[j];
}
array.push_back(1);
result.push_back(array);
}
return result;
}
};
Pascals Triangle II
15.9
15.9 Pascals Triangle II

Given an index k, return the kth row of the Pascals triangle.
For example, given k = 3,
Return [1,3,3,1].
Note: Could you optimize your algorithm to use only O(k) extra space?
247
15.10 Spiral Matrix
// LeetCode, Pascal's Triangle II

//
O(n^2)
O(n)
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> array;
for (int i = 0; i <= rowIndex; i++) {
for (int j = i - 1; j > 0; j--){
array[j] = array[j - 1] + array[j];
}
array.push_back(1);
}
return array;
}
};
Pascals Triangle
15.8
15.10 Spiral Matrix

Given a matrix of m n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example, Given the following matrix:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
You should return [1,2,3,6,9,8,7,4,5].
248
15
// LeetCode, Spiral Matrix

// @author
//
O(n^2)
O(1)
class Solution {
public:
vector<int> spiralOrder(vector<vector<int> >& matrix) {
vector<int> result;
if (matrix.empty()) return result;
int beginX = 0, endX = matrix[0].size() - 1;
int beginY = 0, endY = matrix.size() - 1;
while (true) {
// From left to right
for (int j = beginX; j <= endX; ++j) result.push_back(matrix[beginY][j]);
if (++beginY > endY) break;
// From top to bottom
for (int i = beginY; i <= endY; ++i) result.push_back(matrix[i][endX]);
if (beginX > --endX) break;
// From right to left
for (int j = endX; j >= beginX; --j) result.push_back(matrix[endY][j]);
if (beginY > --endY) break;
// From bottom to top
for (int i = endY; i >= beginY; --i) result.push_back(matrix[i][beginX]);
if (++beginX > endX) break;
}
return result;
}
};
Spiral Matrix II
15.11
15.11 Spiral Matrix II

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
For example, Given n = 3,
You should return the following matrix:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
249
15.11 Spiral Matrix II
1
// LeetCode, Spiral Matrix II
//
O(n^2)
O(n^2)
class Solution {
public:
vector<vector<int> > generateMatrix(int n) {
vector<vector<int> > matrix(n, vector<int>(n));
int begin = 0, end = n - 1;
int num = 1;
while (begin
for (int
for (int
for (int
for (int
++begin;
--end;
}
<
j
i
j
i
end) {
= begin;
= begin;
= end; j
= end; i
j
i
>
>
< end;
< end;
begin;
begin;
++j)
++i)
--j)
--i)
matrix[begin][j]
matrix[i][end] =
matrix[end][j] =
matrix[i][begin]
= num++;
num++;
num++;
= num++;
if (begin == end) matrix[begin][begin] = num;

return matrix;
}
};
2
// LeetCode, Spiral Matrix II
// @author
//
O(n^2)
O(n^2)
class Solution {
public:
vector<vector<int> > generateMatrix(int n) {
vector< vector<int> > matrix(n, vector<int>(n));
if (n == 0) return matrix;
int beginX = 0, endX = n - 1;
int beginY = 0, endY = n - 1;
int num = 1;
while (true) {
for (int j = beginX; j <= endX; ++j) matrix[beginY][j] = num++;
if (++beginY > endY) break;
for (int i = beginY; i <= endY; ++i) matrix[i][endX] = num++;
if (beginX > --endX) break;
for (int j = endX; j >= beginX; --j) matrix[endY][j] = num++;
if (beginY > --endY) break;
250
15
for (int i = endY; i >= beginY; --i) matrix[i][beginX] = num++;

if (++beginX > endX) break;
}
return matrix;
}
};
Spiral Matrix,
15.10
15.12 ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you
may want to display this pattern in a fixed font for better legibility)
P
A
H
N
A P L S I I G
Y
I
R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string text, int nRows);
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".
n=4:
P
I
N
A
L S
I G
Y A
H R
P
I
n=5:
P
H
A
S I
Y
I
R
P L
I
A
N
G
(i, j) = (j + 1) n + i
(i, j) = (j + 1) n i
15.13 Divide Two Integers
// LeetCode, ZigZag Conversion

//
O(n)
O(1)
class Solution {
public:
string convert(string s, int nRows) {
if (nRows <= 1 || s.size() <= 1) return s;
string result;
for (int i = 0; i < nRows; i++) {
for (int j = 0, index = i; index < s.size();
j++, index = (2 * nRows - 2) * j + i) {
result.append(1, s[index]); //
if (i == 0 || i == nRows - 1) continue;
//
if (index + (nRows - i - 1) * 2 < s.size())
result.append(1, s[index + (nRows - i - 1) * 2]);
}
}
return result;
}
};
15.13 Divide Two Integers

Divide two integers without using multiplication, division and mod operator.
1
// LeetCode, Divide Two Integers
//
O(logn)
O(1)
class Solution {
public:
int divide(int dividend, int divisor) {
//
dividend = INT_MIN
-dividend
long long
long long a = dividend >= 0 ? dividend : -(long long)dividend;
long long b = divisor >= 0 ? divisor : -(long long)divisor;
251
252
15
//
dividend = INT_MIN
divisor = -1
long long result = 0;
while (a >= b) {
long long c = b;
for (int i = 0; a >= c; ++i, c <<= 1) {
a -= c;
result += 1 << i;
}
}
long long
return ((dividend^divisor) >> 31) ? (-result) : (result);

}
};
2
// LeetCode, Divide Two Integers
//
O(logn)
O(1)
class Solution {
public:
int divide(int dividend, int divisor) {
int result = 0; //
dividend = INT_MIN
divisor = -1
const bool sign = (dividend > 0 && divisor < 0) ||
(dividend < 0 && divisor > 0); //
//
dividend = INT_MIN
-dividend
unsigned int
unsigned int a = dividend >= 0 ? dividend : -dividend;
unsigned int b = divisor >= 0 ? divisor : -divisor;
while (a >= b) {
int multi = 1;
unsigned int bb = b;
while (a >= bb) {
a -= bb;
result += multi;
if (bb < INT_MAX >> 1) { //
bb += bb;
multi += multi;
}
}
}
if (sign) return -result;
else return result;
}
};
15.14 Text Justification
253
15.14 Text Justification

Given an array of words and a length L, format the text such that each line has exactly L characters and
is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line.
Pad extra spaces ' ' when necessary so that each line has exactly L characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a
line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the
slots on the right.
For the last line of text, it should be left justified and no extra space is inserted between words.
For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.
Return the formatted lines as:
[
"This
is
an",
"example of text",
"justification. "
]
Note: Each word is guaranteed not to exceed L in length.
Corner Cases:
A line other than the last line might contain only one word. What should you do in this case?
In this case, that line should be left
// LeetCode, Text Justification

//
O(n)
O(1)
class Solution {
public:
vector<string> fullJustify(vector<string> &words, int L) {
const int n = words.size();
int begin = 0, len = 0; //
for (int i = 0; i < n; ++i) {
if (len + words[i].size() + (i - begin) > L) {
result.push_back(connect(words, begin, i - 1, len, L, false));
254
15
begin = i;
len = 0;
}
len += words[i].size();
}
//
L
result.push_back(connect(words, begin, n - 1, len, L, true));
return result;
}
/**
* @brief
words[begin, end]
* @param[in] words
* @param[in] begin
* @param[in] end
* @param[in] len words[begin, end]
* @param[in] L
* @param[in] is_last
* @return
*/
string connect(vector<string> &words, int begin, int end,
int len, int L, bool is_last) {
string s;
int n = end - begin + 1;
for (int i = 0; i < n; ++i) {
s += words[begin + i];
addSpaces(s, i, n - 1, L - len, is_last);
}
if (s.size() < L) s.append(L - s.size(), ' ');
return s;
}
/**
* @brief
.
* @param[inout]s
* @param[in] i
* @param[in] n
* @param[in] L
* @param[in] is_last
* @return
*/
void addSpaces(string &s, int i, int n, int L, bool is_last) {
if (n < 1 || i > n - 1) return;
int spaces = is_last ? 1 : (L / n + (i < (L % n) ? 1 : 0));
s.append(spaces, ' ');
}
};
255
15.15 Max Points on a Line
15.15 Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
1
n(n + 1)
2
n
O(n3 )
key
O(n2 )
value
O(n)

//
O(n^3)
class Solution {
public:
int maxPoints(vector<Point> &points) {
if (points.size() < 3) return points.size();
int result = 0;
O(1)
for (int i = 0; i < points.size() - 1; i++) {

for (int j = i + 1; j < points.size(); j++) {
int sign = 0;
int a, b, c;
if (points[i].x == points[j].x) sign = 1;
else {
a = points[j].x - points[i].x;
b = points[j].y - points[i].y;
c = a * points[i].y - b * points[i].x;
}
int count = 0;
for (int k = 0; k < points.size(); k++) {
if ((0 == sign && a * points[k].y == c + b * points[k].x) ||
(1 == sign&&points[k].x == points[j].x))
count++;
}
if (count > result) result = count;
}
}
return result;
}
};
256
15

//
O(n^2)
O(n)
class Solution {
public:
int maxPoints(vector<Point> &points) {
if (points.size() < 3) return points.size();
int result = 0;
unordered_map<double, int> slope_count;
for (int i = 0; i < points.size()-1; i++) {
slope_count.clear();
int samePointNum = 0; //
i
int point_max = 1;
//
i
for (int j = i + 1; j < points.size(); j++) {
double slope; //
if (points[i].x == points[j].x) {
slope = std::numeric_limits<double>::infinity();
if (points[i].y == points[j].y) {
++ samePointNum;
continue;
}
} else {
slope = 1.0 * (points[i].y - points[j].y) /
(points[i].x - points[j].x);
}
int count = 0;
if (slope_count.find(slope) != slope_count.end())
count = ++slope_count[slope];
else {
count = 2;
slope_count[slope] = 2;
}
if (point_max < count) point_max = count;
}
result = max(result, point_max + samePointNum);
}
return result;
}
};

Leetcode CPP

Uploaded by

Copyright:

Available Formats

Leetcode CPP

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Leetcode CPP

Uploaded by

Copyright:

Available Formats

LeetCode

LeetCode Online Judge

Robert Sedgewick, Addison-Wesley Professional, http://book.douban.com/subject/4854123/

from Sorted Array . . .

2.1.23 Single Number . . . . .

2.1.24 Single Number II . . . .

Add Two Numbers . . .

Reverse Linked List II .

from Sorted List . . . .

Median of Two Sorted

2.1.21 Gas Station . . . . . . .

from Sorted Array II . .

2.1.20 Set Matrix Zeroes . . . .

from Sorted List II . . .

From End of List . . . .

Swap Nodes in Pairs . .

Reverse Nodes in k-Group 49

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 . . . . . . .

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 . . . . . 30

2.1.19 Gray Code . . . . . . .

String to Integer (atoi) . . . . .

Longest Palindromic Substring . 62

Regular Expression Matching . .

Longest Common Prefix . . . . 69

Binary Tree Level Order Traversal II . . . . .

Level Order Traversal .

Recover Binary Search

3.10 Integer to Roman . . . . . . . .

3.11 Roman to Integer . . . . . . . .

Symmetric Tree . . . . . 100

3.12 Count and Say . . . . . . . . . . 74

5.1.10 Balanced Binary Tree . . 102

5.1.11 Flatten Binary Tree to

Linked List . . . . . . . 103

3.14 Simplify Path . . . . . . . . . . 76

5.1.12 Populating Next Right

Pointers in Each Node II 105

Construct Binary Tree

from Preorder and In-

Longest Valid Paren-

order Traversal . . . . . 106

torder Traversal . . . . . 107

Evaluate Reverse Polish Notation . . . . . . .

from Inorder and Pos-

Convert Sorted Array to

Binary Search Tree . . . 112

Binary Tree Postorder

Validate Binary Search

Binary Tree Inorder

Binary Tree Preorder