算法题目分类与总结

对遇到的算法题进行分类,归纳整理,形成自己的解题思想。

二分搜索

经典二分查找问题

题目描述:经典二分查找问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int findPosition(vector<int> &nums, int target) {
// write your code here
if (nums.empty()) {
return -1;
}
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = left + ((right - left) / 2);
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
return mid;
}
}
return -1;
}


二分查找(找到第一个)

题目描述:First Position of Target

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int findPosition(vector<int> &nums, int target) {
if (nums.empty()) {
return -1;
}
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = left + ((right - left) / 2);
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
return mid;
}
}
return -1;
}


二分查找(找到最后一个)

题目描述:Last Position of Target

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int lastPosition(vector<int> &nums, int target) {
int start = 0;
int end = nums.size() - 1;
int res = -1;
while (start <= end) {
int mid = start + ((end - start) >> 1);
if (nums[mid] <= target) {
start = mid + 1;
res = mid;
} else {
end = mid - 1;
}
}
if (res != -1 && nums[res] != target) {
return -1;
}
return res;
}


第一个错误的代码版本

题目描述:第一个错误的代码版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int findFirstBadVersion(int n) {
// write your code here
if (n < 1) return -1;
int start = 1;
int end = n;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (SVNRepo::isBadVersion(mid)) {
end = mid;
} else {
start = mid;
}
}
if (SVNRepo::isBadVersion(start)) {
return start;
} else if (SVNRepo::isBadVersion(end)) {
return end;
}
return -1;
}

面试官更喜欢的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int findFirstBadVersion(int n) {
int start = 1;
int end = n;
int res = -1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (SVNRepo::isBadVersion(mid)) {
res = mid;
end = mid-1;
} else {
start = mid+1;
}
}
return res;
}


Search a 2D Matrix

题目描述:Search a 2D Matrix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
/**
* @param matrix: matrix, a list of lists of integers
* @param target: An integer
* @return: a boolean, indicate whether matrix contains target
*/
bool searchMatrix(vector<vector<int>> &matrix, int target) {
if (matrix.empty() || matrix[0].empty()) {
return false;
}
int n = matrix.size();
int m = matrix[0].size();
int top = 0;
int bottom = n - 1;
int row = 0;
while (top <= bottom) {
int mid = top + ((bottom - top) >> 1);
if (matrix[mid][0] <= target) {
row = mid;
top = mid + 1;
} else {
bottom = mid - 1;
}
}
int left = 0;
int right = m - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (matrix[row][mid] > target) {
right = mid - 1;
} else if (matrix[row][mid] < target) {
left = mid + 1;
} else {
return true;
}
}
return false;
}
};


Search a 2D Matrix II

题目描述:Search a 2D Matrix II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int searchMatrix(vector<vector<int>> &matrix, int target) {
// write your code here
if (matrix.size() == 0 || matrix[0].size() == 0) return 0;
int m = matrix.size()-1;
int n = matrix[0].size()-1;
int j = n;
int i = 0;
int count = 0;
while (i <=m && j >= 0) {
if (matrix[i][j] < target) {
++i;
} else if (matrix[i][j] > target) {
--j;
} else {
++count;
++i;
--j;
}
}
return count;
}


Search for a Range

题目描述:Search for a Range

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
vector<int> searchRange(vector<int> &A, int target) {
// write your code here
vector<int> result;
if (A.size() == 0) return vector<int>({-1, -1});
int start = 0;
int end = A.size() - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (target <= A[mid]) {
end = mid;
} else {
start = mid;
}
}
if (A[start] == target) {
result.push_back(start);
} else if (A[end] == target) {
start = end;
result.push_back(end);
} else {
return vector<int>({-1, -1});
}
for (int i=start; i<A.size(); ++i) {
if (A[i] != target) {
break;
}
end = i;
}
result.push_back(end);
return result;
}


寻找峰值

题目描述:寻找峰值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
/*
* @param A: An integers array.
* @return: return any of peek positions.
*/
int findPeak(vector<int>& A) {
if (A.empty() || A.size() < 3) {
return -1;
}
int start = 0;
int end = A.size() - 1;
while (start <= end) {
int mid = start + ((end - start) >> 1);
if (A[mid + 1] < A[mid] && A[mid] > A[mid - 1]) {
return mid;
} else if (A[mid + 1] > A[mid]) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return -1;
}
};


寻找旋转排序数组中的最小值

题目描述:寻找旋转排序数组中的最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
/**
* @param nums: a rotated sorted array
* @return: the minimum number in the array
*/
int findMin(vector<int> &nums) {
int start = 0;
int end = nums.size() - 1;
int target = nums[end];
int res = -1;
while (start <= end) {
int mid = start + ((end - start) >> 1);
if (nums[mid] <= target) {
end = mid - 1;
res = mid;
} else {
start = mid + 1;
}
}
return nums[res];
}
};


搜索旋转排序数组

题目描述:搜索旋转排序数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
/**
* @param A: an integer rotated sorted array
* @param target: an integer to be searched
* @return: an integer
*/
int search(vector<int> &A, int target) {
if (A.empty()) {
return -1;
}
int start = 0;
int end = A.size() - 1;
while (start <= end) {
int mid = start + ((end - start) >> 1);
if (A[mid] == target) {
return mid;
}
if (A[end] >= A[mid]) {
if (A[mid] < target && target <= A[end]) {
start = mid + 1;
} else {
end = mid - 1;
}
} else {
if (A[mid] > target && target >= A[start]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
}
return -1;
}
};


x的平方根

题目描述:x的平方根

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int sqrt(int x) {
if (x < 0) {
return -1;
}
if (x <= 1) {
return x;
}
int start = 1;
int end = x;
int res = 0;
while (start <= end) {
int mid = start + ((end - start) >> 1);
if (mid <= x / mid) {
res = mid;
start = mid + 1;
} else {
end = mid - 1;
}
}
return res;
}


x的平方根II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
double sqrt(double x) {
double start = 0;
double end = x;
double dicision = 1e-12;
if (end < 1.0) {
end = 1.0;
}
while (end - start > dicision) {
double mid = (start + end) / 2;
if (mid * mid > x) {
end = mid;
} else {
start = mid;
}
}
return start;
}

寻找重复数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 解法一
int findDuplicate(vector<int> &nums) {
if (nums.empty()) {
return 0;
}
int start = 0;
int end = nums.size() - 1;
while (start < end) {
int mid = start + ((end - start) >> 1);
int cnt = 0;
for (auto n : nums) {
if (n <= mid) {
cnt++;
}
}
if (cnt <= mid) {
start = mid + 1;
} else {
end = mid;
}
}
return start;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 解法二
int findDuplicate(vector<int> &nums) {
if (nums.empty()) {
return 0;
}
int slow = 0;
int fast = 0;
int t = 0;
while (true) {
slow = nums[slow];
fast = nums[nums[fast]];
if (slow == fast) {
break;
}
}
while (true) {
t = nums[t];
slow = nums[slow];
if (t == slow) {
break;
}
}
return t;
}

木材加工

题目描述:木材加工

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
int maxWood(vector<int> &L) {
int max = L[0];
for (int i=1; i<L.size(); ++i) {
if (L[i] > max) {
max = L[i];
}
}
return max;
}
int woodCutCount(vector<int> &L, int wood) {
int count = 0;
for (int i=0; i<L.size(); ++i) {
count += int(L[i]/wood);
}
return count;
}
int woodCut(vector<int> &L, int k) {
// write your code here
if (L.size() == 0) return 0;
int start = 1;
int end = maxWood(L);
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (woodCutCount(L, mid) < k) {
end = mid;
} else {
start = mid;
}
}
if (woodCutCount(L, start) == k) {
return start;
} else if (woodCutCount(L, end) == k) {
return end;
} else if (woodCutCount(L, start) < k) {
return 0;
}
return start;
}


Copy Books

题目描述:Copy Books

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
int maxPages(vector<int> &pages) {
int maxPage = INT32_MIN;
for (int i=0; i<pages.size(); ++i) {
maxPage = max(maxPage, pages[i]);
}
return maxPage;
}
int countCopies(vector<int> &pages, int limit) {
int count = 1;
int sum = pages[0];
for (int i=1; i<pages.size(); ++i) {
if (sum + pages[i] > limit) {
++count;
sum = 0;
}
sum += pages[i];
}
return count;
}
int copyBooks(vector<int> &pages, int k) {
// write your code here
if (pages.size() == 0) return 0;
int start = maxPages(pages);
int sum = accumulate(pages.begin(), pages.end(), 0);
int end = sum;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (countCopies(pages, mid) > k) {
start = mid;
} else {
end = mid;
}
}
if (countCopies(pages, start) <= k) {
return start;
}
return end;
}


Smallest Rectangle Enclosing Black Pixels

题目描述:Smallest Rectangle Enclosing Black Pixels

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
int minArea(vector<vector<char>> &image, int x, int y) {
if (image.size() == 0 || image[0].size() == 0) {
return 0;
}
int n = image.size();
int m = image[0].size();
int left = findLeft(image, 0, y);
int right = findRight(image, y, m-1);
int top = findTop(image, 0, x);
int bottom = findBottom(image, x, n-1);
return (right - left + 1) * (bottom - top + 1);
}
int findLeft(vector<vector<char>> &image, int x, int y) {
int start = x;
int end = y;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (isEmptyRow(image, mid)) {
start = mid;
} else {
end = mid;
}
}
if (isEmptyRow(image, start)) {
return end;
}
return start;
}
int findRight(vector<vector<char>> &image, int x, int y) {
int start = x;
int end = y;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (isEmptyRow(image, mid)) {
end = mid;
} else {
start = mid;
}
}
if (isEmptyRow(image, end)) {
return start;
}
return end;
}
int findTop(vector<vector<char>> &image, int x, int y) {
int start = x;
int end = y;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (isEmptyColumn(image, mid)) {
start = mid;
} else {
end = mid;
}
}
if (isEmptyColumn(image, start)) {
return end;
}
return start;
}
int findBottom(vector<vector<char>> &image, int x, int y) {
int start = x;
int end = y;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (isEmptyColumn(image, mid)) {
end = mid;
} else {
start = mid;
}
}
if (isEmptyColumn(image, end)) {
return start;
}
return end;
}
bool isEmptyRow(vector<vector<char>> &image, int y) {
for (int i=0; i<image.size(); ++i) {
if (image[i][y] == '1') {
return false;
}
}
return true;
}
bool isEmptyColumn(vector<vector<char>> &image, int x) {
for (int i=0; i<image[0].size(); ++i) {
if (image[x][i] == '1') {
return false;
}
}
return true;
}


Maximum Average Subarray

题目描述:Maximum Average Subarray

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class Solution {
/**
* @param nums an array with positive and negative numbers
* @param k an integer
* @return the maximum average
*/
public double findMaxAverage(int[] nums, int k) {
// Write your code here
double l = Integer.MAX_VALUE, r = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; ++i) {
if (nums[i] < l)
l = nums[i];
if (nums[i] > r)
r = nums[i];
}
while (r - l >= 1e-6) {
double mid = (l + r) / 2.0;
if (check_valid(nums, mid, k)) {
l = mid;
}
else {
r = mid;
}
}
return l;
}
private boolean check_valid(int nums[], double mid, int k) {
int n = nums.length;
double min_pre = 0;
double[] sum = new double[n + 1];
sum[0] = 0;
for (int i = 1; i <= n; ++i) {
sum[i] = sum[i - 1] + nums[i - 1] - mid;
if (i >= k && sum[i] - min_pre >= 0) {
return true;
}
if (i >= k)
min_pre = Math.min(min_pre, sum[i - k + 1]);
}
return false;
}
}


寻找峰值II

题目描述:寻找峰值II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Solution {
public:
/*
* @param A: An integer matrix
* @return: The index of the peak
*/
vector<int> findPeakII(vector<vector<int>> &A) {
vector<int> res;
if (A.empty() || A[0].empty()) {
return res;
}
int top = 1;
int bottom = A.size() - 2;
int left = 1;
int right = A[0].size() - 2;
while (top <= bottom && left <= right) {
// 计算行的二分点
int mid = top + ((bottom - top) >> 1);
int col = findPeakCol(A, mid, left, right);
if (A[mid][col] > A[mid - 1][col] && A[mid][col] > A[mid + 1][col]) {
res.push_back(mid);
res.push_back(col);
return res;
} else if (A[mid][col] > A[mid - 1][col]) {
top = mid + 1;
} else {
bottom = mid - 1;
}
// 计算列的二分点
mid = left + ((right - left) >> 1);
int row = findPeakRow(A, mid, top, bottom);
if (A[row][mid] > A[row][mid - 1] && A[row][mid] > A[row][mid + 1]) {
res.push_back(row);
res.push_back(mid);
return res;
} else if (A[row][mid] > A[row][mid - 1]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return res;
}
int findPeakRow(vector<vector<int>> &A, int col, int top, int bottom) {
int row = top;
for (int i=top; i<=bottom; ++i) {
if (A[i][col] > A[row][col]) {
row = i;
}
}
return row;
}
int findPeakCol(vector<vector<int>> &A, int row, int left, int right) {
int col = left;
for (int i=left; i<=right; ++i) {
if (A[row][i] > A[row][col]) {
col = i;
}
}
return col;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
/*
* @param A: An integer matrix
* @return: The index of the peak
*/
vector<int> findPeakII(vector<vector<int>> &A) {
vector<int> res;
if (A.empty() || A[0].empty()) {
return res;
}
int t = 1;
int b = A.size() - 2;
while (t <= b) {
int mid = t + ((b - t) >> 1);
int col = findPeakArray(A, mid);
if (A[mid][col] > A[mid - 1][col] && A[mid][col] > A[mid + 1][col]) {
res.push_back(mid);
res.push_back(col);
return res;
} else if (A[mid][col] > A[mid - 1][col]) {
t = mid + 1;
} else {
b = mid - 1;
}
}
return res;
}
int findPeakArray(vector<vector<int>> &A, int row) {
int col = 0;
for (int i=0; i<A[row].size(); ++i) {
if (A[row][i] > A[row][col]) {
col = i;
}
}
return col;
}
};

链表

链表求和

题目描述:链表求和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
ListNode * addLists(ListNode * l1, ListNode * l2) {
// write your code here
if (l1 == NULL || l2 == NULL) return l1==NULL ? l2 : l1;
ListNode *dummy = new ListNode(0);
ListNode *pNext = dummy;
int c = 0; // 进位
while (l1 != NULL && l2 != NULL) {
int num = (l1->val+l2->val+c) % 10;
c = (l1->val+l2->val+c) / 10;
ListNode *node = new ListNode(num);
pNext->next = node;
pNext = node;
l1 = l1->next;
l2 = l2->next;
}
ListNode *l3 = l1==NULL ? l2 : l1;
while (l3 != NULL) {
int num = (l3->val+c) % 10;
c = (l3->val+c) / 10;
ListNode *node = new ListNode(num);
pNext->next = node;
pNext = node;
l3 = l3->next;
}
if (c == 1) {
pNext->next = new ListNode(1);
}
return dummy->next;
}


翻转链表

题目描述:翻转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
/**
* @param head: n
* @return: The new head of reversed linked list.
*/
ListNode * reverse(ListNode * head) {
ListNode *cur = head;
ListNode *next = head;
ListNode *pre = NULL;
while (cur != NULL) {
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
};


翻转链表 II

题目描述:翻转链表 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
ListNode * reverseBetween(ListNode * head, int m, int n) {
// write your code here
if (head == NULL || head->next == NULL) return head;
ListNode *dummy = new ListNode(0);
dummy->next = head;
ListNode *pre = dummy;
for (int i=0; i<m-1; ++i) {
pre = pre->next;
}
ListNode *pHead = pre;
pre = pre->next;
ListNode *cur = pre->next;
ListNode *next = NULL;
for (int i=m; i<n; ++i) {
next = cur->next;
pre->next = next;
cur->next = pHead->next;
pHead->next = cur;
cur = next;
}
return dummy->next;
}


删除排序链表中的重复元素

题目描述:删除排序链表中的重复元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
ListNode * deleteDuplicates(ListNode * head) {
// write your code here
if (head == NULL || head->next == NULL) return head;
ListNode *dummy = new ListNode(0);
dummy->next = head;
ListNode *pre = head;
ListNode *cur = pre->next;
while (cur != NULL) {
if (pre->val == cur->val) {
ListNode *tmp = cur;
pre->next = cur->next;
delete tmp;
} else {
pre = pre->next;
}
cur = cur->next;
}
return dummy->next;
}


删除排序链表中的重复数字 II

题目描述:删除排序链表中的重复数字 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
ListNode * deleteDuplicates(ListNode * head) {
// write your code here
if (head == NULL || head->next == NULL) return head;
ListNode *dummy = new ListNode(0);
dummy->next = head;
ListNode *pPre = dummy;
ListNode *pCur = head;
ListNode *pNext = pCur->next;
while (pNext != NULL) {
if (pCur->val == pNext->val) {
while(pNext != NULL && (pNext->val == pCur->val)) {
pCur->next = pNext->next;
delete pNext;
pNext = pCur->next;
}
pPre->next = pCur->next;
delete pCur;
pCur = pPre->next;
if (pCur != NULL) pNext = pCur->next;
} else {
pPre = pCur;
pCur = pNext;
pNext = pCur->next;
}
}
return dummy->next;
}


链表划分

题目描述:链表划分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
ListNode * partition(ListNode * head, int x) {
// write your code here
if (head == NULL || head->next == NULL) return head;
ListNode *dummyLeft = new ListNode(0);
ListNode *dummyRight = new ListNode(0);
ListNode *pLeft = dummyLeft;
ListNode *pRight = dummyRight;
ListNode *pNext = head;
while (pNext != NULL) {
if (pNext->val < x) {
pLeft->next = pNext;
pLeft = pLeft->next;
} else {
pRight->next = pNext;
pRight = pRight->next;
}
pNext = pNext->next;
}
pLeft->next = dummyRight->next;
pRight->next = NULL;
head = dummyLeft->next;
delete dummyLeft;
delete dummyRight;
return head;
}


合并两个链表

题目描述:Merge Two Sorted Lists

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
/**
* @param l1: ListNode l1 is the head of the linked list
* @param l2: ListNode l2 is the head of the linked list
* @return: ListNode head of linked list
*/
ListNode * mergeTwoLists(ListNode * l1, ListNode * l2) {
ListNode dummy(0);
ListNode *head = &dummy;
while (l1 != NULL && l2 != NULL) {
if (l1->val < l2->val) {
head->next = l1;
l1 = l1->next;
} else {
head->next = l2;
l2 = l2->next;
}
head = head->next;
}
ListNode *l3 = l1 == NULL ? l2 : l1;
while (l3 != NULL) {
head->next = l3;
l3 = l3->next;
head = head->next;
}
return dummy.next;
}
};


两个链表的交叉

题目描述:两个链表的交叉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
ListNode * getIntersectionNode(ListNode * headA, ListNode * headB) {
if (headA == NULL || headB == NULL) return NULL;
int mA = 0;
int mB = 0;
ListNode *pNextA = headA;
ListNode *pNextB = headB;
for (; pNextA != NULL; pNextA = pNextA->next, ++mA);
for (; pNextB != NULL; pNextB = pNextB->next, ++mB);
pNextA = headA;
pNextB = headB;
if (mA < mB) {
swap(pNextA, pNextB);
swap(mA, mB);
}
for (int i=0; i<mA-mB; ++i, pNextA = pNextA->next);
while (pNextA != NULL && pNextB != NULL) {
if (pNextA == pNextB) {
return pNextA;
}
pNextA = pNextA->next;
pNextB = pNextB->next;
}
return NULL;
}


交换链表当中两个节点

题目描述:Swap Two Nodes in Linked List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
ListNode * swapNodes(ListNode * head, int v1, int v2) {
ListNode dummy(0);
dummy.next = head;
// find swap node
ListNode *pre1 = &dummy;
ListNode *pre2 = &dummy;
while (pre1->next != NULL) {
if (pre1->next->val == v1) {
break;
}
pre1 = pre1->next;
}
while (pre2->next != NULL) {
if (pre2->next->val == v2) {
break;
}
pre2 = pre2->next;
}
if (pre1->next == NULL || pre2->next == NULL) {
return head;
}
ListNode *cur1 = pre1->next;
ListNode *cur2 = pre2->next;
if (cur1->next == cur2) {
pre1->next = cur2;
ListNode *next = cur2->next;
cur2->next = cur1;
cur1->next = next;
} else if (cur2->next == cur1) {
pre2->next = cur1;
ListNode *next = cur1->next;
cur1->next = cur2;
cur2->next = next;
} else {
pre1->next = cur2;
ListNode *next = cur2->next;
cur2->next = cur1->next;
pre2->next = cur1;
cur1->next = next;
}
return dummy.next;
}


K组翻转链表

题目描述:Reverse Nodes in k-Group

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
ListNode * reverseKGroup(ListNode * head, int k) {
ListNode dummy(0);
dummy.next = head;
head = &dummy;
while (true) {
head = reverse(head, k);
if (head == NULL) {
break;
}
}
return dummy.next;
}
ListNode *reverse(ListNode *head, int k) {
ListNode *curNext = head;
for (int i=0; i<k; ++i) {
if (curNext == NULL) {
return NULL;
}
curNext = curNext->next;
}
if (curNext == NULL) {
return NULL;
}
// reverse
ListNode *curHead = head->next;
ListNode *nextPlus = curNext->next;
ListNode *pre = NULL;
ListNode *cur = curHead;
ListNode *next = NULL;
while (cur != nextPlus) {
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
// concat
head->next = curNext;
curHead->next = nextPlus;
return curHead;
}


重排链表

题目描述:Reorder List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
ListNode* middleList(ListNode *head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode *slow = head;
ListNode *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
ListNode* reverse(ListNode *head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode *pre = NULL;
ListNode *cur = head;
ListNode *next = NULL;
while (cur != NULL) {
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
void orderMerge(ListNode *head1, ListNode *head2) {
ListNode dummy(0);
dummy.next = head1;
ListNode *head = &dummy;
bool flag = true;
while (head1 != NULL && head2 != NULL) {
if (flag) {
head->next = head1;
head1 = head1->next;
flag = false;
} else {
head->next = head2;
head2 = head2->next;
flag = true;
}
head = head->next;
}
while (head1 != NULL) {
head->next = head1;
head1 = head1->next;
head = head->next;
}
while (head2 != NULL) {
head->next = head2;
head2 = head2->next;
head = head->next;
}
}
void reorderList(ListNode * head) {
if (head == NULL) {
return;
}
// middle node
ListNode *mNode = middleList(head);
ListNode *head1 = head;
ListNode *head2 = mNode->next;
mNode->next = NULL;
// reverse
head2 = reverse(head2);
// contact
orderMerge(head1, head2);
}


旋转链表

题目描述:Rotate List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
ListNode * rotateRight(ListNode * head, int k) {
if (head == NULL || k <= 0) {
return head;
}
int n = 0;
ListNode *next = head;
while (next != NULL) {
n++;
next = next->next;
}
k = k % n;
ListNode *pre = NULL;
next = head;
for (int i=0; i<n-k; ++i) {
pre = next;
next = next->next;
}
ListNode *newHead = next;
pre->next = NULL;
if (next == NULL) {
return head;
}
while (next != NULL) {
pre = next;
next = next->next;
}
pre->next = head;
return newHead;
}


复制带随机指针的链表

题目描述:Copy List with Random Pointer
map解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
RandomListNode *copyRandomList(RandomListNode *head) {
if (head == NULL) {
return NULL;
}
map<RandomListNode*, RandomListNode*> m;
RandomListNode *node = head;
while (node != NULL) {
m[node] = new RandomListNode(node->label);
node = node->next;
}
node = head;
while (node != NULL) {
m[node]->random = m[node->random];
m[node]->next = m[node->next];
node = node->next;
}
return m[head];
}

next解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
void copyNext(RandomListNode *head) {
RandomListNode *node = head;
while (node != NULL) {
RandomListNode *tmp = new RandomListNode(node->label);
RandomListNode *next = node->next;
node->next = tmp;
tmp->next = next;
node = next;
}
}
void copyRandom(RandomListNode *head) {
RandomListNode *node = head;
while (node != NULL) {
if (node->random != NULL) {
node->next->random = node->random->next;
} else {
node->next->random = NULL;
}
node = node->next->next;
}
}
RandomListNode* extractNode(RandomListNode *head) {
RandomListNode *node = head->next;
while (node != NULL && node->next != NULL) {
RandomListNode *tmp = node->next->next;
node->next = tmp;
node = tmp;
}
return head->next;
}
RandomListNode *copyRandomList(RandomListNode *head) {
if (head == NULL) {
return NULL;
}
copyNext(head);
copyRandom(head);
RandomListNode *newHead = extractNode(head);
return newHead;
}


链表排序

题目描述:Sort List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
ListNode* findMiddle(ListNode *head) {
ListNode *slow = head;
ListNode *fast = head->next;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
ListNode* merge(ListNode *head1, ListNode *head2) {
ListNode dummy(0);
ListNode *head = &dummy;
while (head1 != NULL && head2 != NULL) {
if (head1->val < head2->val) {
head->next = head1;
head1 = head1->next;
head = head->next;
} else {
head->next = head2;
head2 = head2->next;
head = head->next;
}
}
while (head1 != NULL) {
head->next = head1;
head1 = head1->next;
head = head->next;
}
while (head2 != NULL) {
head->next = head2;
head2 = head2->next;
head = head->next;
}
return dummy.next;
}
ListNode* mergeSort(ListNode *start, ListNode *end) {
if (start == end) {
return start;
}
ListNode *middle = findMiddle(start);
ListNode *middleNext = middle->next;
middle->next = NULL;
ListNode *left = mergeSort(start, middle);
ListNode *right = mergeSort(middleNext, end);
ListNode *head = merge(left, right);
return head;
}
ListNode * sortList(ListNode * head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode *end = head;
while (end->next != NULL) {
end = end->next;
}
mergeSort(head, end);
}


Convert Sorted List to Binary Search Tree

题目描述:Convert Sorted List to Binary Search Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
ListNode *findMiddlePre(ListNode *head) {
ListNode *pre = head;
ListNode *slow = head->next;
ListNode *fast = head->next->next;
while (fast != NULL && fast->next != NULL) {
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
return pre;
}
TreeNode * sortedListToBST(ListNode * head) {
if (head == NULL) {
return NULL;
}
ListNode dummy;
dummy.next = head;
head = &dummy;
ListNode *middlePre = findMiddlePre(head);
ListNode *middle = middlePre->next;
ListNode *middleNext = middle->next;
middlePre->next = NULL;
middle->next = NULL;
TreeNode *root = new TreeNode(middle->val);
root->left = sortedListToBST(dummy.next);
root->right = sortedListToBST(middleNext);
return root;
}


带环链表

题目描述:Linked List Cycle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
/*
* @param head: The first node of linked list.
* @return: True if it has a cycle, or false
*/
bool hasCycle(ListNode * head) {
if (head == NULL || head->next == NULL) {
return false;
}
ListNode *slow = head;
ListNode *fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
return true;
}
}
return false;
}
};


带环链表 II

题目描述:Linked List Cycle II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
/*
* @param head: The first node of linked list.
* @return: The node where the cycle begins. if there is no cycle, return null
*/
ListNode * detectCycle(ListNode * head) {
ListNode *slow = head;
ListNode *fast = head;
ListNode *node = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
break;
}
}
if (fast == NULL || fast->next == NULL) {
return NULL;
}
while (node != slow) {
node = node->next;
slow = slow->next;
}
return node;
}
};


链表插入排序

题目描述:Insertion Sort List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
/**
* @param head: The first node of linked list.
* @return: The head of linked list.
*/
ListNode * insertionSortList(ListNode * head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode dummy(0);
dummy.next = head;
ListNode *nodeCur = head->next;
ListNode *nodePre = head;
while (nodeCur != NULL) {
ListNode *pre = &dummy;
ListNode *cur = dummy.next;
ListNode *next = nodeCur->next;
while (cur != nodeCur && cur->val <= nodeCur->val) {
pre = cur;
cur = cur->next;
}
if (cur != nodeCur) {
nodeCur->next = cur;
pre->next = nodeCur;
nodePre->next = next;
} else {
nodePre = nodeCur;
}
nodeCur = next;
}
return dummy.next;
}
};

队列

拓扑排序

题目描述:拓扑排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*>& graph) {
// 求解入度
map<DirectedGraphNode*, int> indegree;
for (int i=0; i<graph.size(); ++i) {
if (indegree.count(graph[i]) == 0) {
indegree[graph[i]] = 0;
}
for (int j=0; j<graph[i]->neighbors.size(); ++j) {
if (indegree.count(graph[i]->neighbors[j]) == 0) {
indegree[graph[i]->neighbors[j]] = 0;
}
indegree[graph[i]->neighbors[j]] += 1;
}
}
vector<DirectedGraphNode*> result;
queue<DirectedGraphNode *> q;
for (int i=0; i<graph.size(); ++i) {
if (indegree[graph[i]] == 0) {
q.push(graph[i]);
}
}
while (!q.empty()) {
DirectedGraphNode *tmp = q.front();
q.pop();
result.push_back(tmp);
for (int j=0; j<tmp->neighbors.size(); ++j) {
indegree[tmp->neighbors[j]] -= 1;
if (indegree[tmp->neighbors[j]] == 0) {
q.push(tmp->neighbors[j]);
}
}
}
return result;
}


无向图中的最短路径

题目描述:无向图中的最短路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int shortestPath(vector<UndirectedGraphNode*> graph, UndirectedGraphNode* A, UndirectedGraphNode* B) {
// Write your code here
if (A == NULL || B == NULL) return 0;
map<UndirectedGraphNode *, int> distance;
queue<UndirectedGraphNode*> q;
q.push(A);
distance[A] = 0;
while (!q.empty()) {
UndirectedGraphNode *graphNode = q.front();
q.pop();
for (int j=0; j<graphNode->neighbors.size(); ++j) {
if (distance.count(graphNode->neighbors[j]) == 0 ||
distance[graphNode->neighbors[j]] > distance[graphNode]+1) {
distance[graphNode->neighbors[j]] = distance[graphNode]+1;
q.push(graphNode->neighbors[j]);
}
}
}
return distance[B];
}


有效的括号序列

题目描述:有效的括号序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
bool isMatched(char left, char right) {
if (left == '(' && right == ')') {
return true;
} else if (left == '{' && right == '}') {
return true;
} else if (left == '[' && right == ']') {
return true;
}
return false;
}
bool isValidParentheses(string &s) {
if (s.length() == 0) return false;
stack<char> sc;
for (auto c : s) {
if (c == '(' || c == '{' || c == '[') {
sc.push(c);
} else if (c == ')' || c == '}' || c == ']') {
if (sc.empty() || !isMatched(sc.top(), c)) {
return false;
}
sc.pop();
} else {
continue;
}
}
if (sc.empty()) {
return true;
}
return false;
}


最长括号匹配

题目描述:Longest Valid Parentheses

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int longestValidParentheses(string s) {
if (s.length() == 0) return 0;
stack<int> ss;
int start = -1;
int answer = 0;
for (int i=0; i<s.length(); ++i) {
if (s[i] == '(') {
ss.push(i);
} else {
if (ss.empty()) {
start = i;
} else {
ss.pop();
if (ss.empty()) {
answer = max(answer, i-start);
} else {
answer = max(answer, i-ss.top());
}
}
}
}
return answer;
}

时间复杂度:O(n)
空间复杂度:O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int longestValidParentheses(string s) {
if (s.length() == 0) return 0;
int depth = 0;
int answer = 0;
int start = -1;
for (int i=0; i<s.length(); ++i) {
if (s[i] == '(') {
++depth;
} else {
--depth;
if (depth == 0) {
answer = max(answer, i-start);
} else if (depth < 0){
depth = 0;
start = i;
}
}
}
depth = 0;
start = s.length();
for (int i=s.length()-1; i>=0; --i) {
if (s[i] == ')') {
++depth;
} else {
--depth;
if (depth == 0) {
answer = max(answer, start-i);
} else if (depth < 0) {
depth = 0;
start = i;
}
}
}
return answer;
}

时间复杂度:O(n)
空间复杂度:O(1)


栈的压入、弹出序列

题目描述:栈的压入、弹出序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
stack<int> s;
vector<int>::iterator popIt = popV.begin();
vector<int>::iterator pushIt = pushV.begin();
while(popIt != popV.end()) {
if (!s.empty() && (*popIt == s.top())) {
s.pop();
++popIt;
} else {
if (pushIt == pushV.end()) {
return false;
}
s.push(*pushIt);
++pushIt;
}
}
return true;
}


Decode String

题目描述:Decode String

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
string expressionExpand(string &s) {
stack<int> qstack;
int num = 0;
int flag = false;
for (int i=0; i<s.length(); ++i) {
if (isdigit(s[i])) {
num = num * 10 + s[i] - '0';
flag = true;
} else if (isalpha(s[i]) || s[i] == '[') {
if (flag) {
qstack.push(num);
flag = false;
num = 0;
}
qstack.push(s[i]);
} else if (s[i] == ']') {
string str;
while (qstack.top() != '[') {
str.push_back(qstack.top());
qstack.pop();
}
qstack.pop();
int n = qstack.top();
qstack.pop();
reverse(str.begin(), str.end());
for (int i=0; i<n; ++i) {
for (int j=0; j<str.size(); ++j) {
qstack.push(str[j]);
}
}
}
}
string res;
while (!qstack.empty()) {
res.push_back(qstack.top());
qstack.pop();
}
reverse(res.begin(), res.end());
return res;
}


用栈实现队列

题目描述:Implement Queue by Two Stacks

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class MyQueue {
private:
stack<int> stack1;
stack<int> stack2;
void fillup() {
if (stack2.empty()) {
while (!stack1.empty()) {
stack2.push(stack1.top());
stack1.pop();
}
}
}
public:
MyQueue() { }
/*
* @param element: An integer
* @return: nothing
*/
void push(int element) {
stack1.push(element);
}
/*
* @return: An integer
*/
int pop() {
fillup();
int top = stack2.top();
stack2.pop();
return top;
}
/*
* @return: An integer
*/
int top() {
fillup();
return stack2.top();
}
};


用队列实现栈

题目描述:Implement Stack by Two Queues

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Stack {
private:
queue<int> queue1;
queue<int> queue2;
bool isQueue1;
public:
/*
* @param x: An integer
* @return: nothing
*/
void push(int x) {
if (isQueue1) {
queue1.push(x);
} else {
queue2.push(x);
}
}
/*
* @return: nothing
*/
void pop() {
if (isQueue1) {
while (queue1.size() > 1) {
queue2.push(queue1.front());
queue1.pop();
}
if (queue1.size() == 1) {
queue1.pop();
}
} else {
while (queue2.size() > 1) {
queue1.push(queue2.front());
queue2.pop();
}
if (queue2.size() == 1) {
queue2.pop();
}
}
isQueue1 = !isQueue1;
}
/*
* @return: An integer
*/
int top() {
if (isQueue1) {
return queue1.back();
} else {
return queue2.back();
}
}
/*
* @return: True if the stack is empty
*/
bool isEmpty() {
return queue1.empty() && queue2.empty();
}
};

摊平嵌套的列表

题目描述:Flatten Nested List Iterator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class NestedIterator {
public:
stack<NestedInteger> snt;
NestedIterator(vector<NestedInteger> &nestedList) {
for (int i=nestedList.size()-1; i>=0; --i) {
snt.push(nestedList[i]);
}
}
// @return {int} the next element in the iteration
int next() {
int top = snt.top().getInteger();
snt.pop();
return top;
}
// @return {boolean} true if the iteration has more element or false
bool hasNext() {
while (!snt.empty()) {
if (snt.top().isInteger()) {
return true;
}
auto nestedList = snt.top().getList();
snt.pop();
for (int i=nestedList.size()-1; i>=0; --i) {
snt.push(nestedList[i]);
}
}
return false;
}
};

左旋右旋迭代器

题目描述:Zigzag Iterator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class ZigzagIterator {
public:
queue<int> q;
/*
* @param v1: A 1d vector
* @param v2: A 1d vector
*/
ZigzagIterator(vector<int>& v1, vector<int>& v2) {
bool flag = true;
int i = 0;
int j = 0;
while (i < v1.size() && j < v2.size()) {
if (flag) {
q.push(v1[i++]);
} else {
q.push(v2[j++]);
}
flag = !flag;
}
while (i < v1.size()) {
q.push(v1[i++]);
}
while (j < v2.size()) {
q.push(v2[j++]);
}
}
/*
* @return: An integer
*/
int next() {
int front = q.front();
q.pop();
return front;
}
/*
* @return: True if has next
*/
bool hasNext() {
return !q.empty();
}
};


左旋右旋迭代器 II

题目描述:Zigzag Iterator II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class ZigzagIterator2 {
public:
queue<int> q;
/*
* @param vecs: a list of 1d vectors
*/
ZigzagIterator2(vector<vector<int>>& vecs) {
int k = vecs.size();
vector<int> indexs(k);
int nMax = 0;
for (auto vec : vecs) {
nMax = max(nMax, (int)vec.size());
}
int count = 0;
while (count <= k * nMax) {
int i = count % k;
if (indexs[i] < vecs[i].size()) {
q.push(vecs[i][indexs[i]]);
++indexs[i];
}
++count;
}
}
/*
* @return: An integer
*/
int next() {
int front = q.front();
q.pop();
return front;
}
/*
* @return: True if has next
*/
bool hasNext() {
return !q.empty();
}
};


带最小值操作的栈

题目描述:Min Stack]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class MinStack {
private:
stack<int> s;
stack<int> minStack;
public:
MinStack() { }
/*
* @param number: An integer
* @return: nothing
*/
void push(int number) {
s.push(number);
if (minStack.empty() || number <= minStack.top()) {
minStack.push(number);
}
}
/*
* @return: An integer
*/
int pop() {
int top = s.top();
s.pop();
if (top == minStack.top()) {
minStack.pop();
}
return top;
}
/*
* @return: An integer
*/
int min() {
return minStack.top();
}
};


字符串

旋转字符串

题目描述:旋转字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Reverse(string &str, int from, int to) {
while (from < to) {
char t = str[from];
str[from++] = str[to];
str[to--] = t;
}
}
void rotateString(string &str, int offset) {
if (str.length() == 0) return;
int n = str.length();
offset %= n;
Reverse(str, 0, n - offset - 1);
Reverse(str, n - offset, n - 1);
Reverse(str, 0, n - 1);
}

时间复杂度:O(n)
空间复杂度:O(1)


最长公共子序列

题目描述:Longest Common Subsequence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
string longestCommonSubsequence(string &A, string &B) {
vector<vector<int>> d(A.size()+1, vector<int>(B.size()+1));
for (int i=1; i<=A.size(); ++i) {
for (int j=1; j<=B.size(); ++j) {
if (A[i-1] == B[j-1]) {
d[i][j] = d[i-1][j-1]+1;
} else {
d[i][j] = max(d[i][j-1], d[i-1][j]);
}
}
}
int i = A.size();
int j = B.size();
string subStr;
while ((i!=0) && (j!=0)) {
if (A[i-1] == B[j-1]) {
subStr.push_back(A[i-1]);
--i;
--j;
} else {
if (d[i][j-1] > d[i-1][j]) {
--j;
} else {
--i;
}
}
}
reverse(subStr.begin(), subStr.end());
return subStr;
}


全排列

题目描述:全排列
递归做法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void helper(vector<int> &nums, int n, vector<int> &permute, vector<vector<int>> &result) {
if (n == nums.size()) {
result.push_back(permute);
}
for (int i=n; i<nums.size(); ++i) {
swap(nums[i], nums[n]);
permute.push_back(nums[n]);
helper(nums, n+1, permute, result);
swap(nums[i], nums[n]);
permute.pop_back();
}
}
vector<vector<int>> permute(vector<int> &nums) {
if (nums.size() == 0) {
return vector<vector<int>>(1, vector<int>());
}
vector<vector<int>> result;
vector<int> perm;
helper(nums, 0, perm, result);
return result;
}

时间复杂度:O((n+1)!)
空间复杂度:O(n*n!)


非递归做法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
void Reverse(vector<int> &nums, int from, int to) {
while (from < to) {
int t = nums[from];
nums[from++] = nums[to];
nums[to--] = t;
}
}
bool getLittlePermute(vector<int> &nums, vector<vector<int>> &result) {
// 后找
int i = nums.size()-2;
while (i>=0 && nums[i] >= nums[i+1]) {
i--;
}
if (i<0) return false;
// 大小
int j = nums.size()-1;
while(nums[i] >= nums[j]) {
--j;
}
// 交换
swap(nums[i], nums[j]);
// 翻转
Reverse(nums, i+1, nums.size()-1);
result.push_back(nums);
}
vector<vector<int>> permute(vector<int> &nums) {
if (nums.size() == 0) {
return vector<vector<int>>(1, vector<int>());
}
sort(nums.begin(), nums.end());
vector<vector<int>> result;
result.push_back(nums);
while(getLittlePermute(nums, result));
return result;
}

时间复杂度:O((n+1)!)
空间复杂度:O(n*n!)


最长回文子串

题目描述:最长回文子串
暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
string longestPalindrome(string &s) {
// write your code here
if (s.length() == 0) return string();
int n = s.length();
string result;
string str;
for (int i=0; i<n; ++i) {
str.clear();
str.push_back(s[i]);
// 奇数点
for (int j=i-1, k=i+1; j>=0&&k<n; --j, ++k) {
if (s[j] == s[k]) {
str = s[j] + str + s[k];
} else {
break;
}
}
if (str.length() > result.length()) {
result = str;
}
str.clear();
// 偶数点
for (int j=i, k=i+1; j>=0&&k<n; --j, ++k) {
if (s[j] == s[k]) {
str = s[j] + str + s[k];
} else {
break;
}
}
if (str.length() > result.length()) {
result = str;
}
}
return result;
}

Manacher算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
string constructString(string &s) {
string result;
result.push_back('$');
for (int i=0; i<s.length(); ++i) {
result.push_back('#');
result.push_back(s[i]);
}
result.push_back('#');
return result;
}
string Manacher(string &s) {
vector<int> p(s.length());
int id = 0;
int mx = 1;
int mxIndex = 1;
int mxLength = 0;
for (int i=1; i<s.length(); ++i) {
if (mx > i) {
p[i] = min(p[2*id-i], mx-i);
} else {
p[i] = 1;
}
for (; s[i-p[i]] == s[i+p[i]]; p[i]++);
if (mx < i + p[i]) {
mx = i + p[i];
id = i;
}
if (mxLength < p[i]) {
mxLength = p[i];
mxIndex = i;
}
}
string result;
mxLength--;
for (int i=mxIndex-mxLength; i<=mxIndex+mxLength; ++i) {
if (s[i] != '#') {
result.push_back(s[i]);
}
}
return result;
}
string longestPalindrome(string &s) {
if (s.length() == 0) return string();
string newS = constructString(s);
string result = Manacher(newS);
return result;
}

时间复杂度:O(n)
空间复杂度:O(n)

字符串查找(KMP)

题目描述:字符串查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
vector<int> getNext(const char *target) {
int n = strlen(target);
vector<int> next(n);
next[0] = -1;
int k = -1;
int j = 0;
while (j < n - 1) {
if (k == -1 || target[j] == target[k]) {
++j;
++k;
next[j] = k;
} else {
k = next[k];
}
}
return next;
}
int strStr(const char *source, const char *target) {
if (source == NULL || target == NULL) {
return -1;
}
if (strlen(target) == 0) {
return 0;
}
vector<int> next = getNext(target);
int n = strlen(source);
int m = strlen(target);
int i = 0;
int j = 0;
int ans = -1;
while (i < n) {
if (j == -1 || source[i] == target[j]) {
++i;
++j;
} else {
j = next[j];
}
if (j == m) {
ans = i - m;
break;
}
}
return ans;
}

时间复杂度:O(m+n)
空间复杂度:O(m)
改进的next数组:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<int> getNext(const char *target) {
int n = strlen(target);
vector<int> next(n);
next[0] = -1;
int k = -1;
int j = 0;
while (j < n - 1) {
if (k == -1 || target[j] == target[k]) {
++j;
++k;
if (target[j] == target[k]) {
next[j] = next[k];
} else {
next[j] = k;
}
} else {
k = next[k];
}
}
return next;
}


数组

众数

题目描述:Majority Element

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
/*
* @param nums: a list of integers
* @return: find a majority number
*/
int majorityNumber(vector<int> &nums) {
if (nums.empty()) {
return -1;
}
int count = 0;
int m = nums[0];
for (int i=0; i<nums.size(); ++i) {
if (count == 0) {
count = 1;
m = nums[i];
} else if (m == nums[i]) {
count++;
} else if (m != nums[i]) {
count--;
}
}
if (count == 0) {
return -1;
}
return m;
}
};

时间复杂度:O(n)
空间复杂度:O(1)


众数 II

题目描述:Majority Element II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
/*
* @param nums: a list of integers
* @return: The majority number that occurs more than 1/3
*/
int majorityNumber(vector<int> &nums) {
assert(!nums.empty());
int candidate1 = 0;
int candidate2 = 0;
int count1 = 0;
int count2 = 0;
for (int i=0; i<nums.size(); ++i) {
if (candidate1 == nums[i]) {
count1++;
} else if (candidate2 == nums[i]) {
count2++;
} else if (count1 == 0) {
count1 = 1;
candidate1 = nums[i];
} else if(count2 == 0) {
count2 = 1;
candidate2 = nums[i];
} else {
count1--;
count2--;
}
}
count1 = count2 = 0;
for (int i=0; i<nums.size(); ++i) {
if (nums[i] == candidate1) {
count1++;
} else if (nums[i] == candidate2) {
count2++;
}
}
return count1 > count2 ? candidate1 : candidate2;
}
};


子数组之和

题目描述:Subarray Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> subarraySum(vector<int> &nums) {
vector<int> res;
if (nums.size() == 0) {
return res;
}
map<int, int> m;
int sum = 0;
m[0] = -1;
for (int i=0; i<nums.size(); ++i) {
sum += nums[i];
if (m.find(sum) != m.end()) {
res.push_back(m[sum] + 1);
res.push_back(i);
return res;
}
m[sum] = i;
}
return res;
}


合并排序数组

题目描述:Merge Sorted Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
vector<int> mergeSortedArray(vector<int> &A, vector<int> &B) {
int i=0;
int j=0;
vector<int> res;
while (i<A.size() && j<B.size()) {
if (A[i] < B[j]) {
res.push_back(A[i]);
i++;
} else {
res.push_back(B[j]);
j++;
}
}
while (i<A.size()) {
res.push_back(A[i]);
i++;
}
while(j<B.size()) {
res.push_back(B[j]);
j++;
}
return res;
}


合并排序数组 II

题目描述:Merge Two Sorted Arrays

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void mergeSortedArray(int A[], int m, int B[], int n) {
int index = m + n - 1;
int i = m - 1;
int j = n - 1;
while (i>=0 && j>=0) {
if (A[i] > B[j]) {
A[index--] = A[i--];
} else {
A[index--] = B[j--];
}
}
while (j>=0) {
A[index--] = B[j--];
}
}


最接近零的子数组和

题目描述:最接近零的子数组和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
return a.first < b.first;
}
class Solution {
public:
/*
* @param nums: A list of integers
* @return: A list of integers includes the index of the first number and the index of the last number
*/
vector<int> subarraySumClosest(vector<int> &nums) {
if (nums.empty()) {
return vector<int>(2, -1);
}
int n = nums.size();
if (n == 1) {
return vector<int>(2, 0);
}
vector<int> res(2, -1);
vector<pair<int, int>> sums(n + 1, pair<int, int>(0, 0));
for (int i=1; i<=n; ++i) {
sums[i] = pair<int, int>(sums[i - 1].first + nums[i - 1], i);
}
sort(sums.begin(), sums.end(), cmp);
int difference = INT32_MAX;
for (int i=1; i<=n; ++i) {
if (difference > sums[i].first - sums[i - 1].first) {
difference = sums[i].first - sums[i - 1].first;
vector<int> tmp;
tmp.push_back(sums[i].second - 1);
tmp.push_back(sums[i - 1].second - 1);
sort(tmp.begin(), tmp.end());
res[0] = tmp[0] + 1;
res[1] = tmp[1];
}
}
return res;
}
};


最大子数组

题目描述:最大子数组
解法一:前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int maxSubArray(vector<int> &nums) {
if (nums.size() == 0) return 0;
int sum = nums[0];
int maxSum = sum;
for (int i=1; i<nums.size(); ++i) {
if (sum > 0) {
sum += nums[i];
} else {
sum = nums[i];
}
maxSum = max(maxSum, sum);
}
return maxSum;
}

解法二:Greedy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int maxSubArray(vector<int> &nums) {
if (nums.empty()) {
return 0;
}
int maxSum = INT32_MIN;
int sum = 0;
for (int i=0; i<nums.size(); ++i) {
sum += nums[i];
maxSum = max(maxSum, sum);
sum = max(sum, 0);
}
return maxSum;
}

时间复杂度:O(n)
空间复杂度:O(1)


最长连续序列

题目描述:最长连续序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int longestConsecutive(vector<int> &num) {
if (num.size() == 0) return 0;
sort(num.begin(), num.end());
int preNum = num[0];
int count = 1;
int result = 1;
for (int i=1; i<num.size(); ++i) {
if (num[i] == preNum) {
continue;
} else if (num[i] == preNum + 1) {
count++;
} else {
count = 1;
}
preNum = num[i];
result = max(result, count);
}
return result;
}

时间复杂度:O(nlogn)
空间复杂度:O(1)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
/**
* @param num: A list of integers
* @return: An integer
*/
int longestConsecutive(vector<int> &num) {
unordered_set<int> hash;
for (int i=0; i<num.size(); ++i) {
hash.insert(num[i]);
}
int longest = 0;
for (int i=0; i<num.size(); ++i) {
int left = num[i] - 1;
int right = num[i] + 1;
while(hash.find(left) != hash.end()) {
hash.erase(left);
left--;
}
while(hash.find(right) != hash.end()) {
hash.erase(right);
right++;
}
longest = max(longest, right - left - 1);
}
return longest;
}
};

时间复杂度:O(n)
空间复杂度:O(n)


最长上升子序列

题目描述:Longest Increasing Subsequence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int longestIncreasingSubsequence(vector<int> &nums) {
if (nums.size() == 0) return 0;
vector<int> d(nums.size());
int result = 1;
d[0] = 1;
for (int i=1; i<nums.size(); ++i) {
d[i] = 1;
for (int j=0; j<i; ++j) {
if (nums[i] > nums[j]) {
d[i] = max(d[i], d[j]+1);
}
}
result = max(result, d[i]);
}
return result;
}

时间复杂度:O(n^2)
空间复杂度:O(n)


两个数组的交

题目描述:Intersection of Two Arrays
sort & merge

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
vector<int> intersection(vector<int> nums1, vector<int> nums2) {
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
vector<int> res;
int index = 0;
int i = 0;
int j = 0;
while (i<nums1.size() && j<nums2.size()) {
if (nums1[i] == nums2[j]) {
if (index == 0 || res[index - 1] != nums1[i]) {
res.push_back(nums1[i]);
++index;
}
++i;
++j;
} else if (nums1[i] < nums2[j]) {
++i;
} else {
++j;
}
}
return res;
}

set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> intersection(vector<int> nums1, vector<int> nums2) {
set<int> numsSet;
set<int> resSet;
vector<int> res;
for (int i=0; i<nums1.size(); ++i) {
numsSet.insert(nums1[i]);
}
for (int i=0; i<nums2.size(); ++i) {
if (numsSet.find(nums2[i]) != numsSet.end()) {
if (resSet.find(nums2[i]) == resSet.end()) {
res.push_back(nums2[i]);
resSet.insert(nums2[i]);
}
}
}
return res;
}

两个排序数组的中位数

题目描述:Median of two Sorted Arrays

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int findKth(vector<int> &A, int startA, vector<int> &B, int startB, int k) {
if (startA >= A.size()) {
return B[startB + k - 1];
}
if (startB >= B.size()) {
return A[startA + k - 1];
}
if (k == 1) {
return min(A[startA], B[startB]);
}
int kthOfA = startA + k / 2 - 1 < A.size() ?
A[startA + k / 2 - 1] : INT32_MAX;
int kthOfB = startB + k / 2 - 1 < B.size() ?
B[startB + k / 2 - 1] : INT32_MAX;
if (kthOfA < kthOfB) {
findKth(A, startA + k / 2, B, startB, k - k / 2);
} else {
findKth(A, startA, B, startB + k / 2, k - k / 2);
}
}
double findMedianSortedArrays(vector<int> &A, vector<int> &B) {
int n = A.size() + B.size();
if (n % 2 == 0) {
return (findKth(A, 0, B, 0, n / 2) + findKth(A, 0, B, 0, n / 2 + 1)) / 2.0;
}
return findKth(A, 0, B, 0, n / 2 + 1);
}


和大于S的最小子数组

题目描述:和大于S的最小子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int minimumSize(vector<int> &nums, int s) {
int sum = 0;
int res = -1;
int j = 0;
for (int i=0; i<nums.size(); ++i) {
while (j < nums.size() && sum < s) {
sum += nums[j];
++j;
}
if ((res == -1 || j - i < res) && sum >= s) {
res = j - i;
}
sum -= nums[i];
}
return res;
}


接雨水

题目描述:Trapping Rain Water

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int trapRainWater(vector<int> &heights) {
int res = 0;
int i = 0;
int j = 0;
while (i < heights.size()) {
int ans = 0;
int maxHeight = 0;
int maxIndex = i;
for (j=i+1; j<heights.size(); ++j) {
if (maxHeight <= heights[j]) {
maxHeight = heights[j];
maxIndex = j;
}
if (heights[j] >= heights[i]) {
break;
}
ans += heights[i] - heights[j];
}
if (j == heights.size()) {
ans = 0;
for (j=i+1; j<maxIndex; ++j) {
ans += maxHeight - heights[j];
}
}
res += ans;
i = j;
}
return res;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int trapRainWater(vector<int> &heights) {
int maxHeight = 0;
int maxIndex = 0;
int ans = 0;
for (int i=0; i<heights.size(); ++i) {
if (maxHeight < heights[i]) {
maxHeight = heights[i];
maxIndex = i;
}
}
maxHeight = 0;
for (int i=0; i<maxIndex; ++i) {
if (maxHeight > heights[i]) {
ans += maxHeight - heights[i];
}
maxHeight = max(maxHeight, heights[i]);
}
maxHeight = 0;
for (int i=heights.size()-1; i>maxIndex; --i) {
if (maxHeight > heights[i]) {
ans += maxHeight - heights[i];
}
maxHeight = max(maxHeight, heights[i]);
}
return ans;
}

Submatrix Sum

题目描述:Submatrix Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
public:
/*
* @param matrix: an integer matrix
* @return: the coordinate of the left-up and right-down number
*/
vector<vector<int>> submatrixSum(vector<vector<int>> &matrix) {
vector<vector<int>> res;
if (matrix.empty() || matrix[0].empty()) {
return res;
}
int n = matrix.size();
int m = matrix[0].size();
vector<vector<int>> sum(n + 1, vector<int>(m));
for (int i=0; i<n; ++i) {
for (int j=0; j<m; ++j) {
sum[i + 1][j] = sum[i][j] + matrix[i][j];
}
}
for (int i=1; i<=n; ++i) {
for (int j=0; j<i; ++j) {
vector<int> tmp(m);
for (int k=0; k<m; ++k) {
tmp[k] = sum[i][k] - sum[j][k];
}
vector<int> arrRes = subarraySum(tmp);
if (!arrRes.empty()) {
vector<int> leftup;
leftup.push_back(j);
leftup.push_back(arrRes[0]);
vector<int> rightdown;
rightdown.push_back(i - 1);
rightdown.push_back(arrRes[1]);
res.push_back(leftup);
res.push_back(rightdown);
return res;
}
}
}
return res;
}
vector<int> subarraySum(vector<int> &nums) {
vector<int> res;
map<int, int> hash;
int sum = 0;
hash[0] = -1;
for (int i=0; i<nums.size(); ++i) {
sum += nums[i];
if (hash.find(sum) != hash.end()) {
res.push_back(hash[sum] + 1);
res.push_back(i);
return res;
}
hash[sum] = i;
}
return res;
}
};


Subarray Sum II

题目描述:Subarray Sum II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
/**
* @param A: An integer array
* @param start: An integer
* @param end: An integer
* @return: the number of possible answer
*/
int subarraySumII(vector<int> &A, int start, int end) {
if (A.empty()) {
return 0;
}
int n = A.size();
vector<int> sum(n + 1);
int ans = 0;
for (int i=0; i<n; ++i) {
sum[i + 1] = sum[i] + A[i];
}
for (int i=1; i<=n; ++i) {
for (int j=0; j<i; ++j) {
if (sum[i] - sum[j] >= start && sum[i] - sum[j] <= end) {
++ans;
}
}
}
return ans;
}
};


连续子数组求和

题目描述:Continuous Subarray Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
/*
* @param A: An integer array
* @return: A list of integers includes the index of the first number and the index of the last number
*/
vector<int> continuousSubarraySum(vector<int> &A) {
vector<int> res(2, 0);
if (A.empty()) {
return res;
}
int n = A.size();
int sum = A[0];
int largest = A[0];
int i = 0;
int j = 1;
while (i < n && j < n) {
if (sum >= 0) {
sum += A[j];
if (sum > largest) {
res[0] = i;
res[1] = j;
largest = sum;
}
++j;
} else {
sum -= A[i];
++i;
}
}
return res;
}
};


连续子数组求和 II

题目描述:Continuous Subarray Sum II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
public:
/*
* @param A: An integer array
* @return: A list of integers includes the index of the first number and the index of the last number
*/
vector<int> continuousSubarraySumII(vector<int> &A) {
if (A.empty()) {
return vector<int>(2, -1);
}
int n = A.size();
int largest = INT32_MIN;
int smallest = INT32_MAX;
int i = 0;
int j = 0;
int sum = 0;
int arraySum = 0;
vector<int> lRes(2, 0);
vector<int> sRes(2, 0);
for (auto num : A) {
arraySum += num;
}
while (i < n && j < n) {
sum += A[j];
if (sum > largest) {
lRes[0] = i;
lRes[1] = j;
largest = sum;
}
if (sum >= 0) {
++j;
} else {
sum = 0;
++i;
j = i;
}
}
i = 0;
j = 0;
while (i < n && j < n) {
sum += A[j];
if (sum < smallest) {
sRes[0] = i;
sRes[1] = j;
smallest = sum;
}
if (sum < 0) {
++j;
} else {
sum = 0;
++i;
j = i;
}
}
if (arraySum != smallest && arraySum - smallest > largest) {
lRes[0] = (sRes[1] + 1) % n;
lRes[1] = (sRes[0] - 1 + n) % n;
}
return lRes;
}
};


摆动排序

题目描述:Wiggle Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
/*
* @param nums: A list of integers
* @return: nothing
*/
void wiggleSort(vector<int> &nums) {
for (int i=1; i<nums.size(); ++i) {
if ((i % 2 == 1) && (nums[i] < nums[i - 1]) ||
(i % 2 == 0) && (nums[i] > nums[i - 1])) {
swap(nums[i], nums[i - 1]);
}
}
}
};


摆动排序II

题目描述:Wiggle Sort II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
class Solution {
public:
/*
* @param nums: A list of integers
* @return: nothing
*/
void wiggleSort(vector<int> &nums) {
if (nums.empty()) {
return;
}
int n = nums.size();
vector<int> tmp(nums.begin(), nums.end());
int mid = quickSelect(tmp, 0, n - 1, n / 2);
vector<int> ans(n);
for (int i=0; i<n; ++i) {
ans[i] = mid;
}
if (n % 2 == 0) {
int left = 1;
int right = n - 2;
for (int i=0; i<n; ++i) {
if (nums[i] > mid) {
ans[left] = nums[i];
left += 2;
} else if (nums[i] < mid) {
ans[right] = nums[i];
right -= 2;
}
}
} else {
int left = 0;
int right = n - 2;
for (int i=0; i<n; ++i) {
if (nums[i] < mid) {
ans[left] = nums[i];
left += 2;
} else if (nums[i] > mid) {
ans[right] = nums[i];
right -= 2;
}
}
}
for (int i=0; i<n; ++i) {
nums[i] = ans[i];
}
}
int quickSelect(vector<int> &nums, int start, int end, int k) {
if (start == end) {
return nums[start];
}
int left = start;
int right = end;
int pivot = nums[left];
while (left < right) {
while (left < right && nums[right] >= pivot) {
--right;
}
nums[left] = nums[right];
while (left < right && nums[left] <= pivot) {
++left;
}
nums[right] = nums[left];
}
if (left + 1 == k) {
return pivot;
} else if (left + 1 > k) {
return quickSelect(nums, start, left - 1, k);
} else {
return quickSelect(nums, left + 1, end, k);
}
}
};


Nuts 和 Bolts 的问题

题目描述:Nuts & Bolts Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/**
* class Comparator {
* public:
* int cmp(string a, string b);
* };
* You can use compare.cmp(a, b) to compare nuts "a" and bolts "b",
* if "a" is bigger than "b", it will return 1, else if they are equal,
* it will return 0, else if "a" is smaller than "b", it will return -1.
* When "a" is not a nut or "b" is not a bolt, it will return 2, which is not valid.
*/
class Solution {
public:
/**
* @param nuts: a vector of integers
* @param bolts: a vector of integers
* @param compare: a instance of Comparator
* @return: nothing
*/
void sortNutsAndBolts(vector<string> &nuts, vector<string> &bolts, Comparator compare) {
if (nuts.empty() || bolts.empty()) {
return;
}
if (nuts.size() != bolts.size()) {
return;
}
quickSort(nuts, bolts, compare, 0, nuts.size() - 1);
}
void quickSort(vector<string> &nuts, vector<string> &bolts, Comparator compare, int start, int end) {
if (start >= end) {
return;
}
int pivot_idx = partition(nuts, bolts[start], compare, start, end);
partition(bolts, nuts[pivot_idx], compare, start, end);
quickSort(nuts, bolts, compare, start, pivot_idx - 1);
quickSort(nuts, bolts, compare, pivot_idx + 1, end);
}
int partition(vector<string> &str, string pivot, Comparator compare, int start ,int end) {
for (int i=start; i<=end; ++i) {
if (compare.cmp(str[i], pivot) == 0 ||
compare.cmp(pivot, str[i]) == 0) {
swap(str[start], str[i]);
break;
}
}
int left = start;
int right = end;
string now = str[left];
while (left < right) {
while (left < right && (compare.cmp(str[right], pivot) == -1 ||
compare.cmp(pivot, str[right]) == 1)) {
--right;
}
str[left] = str[right];
while (left < right && (compare.cmp(str[left], pivot) == 1 ||
compare.cmp(pivot, str[left]) == -1)) {
++left;
}
str[right] = str[left];
}
str[left] = now;
return left;
}
};


二叉树

二叉树的前序遍历

题目描述:二叉树的前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> preorderTraversal(TreeNode * root) {
vector<int> result;
if (root == NULL) return result;
stack<TreeNode *> s;
s.push(root);
while (!s.empty()) {
TreeNode *node = s.top();
s.pop();
result.push_back(node->val);
if (node->right != NULL) s.push(node->right);
if (node->left != NULL) s.push(node->left);
}
return result;
}


二叉树的中序遍历

题目描述:Binary Tree Inorder Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
vector<int> inorderTraversal(TreeNode * root) {
vector<int> result;
if (root == NULL) return result;
stack<TreeNode*> s;
TreeNode *next = root;
while (true) {
while (next) {
s.push(next);
next = next->left;
}
if (s.empty()) {
break;
}
TreeNode *node = s.top();
s.pop();
result.push_back(node->val);
next = node->right;
}
return result;
}


二叉树的后续遍历

题目描述:Binary Tree Postorder Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> postorderTraversal(TreeNode * root) {
vector<int> result;
if (root == NULL) return result;
stack<TreeNode*> s;
TreeNode *pre = NULL;
s.push(root);
while (!s.empty()) {
TreeNode *cur = s.top();
if ((cur->left == NULL && cur->right == NULL) || (pre != NULL && (cur->left == pre || cur->right == pre))) {
s.pop();
result.push_back(cur->val);
pre = cur;
} else {
if (cur->right != NULL) s.push(cur->right);
if (cur->left != NULL) s.push(cur->left);
}
}
return result;
}


二叉树的最大深度

题目描述:二叉树的最大深度

1
2
3
4
5
6
7
8
9
// Divide Conquer
int maxDepth(TreeNode * root) {
if (root == NULL) return 0;
int maxLeftDepth = maxDepth(root->left);
int maxRightDepth = maxDepth(root->right);
return max(maxLeftDepth, maxRightDepth) + 1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Traverse
int depth = 0;
int maxDepth(TreeNode * root) {
if (root == NULL) return 0;
helper(root, 1);
return depth;
}
void helper(TreeNode *root, int curDepth) {
if (root == NULL) return;
if (curDepth > depth) {
depth = curDepth;
}
helper(root->left, curDepth+1);
helper(root->right, curDepth+1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// BFS
int maxDepth(TreeNode * root) {
if (root == NULL) return 0;
queue<TreeNode*> q;
q.push(root);
int depth = 0;
while (!q.empty()) {
int size = q.size();
for (int i=0; i<size; ++i) {
TreeNode *node = q.front();
q.pop();
if (node->left != NULL) q.push(node->left);
if (node->right != NULL) q.push(node->right);
}
++depth;
}
return depth;
}

Binary Tree Paths

题目描述:Binary Tree Paths

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Divide Conquer
vector<string> binaryTreePaths(TreeNode * root) {
vector<string> result;
if (root == NULL) return result;
if (root->left == NULL && root->right == NULL) {
result.push_back(to_string(root->val));
return result;
}
vector<string> leftPath = binaryTreePaths(root->left);
vector<string> rightPath = binaryTreePaths(root->right);
for (int i=0; i<leftPath.size(); ++i) {
result.push_back(to_string(root->val) + "->" + leftPath[i]);
}
for (int i=0; i<rightPath.size(); ++i) {
result.push_back(to_string(root->val) + "->" + rightPath[i]);
}
return result;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Traverse
vector<string> binaryTreePaths(TreeNode * root) {
vector<string> result;
if (root == NULL) return result;
string path = "";
helper(root, path, result);
return result;
}
void helper(TreeNode *root, string path, vector<string> &result) {
if (root == NULL) return;
if (root->left == NULL && root->right == NULL) {
result.push_back(path+to_string(root->val));
}
helper(root->left, path + to_string(root->val) + "->", result);
helper(root->right, path + to_string(root->val) + "->", result);
}

Balanced Binary Tree

题目描述:Balanced Binary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
struct ResultType {
int m_height;
bool m_isBalanced;
ResultType(int height, bool isBalanced) : m_height(height), m_isBalanced(isBalanced) {}
};
bool isBalanced(TreeNode * root) {
if (root == NULL) {
return true;
}
ResultType *result = helper(root);
return result->m_isBalanced;
}
ResultType *helper(TreeNode *root) {
if (root == NULL) {
return new ResultType(0, true);
}
ResultType *leftResult = helper(root->left);
ResultType *rightResult = helper(root->right);
ResultType *result = NULL;
if (abs(leftResult->m_height - rightResult->m_height) <= 1 && leftResult->m_isBalanced && rightResult->m_isBalanced) {
result = new ResultType(max(leftResult->m_height, rightResult->m_height)+1, true);
} else {
result = new ResultType(max(leftResult->m_height, rightResult->m_height)+1, false);
}
delete leftResult;
delete rightResult;
leftResult = NULL;
rightResult = NULL;
return result;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int depth(TreeNode *root) {
if (root == NULL) {
return 0;
}
int left = depth(root->left);
int right = depth(root->right);
if (left == -1 || right == -1 || abs(left - right) > 1) {
return -1;
}
return max(left, right) + 1;
}
bool isBalanced(TreeNode * root) {
return depth(root) != -1;
}

Flatten Binary Tree to Linked List

题目描述:Flatten Binary Tree to Linked List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Divide Conquer
void flatten(TreeNode * root) {
helper(root);
}
TreeNode *helper(TreeNode *root) {
if (root == NULL) {
return NULL;
}
TreeNode *left = helper(root->left);
TreeNode *right = helper(root->right);
if (left != NULL) {
root->right = left;
root->left = NULL;
while(left->right != NULL) {
left = left->right;
}
left->right = right;
}
return root;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Traverse
TreeNode *curNode = NULL;
void flatten(TreeNode * root) {
if (root == NULL) {
return;
}
if (curNode != NULL) {
curNode->left = NULL;
curNode->right = root;
}
curNode = root;
TreeNode *right = root->right;
flatten(root->left);
flatten(right);
}

最近公共祖先

题目描述:最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
TreeNode * lowestCommonAncestor(TreeNode * root, TreeNode * A, TreeNode * B) {
if (root == NULL || root == A || root == B) {
return root;
}
TreeNode *leftNode = lowestCommonAncestor(root->left, A, B);
TreeNode *rightNode = lowestCommonAncestor(root->right, A, B);
if (leftNode != NULL && rightNode != NULL) {
return root;
} else if (leftNode != NULL) {
return leftNode;
} else if (rightNode != NULL) {
return rightNode;
}
return NULL;
}


Binary Tree Longest Consecutive Sequence

题目描述:Binary Tree Longest Consecutive Sequence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// Divide Conquer
struct ResultType {
int m_subTreeLongest;
int m_curLongest;
ResultType(int subTreeLongest, int curLongest) : m_subTreeLongest(subTreeLongest), m_curLongest(curLongest) {}
};
int longestConsecutive(TreeNode * root) {
ResultType *result = helper(root);
return result->m_subTreeLongest;
}
ResultType *helper(TreeNode *root) {
if (root == NULL) {
return new ResultType(0, 0);
}
ResultType *leftResult = helper(root->left);
ResultType *rightResult = helper(root->right);
ResultType *result = new ResultType(0, 1);
if (root->left != NULL && root->val + 1 == root->left->val) {
result->m_curLongest = max(result->m_curLongest, leftResult->m_curLongest + 1);
}
if (root->right != NULL && root->val + 1 == root->right->val) {
result->m_curLongest = max(result->m_curLongest, rightResult->m_curLongest + 1);
}
result->m_subTreeLongest = max(max(leftResult->m_subTreeLongest, rightResult->m_subTreeLongest), result->m_curLongest);
delete leftResult;
delete rightResult;
leftResult = NULL;
rightResult = NULL;
return result;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Traverse & Divide Conquer
int longestConsecutive(TreeNode * root) {
return helper(root, NULL, 0);
}
int helper(TreeNode *root, TreeNode *parent, int curLength) {
if (root == NULL) {
return 0;
}
int length = (parent != NULL && parent->val+1 == root->val) ?
curLength + 1 :
1;
int left = helper(root->left, root, length);
int right = helper(root->right, root, length);
return max(length, max(left, right));
}

Binary Tree Longest Consecutive Sequence II

题目描述:Binary Tree Longest Consecutive Sequence II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
struct ResultType {
int m_increasing;
int m_descending;
int m_longest;
ResultType(int increasing, int desending, int longest) : m_increasing(increasing),
m_descending(desending), m_longest(longest) {}
};
int longestConsecutive2(TreeNode * root) {
ResultType *result = helper(root);
return result->m_longest;
}
ResultType *helper(TreeNode *root) {
if (root == NULL) {
return new ResultType(0, 0, 0);
}
ResultType *left = helper(root->left);
ResultType *right = helper(root->right);
ResultType *result = new ResultType(1, 1, 1);
if (root->left != NULL && root->val - 1 == root->left->val) {
result->m_increasing = max(result->m_increasing, left->m_increasing + 1);
}
if (root->left != NULL && root->val + 1 == root->left->val) {
result->m_descending = max(result->m_descending, left->m_descending + 1);
}
if (root->right != NULL && root->val - 1 == root->right->val) {
result->m_increasing = max(result->m_increasing, right->m_increasing + 1);
}
if (root->right != NULL && root->val + 1 == root->right->val) {
result->m_descending = max(result->m_descending, right->m_descending + 1);
}
if (root->left != NULL && root->right != NULL && root->val + 1 == root->left->val &&
root->val - 1 == root->right->val) {
result->m_longest = max(result->m_longest, left->m_descending + right->m_increasing + 1);
}
if (root->left != NULL && root->right != NULL && root->val - 1 == root->left->val &&
root->val + 1 == root->right->val) {
result->m_longest = max(result->m_longest, left->m_increasing + right->m_descending + 1);
}
result->m_longest = max(result->m_longest, max(result->m_increasing, result->m_descending));
result->m_longest = max(result->m_longest, max(left->m_longest, right->m_longest));
return result;
}


Binary Tree Path Sum

题目描述:Binary Tree Path Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// Traverse
vector<vector<int>> binaryTreePathSum(TreeNode * root, int target) {
vector<int> path;
vector<vector<int>> result;
helper(root, target, path, result);
return result;
}
void helper(TreeNode *root, int target, vector<int> path, vector<vector<int>> &result) {
if (root == NULL) {
return;
}
if (root->left == NULL && root->right == NULL) {
if (target == root->val) {
path.push_back(root->val);
result.push_back(path);
}
return;
}
path.push_back(root->val);
helper(root->left, target - root->val, path, result);
helper(root->right, target - root->val, path, result);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// Divide Conquer
vector<vector<int>> binaryTreePathSum(TreeNode * root, int target) {
vector<vector<int>> result;
if (root == NULL) {
return result;
}
vector<vector<int>> leftResult = binaryTreePathSum(root->left, target - root->val);
vector<vector<int>> rightResult = binaryTreePathSum(root->right, target - root->val);
if (root->left == NULL && root->right == NULL) {
if (root->val == target) {
result.push_back(vector<int>(1, root->val));
}
}
for (int i=0; i<leftResult.size(); ++i) {
leftResult[i].insert(leftResult[i].begin(), root->val);
result.push_back(leftResult[i]);
}
for (int i=0; i<rightResult.size(); ++i) {
rightResult[i].insert(rightResult[i].begin(), root->val);
result.push_back(rightResult[i]);
}
return result;
}

Validate Binary Search Tree

题目描述:Validate Binary Search Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Divide Conquer
bool isValidBST(TreeNode * root) {
return helper(root, INT64_MIN, INT64_MAX);
}
bool helper(TreeNode *root, long min, long max) {
if (root == NULL) {
return true;
}
bool left = helper(root->left, min, root->val);
bool right = helper(root->right, root->val, max);
if (!left || !right) {
return false;
}
if (root->val > min && root->val < max) {
return true;
} else {
return false;
}
}

更简洁的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool isValidBST(TreeNode * root) {
return helper(root, INT64_MIN, INT64_MAX);
}
bool helper(TreeNode *root, long min, long max) {
if (root == NULL) {
return true;
}
if (root->val <= min || root->val >= max) {
return false;
}
return helper(root->left, min, root->val) &&
helper(root->right, root->val, max);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Traverse
long lastNode = INT64_MIN;
bool isValidBST(TreeNode * root) {
if (root == NULL) {
return true;
}
if (!isValidBST(root->left)) {
return false;
}
if (lastNode >= root->val) {
return false;
}
lastNode = root->val;
if (!isValidBST(root->right)) {
return false;
}
return true;
}

非递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
bool isValidBST(TreeNode * root) {
if (root == NULL) {
return true;
}
stack<TreeNode*> s;
TreeNode *next = root;
long lastNode = INT64_MIN;
while (true) {
while (next != NULL) {
s.push(next);
next = next->left;
}
if (s.empty()) {
break;
}
TreeNode *node = s.top();
s.pop();
if (lastNode >= node->val) {
return false;
}
lastNode = node->val;
next = node->right;
}
return true;
}


Convert Binary Search Tree to Doubly Linked List

题目描述:Convert Binary Search Tree to Doubly Linked List
非递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
DoublyListNode * bstToDoublyList(TreeNode * root) {
if (root == NULL) return NULL;
DoublyListNode *dummy = new DoublyListNode(0);
DoublyListNode *preNode = dummy;
TreeNode *nextNode = root;
stack<TreeNode*> s;
while (true) {
while (nextNode != NULL) {
s.push(nextNode);
nextNode = nextNode->left;
}
if (s.empty()) {
break;
}
TreeNode *node = s.top();
s.pop();
DoublyListNode *curNode = new DoublyListNode(node->val);
preNode->next = curNode;
curNode->prev = preNode;
preNode = curNode;
nextNode = node->right;
}
return dummy->next;
}


Inorder Successor in BST

题目描述:Inorder Successor in BST

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
TreeNode * inorderSuccessor(TreeNode * root, TreeNode * p) {
if (root == nullptr) {
return nullptr;
}
stack<TreeNode*> s;
TreeNode *next = root;
bool nextFlag = false;
while (true) {
while (next != nullptr) {
s.push(next);
next = next->left;
}
if (s.empty()) {
break;
}
TreeNode *node = s.top();
s.pop();
if (nextFlag) {
return node;
}
if (node == p) {
nextFlag = true;
}
next = node->right;
}
return nullptr;
}

时间复杂度:O(n)
空间复杂度:O(n)


递归解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
TreeNode *pre = nullptr;
TreeNode *suc = nullptr;
TreeNode * inorderSuccessor(TreeNode * root, TreeNode * p) {
inOrderTraverse(root, p);
return suc;
}
void inOrderTraverse(TreeNode *root, TreeNode *p) {
if (root == nullptr) {
return;
}
inOrderTraverse(root->left, p);
if (pre == p) {
suc = root;
}
pre = root;
inOrderTraverse(root->right, p);
}

时间复杂度:O(n)
空间复杂度:O(1)


更快的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
TreeNode * inorderSuccessor(TreeNode * root, TreeNode * p) {
TreeNode *node = root;
TreeNode *res = nullptr;
while (node != nullptr) {
if (node->val > p->val) {
res = node;
node = node->left;
} else {
node = node->right;
}
}
return res;
}

时间复杂度:O(h)
空间复杂度:O(1)


另一种写法

1
2
3
4
5
6
7
8
9
10
11
12
TreeNode * inorderSuccessor(TreeNode * root, TreeNode * p) {
if (root == nullptr) {
return nullptr;
}
if (root->val <= p->val) {
return inorderSuccessor(root->right, p);
} else {
TreeNode *left = inorderSuccessor(root->left, p);
return left != nullptr ? left : root;
}
}


Binary Search Tree Iterator

题目描述:Binary Search Tree Iterator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class BSTIterator {
public:
/*
* @param root: The root of binary tree.
*/
stack<TreeNode*> s;
BSTIterator(TreeNode * root) {
BSTStackInit(root);
}
/*
* @param root: The root of binary tree.
*/
void BSTStackInit(TreeNode *root) {
while (root != nullptr) {
s.push(root);
root = root->left;
}
}
/*
* @return: True if there has next node, or false
*/
bool hasNext() {
return !s.empty();
}
/*
* @return: return next node
*/
TreeNode * next() {
if (!hasNext()) {
return nullptr;
}
TreeNode *node = s.top();
s.pop();
BSTStackInit(node->right);
return node;
}
};

时间复杂度:O(1) in average
空间复杂度:O(h)


Search Range in Binary Search Tree

题目描述:Search Range in Binary Search Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
vector<int> result;
if (root == nullptr) {
return result;
}
TreeNode *next = root;
stack<TreeNode*> s;
while (true) {
while (next != nullptr) {
s.push(next);
next = next->left;
}
if (s.empty()) {
break;
}
TreeNode *node = s.top();
s.pop();
if (node->val >= k1 && node->val <= k2) {
result.push_back(node->val);
}
if (node->val > k2) {
break;
}
next = node->right;
}
return result;

时间复杂度:O(n)
空间复杂度:O(n)
另一种解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<int> searchRange(TreeNode * root, int k1, int k2) {
vector<int> result;
inOrder(root, k1, k2, result);
sort(result.begin(), result.end());
return result;
}
void inOrder(TreeNode *root, int k1, int k2, vector<int> &result) {
if (root == nullptr) {
return;
}
if (root->val > k2) {
inOrder(root->left, k1, k2, result);
} else if (root->val < k1) {
inOrder(root->right, k1, k2, result);
} else {
result.push_back(root->val);
inOrder(root->left, k1, k2, result);
inOrder(root->right, k1, k2, result);
}
}

时间复杂度:O(h+(k2-k1)log(k2-k1))
空间复杂度:O(1)


Insert Node in a Binary Search Tree

题目描述:Insert Node in a Binary Search Tree
非递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
TreeNode * insertNode(TreeNode * root, TreeNode * node) {
if (root == nullptr) {
return node;
}
TreeNode *next = root;
while (next != nullptr) {
if (next->val > node->val) {
if (next->left == nullptr) {
next->left = node;
break;
} else {
next = next->left;
}
} else {
if (next->right == nullptr) {
next->right = node;
break;
} else {
next = next->right;
}
}
}
return root;
}

递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
TreeNode * insertNode(TreeNode * root, TreeNode * node) {
if (root == nullptr) {
return node;
}
if (root->val > node->val) {
root->left = insertNode(root->left, node);
} else {
root->right = insertNode(root->right, node);
}
return root;
}


Remove Node in Binary Search Tree

题目描述:Remove Node in Binary Search Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
void deleteSingleNode(TreeNode *parent, TreeNode *root) {
if (parent != nullptr) {
if (parent->left == root) {
parent->left = nullptr;
} else {
parent->right = nullptr;
}
}
delete root;
}
void deleteOneChild(TreeNode *parent, TreeNode *root) {
TreeNode *son = root->left!=nullptr ? root->left : root->right;
if (parent != nullptr) {
if (parent->left == root) {
parent->left = son;
} else {
parent->right = son;
}
}
delete root;
}
TreeNode * removeNode(TreeNode * root, int value) {
if (root == nullptr) {
return nullptr;
}
TreeNode *node = root;
TreeNode *pre = nullptr;
// find the value that will be deleted
while (node != nullptr) {
if (node->val > value) {
pre = node;
node = node->left;
} else if (node->val < value) {
pre = node;
node = node->right;
} else {
break;
}
}
if (node == nullptr) {
return root;
}
if (node->left == nullptr && node->right == nullptr) {
if (node == root) {
root = nullptr;
}
deleteSingleNode(pre, node);
} else if (node->left == nullptr || node->right == nullptr) {
if (node == root) {
root = root->left!=nullptr ? root->left : root->right;
}
deleteOneChild(pre, node);
} else {
pre = node;
TreeNode *next = node->right;
while (next->left != nullptr) {
pre = next;
next = next->left;
}
node->val = next->val;
if (next->right == nullptr) {
deleteSingleNode(pre, next);
} else {
deleteOneChild(pre, next);
}
}
return root;
}


根据前序中序,构造二叉树

题目描述:根据前序中序,构造二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
TreeNode * buildTree(vector<int> &preorder, vector<int> &inorder) {
return helper(preorder, inorder, 0, preorder.size(), 0, inorder.size());
}
TreeNode *helper(vector<int> &preorder, vector<int> &inorder, int pstart, int pend, int istart, int iend) {
if (pstart == pend) {
return nullptr;
}
int value = preorder[pstart];
TreeNode *root = new TreeNode(value);
int posInOrder = istart;
for (; posInOrder<inorder.size(); ++posInOrder) {
if (inorder[posInOrder] == value) {
break;
}
}
root->left = helper(preorder, inorder, pstart+1, pstart+1+(posInOrder-istart), istart, posInOrder);
root->right = helper(preorder, inorder, pstart+1+(posInOrder-istart), pend, posInOrder+1, iend);
}


根据后序中序,构造二叉树

题目描述:根据后序中序,构造二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef vector<int>::iterator Iter;
typedef vector<int>::reverse_iterator RIter;
TreeNode * buildTree(vector<int> &inorder, vector<int> &postorder) {
return helper(inorder.begin(), inorder.end(), postorder.rbegin(), postorder.rend());
}
TreeNode *helper(Iter istart, Iter iend, RIter pstart, RIter pend) {
if (istart == iend) {
return nullptr;
}
int value = *pstart;
TreeNode *root = new TreeNode(value);
Iter irootstart = find(istart, iend, value);
root->left = helper(istart, irootstart, pstart+(iend-irootstart), pend);
root->right = helper(irootstart+1, iend, pstart+1, pstart+(iend-irootstart));
return root;
}


largest BST subtree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
TreeNode *subTreeRoot = nullptr;
int largetSubTree = 0;
TreeNode *largestBSTSubtree(TreeNode *root) {
}
bool helper(TreeNode *root, int &maxValue, int &minValue, int &count) {
count = 0;
if (root == nullptr) {
return true;
}
int c1 = 0, c2 = 0;
bool left = helper(root->left, root->val, minValue, c1);
bool right = helper(root->right, maxValue, root->val, c2);
if (root->val <= min || root->val >= max) {
return false;
}
if(left && right) {
return false;
}
count = c1 + c2 + 1;
minValue = min(minValue, root->val);
maxValue = max(maxValue, root->val);
if (count > largestSubTree) {
subTreeRoot = root;
largestSubTree = count;
}
return true;
}

翻转二叉树

题目描述:Invert Binary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
/**
* @param root: a TreeNode, the root of the binary tree
* @return: nothing
*/
public:
void invertBinaryTree(TreeNode* root) {
if (root == NULL) {
return;
}
swap(root->left, root->right);
invertBinaryTree(root->left);
invertBinaryTree(root->right);
}
};


所有括号匹配的字符串

题目描述:Generate Parentheses

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
map<int, vector<string>> cache;
void merge(vector<string> &result, vector<string> &prefix, vector<string> &suffix) {
for (vector<string>::iterator ip=prefix.begin(); ip!=prefix.end(); ++ip) {
for (vector<string>::iterator is=suffix.begin(); is!=suffix.end(); ++is) {
result.push_back("");
string &r = result.back();
r += "(";
r += *ip;
r += ")";
r += *is;
}
}
}
vector<string> generateParenthesis(int n) {
if (n == 0) {
return vector<string>(1, "");
}
if (n == 1) {
return vector<string>(1, "()");
}
map<int, vector<string>>::iterator it = cache.find(n);
if (it != cache.end()) {
return (*it).second;
}
vector<string> result, prefix, suffix;
for (int i=0; i<n; ++i) {
prefix = generateParenthesis(i);
suffix = generateParenthesis(n-i-1);
merge(result, prefix, suffix);
}
cache[n] = result;
return result;
}


K个不同字符的最长子串

题目描述:Longest Substring with At Most K Distinct Characters

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int lengthOfLongestSubstringKDistinct(string &s, int k) {
if (s.length() == 0) {
return 0;
}
int i = 0, j = 0;
int n = s.length();
int maxLength = 0;
map<char, int> m;
for (j=0; j<n; ++j) {
m[s[j]]++;
while (m.size() > k) {
m[s[i]]--;
if (m[s[i]] == 0) {
m.erase(s[i]);
}
i++;
}
maxLength = max(maxLength, j - i + 1);
}
return maxLength;
}


BFS

树的层次遍历

题目描述:树的层次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
vector<vector<int>> levelOrder(TreeNode * root) {
vector<vector<int>> result;
if (root == nullptr) {
return result;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
vector<int> level;
int size = q.size();
for (int i=0; i<size; ++i) {
TreeNode *node = q.front();
level.push_back(node->val);
q.pop();
if (node->left != nullptr) {
q.push(node->left);
}
if (node->right != nullptr) {
q.push(node->right);
}
}
result.push_back(level);
}
return result;
}


树的序列化和反序列化

题目描述:Serialize and Deserialize Binary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
string serialize(TreeNode * root) {
string res;
if (root == nullptr) {
return res;
}
queue<TreeNode *> q;
q.push(root);
res += to_string(root->val)+" ";
while (!q.empty()) {
TreeNode *node = q.front();
q.pop();
if (node->left != nullptr) {
q.push(node->left);
res += to_string(node->left->val) + " ";
} else {
res += "# ";
}
if (node->right != nullptr) {
q.push(node->right);
res += to_string(node->right->val) + " ";
} else {
res += "# ";
}
}
return res;
}
TreeNode *nextNode(string &data, int &i) {
int pos = data.find(" ", i);
string str = data.substr(i, pos - i);
i = pos;
if (str == "#") {
return nullptr;
}
return new TreeNode(atoi(str.c_str()));
}
TreeNode * deserialize(string &data) {
if (data.length() == 0) {
return nullptr;
}
int i = 0;
TreeNode *root = nextNode(data, i);
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode *node = q.front();
q.pop();
node->left = nextNode(data, ++i);
if (node->left != nullptr) {
q.push(node->left);
}
node->right = nextNode(data, ++i);
if (node->right != nullptr) {
q.push(node->right);
}
}
return root;
}


Graph Valid Tree

题目描述:Graph Valid Tree
Union-Find

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool validTree(int n, vector<vector<int>> &edges) {
vector<int> root(n, -1);
for (int i=0; i<edges.size(); ++i) {
int root1 = find(root, edges[i][0]);
int root2 = find(root, edges[i][1]);
if (root1 == root2) {
return false;
}
root[root1] = root2;
}
return edges.size() == n-1;
}
int find(vector<int> &root, int e) {
if (root[e] == -1) {
return e;
}
return root[e] = find(root, root[e]);
}

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
bool validTree(int n, vector<vector<int>> &edges) {
vector<unordered_set<int>> g(n, unordered_set<int>());
queue<int> q;
set<int> v;
q.push(0);
v.insert(0);
// 生成邻接表
for (auto e : edges) {
g[e[0]].insert(e[1]);
g[e[1]].insert(e[0]);
}
// BFS遍历
while (!q.empty()) {
int index = q.front();
q.pop();
for (auto e : g[index]) {
if (v.find(e) != v.end()) {
return false;
}
v.insert(e);
q.push(e);
g[e].erase(index);
}
}
return v.size() == n;
}


克隆图

题目描述:Clone Graph
BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
UndirectedGraphNode* cloneGraph(UndirectedGraphNode* node) {
if (node == nullptr) {
return nullptr;
}
map<UndirectedGraphNode*, UndirectedGraphNode*> m;
set<UndirectedGraphNode*> v;
queue<UndirectedGraphNode*> q;
q.push(node);
m[node] = new UndirectedGraphNode(node->label);
v.insert(node);
while (!q.empty()) {
UndirectedGraphNode *tmp = q.front();
q.pop();
for (auto e : tmp->neighbors) {
if (v.find(e) == v.end()) {
q.push(e);
m[e] = new UndirectedGraphNode(e->label);
}
v.insert(e);
m[tmp]->neighbors.push_back(m[e]);
}
}
return m[node];
}

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
UndirectedGraphNode* cloneGraph(UndirectedGraphNode* node) {
map<int, UndirectedGraphNode*> m;
return clone(node, m);
}
UndirectedGraphNode* clone(UndirectedGraphNode *node, map<int, UndirectedGraphNode*> &m) {
if (node == nullptr) {
return nullptr;
}
if (m.find(node->label) != m.end()) {
return m[node->label];
}
UndirectedGraphNode *newNode = new UndirectedGraphNode(node->label);
m[node->label] = newNode;
for (auto e : node->neighbors) {
UndirectedGraphNode *tmp = clone(e, m);
m[node->label]->neighbors.push_back(tmp);
}
return newNode;
}

拓扑排序

题目描述:Topological Sorting
BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
vector<DirectedGraphNode*> topSort_2(vector<DirectedGraphNode*>& graph) {
queue<DirectedGraphNode*> q;
map<DirectedGraphNode*, int> degree;
vector<DirectedGraphNode*> result;
// 求解入度
for (int i=0; i<graph.size(); ++i) {
for (int j=0; j<graph[i]->neighbors.size(); ++j) {
if (degree.find(graph[i]->neighbors[j]) == degree.end()) {
degree[graph[i]->neighbors[j]] = 1;
} else {
degree[graph[i]->neighbors[j]] += 1;
}
}
}
for (int i=0; i<graph.size(); ++i) {
if (degree[graph[i]] == 0) {
q.push(graph[i]);
}
}
while (!q.empty()) {
DirectedGraphNode *node = q.front();
q.pop();
result.push_back(node);
for (int i=0; i<node->neighbors.size(); ++i) {
degree[node->neighbors[i]]--;
if (degree[node->neighbors[i]] == 0) {
q.push(node->neighbors[i]);
}
}
}
return result;
}

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void dfs(DirectedGraphNode *graph, map<DirectedGraphNode*, int> &degree, vector<DirectedGraphNode*> &result) {
result.push_back(graph);
degree[graph]--;
for (int i=0; i<graph->neighbors.size(); ++i) {
degree[graph->neighbors[i]]--;
if (degree[graph->neighbors[i]] == 0) {
dfs(graph->neighbors[i], degree, result);
}
}
}
vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*>& graph) {
queue<DirectedGraphNode*> q;
map<DirectedGraphNode*, int> degree;
vector<DirectedGraphNode*> result;
// 求解入度
for (int i=0; i<graph.size(); ++i) {
for (int j=0; j<graph[i]->neighbors.size(); ++j) {
if (degree.find(graph[i]->neighbors[j]) == degree.end()) {
degree[graph[i]->neighbors[j]] = 1;
} else {
degree[graph[i]->neighbors[j]] += 1;
}
}
}
for (int i=0; i<graph.size(); ++i) {
if (degree[graph[i]] == 0) {
dfs(graph[i], degree, result);
}
}
return result;
}


Course Schedule

题目描述:Course Schedule

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<unordered_set<int>> graph(numCourses, unordered_set<int>());
map<int, int> degree;
queue<int> q;
vector<int> result;
// 构建邻接表,并计算入度表
for (int i=0; i<prerequisites.size(); ++i) {
if (graph[prerequisites[i].second].find(prerequisites[i].first) != graph[prerequisites[i].second].end()) {
continue;
}
graph[prerequisites[i].second].insert(prerequisites[i].first);
if (degree.find(prerequisites[i].first) == degree.end()) {
degree[prerequisites[i].first] = 1;
} else {
degree[prerequisites[i].first] += 1;
}
}
// 将入度为0的添加到队列中
for (int i=0; i<numCourses; ++i) {
if (degree[i] == 0) {
q.push(i);
}
}
// BFS
while (!q.empty()) {
int node = q.front();
q.pop();
result.push_back(node);
for (auto e : graph[node]) {
degree[e]--;
if (degree[e] == 0) {
q.push(e);
}
}
}
return result.size() == numCourses;
}


Course Schedule II

题目描述:Course Schedule II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
/*
* @param numCourses: a total of n courses
* @param prerequisites: a list of prerequisite pairs
* @return: true if can finish all courses or false
*/
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<unordered_set<int>> graph(numCourses, unordered_set<int>());
map<int, int> degree;
queue<int> q;
vector<int> result;
// 构建邻接表,并计算入度表
for (int i=0; i<prerequisites.size(); ++i) {
if (graph[prerequisites[i].second].find(prerequisites[i].first) != graph[prerequisites[i].second].end()) {
continue;
}
graph[prerequisites[i].second].insert(prerequisites[i].first);
if (degree.find(prerequisites[i].first) == degree.end()) {
degree[prerequisites[i].first] = 1;
} else {
degree[prerequisites[i].first] += 1;
}
}
// 将入度为0的添加到队列中
for (int i=0; i<numCourses; ++i) {
if (degree[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int node = q.front();
q.pop();
result.push_back(node);
for (auto e : graph[node]) {
degree[e]--;
if (degree[e] == 0) {
q.push(e);
}
}
}
for_each(result.begin(), result.end(), [](int &x){cout << x << " ";});
cout << endl;
return result.size() == numCourses;
}
};


Sequence Reconstruction

题目描述:Sequence Reconstruction

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
bool sequenceReconstruction(vector<int> &org, vector<vector<int>> &seqs) {
vector<unordered_set<int>> graph(org.size()+1, unordered_set<int>());
queue<int> q;
map<int, int> degree;
int count = 0;
// 将seqs转换为图,并计算入度
for (int i=0; i<seqs.size(); ++i) {
count += seqs[i].size();
for (int j=1; j<seqs[i].size(); ++j) {
if (graph[seqs[i][j-1]].find(seqs[i][j]) != graph[seqs[i][j-1]].end()) {
continue;
}
graph[seqs[i][j-1]].insert(seqs[i][j]);
if (degree.find(seqs[i][j-1]) == degree.end()) {
degree[seqs[i][j]] = 1;
} else {
degree[seqs[i][j]] += 1;
}
}
}
if (count < org.size()) {
return false;
}
// 将入度为0的加入到队列中
for (int i=0; i<org.size(); ++i) {
if (degree[org[i]] == 0) {
q.push(org[i]);
}
}
// BFS
int index = 0;
int cnt = 0;
while (!q.empty()) {
if (q.size() != 1) {
return false;
}
int node = q.front();
++cnt;
q.pop();
if (node != org[index++]) {
return false;
}
for (auto e : graph[node]) {
degree[e]--;
if (degree[e] == 0) {
q.push(e);
}
}
}
return cnt == org.size();
}

Number of Islands

题目描述:Number of Islands

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
bool isValid(vector<vector<bool>> &grid, int i, int j) {
if (i<0 || i>=grid.size() || j<0 || j>=grid[0].size()) {
return false;
}
return true;
}
void bfs(vector<vector<bool>> &grid, vector<vector<bool>> &visited, int i, int j) {
queue<pair<int, int>> q;
int directX[4] = {0, 1, 0, -1};
int directY[4] = {-1, 0, 1, 0};
q.push(pair<int, int>(i, j));
while (!q.empty()) {
pair<int, int> d = q.front();
q.pop();
int x = d.first;
int y = d.second;
visited[x][y] = true;
for (int i=0; i<4; ++i) {
int newX = x + directX[i];
int newY = y + directY[i];
if (isValid(grid, newX, newY) && grid[newX][newY] && !visited[newX][newY]) {
q.push(pair<int, int>(newX, newY));
}
}
}
}
int numIslands(vector<vector<bool>> &grid) {
if (grid.size() == 0) {
return 0;
}
vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size()));
int cnt = 0;
for (int i=0; i<grid.size(); ++i) {
for (int j=0; j<grid[i].size(); ++j) {
if (grid[i][j] && !visited[i][j]) {
++cnt;
bfs(grid, visited, i, j);
}
}
}
return cnt;
}


Word Ladder

题目描述:Word Ladder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int ladderLength(string &start, string &end, unordered_set<string> &dict) {
queue<string> q;
set<string> visited;
q.push(start);
int cnt = 1;
while (!q.empty()) {
int size = q.size();
for (int i=0; i<size; ++i) {
string str = q.front();
q.pop();
if (str == end) {
return cnt;
}
for (int j=0; j<str.length(); ++j) {
string tmp = str;
for (int k='a'; k<='z'; ++k) {
tmp[j] = k;
if (visited.find(tmp) != visited.end()) {
continue;
}
if (dict.find(tmp) != dict.end() || tmp == end) {
visited.insert(tmp);
q.push(tmp);
}
}
}
}
++cnt;
}
return 0;
}


Surrounded Regions

题目描述:Surrounded Regions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
void surroundedRegions(vector<vector<char>> &board) {
if (board.size() == 0) {
return;
}
int n = board.size();
int m = board[0].size();
for (int i=0; i<n; ++i) {
if (board[i][0] == 'O') {
fillRegions(board, i, 0);
}
if (board[i][m-1] == 'O') {
fillRegions(board, i, m-1);
}
}
for (int j=0; j<m; ++j) {
if (board[0][j] == 'O') {
fillRegions(board, 0, j);
}
if (board[n-1][j] == 'O') {
fillRegions(board, n-1, j);
}
}
for (int i=0; i<n; ++i) {
for (int j=0; j<m; ++j) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
} else if (board[i][j] == '*') {
board[i][j] = 'O';
}
}
}
}
bool isValid(vector<vector<char>> &board, int i, int j) {
if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size()) {
return false;
}
return board[i][j] == 'O';
}
void fillRegions(vector<vector<char>> &board, int i, int j) {
int directX[4] = {-1, 0, 0, 1};
int directY[4] = {0, -1, 1, 0};
queue<pair<int, int>> q;
q.push(pair<int, int>(i, j));
while (!q.empty()) {
auto pos = q.front();
q.pop();
int x = pos.first;
int y = pos.second;
board[x][y] = '*';
for (int k=0; k<4; ++k) {
int newX = x + directX[k];
int newY = y + directY[k];
if (isValid(board, newX, newY)) {
q.push(pair<int, int>(newX, newY));
}
}
}
}


DFS

Subsets

题目描述:Subsets
// DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void dfs(vector<int> &nums, int index, vector<int> path, vector<vector<int>> &result) {
if (index == nums.size()) {
return;
}
for (int i=index; i<nums.size(); ++i) {
path.push_back(nums[i]);
result.push_back(path);
dfs(nums, i+1, path, result);
path.pop_back();
}
}
vector<vector<int>> subsets(vector<int> &nums) {
vector<vector<int>> result;
vector<int> path;
sort(nums.begin(), nums.end());
result.push_back(vector<int>());
dfs(nums, 0, path, result);
return result;
}

二进制解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<vector<int>> subsets(vector<int> &nums) {
vector<vector<int>> result;
int n = nums.size();
sort(nums.begin(), nums.end());
for (int i=0; i<(1<<n); ++i) {
vector<int> subset;
for (int j=0; j<n; ++j) {
if ((i & (1 << j)) != 0) {
subset.push_back(nums[j]);
}
}
result.push_back(subset);
}
return result;
}


Subsets II

题目描述:Subsets II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
/**
* @param nums: A set of numbers.
* @return: A list of lists. All valid subsets.
*/
vector<vector<int>> subsetsWithDup(vector<int> &nums) {
vector<vector<int>> res;
vector<int> path;
sort(nums.begin(), nums.end());
res.push_back(vector<int>());
dfs(nums, 0, path, res);
return res;
}
void dfs(vector<int> &nums, int start, vector<int> path, vector<vector<int>> &res) {
if (start >= nums.size()) {
return;
}
for (int i=start; i<nums.size(); ++i) {
if (i != start && nums[i] == nums[i - 1]) {
continue;
}
path.push_back(nums[i]);
res.push_back(path);
dfs(nums, i + 1, path, res);
path.pop_back();
}
}
};


Combination Sum

题目描述:Combination Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
/**
* @param candidates: A list of integers
* @param target: An integer
* @return: A list of lists of integers
*/
void dfs(vector<int> &candidates, vector<int> path, vector<vector<int>> &result, int index, int target) {
if (target == 0) {
result.push_back(path);
}
for (int i=index; i<candidates.size(); ++i) {
if (i != 0 && candidates[i] == candidates[i - 1]) {
continue;
}
if (target - candidates[i] < 0) {
continue;
}
path.push_back(candidates[i]);
dfs(candidates, path, result, i, target - candidates[i]);
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
vector<vector<int>> result;
vector<int> path;
sort(candidates.begin(), candidates.end());
dfs(candidates, path, result, 0, target);
return result;
}
};


Combination Sum II

题目描述:Combination Sum II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void dfs(vector<int> &candidates, vector<int> path, vector<vector<int>> &result, int index, int target) {
if (target < 0) {
return;
}
for (int i=index; i<candidates.size(); ++i) {
if (i != index && candidates[i] == candidates[i-1]) {
continue;
}
path.push_back(candidates[i]);
if (target == candidates[i]) {
result.push_back(path);
continue;
}
dfs(candidates, path, result, i+1, target - candidates[i]);
path.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int> &candidates, int target) {
vector<vector<int>> result;
vector<int> path;
sort(candidates.begin(), candidates.end());
dfs(candidates, path, result, 0, target);
return result;
}


Palindrome Partitioning

题目描述:Palindrome Partitioning

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
bool isPalindrome(string &s, int from, int to) {
while (from < to) {
if (s[from++] != s[to--]) {
return false;
}
}
return true;
}
void dfs(string &s, int start, vector<string> path, vector<vector<string>> &result) {
if (start == s.length()) {
result.push_back(path);
return;
}
for (int i=start; i<s.length(); ++i) {
string str = s.substr(start, i - start + 1);
if (!isPalindrome(s, start, i)) {
continue;
}
path.push_back(str);
dfs(s, i + 1, path, result);
path.pop_back();
}
}
vector<vector<string>> partition(string &s) {
vector<vector<string>> result;
vector<string> path;
dfs(s, 0, path, result);
return result;
}


Permutations II

题目描述:Permutations II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void permute(vector<int> &nums, vector<int> permutation, vector<vector<int>> &result, set<int> &visited) {
if (visited.size() == nums.size()) {
result.push_back(permutation);
return;
}
for (int i=0; i<nums.size(); ++i) {
if (visited.find(i) != visited.end()) {
continue;
}
if (i > 0 && nums[i] == nums[i-1] && !visited.count(i-1)) {
continue;
}
visited.insert(i);
permutation.push_back(nums[i]);
permute(nums, permutation, result, visited);
permutation.pop_back();
visited.erase(i);
}
}
vector<vector<int>> permuteUnique(vector<int> &nums) {
vector<vector<int>> result;
vector<int> permutation;
sort(nums.begin(), nums.end());
set<int> visited;
permute(nums, 0, permutation, result, visited);
return result;
}


n皇后问题

题目描述:N-Queens

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> result;
vector<int> path;
search(n, path, result);
return result;
}
void search(int n, vector<int> &path, vector<vector<string>> &result) {
if (path.size() == n) {
result.push_back(draw(path));
}
for (int i=0; i<n; ++i) {
if (!isValid(path, i)) {
continue;
}
path.push_back(i);
search(n, path, result);
path.pop_back();
}
}
bool isValid(vector<int> &path, int col) {
int row = path.size();
for (int i=0; i<row; ++i) {
if (path[i] == col) {
return false;
} else if (i - path[i] == row - col) {
return false;
} else if (i + path[i] == row + col) {
return false;
}
}
return true;
}
vector<string> draw(vector<int> &path) {
vector<string> res;
int n = path.size();
for (int i=0; i<n; ++i) {
string str(n, '.');
str[path[i]] = 'Q';
res.push_back(str);
}
return res;
}


Word Ladder II

题目描述:Word Ladder II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
vector<vector<string>> ans;
vector<vector<string>> findLadders(string &start, string &end, unordered_set<string> &dict) {
dict.insert(end);
unordered_map<string, vector<string>> next;
unordered_map<string, int> v;
queue<string> q;
q.push(start);
v[start] = 0;
while (!q.empty()) {
string str = q.front();
q.pop();
if (str == end) {
break;
}
int step = v[str];
vector<string> snext;
for (int i=0; i<str.size(); ++i) {
string newStr = str;
for (int c='a'; c<='z'; ++c) {
newStr[i] = c;
if (c == str[i] || !dict.count(newStr)) {
continue;
}
if (v.count(newStr) == 0) {
v[newStr] = step + 1;
q.push(newStr);
}
snext.push_back(newStr);
}
}
next[str] = snext;
}
vector<string> path;
path.push_back(start);
dfspath(start, end, next, v, path);
return ans;
}
void dfspath(string &start, string &end, unordered_map<string, vector<string>> &next, unordered_map<string, int> &v, vector<string> &path) {
if (start == end) {
ans.push_back(path);
} else {
vector<string> nextStr = next[start];
int vsn = v[start];
for (int i=0; i<nextStr.size(); ++i) {
if (v[nextStr[i]] != vsn + 1) {
continue;
}
path.push_back(nextStr[i]);
dfspath(nextStr[i], end, next, v, path);
path.pop_back();
}
}
}


老鼠吃奶酪

题目描述:一只老师位于迷宫左上角(0,0)处,迷宫中的数字9处有块大奶酪。0表示墙,1表示可以通过,给出一条可以吃到奶酪的路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class MouseEatCheese {
public:
vector<pair<int, int>> mouseEatCheese(vector<vector<int>> &chess) {
vector<pair<int, int>> path;
if (chess.size() == 0 || chess[0].size() == 0) {
return path;
}
vector<vector<bool>> visited(chess.size(), vector<bool>(chess[0].size()));
visited[0][0] = true;
dfs(chess, 0, 0, path, visited);
return path;
}
bool dfs(vector<vector<int>> &chess, int i, int j, vector<pair<int, int>> &path, vector<vector<bool>> &visited) {
if (chess[i][j] == 9) {
return true;
}
int n = chess.size();
int m = chess[0].size();
int directX[4] = {-1, 0, 0, 1};
int directY[4] = {0, -1, 1, 0};
for (int k=0; k<4; ++k) {
int x = i + directX[k];
int y = j + directY[k];
if (x < 0 || x >= n || y < 0 || y >= m) {
continue;
}
if (!visited[x][y] && chess[x][y]) {
visited[x][y] = true;
path.push_back(make_pair(x, y));
if (dfs(chess, x, y, path, visited)) {
return true;
}
path.pop_back();
}
}
return false;
}
};
int main() {
vector<vector<int>> chess = {
{1, 1, 0, 0, 0, 0, 0, 1},
{1, 1, 1, 1, 1, 1, 1, 1},
{1, 0, 0, 0, 1, 0, 0, 1},
{1, 1, 1, 0, 1, 0, 0, 1},
{0, 1, 0, 0, 1, 1, 1, 1},
{0, 1, 0, 0, 0, 0, 0, 1},
{0, 1, 0, 9, 1, 1, 1, 1},
{0, 1, 1, 1, 0, 0, 1, 0}
};
MouseEatCheese mec;
auto res = mec.mouseEatCheese(chess);
for_each(res.begin(), res.end(), [](pair<int, int> x){cout << x.first << " " << x.second << endl;});
return 0;
}


数独Sudoku

题目描述:数独Sudoku

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
void solveSudoku(vector<vector<int>> &board) {
sudoku(board);
}
bool isValid(vector<vector<int>> &board, int i, int j) {
int n = board.size();
int t = board[i][j];
for (int k=0; k<n; ++k) {
if (j != k && board[i][k] == t) { // 行
return false;
}
if (i != k && board[k][j] == t) { // 列
return false;
}
}
int iGrid = (i / 3) * 3;
int jGrid = (j / 3) * 3;
for (int k1=iGrid; k1<iGrid+3; ++k1) {
for (int k2=jGrid; k2<jGrid+3; ++k2) {
if (k1 == i && k2 == j) {
continue;
}
if (t == board[k1][k2]) {
return false;
}
}
}
return true;
}
bool sudoku(vector<vector<int>> &board) {
int n = board.size();
for (int i=0; i<n; ++i) {
for (int j=0; j<n; ++j) {
if (board[i][j] != 0) {
continue;
}
for (int k=1; k<10; ++k) {
board[i][j] = k;
if (isValid(board, i, j) && sudoku(board)) {
return true;
}
board[i][j] = 0;
}
return false;
}
}
return true;
}


两根指针

移动零

题目描述:Move Zeroes

1
2
3
4
5
6
7
8
9
10
11
void moveZeroes(vector<int> &nums) {
int left = 0;
int right = 0;
while (right < nums.size()) {
if (nums[right] != 0) {
swap(nums[left], nums[right]);
++left;
}
++right;
}
}


去除重复元素

题目描述:Remove Duplicate Numbers in Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int deduplication(vector<int> &nums) {
set<int> s;
int left = 0;
int right = 0;
while (right < nums.size()) {
if (s.find(nums[right]) == s.end()) {
swap(nums[left], nums[right]);
s.insert(nums[left]);
s.insert(nums[right]);
++left;
}
++right;
}
return left;
}


有效回文串

题目描述:Valid Palindrome

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool isPalindrome(string &s) {
int start = 0;
int end = s.length() - 1;
while (start < end) {
if (!isalnum(s[start])) {
start++;
} else if (!isalnum(s[end])) {
end--;
} else {
if (tolower(s[start++]) != tolower(s[end--])) {
return false;
}
}
}
return true;
}


数组划分

题目描述:Partition Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
/**
* @param nums: The integer array you should partition
* @param k: An integer
* @return: The index after partition
*/
int partitionArray(vector<int> &nums, int k) {
if (nums.empty()) {
return 0;
}
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
while (left <= right && nums[right] >= k) {
right--;
}
while(left <= right && nums[left] < k) {
left++;
}
if (left <= right) {
swap(nums[left], nums[right]);
left++;
right--;
}
}
return left;
}
};


无序数组K小元素

题目描述:Kth Smallest Numbers in Unsorted Array
Algorithm 1: heap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int kthSmallest_1(int k, vector<int> &nums) {
priority_queue<int> heap;
for (int i=0; i<nums.size(); ++i) {
if (heap.size() == k) {
int value = heap.top();
if (value > nums[i]) {
heap.pop();
heap.push(nums[i]);
}
} else {
heap.push(nums[i]);
}
}
return heap.top();
}

时间复杂度:O(nlogk)
空间复杂度:O(k)
Algorithm 2: quick select

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int kthSmallest(int k, vector<int> &nums) {
return quickSelect(nums, 0, nums.size() - 1, k - 1);
}
int quickSelect(vector<int> &nums, int start, int end, int k) {
if (start == end) {
return nums[start];
}
int left = start;
int right = end;
int pivot = nums[left + (right - left) / 2];
while (left <= right) {
while (left <= right && nums[left] < pivot) {
++left;
}
while (left <= right && nums[right] > pivot) {
--right;
}
if (left <= right) {
swap(nums[left], nums[right]);
++left;
--right;
}
}
if (right >= k && start <= right) {
return quickSelect(nums, start, right, k);
} else if (left <=k && left <= end) {
return quickSelect(nums, left, end, k);
} else {
return nums[k];
}
}

时间复杂度:O(n)
空间复杂度:O(1)


第k大元素

题目描述:Kth Largest Element

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
/*
* @param n: An integer
* @param nums: An array
* @return: the Kth largest element
*/
int kthLargestElement(int n, vector<int> &nums) {
assert(!nums.empty());
return quickSelect(nums, 0, nums.size() - 1, n);
}
int quickSelect(vector<int> &nums, int start, int end, int k) {
if (start == end) {
return nums[start];
}
int left = start;
int right = end;
int pivot = nums[left];
while (left < right) {
while (left < right && nums[right] <= pivot) {
--right;
}
nums[left] = nums[right];
while (left < right && nums[left] >= pivot) {
++left;
}
nums[right] = nums[left];
}
nums[left] = pivot;
if (left + 1 > k) {
return quickSelect(nums, start, left - 1, k);
} else if (left + 1 < k) {
return quickSelect(nums, left + 1, end, k);
} else {
return nums[left];
}
}
};


奇偶分割数组

题目描述:Partition Array by Odd and Even

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void partitionArray(vector<int> &nums) {
int left = 0;
int right = nums.size() - 1;
while (left < right) {
while (left < right && (nums[left] & 1)) {
++left;
}
while (left < right && !(nums[right] & 1)) {
--right;
}
if (left < right) {
swap(nums[left], nums[right]);
++left;
--right;
}
}
}


交错正负数

题目描述:Interleaving Positive and Negative Numbers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void rerange(vector<int> &A) {
int posNumCnt = 0;
int negNumCnt = 0;
for (auto num : A) {
if (num > 0) {
++posNumCnt;
} else if (num < 0) {
++negNumCnt;
}
}
int posIndex = 1;
int negIndex = 0;
if (posNumCnt > negNumCnt) {
posIndex = 0;
negIndex = 1;
}
while (posIndex < A.size() && negIndex < A.size()) {
while (posIndex < A.size() && A[posIndex] > 0) {
posIndex += 2;
}
while (negIndex < A.size() && A[negIndex] < 0) {
negIndex += 2;
}
if (posIndex < A.size() && negIndex < A.size()) {
swap(A[posIndex], A[negIndex]);
posIndex += 2;
negIndex += 2;
}
}
}


字符大小写排序

题目描述:Sort Letters by Case

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void sortLetters(string &chars) {
int left = 0;
int right = chars.length() - 1;
while (left < right) {
while (left < right && islower(chars[left])) {
++left;
}
while (left < right && isupper(chars[right])) {
--right;
}
if (left < right) {
swap(chars[left], chars[right]);
++left;
--right;
}
}
}


荷兰国旗

题目描述:Sort Colors

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void sortColors(vector<int> &nums) {
int left = 0;
int right = nums.size() - 1;
int i = 0;
while (i <= right) {
if (nums[i] == 0) {
swap(nums[i], nums[left]);
++left;
++i;
} else if (nums[i] == 2) {
swap(nums[i], nums[right]);
--right;
} else {
++i;
}
}
}


Sort Colors II

题目描述:Sort Colors II
Algorithm 1 : Count Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void sortColors2(vector<int> &colors, int k) {
countSort(colors, k);
}
void countSort(vector<int> &colors, int k) {
vector<int> count(k+1);
for (int i=0; i<colors.size(); ++i) {
++count[colors[i]];
}
int index = 0;
for (int i=0; i<count.size(); ++i) {
for (int j=0; j<count[i]; ++j) {
colors[index++] = i;
}
}
}

Algorithm 2 : Quick Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void quickSortColor(vector<int> &colors, int start, int end, int colorFrom, int colorTo) {
if (colorFrom == colorTo) {
return;
}
if (start >= end) {
return;
}
int colorMid = colorFrom + (colorTo - colorFrom) / 2;
int left = start;
int right = end;
while (left <= right) {
while (left <= right && colors[left] <= colorMid) {
++left;
}
while (left <= right && colors[right] > colorMid) {
--right;
}
if (left <= right) {
swap(colors[left], colors[right]);
++left;
--right;
}
}
quickSortColor(colors, start, right, colorFrom, colorMid);
quickSortColor(colors, left, end, colorMid + 1, colorTo);
}


Two Sum

题目描述:Two Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> twoSum(vector<int> &numbers, int target) {
vector<int> res;
map<int, int> m;
for (int i=0; i<numbers.size(); ++i) {
if (m.find(numbers[i]) != m.end()) {
res.push_back(m[numbers[i]]);
res.push_back(i);
return res;
}
m[target - numbers[i]] = i;
}
res.push_back(-1);
res.push_back(-1);
return res;
}


Two Sum II - Input array is sorted

题目描述:Two Sum II - Input array is sorted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> twoSum(vector<int> &nums, int target) {
vector<int> res;
int left = 0;
int right = nums.size() - 1;
while (left < right) {
if (nums[left] + nums[right] == target) {
res.push_back(left+1);
res.push_back(right+1);
return res;
} else if (nums[left] + nums[right] < target) {
++left;
} else {
--right;
}
}
res.push_back(-1);
res.push_back(-1);
return res;
}


Two Sum III - Data structure design

题目描述:Two Sum III - Data structure design

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> nums;
void add(int number) {
nums.push_back(number);
}
/*
* @param value: An integer
* @return: Find if there exists any pair of numbers which sum is equal to the value.
*/
bool find(int value) {
set<int> iset;
for (auto item : nums) {
if (iset.find(item) != iset.end()) {
return true;
}
iset.insert(value - item);
}
return false;
}


Two Sum - Unique pairs

题目描述:Two Sum - Unique pairs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int twoSum6(vector<int> &nums, int target) {
int cnt = 0;
int left = 0;
int right = nums.size() - 1;
sort(nums.begin(), nums.end());
while (left < right) {
if (nums[left] + nums[right] == target) {
++cnt;
++left;
--right;
while (left < right && nums[right] == nums[right + 1]) {
--right;
}
while (left > right && nums[left] == nums[left - 1]) {
++left;
}
} else if (nums[left] + nums[right] < target) {
++left;
} else {
--right;
}
}
return cnt;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int twoSum6(vector<int> &nums, int target) {
int cnt = 0;
int i = 0;
int j = nums.size() - 1;
sort(nums.begin(), nums.end());
for (i=0; i<nums.size(); ++i) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
while (j > i && nums[i] + nums[j] > target) {
--j;
}
if (j > i && nums[i] + nums[j] == target) {
++cnt;
}
}
return cnt;
}

3Sum

题目描述:3Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
vector<vector<int>> twoSum(vector<int> &numbers, int start, int target) {
vector<vector<int>> res;
int i = start;
int j = numbers.size() - 1;
for (i=start; i<numbers.size(); ++i) {
if (i > start && numbers[i] == numbers[i - 1]) {
continue;
}
while (j > i && numbers[i] + numbers[j] > target) {
--j;
}
if (j > i && numbers[i] + numbers[j] == target) {
vector<int> pos;
pos.push_back(numbers[i]);
pos.push_back(numbers[j]);
res.push_back(pos);
}
}
return res;
}
vector<vector<int>> threeSum(vector<int> &numbers) {
sort(numbers.begin(), numbers.end());
vector<vector<int>> res;
for (int i=0; i<numbers.size(); ++i) {
if (i > 0 && numbers[i] == numbers[i - 1]) {
continue;
}
auto twoSumRes = twoSum(numbers, i + 1, -numbers[i]);
for (auto item : twoSumRes) {
item.insert(item.begin(), numbers[i]);
res.push_back(item);
}
}
return res;
}


Two Sum - Less than or equal to target

题目描述:Two Sum - Less than or equal to target

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int twoSum5(vector<int> &nums, int target) {
int res = 0;
int left = 0;
int right = nums.size() - 1;
sort(nums.begin(), nums.end());
while (left < right) {
if (nums[left] + nums[right] <= target) {
res += right - left;
++left;
} else {
--right;
}
}
return res;
}


Two Sum - Greater than target

题目描述:Two Sum - Greater than target

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int twoSum2(vector<int> &nums, int target) {
int res = 0;
int left = 0;
int right = nums.size() - 1;
sort(nums.begin(), nums.end());
while (left < right) {
if (nums[left] + nums[right] > target) {
res += right - left;
--right;
} else {
++left;
}
}
return res;
}


3Sum Closest

题目描述:3Sum Closest

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int threeSumClosest(vector<int> &numbers, int target) {
if (numbers.size() < 3) {
return -1;
}
sort(numbers.begin(), numbers.end());
int bestSum = numbers[0] + numbers[1] + numbers[2];
for (int i=0; i<numbers.size(); ++i) {
int start = i + 1;
int end = numbers.size() - 1;
while (start < end) {
int sum = numbers[i] + numbers[start] + numbers[end];
if (abs(target - sum) < abs(target - bestSum)) {
bestSum = sum;
}
if (sum < target) {
++start;
} else {
--end;
}
}
}
return bestSum;
}


4Sum

题目描述:4Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
void twoSum(vector<int> &numbers, int s, int start, int target, vector<vector<int>> &result) {
int i = start;
int j = numbers.size() - 1;
for (i=start; i<numbers.size(); ++i) {
if (i > start && numbers[i] == numbers[i - 1]) {
continue;
}
while (j > i && numbers[i] + numbers[j] > target) {
--j;
}
if (j > i && numbers[i] + numbers[j] == target) {
vector<int> pos;
pos.push_back(numbers[s - 1]);
pos.push_back(numbers[start - 1]);
pos.push_back(numbers[i]);
pos.push_back(numbers[j]);
result.push_back(pos);
}
}
}
void threeSum(vector<int> &numbers, int start, int target, vector<vector<int>> &result) {
for (int i=start; i<numbers.size(); ++i) {
if (i > start && numbers[i] == numbers[i - 1]) {
continue;
}
twoSum(numbers, start, i + 1, target-numbers[i], result);
}
}
vector<vector<int>> fourSum(vector<int> &numbers, int target) {
vector<vector<int>> res;
if (numbers.size() < 4) {
return res;
}
sort(numbers.begin(), numbers.end());
for (int i=0; i<numbers.size(); ++i) {
if (i > 0 && numbers[i] == numbers[i - 1]) {
continue;
}
threeSum(numbers, i + 1, target-numbers[i], res);
}
return res;
}


Two Sum - Difference equals to target

题目描述:Two Sum - Difference equals to target

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Cmp {
public:
bool operator() (pair<int, int> &left, pair<int, int> &right) {
return left.first < right.first;
}
};
vector<int> twoSum7(vector<int> &nums, int target) {
vector<int> res;
vector<pair<int, int>> newNums;
int i = 0;
int j = 0;
for (int i=0; i<nums.size(); ++i) {
newNums.push_back(make_pair(nums[i], i + 1));
}
sort(newNums.begin(), newNums.end(), Cmp());
while (j < newNums.size()) {
if ( i == j) {
++j;
}
if (newNums[j].first - newNums[i].first == abs(target)) {
res.push_back(min(newNums[i].second, newNums[j].second));
res.push_back(max(newNums[i].second, newNums[j].second));
return res;
} else if (newNums[j].first - newNums[i].first < abs(target)) {
++j;
} else {
++i;
}
}
res.push_back(-1);
res.push_back(-1);
return res;
}


最长无重复字符的子串

题目描述:Longest Substring Without Repeating Characters

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int lengthOfLongestSubstring(string &s) {
vector<char> hash(256);
int i = 0;
int j = 0;
int res = 0;
for (int i=0; i<s.length(); ++i) {
hash[s[i]]++;
while (hash[s[i]] > 1) {
hash[s[j]]--;
j++;
}
res = max(res, i - j + 1);
}
return res;
}


最小子串覆盖

题目描述:Minimum Window Substring

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
string minWindow(string &source , string &target) {
vector<char> tHash(256, 0);
vector<char> sHash(256, 0);
int tLen = target.length();
int sLen = source.length();
int numT = 0;
for (int i=0; i<tLen; ++i) {
tHash[target[i]]++;
if (tHash[target[i]] == 1) {
numT++;
}
}
int r = 0;
int l = 0;
int numS = 0;
string res;
for (r = 0; r < sLen; ++r) {
sHash[source[r]]++;
if (sHash[source[r]] == tHash[source[r]]) {
numS++;
}
while (numS >= numT) {
if (res.empty() || r - l + 1 < res.length()) {
res = source.substr(l, r - l + 1);
}
if (sHash[source[l]] == tHash[source[l]]) {
numS--;
}
sHash[source[l]]--;
l++;
}
}
return res;
}


Hash

Rehashing

题目描述:Rehashing

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
vector<ListNode*> rehashing(vector<ListNode*> hashTable) {
int capacity = hashTable.size() * 2;
vector<ListNode*> rehashTable(capacity);
for (int i=0; i<hashTable.size(); ++i) {
if (hashTable[i] != NULL) {
ListNode *head = hashTable[i];
while (head != NULL) {
int index = (head->val % capacity + capacity) % capacity;
if (rehashTable[index] == NULL) {
rehashTable[index] = new ListNode(head->val);
} else {
ListNode *node = rehashTable[index];
while (node->next != NULL) {
node = node->next;
}
node->next = new ListNode(head->val);
}
head = head->next;
}
}
}
return rehashTable;
}


LRU Cache

题目描述:LRU Cache

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
class LRUCache {
private:
struct ListNode {
ListNode *pre;
ListNode *next;
int key;
int val;
ListNode(int key, int val) {
pre = NULL;
next = NULL;
this->key = key;
this->val = val;
}
};
unordered_map<int, ListNode*> hash;
ListNode *head;
ListNode *tail;
int capacity;
int size;
void moveToTail(ListNode *pre) {
if (pre->next == tail) {
return;
}
ListNode *node = pre->next;
pre->next = node->next;
if (node->next != NULL) {
hash[node->next->key] = pre;
}
tail->next = node;
node->next = NULL;
hash[node->key] = tail;
tail = node;
}
public:
/*
* @param capacity: An integer
*/
LRUCache(int capacity) {
this->capacity = capacity;
this->size = 0;
head = new ListNode(0, 0);
tail = head;
}
/*
* @param key: An integer
* @return: An integer
*/
int get(int key) {
if (hash.find(key) == hash.end()) {
return -1;
}
moveToTail(hash[key]);
return hash[key]->next->val;
}
/*
* @param key: An integer
* @param value: An integer
* @return: nothing
*/
void set(int key, int value) {
if (hash.find(key) != hash.end()) {
moveToTail(hash[key]);
hash[key]->next->val = value;
} else {
ListNode *node = new ListNode(key, value);
tail->next = node;
hash[key] = tail;
tail = node;
++size;
if (size > capacity) {
hash.erase(head->next->key);
head->next = head->next->next;
if (head->next != NULL) {
hash[head->next->key] = head;
}
}
}
}
};


乱序字符串

题目描述:乱序字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<string> anagrams(vector<string> &strs) {
vector<string> res;
map<string, int> strmap;
for (int i=0; i<strs.size(); ++i) {
string str = strs[i];
sort(str.begin(), str.end());
strmap[str] += 1;
}
for (int i=0; i<strs.size(); ++i) {
string str = strs[i];
sort(str.begin(), str.end());
if (strmap[str] > 1) {
res.push_back(strs[i]);
}
}
return res;
}


丑数II

题目描述:Ugly Number II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int nthUglyNumber(int n) {
vector<int> num;
num.push_back(1);
int p2 = 0;
int p3= 0;
int p5 = 0;
for (int i=1; i<n; ++i) {
int lastNumber = num[i - 1];
while (num[p2] * 2 <= lastNumber) {
++p2;
}
while (num[p3] * 3 <= lastNumber) {
++p3;
}
while (num[p5] * 5 <= lastNumber) {
++p5;
}
num.push_back(min(num[p2] * 2, min(num[p3] * 3, num[p5] * 5)));
}
return num[n - 1];
}


前K大数 II

题目描述:Top k Largest Numbers II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
int maxSize;
priority_queue<int, deque<int>, greater<int> > minHeap;
/*
* @param k: An integer
*/Solution(int k) {
maxSize = k;
}
/*
* @param num: Number to be added
* @return: nothing
*/
void add(int num) {
minHeap.push(num);
if (minHeap.size() > maxSize) {
minHeap.pop();
}
}
/*
* @return: Top k element
*/
vector<int> topk() {
vector<int> res;
while (!minHeap.empty()) {
res.push_back(minHeap.top());
minHeap.pop();
}
for (int i=0; i<res.size(); ++i) {
minHeap.push(res[i]);
}
sort(res.begin(), res.end(), greater<int>());
return res;
}
};


优秀成绩

题目描述:High Five

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class RecordCmp {
public:
int id;
double score;
RecordCmp(int id, double score) {
this->id = id;
this->score = score;
}
bool operator < (const RecordCmp &r) const {
return this->score > r.score;
}
};
class Solution {
public:
/**
* @param results a list of <student_id, score>
* @return find the average of 5 highest scores for each person
* map<int, double> (student_id, average_score)
*/
map<int, double> highFive(vector<Record>& results) {
map<int, priority_queue<double, deque<double>, greater<int>>> amap;
map<int, double> rmap;
for (int i=0; i<results.size(); ++i) {
amap[results[i].id].push(results[i].score);
if (amap[results[i].id].size() > 5) {
amap[results[i].id].pop();
}
}
for (auto a : amap) {
double sum = 0.0;
while (!a.second.empty()) {
sum += a.second.top();
a.second.pop();
}
rmap[a.first] = sum / 5.0;
}
return rmap;
}
};


K个最近的点

题目描述:K Closest Points

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
Point ori;
bool operator < (const Point &l, const Point &r) {
int dis1 = (l.x - ori.x) * (l.x - ori.x) + (l.y - ori.y) * (l.y - ori.y);
int dis2 = (r.x - ori.x) * (r.x - ori.x) + (r.y - ori.y) * (r.y - ori.y);
if (dis1 == dis2) {
if (l.x == r.x) {
return l.y > r.y;
} else {
return l.x > r.x;
}
}
return dis1 > dis2;
}
class Solution {
public:
/**
* @param points: a list of points
* @param origin: a point
* @param k: An integer
* @return: the k closest points
*/
vector<Point> kClosest(vector<Point> &points, Point &origin, int k) {
ori.x = origin.x;
ori.y = origin.y;
priority_queue<Point> pq;
vector<Point> res;
for (int i=0; i<points.size(); ++i) {
pq.push(points[i]);
}
for (int i=0; i<k; ++i) {
if (!pq.empty()) {
res.push_back(pq.top());
pq.pop();
}
}
return res;
}
};


Merge K Sorted Lists

题目描述:Merge K Sorted Lists
heap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
bool operator < (const ListNode &l, const ListNode &r) {
return l.val > r.val;
}
class Solution {
public:
/**
* @param lists: a list of ListNode
* @return: The head of one sorted list.
*/
ListNode *mergeKLists(vector<ListNode *> &lists) {
priority_queue<ListNode> pq;
for (int i=0; i<lists.size(); ++i) {
ListNode *head = lists[i];
while (head != NULL) {
pq.push(*head);
head = head->next;
}
}
ListNode dummy(0);
ListNode *pre = &dummy;
while (!pq.empty()) {
ListNode *node = new ListNode(pq.top().val);
pre->next = node;
pre = pre->next;
pq.pop();
}
ListNode *head = dummy.next;
while (head != NULL) {
head = head->next;
}
return dummy.next;
}
};

two sorted list merge

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
ListNode *mergeKLists(vector<ListNode *> &lists) {
if (lists.size() == 0) {
return NULL;
}
return mergeHelper(lists, 0, lists.size() - 1);
}
ListNode *mergeHelper(vector<ListNode *> &lists, int start, int end) {
if (start == end) {
return lists[start];
}
int mid = start + (end - start) / 2;
ListNode *head1 = mergeHelper(lists, start, mid);
ListNode *head2 = mergeHelper(lists, mid + 1, end);
return merge(head1, head2);
}
ListNode *merge(ListNode *head1, ListNode *head2) {
ListNode dummy;
ListNode *next = &dummy;
while (head1 != NULL && head2 != NULL) {
if (head1->val < head2->val) {
next->next = head1;
head1 = head1->next;
next = next->next;
} else {
next->next = head2;
head2 = head2->next;
next = next->next;
}
}
if (head1 != NULL) {
next->next = head1;
}
if (head2 != NULL) {
next->next = head2;
}
return dummy.next;
}


Merge K Sorted Arrays

题目描述:Merge K Sorted Arrays

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class cmp {
public:
bool operator() (const pair<int, int> &l, const pair<int, int> &r) {
return l.second > r.second;
}
};
class Solution {
public:
/**
* @param arrays: k sorted integer arrays
* @return: a sorted array
*/
vector<int> mergekSortedArrays(vector<vector<int>> &arrays) {
vector<int> res;
vector<int> indexs(arrays.size());
priority_queue<pair<int, int>, deque<pair<int, int> >, cmp> minHeap;
for (int i=0; i<arrays.size(); ++i) {
if (arrays[i].size() > 0) {
minHeap.push(make_pair(i, arrays[i][0]));
}
}
while (!minHeap.empty()) {
pair<int, int> top = minHeap.top();
minHeap.pop();
res.push_back(top.second);
int index = top.first;
if (indexs[index] + 1 < arrays[index].size()) {
indexs[index] += 1;
minHeap.push(make_pair(index, arrays[index][indexs[index]]));
}
}
return res;
}
};


排序矩阵中的从小到大第k个数

题目描述:Kth Smallest Number in Sorted Matrix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public:
/**
* @param matrix: a matrix of integers
* @param k: An integer
* @return: the kth smallest number in the matrix
*/
class Element {
public:
int m_val;
int m_x;
int m_y;
Element(int val, int x, int y) : m_val(val), m_x(x), m_y(y) { }
bool operator < (const Element &r) const {
return m_val > r.m_val;
}
};
int kthSmallest(vector<vector<int>> &matrix, int k) {
if (matrix.size() == 0 || matrix[0].size() == 0) {
return -1;
}
// 方向数组
int directX[2] = {0, 1};
int directY[2] = {1, 0};
// 最小堆
priority_queue<Element> minHeap;
minHeap.push(Element(matrix[0][0], 0, 0));
int m = matrix.size();
int n = matrix[0].size();
vector<vector<int> > visited(m, vector<int>(n));
visited[0][0] = 1;
for (int i=0; i<k-1; ++i) {
Element e = minHeap.top();
minHeap.pop();
for (int j=0; j<2; ++j) {
int x = e.m_x + directX[j];
int y = e.m_y + directY[j];
if (x < m && y < n) {
if (visited[x][y] == 0) {
minHeap.push(Element(matrix[x][y], x, y));
visited[x][y] = 1;
}
}
}
}
return minHeap.top().m_val;
}
};


接雨水II

题目描述:Trapping Rain Water II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class CursorPoint {
public:
int x;
int y;
int val;
CursorPoint(int x, int y, int val) {
this->x = x;
this->y = y;
this->val = val;
}
bool operator < (const CursorPoint &r) const {
return val > r.val;
}
};
class Solution {
public:
/**
* @param heights: a matrix of integers
* @return: an integer
*/
int trapRainWater(vector<vector<int>> &heights) {
if (heights.size() == 0 || heights[0].size() == 0) {
return 0;
}
priority_queue<CursorPoint> minHeap;
int directX[] = {1, 0, -1, 0};
int directY[] = {0, 1, 0, -1};
int n = heights.size();
int m = heights[0].size();
vector<vector<bool>> visited(n, vector<bool>(m, false));
int res = 0;
for (int i=0; i<n; ++i) {
minHeap.push(CursorPoint(i, 0, heights[i][0]));
minHeap.push(CursorPoint(i, m-1, heights[i][m-1]));
visited[i][0] = true;
visited[i][m-1] = true;
}
for (int i=1; i<m-1; ++i) {
minHeap.push(CursorPoint(0, i, heights[0][i]));
minHeap.push(CursorPoint(n-1, i, heights[n-1][i]));
visited[0][i] = true;
visited[n-1][i] = true;
}
while (!minHeap.empty()) {
CursorPoint top = minHeap.top();
minHeap.pop();
for (int i=0; i<4; ++i) {
int x = top.x + directX[i];
int y = top.y + directY[i];
if (isValid(x, y, n, m) && !visited[x][y]) {
visited[x][y] = true;
if (heights[x][y] < top.val) {
res += top.val - heights[x][y];
minHeap.push(CursorPoint(x, y, top.val));
} else {
minHeap.push(CursorPoint(x, y, heights[x][y]));
}
}
}
}
return res;
}
bool isValid(int x, int y, int n, int m) {
return x >= 0 && x < n && y >= 0 && y < m;
}
};


滑动窗口的中位数

题目描述:Sliding Window Median

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
vector<int> medianSlidingWindow(vector<int> &nums, int k) {
vector<int> res;
if (nums.empty()) {
return res;
}
multiset<int, less<int>> minHeap;
multiset<int, greater<int>> maxHeap;
int n = nums.size();
for (int i=0; i<k&&i<n; ++i) {
minHeap.insert(nums[i]);
if (i & 1) {
if (*maxHeap.begin() > *minHeap.begin()) {
minHeap.insert(*maxHeap.begin());
maxHeap.insert(*minHeap.begin());
minHeap.erase(minHeap.lower_bound(*minHeap.begin()));
maxHeap.erase(maxHeap.lower_bound(*maxHeap.begin()));
}
} else {
maxHeap.insert(*minHeap.begin());
minHeap.erase(minHeap.lower_bound(*minHeap.begin()));
}
}
res.push_back(*maxHeap.begin());
for (int i=k; i<n; ++i) {
if (maxHeap.find(nums[i-k]) != maxHeap.end()) {
maxHeap.erase(maxHeap.lower_bound(nums[i-k]));
minHeap.insert(nums[i]);
maxHeap.insert(*minHeap.begin());
minHeap.erase(minHeap.lower_bound(*minHeap.begin()));
} else {
minHeap.erase(minHeap.lower_bound(nums[i-k]));
minHeap.insert(nums[i]);
if (*maxHeap.begin() > *minHeap.begin()) {
minHeap.insert(*maxHeap.begin());
maxHeap.insert(*minHeap.begin());
minHeap.erase(minHeap.lower_bound(*minHeap.begin()));
maxHeap.erase(maxHeap.lower_bound(*maxHeap.begin()));
}
}
res.push_back(*maxHeap.begin());
}
return res;
}


动态规划

数字三角形

题目描述:Triangle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class Solution {
public:
/**
* @param triangle: a list of lists of integers
* @return: An integer, minimum path sum
*/
int best = INT32_MAX;
int minimumTotal(vector<vector<int>> &triangle) {
/*traverse*/
// traverse(triangle, 0, 0, 0);
// return best;
/*divide conquer*/
// map<pair<int, int>, int> cache;
// return divideConquer(triangle, 0, 0, cache);
/*dynamic programming*/
int n = triangle.size();
vector<vector<int>> d(n, vector<int>(n));
// 自底向上
// for (int i=0; i<n; ++i) {
// d[n - 1][i] = triangle[n - 1][i];
// }
// for (int i=n-2; i>=0; --i) {
// for (int j=0; j<=i; ++j) {
// d[i][j] = min(d[i+1][j], d[i+1][j+1]) + triangle[i][j];
// }
// }
// return d[0][0];
// 自顶向下
d[0][0] = triangle[0][0];
for (int i=1; i<n; ++i) {
d[i][0] = d[i - 1][0] + triangle[i][0];
d[i][i] = d[i - 1][i - 1] + triangle[i][i];
}
for (int i=1; i<n; ++i) {
for (int j=1; j<i; ++j) {
d[i][j] = min(d[i - 1][j], d[i - 1][j - 1]) + triangle[i][j];
}
}
int minSum = INT32_MAX;
for (int i=0; i<n; ++i) {
minSum = min(minSum, d[n - 1][i]);
}
return minSum;
}
void traverse(vector<vector<int>> &triangle, int x, int y, int sum) {
if (x == triangle.size()) {
if (best > sum) {
best = sum;
}
return;
}
traverse(triangle, x + 1, y, sum + triangle[x][y]);
traverse(triangle, x + 1, y + 1, sum + triangle[x][y]);
}
int divideConquer(vector<vector<int>> &triangle, int x, int y, map<pair<int, int>, int> &cache) {
if (x == triangle.size()) {
return 0;
}
pair<int, int> pos = make_pair(x, y);
if (cache.find(pos) != cache.end()) {
return cache[pos];
}
cache[pos] = triangle[x][y] + min(
divideConquer(triangle, x + 1, y, cache),
divideConquer(triangle, x + 1, y + 1, cache)
);
return cache[pos];
}
};


最小路径和

题目描述:Minimum Path Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int minPathSum(vector<vector<int>> &grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> d(m, vector<int>(n));
d[0][0] = grid[0][0];
for (int i=1; i<n; ++i) {
d[0][i] = d[0][i - 1] + grid[0][i];
}
for (int i=1; i<m; ++i) {
d[i][0] = d[i - 1][0] + grid[i][0];
}
for (int i=1; i<m; ++i) {
for (int j=1; j<n; ++j) {
d[i][j] = min(d[i - 1][j], d[i][j - 1]) + grid[i][j];
}
}
return d[m - 1][n - 1];
}


不同的路径

题目描述:Unique Paths

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int uniquePaths(int m, int n) {
vector<vector<int>> path(m, vector<int>(n));
for (int i=0; i<m; ++i) {
path[i][0] = 1;
}
for (int i=0; i<n; ++i) {
path[0][i] = 1;
}
for (int i=1; i<m; ++i) {
for (int j=1; j<n; ++j) {
path[i][j] = path[i - 1][j] + path[i][j - 1];
}
}
return path[m - 1][n - 1];
}


爬楼梯

题目描述:Climbing Stairs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int climbStairs(int n) {
if (n == 0) {
return 0;
}
int f1 = 1;
int f2 = 1;
for (int i=2; i<=n; ++i) {
f2 = f1 + f2;
f1 = f2 - f1;
}
return f2;
}


跳跃游戏

题目描述:Jump Game
Dynamic programing

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool canJump(vector<int> &A) {
int n = A.size();
vector<bool> f(n);
f[0] = true;
for (int i=1; i<n; ++i) {
for (int j=0; j<i; ++j) {
if (f[j] && A[j] + j >= i) {
f[i] = true;
break;
}
}
}
return f[n - 1];
}

Greedy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool canJump(vector<int> &A) {
if (A.size() == 0) {
return false;
}
int farthest = A[0];
for (int i=1; i<A.size(); ++i) {
if (i <= farthest && A[i] + i >= farthest) {
farthest = A[i] + i;
}
}
return farthest >= A.size() - 1;
}


最长上升子序列(LIS)

题目描述:Longest Increasing Subsequence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int longestIncreasingSubsequence(vector<int> &nums) {
if (nums.size() == 0) {
return 0;
}
int n = nums.size();
int longest = 1;
vector<int> f(n, 1);
for (int i=1; i<n; ++i) {
for (int j=0; j<i; ++j) {
if (nums[i] > nums[j]) {
f[i] = max(f[i] - 1, f[j]) + 1;
}
}
if (longest < f[i]) {
longest = f[i];
}
}
return longest;
}


完美平方

题目描述:Perfect Squares

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int numSquares(int n) {
vector<int> f(n + 1, INT32_MAX);
f[0] = 0;
for (int i=1; i<=n; ++i) {
for (int j=1; j<=i; ++j) {
if (i - j * j >= 0) {
f[i] = min(f[i], f[i - j * j] + 1);
}
}
}
return f[n];
}


最大整除子集

题目描述:Largest Divisible Subset

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
vector<int> largestDivisibleSubset(vector<int> &nums) {
sort(nums.begin(), nums.end());
vector<int> res;
if (nums.size() == 0) {
return res;
}
int n = nums.size();
int m = 0;
int index = -1;
vector<int> dp(n, 1);
vector<int> pre(n, -1);
for (int i=0; i<n; ++i) {
for (int j=0; j<i; ++j) {
if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
pre[i] = j;
}
}
if (dp[i] >= m) {
m = dp[i];
index = i;
}
}
for (int i=0; i<m; ++i) {
res.push_back(nums[index]);
index = pre[index];
}
return res;
}


俄罗斯套娃

题目描述:Russian Doll Envelopes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class EnvelopsCmp {
public:
bool operator() (pair<int, int> &l, pair<int, int> &r) {
if (l.first == r.first) {
return l.second > r.second;
}
return l.first < r.first;
}
};
class Solution {
public:
/*
* @param envelopes: a number of envelopes with widths and heights
* @return: the maximum number of envelopes
*/
int maxEnvelopes(vector<pair<int, int>>& envelopes) {
sort(envelopes.begin(), envelopes.end(), EnvelopsCmp());
int n = envelopes.size();
vector<int> dp(n);
vector<int> height(n + 1, INT32_MAX);
int res = 0;
for (int i=0; i<n; ++i) {
int k = lower_bound(height.begin(), height.end(), envelopes[i].second) - height.begin();
dp[i] = k;
height[k] = envelopes[i].second;
if (res < dp[i]) {
res = dp[i];
}
}
return res + 1;
}
};


青蛙过河

题目描述:Frog Jump

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
bool canCross(vector<int> &stones) {
map<int, unordered_set<int> > dp;
for (int i=0; i<stones.size(); ++i) {
unordered_set<int> tmp;
dp[stones[i]] = tmp;
}
dp[0].insert(0);
for (int i=0; i<stones.size() - 1; ++i) {
int stone = stones[i];
for (int k : dp[stone]) {
if (k - 1 > 0 && dp.count(stone + k - 1)) {
dp[stone + k - 1].insert(k - 1);
}
if (dp.count(stone + k)) {
dp[stone + k].insert(k);
}
if (dp.count(stone + k + 1)) {
dp[stone + k + 1].insert(k + 1);
}
}
}
return !dp[stones[stones.size() - 1]].empty();
}


Edit Distance

题目描述:Edit Distance

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
/**
* @param word1: A string
* @param word2: A string
* @return: The minimum number of steps.
*/
int minDistance(string &word1, string &word2) {
int n = word1.length();
int m = word2.length();
vector<vector<int>> f(n + 1, vector<int>(m + 1));
for (int i=0; i<=n; ++i) {
f[i][0] = i;
}
for (int j=0; j<=m; ++j) {
f[0][j] = j;
}
for (int i=1; i<=n; ++i) {zuid
for (int j=1; j<=m; ++j) {
if (word1[i - 1] == word2[j - 1]) {
f[i][j] = f[i - 1][j - 1];
} else {
f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])) + 1;
}
}
}
return f[n][m];
}
};


K Edit Distance

题目描述:K Edit Distance

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class TrieNode {
public:
bool isWord;
string word;
map<char, TrieNode*> branch;
TrieNode() : isWord(false) { }
};
class TrieTree {
public:
TrieNode *root;
TrieTree() {
this->root = new TrieNode();
}
void insert(string &word) {
TrieNode *node = root;
for (int i=0; i<word.length(); ++i) {
if (node->branch.find(word[i]) == node->branch.end()) {
node->branch[word[i]] = new TrieNode();
}
node = node->branch[word[i]];
}
node->isWord = true;
node->word = word;
}
};
class Solution {
public:
/**
* @param words: a set of stirngs
* @param target: a target string
* @param k: An integer
* @return: output all the strings that meet the requirements
*/
vector<string> kDistance(vector<string> &words, string &target, int k) {
TrieTree trie;
for (string word : words) {
trie.insert(word);
}
vector<int> dp(target.size() + 1, 0);
for (int i=0; i<=target.size(); ++i) {
dp[i] = i;
}
vector<string> res;
findall(target, k, res, trie.root, dp);
return res;
}
void findall(string &target, int k, vector<string> &res, TrieNode *root, vector<int> &dp) {
if (root->isWord && dp[target.size()] <= k) {
res.push_back(root->word);
}
for (auto b : root->branch) {
vector<int> nextdp(target.size() + 1);
for (int j=0; j<=target.size(); ++j) {
if (j == 0) {
nextdp[0] = dp[0] + 1;
} else if (b.first == target[j - 1]) {
nextdp[j] = dp[j - 1];
} else {
nextdp[j] = min(nextdp[j - 1], min(dp[j], dp[j - 1])) + 1;
}
}
findall(target, k, res, b.second, nextdp);
}
}
};


House Robber

题目描述:House Robber

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
/**
* @param A: An array of non-negative integers
* @return: The maximum amount of money you can rob tonight
*/
long long houseRobber(vector<int> &A) {
if (A.empty()) {
return 0;
}
vector<long long> dp(2, 0);
dp[0] = 0;
dp[1] = A[0];
for (int i=2; i<=A.size(); ++i) {
dp[i%2] = max(dp[(i - 2)%2] + A[i - 1], dp[(i - 1)%2]);
}
return dp[A.size() % 2];
}
};


House Robber II

题目描述:House Robber II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
/**
* @param nums: An array of non-negative integers.
* @return: The maximum amount of money you can rob tonight
*/
int houseRobber2(vector<int> &nums) {
if (nums.empty()) {
return 0;
}
if (nums.size() == 1) {
return nums[0];
}
vector<long long> dp1(2, 0);
dp1[0] = 0;
dp1[1] = nums[0];
vector<long long> dp2(2, 0);
dp2[0] = 0;
dp2[1] = 0;
for (int i=2; i<=nums.size()-1; ++i) {
dp1[i%2] = max(dp1[(i - 2)%2] + nums[i - 1], dp1[(i - 1)%2]);
}
for (int i=2; i<=nums.size(); ++i) {
dp2[i % 2] = max(dp2[(i - 2) % 2] + nums[i - 1], dp2[(i - 1) % 2]);
}
return max(dp1[(nums.size() - 1) % 2], dp2[nums.size() % 2]);
}
};


Longest Continuous Increasing Subsequence II

题目描述:Longest Continuous Increasing Subsequence II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:
/**
* @param matrix: A 2D-array of integers
* @return: an integer
*/
int longestContinuousIncreasingSubsequence2(vector<vector<int>> &matrix) {
if (matrix.empty() || matrix[0].empty()) {
return 0;
}
int n = matrix.size();
int m = matrix[0].size();
vector<vector<int>> dp(n, vector<int>(m));
int ans = 0;
for (int i=0; i<n; ++i) {
for (int j=0; j<m; ++j) {
dp[i][j] = search(matrix, i, j, dp);
ans = max(ans, dp[i][j]);
}
}
return ans;
}
int search(vector<vector<int>> &matrix, int x, int y, vector<vector<int>> &dp) {
if (dp[x][y] != 0) {
return dp[x][y];
}
int directX[] = {1, 0, -1, 0};
int directY[] = {0, 1, 0, -1};
int n = matrix.size();
int m = matrix[0].size();
int ans = 1;
for (int i=0; i<4; ++i) {
int newX = x + directX[i];
int newY = y + directY[i];
if (isValid(n, m, newX, newY)) {
if (matrix[x][y] > matrix[newX][newY]) {
ans = max(ans, search(matrix, newX, newY, dp) + 1);
}
}
}
dp[x][y] = ans;
return ans;
}
bool isValid(int n, int m, int x, int y) {
return x >= 0 && x < n && y >= 0 && y < m;
}
};


Maximal Square

题目描述:Maximal Square

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 解法一
class Solution {
public:
/**
* @param matrix: a matrix of 0 and 1
* @return: an integer
*/
int maxSquare(vector<vector<int>> &matrix) {
if (matrix.empty() || matrix[0].empty()) {
return 0;
}
int n = matrix.size();
int m = matrix[0].size();
vector<vector<int>> up(n + 1, vector<int>(m + 1, 0));
vector<vector<int>> left(n + 1, vector<int>(m + 1, 0));
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
int ans = 0;
for (int i=1; i<=n; ++i) {
for (int j=1; j<=m; ++j) {
dp[i][j] = 0;
up[i][j] = 0;
left[i][j] = 0;
if (matrix[i-1][j-1]) {
dp[i][j] = min(dp[i - 1][j - 1], min(up[i - 1][j], left[i][j - 1])) + 1;
up[i][j] = up[i - 1][j] + 1;
left[i][j] = left[i][j - 1] + 1;
}
ans = max(ans, dp[i][j]);
}
}
return ans * ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 解法二
class Solution {
public:
/**
* @param matrix: a matrix of 0 and 1
* @return: an integer
*/
int maxSquare(vector<vector<int>> &matrix) {
if (matrix.empty() || matrix[0].empty()) {
return 0;
}
int n = matrix.size();
int m = matrix[0].size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
int ans = 0;
for (int i=1; i<=n; ++i) {
for (int j=1; j<=m; ++j) {
dp[i][j] = 0;
if (matrix[i-1][j-1]) {
dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
}
ans = max(ans, dp[i][j]);
}
}
return ans * ans;
}
};

Coins in a Line

题目描述:Coins in a Line

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 解法一:动态规划
class Solution {
public:
/**
* @param n: An integer
* @return: A boolean which equals to true if the first player will win
*/
bool firstWillWin(int n) {
vector<bool> dp(n + 1);
dp[0] = false;
dp[1] = true;
dp[2] = true;
dp[3] = false;
for (int i=4; i<=n; ++i) {
dp[i] = (dp[i - 2] && dp[i - 3]) || (dp[i - 3] && dp[i - 4]);
}
return dp[n];
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 解法二:记忆化搜索
class Solution {
public:
/**
* @param n: An integer
* @return: A boolean which equals to true if the first player will win
*/
bool firstWillWin(int n) {
vector<int> dp(n + 1);
return memorySearch(n, dp);
}
bool memorySearch(int n, vector<int> &dp) {
if (dp[n] != 0) {
if (dp[n] == 1) {
return true;
} else {
return false;
}
}
if (n == 0) {
return false;
} else if (n == 1) {
return true;
} else if (n == 2) {
return true;
} else {
if (!memorySearch(n - 1, dp) || !memorySearch(n - 2, dp)) {
dp[n] = 1;
} else {
dp[n] = 2;
}
}
if (dp[n] == 1) {
return true;
}
return false;
}
};

Coins in a Line II

题目描述:Coins in a Line II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
/**
* @param values: a vector of integers
* @return: a boolean which equals to true if the first player will win
*/
bool firstWillWin(vector<int> &values) {
int n = values.size();
vector<int> dp(n + 1);
dp[0] = 0;
dp[1] = values[n - 1];
dp[2] = values[n - 1] + values[n - 2];
int sum = values[n - 1] + values[n - 2];
for (int i=3; i<=n; ++i) {
sum += values[n - i];
dp[i] = max(min(dp[i - 2], dp[i - 3]) + values[n - i], min(dp[i - 3], dp[i - 4]) + values[n - i] + values[n - i + 1]);
}
return dp[n] > sum / 2;
}
};


Coins in a Line III

题目描述:Coins in a Line III

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 方法一:动态规划
class Solution {
public:
/**
* @param values: a vector of integers
* @return: a boolean which equals to true if the first player will win
*/
bool firstWillWin(vector<int> &values) {
if (values.empty()) {
return true;
}
int n = values.size();
vector<vector<int>> dp(n, vector<int>(n));
int sum = 0;
for (int i=0; i<n; ++i) {
dp[i][i] = values[i];
sum += values[i];
}
for (int i=0; i<n-1; ++i) {
dp[i][i + 1] = max(values[i], values[i + 1]);
}
for (int i=n-1; i>=0; --i) {
for (int j=i+2; j<n; ++j) {
int left = min(dp[i + 2][j], dp[i + 1][j - 1]) + values[i];
int right = min(dp[i][j - 2], dp[i + 1][j - 1]) + values[j];
dp[i][j] = max(left, right);
}
}
return dp[0][n - 1] > sum / 2;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// 解法二:记忆化搜索
class Solution {
public:
/**
* @param values: a vector of integers
* @return: a boolean which equals to true if the first player will win
*/
bool firstWillWin(vector<int> &values) {
if (values.empty()) {
return true;
}
int n = values.size();
vector<vector<int>> dp(n, vector<int>(n));
int sum = 0;
for (auto v : values) {
sum += v;
}
memorySearch(values, 0, n - 1, dp);
return dp[0][n - 1] > sum / 2;
}
int memorySearch(vector<int> &values, int left, int right, vector<vector<int>> &dp) {
if (dp[left][right] != 0) {
return dp[left][right];
}
if (left > right) {
dp[left][right] = 0;
} else if (left == right) {
dp[left][right] = values[left];
} else if (left + 1 == right) {
dp[left][right] = max(values[left], values[right]);
} else {
int pick_left = min(memorySearch(values, left + 2, right, dp), memorySearch(values, left + 1, right - 1, dp)) + values[left];
int pick_right = min(memorySearch(values, left, right - 2, dp), memorySearch(values, left + 1, right - 1, dp)) + values[right];
dp[left][right] = max(pick_left, pick_right);
}
return dp[left][right];
}
};

Burst Balloons

题目描述:Burst Balloons

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
/**
* @param nums: A list of integer
* @return: An integer, maximum coins
*/
int maxCoins(vector<int> &nums) {
if (nums.empty()) {
return 0;
}
nums.insert(nums.begin(), 1);
nums.push_back(1);
int n = nums.size();
vector<vector<int>> dp(n, vector<int>(n));
for (int i=n-1; i>=0; --i) {
for (int j=i + 2; j<n; ++j) {
for (int k=i+1; k<j; ++k) {
int midValue = nums[i] * nums[k] * nums[j];
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + midValue);
}
}
}
return dp[0][n - 1];
}
};


Backpack

题目描述:Backpack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
/**
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
* @return: The maximum size
*/
int backPack(int m, vector<int> &A) {
int n = A.size();
vector<vector<int>> dp(2, vector<int>(m + 1));
for (int i=1; i<=n; ++i) {
for (int j=1; j<=m; ++j) {
dp[i % 2][j] = dp[(i - 1) % 2][j];
if (j - A[i - 1] >= 0) {
dp[i % 2][j] = max(dp[i % 2][j], dp[(i - 1) % 2][j - A[i - 1]] + A[i - 1]);
}
}
}
return dp[n % 2][m];
}
};

BackpackII

题目描述:BackpackII

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
/**
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
* @param V: Given n items with value V[i]
* @return: The maximum value
*/
int backPackII(int m, vector<int> &A, vector<int> &V) {
int n = A.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1));
for (int i=1; i<=n; ++i) {
for (int j=1; j<=m; ++j) {
dp[i][j] = dp[i - 1][j];
if (j - A[i - 1] >= 0) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - A[i - 1]] + V[i - 1]);
}
}
}
return dp[n][m];
}
};


BackpackIII

题目描述:BackpackII

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
/**
* @param A: an integer array
* @param V: an integer array
* @param m: An integer
* @return: an array
*/
int backPackIII(vector<int> &A, vector<int> &V, int m) {
int n = A.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1));
for (int i=1; i<=n; ++i) {
for (int j=1; j<=m; ++j) {
dp[i][j] = dp[i - 1][j];
for (int k = 1; k<= j / A[i - 1]; ++k) {
dp[i][j] = max(dp[i][j], dp[i][j - k * A[i - 1]] + k * V[i - 1]);
}
}
}
return dp[n][m];
}
};


BackpackIV

题目描述:BackpackIV

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
/**
* @param nums: an integer array and all positive numbers, no duplicates
* @param target: An integer
* @return: An integer
*/
int backPackIV(vector<int> &nums, int target) {
int n = nums.size();
vector<vector<int>> dp(n + 1, vector<int>(target + 1));
for (int i=0; i<=n; ++i) {
dp[i][0] = 1;
}
for (int j=1; j<=target; ++j) {
dp[0][j] = 0;
}
for (int i=1; i<=n; ++i) {
for (int j=1; j<=target; ++j) {
dp[i][j] = dp[i - 1][j];
for (int k=1; k<=j/nums[i-1]; ++k) {
dp[i][j] += dp[i - 1][j - k * nums[i - 1]];
}
}
}
return dp[n][target];
}
};


k Sum

题目描述:k Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
/**
* @param A: An integer array
* @param k: A positive integer (k <= length(A))
* @param target: An integer
* @return: An integera
*/
int kSum(vector<int> &A, int k, int target) {
int n = A.size();
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(k + 1, vector<int>(target + 1)));
for (int i=0; i<=n; ++i) {
dp[i][0][0] = 1;
}
for (int i=1; i<=n; ++i) {
for (int j=1; j<=k; ++j) {
for (int t=1; t<=target; ++t){
dp[i][j][t] = dp[i - 1][j][t];
if (t - A[i - 1] >= 0) {
dp[i][j][t] += dp[i - 1][j - 1][t - A[i - 1]];
}
}
}
}
return dp[n][k][target];
}
};


最小调整代价

题目描述:Minimum Adjustment Cost

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
/*
* @param A: An integer array
* @param target: An integer
* @return: An integer
*/
int MinAdjustmentCost(vector<int> &A, int target) {
if (A.empty()) {
return 0;
}
int n = A.size();
int m = 0;
for (auto num : A) {
m = max(m, num);
}
vector<vector<int>> dp(n, vector<int>(m + 1, INT32_MAX));
for (int i=0; i<=m; ++i) {
dp[0][i] = abs(A[0] - i);
}
for (int i=1; i<n; ++i) {
for (int j=0; j<=m; ++j) {
for (int k=0; k<=m; ++k) {
if (abs(k - j) <= target) {
dp[i][j] = min(dp[i][j], dp[i - 1][k] + abs(A[i] - j));
}
}
}
}
int ans = INT32_MAX;
for (int j=0; j<=m; ++j) {
ans = min(ans, dp[n - 1][j]);
}
return ans;
}
};


Stone Game

题目描述:Stone Game

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
/**
* @param A: An integer array
* @return: An integer
*/
int stoneGame(vector<int> &A) {
if (A.empty()) {
return 0;
}
int n = A.size();
vector<vector<int>> dp(n, vector<int>(n, INT32_MAX));
vector<int> sum(n + 1);
for (int i=1; i<=n; ++i) {
sum[i] = sum[i - 1] + A[i - 1];
}
for (int i=0; i<n; ++i) {
dp[i][i] = 0;
}
for (int i=n-1; i>=0; --i) {
for (int j=i+1; j<n; ++j) {
for (int k=i; k<j; ++k) {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j + 1] - sum[i]);
}
}
}
return dp[0][n - 1];
}
};


攀爬字符串

题目描述:Scramble String

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
/**
* @param s1: A string
* @param s2: Another string
* @return: whether s2 is a scrambled string of s1
*/
map<string, bool> hash;
bool isScramble(string &s1, string &s2) {
if (s1.length() != s2.length()) {
return false;
}
if (hash.find(s1 + "#" + s2) != hash.end()) {
return false;
}
int len = s1.length();
if (len == 1) {
return s1 == s2;
}
for (int i=1; i<len; ++i) {
string s1_1 = s1.substr(0, i);
string s2_1 = s2.substr(0, i);
string s1_2 = s1.substr(i, len - i);
string s2_2 = s2.substr(i, len - i);
string s2_3 = s2.substr(len - i, i);
string s2_4 = s2.substr(0, len - i);
if (isScramble(s1_1, s2_1) && isScramble(s1_2, s2_2) ||
isScramble(s1_1, s2_3) && isScramble(s1_2, s2_4)) {
hash[s1 + "#" + s2] = true;
return true;
}
}
hash[s1 + "#" + s2] = false;
return false;
}
};


Longest Common Substring

题目描述:Longest Common Substring

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
/**
* @param A: A string
* @param B: A string
* @return: the length of the longest common substring.
*/
int longestCommonSubstring(string &A, string &B) {
int n = A.length();
int m = B.length();
int ans = 0;
vector<vector<int>> dp(n + 1, vector<int>(m + 1));
for (int i=1; i<=n; ++i) {
for (int j=1; j<=m; ++j) {
dp[i][j] = 0;
if (A[i - 1] == B[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
ans = max(ans, dp[i][j]);
}
}
return ans;
}
};


不同的子序列

题目描述:Distinct Subsequences

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
/*
* @param : A string
* @param : A string
* @return: Count the number of distinct subsequences
*/
int numDistinct(string S, string T) {
int n = S.length();
int m = T.length();
vector<vector<int>> dp(n + 1, vector<int>(m + 1));
for (int i=0; i<=n; ++i) {
dp[i][0] = 1;
}
for (int i=1; i<=n; ++i) {
for (int j=1; j<=m; ++j) {
dp[i][j] = dp[i - 1][j];
if (S[i - 1] == T[j - 1]) {
dp[i][j] += dp[i - 1][j - 1];
}
}
}
return dp[n][m];
}
};


交叉字符串

题目描述:Interleaving String

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
/**
* @param s1: A string
* @param s2: A string
* @param s3: A string
* @return: Determine whether s3 is formed by interleaving of s1 and s2
*/
bool isInterleave(string &s1, string &s2, string &s3) {
if (s1.length() + s2.length() != s3.length()) {
return false;
}
int n = s1.length();
int m = s2.length();
vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));
dp[0][0] = true;
for (int i=1; i<=n; ++i) {
if (s3[i - 1] == s1[i - 1] && dp[i - 1][0]) {
dp[i][0] = true;
}
}
for (int i=1; i<=m; ++i) {
if (s3[i - 1] == s2[i - 1] && dp[0][i - 1]) {
dp[0][i] = true;
}
}
for (int i=1; i<=n; ++i) {
for (int j=1; j<=m; ++j) {
if (s3[i + j - 1] == s1[i - 1] && dp[i - 1][j] ||
s3[i + j - 1] == s2[j - 1] && dp[i][j - 1]) {
dp[i][j] = true;
}
}
}
return dp[n][m];
}
};


合并集

连接图

题目描述:Connecting Graph

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class ConnectingGraph {
public:
vector<int> father;
/*
* @param n: An integer
*/ConnectingGraph(int n) {
father.reserve(n + 1);
for (int i=1; i<=n; ++i) {
father[i] = i;
}
}
/*
* @param a: An integer
* @param b: An integer
* @return: nothing
*/
void connect(int a, int b) {
int root_a = find(a);
int root_b = find(b);
if (root_a != root_b) {
father[root_a] = root_b;
}
}
/*
* @param a: An integer
* @param b: An integer
* @return: A boolean
*/
bool query(int a, int b) {
int root_a = find(a);
int root_b = find(b);
return root_a == root_b;
}
protected:
int find(int x) {
if (father[x] == x) {
return x;
}
return father[x] = find(father[x]);
}
};


连接图II

题目描述:Connecting Graph II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class ConnectingGraph2 {
public:
vector<int> father;
vector<int> count;
/*
* @param n: An integer
*/ConnectingGraph2(int n) {
father.reserve(n + 1);
count.reserve(n + 1);
for (int i=1; i<=n; ++i) {
father[i] = i;
count[i] = 1;
}
}
/*
* @param a: An integer
* @param b: An integer
* @return: nothing
*/
void connect(int a, int b) {
int root_a = find(a);
int root_b = find(b);
if (root_a != root_b) {
father[root_a] = root_b;
count[root_b] += count[root_a];
}
}
/*
* @param a: An integer
* @return: An integer
*/
int query(int a) {
int root_a = find(a);
return count[root_a];
}
protected:
int find(int x) {
if (father[x] == x) {
return x;
}
return father[x] = find(father[x]);
}
};


连接图III

题目描述:Connecting Graph III

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class ConnectingGraph3 {
public:
vector<int> father;
int count;
/*
* @param n: An integer
*/
ConnectingGraph3(int n) {
father.reserve(n + 1);
count = n;
for (int i=1; i<=n; ++i) {
father[i] = i;
}
}
/*
* @param a: An integer
* @param b: An integer
* @return: nothing
*/
void connect(int a, int b) {
int root_a = find(a);
int root_b = find(b);
if (root_a != root_b) {
father[root_a] = root_b;
count--;
}
}
/*
* @return: An integer
*/
int query() {
return count;
}
protected:
int find(int x) {
if (father[x] == x) {
return x;
}
return father[x] = find(father[x]);
}
};


岛屿的个数

题目描述:Number of Islands

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
public:
/**
* @param grid: a boolean 2D matrix
* @return: an integer
*/
bool isValid(vector<vector<bool>> &grid, int x, int y) {
return x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size();
}
int numIslands(vector<vector<bool>> &grid) {
if (grid.size() == 0 || grid[0].size() == 0) {
return 0;
}
int directX[] = {0, 1, 0, -1};
int directY[] = {1, 0, -1, 0};
int m = grid.size();
int n = grid[0].size();
int count = m * n;
vector<int> father(m * n);
for (int i=0; i<m; ++i) {
for (int j=0; j<n; ++j) {
father[i * n + j] = i * n + j;
}
}
for (int i=0; i<m; ++i) {
for (int j=0; j<n; ++j) {
if (grid[i][j]) {
int root1 = find(father, i * n + j);
for (int k=0; k<4; ++k) {
int x = i + directX[k];
int y = j + directY[k];
if (isValid(grid, x, y) && grid[x][y]) {
int root2 = find(father, x * n + y);
if (root1 != root2) {
father[root2] = root1;
count--;
}
}
}
} else {
count--;
}
}
}
return count;
}
int find(vector<int> &father, int x) {
if (father[x] == x) {
return x;
}
return father[x] = find(father, father[x]);
}
};


岛屿的个数II

题目描述:Number of Islands II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
public:
/**
* @param n: An integer
* @param m: An integer
* @param operators: an array of point
* @return: an integer array
*/
vector<int> numIslands2(int n, int m, vector<Point> &operators) {
vector<int> res;
int directX[] = {0, 1, 0, -1};
int directY[] = {1, 0, -1, 0};
int count = 0;
vector<int> father(n * m);
vector<vector<bool>> island(n, vector<bool>(m, false));
for (int i=0; i<n; ++i) {
for (int j=0; j<m; ++j) {
father[i * m + j] = i * m + j;
}
}
for (int i=0; i<operators.size(); ++i) {
Point p = operators[i];
if (island[p.x][p.y]) {
res.push_back(count);
continue;
}
int root1 = find(father, p.x * m + p.y);
island[p.x][p.y] = true;
count++;
for (int j=0; j<4; ++j) {
int x = p.x + directX[j];
int y = p.y + directY[j];
if (x >= 0 && x < n && y >= 0 && y < m && island[x][y]) {
int root2 = find(father, x * m + y);
if (root1 != root2) {
father[root2] = root1;
count--;
}
}
}
res.push_back(count);
}
return res;
}
int find(vector<int> &father, int x) {
if (father[x] == x) {
return x;
}
return father[x] = find(father, father[x]);
}
};


岛屿的个数II

题目描述:Number of Islands II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
public:
/**
* @param n: An integer
* @param m: An integer
* @param operators: an array of point
* @return: an integer array
*/
vector<int> numIslands2(int n, int m, vector<Point> &operators) {
vector<int> res;
int directX[] = {0, 1, 0, -1};
int directY[] = {1, 0, -1, 0};
int count = 0;
vector<int> father(n * m);
vector<vector<bool>> island(n, vector<bool>(m, false));
for (int i=0; i<n; ++i) {
for (int j=0; j<m; ++j) {
father[i * m + j] = i * m + j;
}
}
for (int i=0; i<operators.size(); ++i) {
Point p = operators[i];
if (island[p.x][p.y]) {
res.push_back(count);
continue;
}
int root1 = find(father, p.x * m + p.y);
island[p.x][p.y] = true;
count++;
for (int j=0; j<4; ++j) {
int x = p.x + directX[j];
int y = p.y + directY[j];
if (x >= 0 && x < n && y >= 0 && y < m && island[x][y]) {
int root2 = find(father, x * m + y);
if (root1 != root2) {
father[root2] = root1;
count--;
}
}
}
res.push_back(count);
}
return res;
}
int find(vector<int> &father, int x) {
if (father[x] == x) {
return x;
}
return father[x] = find(father, father[x]);
}
};


图是否是树

题目描述:Graph Valid Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
bool validTree_2(int n, vector<vector<int>> &edges) {
if (edges.size() == 0 && n!=1) {
return false;
}
vector<int> root(n, -1);
for (int i=0; i<edges.size(); ++i) {
int root1 = find(root, edges[i][0]);
int root2 = find(root, edges[i][1]);
if (root1 == root2) {
return false;
}
root[root1] = root2;
}
return edges.size() == n-1;
}
int find(vector<int> &root, int e) {
if (root[e] == -1) {
return e;
}
return root[e] = find(root, root[e]);
}


Trie树

Implement Trie (Prefix Tree)

题目描述:Implement Trie

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
struct TrieNode {
char charact;
map<char, TrieNode*> branch;
bool isWord;
TrieNode(char c) : charact(c) , isWord(false) { };
};
class Trie {
public:
TrieNode *root;
Trie() {
root = new TrieNode(0);
}
/*
* @param word: a word
* @return: nothing
*/
void insert(string &word) {
TrieNode *node = root;
int index = 0;
while (index < word.length()) {
if (node->branch.find(word[index]) == node->branch.end()) {
node->branch[word[index]] = new TrieNode(word[index]);
}
node = node->branch[word[index]];
index++;
}
node->isWord = true;
}
/*
* @param word: A string
* @return: if the word is in the trie.
*/
bool search(string &word) {
TrieNode *node = root;
int index = 0;
while (index < word.length()) {
if (node->branch.find(word[index]) == node->branch.end()) {
return false;
}
node = node->branch[word[index]];
index++;
}
return node->isWord;
}
/*
* @param prefix: A string
* @return: if there is any word in the trie that starts with the given prefix.
*/
bool startsWith(string &prefix) {
TrieNode *node = root;
int index = 0;
while (index < prefix.length()) {
if (node->branch.find(prefix[index]) == node->branch.end()) {
return false;
}
node = node->branch[prefix[index]];
index++;
}
return true;
}
};


Add and Search Word

题目描述:Add and Search Word

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
struct TrieNode {
char c;
map<char, TrieNode*> branch;
bool isWord;
TrieNode(char ch) : c(ch), isWord(false) { }
};
class TrieTree {
public:
TrieTree() {
root = new TrieNode(0);
}
~TrieTree() {
delete root;
}
void insert(string &word) {
TrieNode *node = root;
for (int i=0; i<word.length(); ++i) {
if (node->branch.find(word[i]) == node->branch.end()) {
node->branch[word[i]] = new TrieNode(word[i]);
}
node = node->branch[word[i]];
}
node->isWord = true;
}
bool search(string &word) {
return searchIn(word, 0, root);
}
private:
bool searchIn(string &word, int start, TrieNode *pre) {
if (start >= word.length()) {
return pre->isWord;
}
TrieNode *node = pre;
if (word[start] == '.') {
for (auto b : node->branch) {
if (searchIn(word, start + 1, b.second)) {
return true;
}
}
} else {
if (node->branch.find(word[start]) == node->branch.end()) {
return false;
}
node = node->branch[word[start]];
if (searchIn(word, start + 1, node)) {
return true;
}
}
return false;
}
TrieNode *root;
};
class WordDictionary {
public:
TrieTree root;
/*
* @param word: Adds a word into the data structure.
* @return: nothing
*/
void addWord(string &word) {
root.insert(word);
}
/*
* @param word: A word could contain the dot character '.' to represent any one letter.
* @return: if the word is in the data structure.
*/
bool search(string &word) {
return root.search(word);
}
};


单词搜索 II

题目描述:Word Search II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
struct TrieNode {
string word;
map<char, TrieNode*> branches;
};
class TrieTree {
public:
TrieNode *root;
TrieTree() {
root = new TrieNode();
}
~TrieTree() {
delete root;
}
void insert(string &word) {
TrieNode *node = root;
for (int i=0; i<word.length(); ++i) {
if (node->branches.find(word[i]) == node->branches.end()) {
node->branches[word[i]] = new TrieNode();
}
node = node->branches[word[i]];
}
node->word = word;
}
};
class Solution {
public:
void search(vector<vector<char>> &board, int x, int y, TrieNode *root, vector<string> &res, set<string> &contains) {
if (root->branches.find(board[x][y]) == root->branches.end()) {
return;
}
root = root->branches[board[x][y]];
int directX[] = {0, 1, 0, -1};
int directY[] = {1, 0, -1, 0};
if (!root->word.empty()) {
if (contains.find(root->word) == contains.end()) {
res.push_back(root->word);
contains.insert(root->word);
}
}
char tmp = board[x][y];
board[x][y] = 0;
for (int i=0; i<4; ++i) {
int newX = x + directX[i];
int newY = y + directY[i];
if (isValid(board, newX, newY)) {
search(board, newX, newY, root, res, contains);
}
}
board[x][y] = tmp;
}
bool isValid(vector<vector<char>> &board, int x, int y) {
return x >= 0 && x < board.size() && y >= 0 && y < board[0].size();
}
/**
* @param board: A list of lists of character
* @param words: A list of string
* @return: A list of string
*/
vector<string> wordSearchII(vector<vector<char>> &board, vector<string> &words) {
vector<string> res;
set<string> contains;
TrieTree trie;
for (int i=0; i<words.size(); ++i) {
trie.insert(words[i]);
}
for (int i=0; i<board.size(); ++i) {
for (int j=0; j<board[0].size(); ++j) {
search(board, i, j, trie.root, res, contains);
}
}
return res;
}
};


扫描线

数飞机

题目描述:Number of Airplanes in the Sky

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
* Definition of Interval:
* classs Interval {
* int start, end;
* Interval(int start, int end) {
* this->start = start;
* this->end = end;
* }
* }
*/
class Points {
public:
int time;
int flag;
Points (int time, int flag) {
this->time = time;
this->flag = flag;
}
bool operator<(const Points &other) const {
if (time == other.time) {
return flag < other.flag;
}
return time < other.time;
}
};
class Solution {
public:
/**
* @param airplanes: An interval array
* @return: Count of airplanes are in the sky.
*/
int countOfAirplanes(vector<Interval> &airplanes) {
if (airplanes.empty()) {
return 0;
}
vector<Points> vp;
for (auto i : airplanes) {
vp.push_back(Points(i.start, 1));
vp.push_back(Points(i.end, 0));
}
sort(vp.begin(), vp.end());
int cnt = 0;
int maxAirplane = 0;
for (auto p : vp) {
if (p.flag) {
++cnt;
} else {
--cnt;
}
maxAirplane = max(maxAirplane, cnt);
}
return maxAirplane;
}
};


The Skyline Problem

题目描述:The Skyline Problem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Node {
public:
int x;
int isLeft;
int h;
Node (int _x, int _h, int _isLeft) : x(_x), h(_h), isLeft(_isLeft) { }
bool operator<(const Node &that) const {
if (x == that.x) {
return isLeft < that.isLeft;
}
return x < that.x;
}
};
class Solution {
public:
/**
* @param buildings: A list of lists of integers
* @return: Find the outline of those buildings
*/
vector<vector<int>> buildingOutline(vector<vector<int>> &buildings) {
vector<vector<int>> result;
multiset<int> s;
vector<Node> p;
int n = buildings.size();
for (int i=0; i<n; ++i) {
p.push_back(Node(buildings[i][0], buildings[i][2], 1));
p.push_back(Node(buildings[i][1], buildings[i][2], 0));
}
sort(p.begin(), p.end());
n = 2 * n;
int last = 0;
int size = 0;
for (int i=0; i<n; ++i) {
if (s.empty()) {
last = p[i].x;
}
if (!s.empty() && (*s.rbegin() <= p[i].h) && p[i].x > last) {
vector<int> tmp;
if (size > 0 && (result[size - 1][2] == (*s.rbegin())) && (result[size - 1][1] == last)) {
result[size - 1][1] = p[i].x;
} else {
tmp.push_back(last);
tmp.push_back(p[i].x);
tmp.push_back(*s.rbegin());
result.push_back(tmp);
++size;
}
last = p[i].x;
}
if (p[i].isLeft) {
s.insert(p[i].h);
} else {
s.erase(s.lower_bound(p[i].h));
}
}
return result;
}
};


其他

最多有多少个点在一条直线上

题目描述:Max Points on a Line

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
* Definition for a point.
* struct Point {
* int x;
* int y;
* Point() : x(0), y(0) {}
* Point(int a, int b) : x(a), y(b) {}
* };
*/
class Solution {
public:
/**
* @param points: an array of point
* @return: An integer
*/
int maxPoints(vector<Point> &points) {
if (points.empty()) {
return 0;
}
int count = 0;
for (int i=0; i<points.size(); ++i) {
map<pair<int, int>, int> m;
int res = 0;
int samepoint = 0;
for (int j=i+1; j<points.size(); ++j) {
if (points[i].x == points[j].x && points[i].y == points[j].y) {
samepoint++;
continue;
}
int xdiff = points[i].x - points[j].x;
int ydiff = points[i].y - points[j].y;
int g = gcd(xdiff, ydiff);
xdiff /= g;
ydiff /= g;
res = max(res, ++m[pair<int, int>(xdiff, ydiff)]);
}
count = max(count, res + samepoint + 1);
}
return count;
}
private:
int gcd(int a, int b) {
if (b == 0) {
return a;
}
while (a % b != 0) {
int tmp = b;
b = a % b;
a = tmp;
}
return b;
}
};