「leetcode刷题」两天冲刺挑战(100题)

本文最后更新于:2022年8月17日 上午

​ 时间: 2021-08-23 21:14:55—->2021-08-26 10:43:12

​ 完结撒花

1 | 反转链表

https://leetcode-cn.com/problems/reverse-linked-list/

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head) return head;
ListNode* pre = nullptr, *nex = nullptr;
while (head != nullptr) {
nex = head->next, head->next = pre, pre = head, head = nex;
}
return pre;
}
};

2 | 无重复字符的最长子串

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// set记录字符出现
unordered_set<char> st;
int ans = 0;
for (int r = 0, l = 0; r < s.size(); ++r) {
// 如果发现set中已经含有当前字符
if (st.count(s[r])) {
while (s[r] != s[l]) st.erase(s[l++]); // 这里没必要考虑l和r相遇, 因为移动到r自然就退出了
// 现在 s[r] == s[l]还需要将s[l]删除
st.erase(s[l++]);
}
// 最后将s[r]插入
st.insert(s[r]);
ans = max(ans, r - l + 1);
}
return ans;
}
};

3 | LRU 缓存机制

note:

自己写链表还是太麻烦了

一定要记得将「移动到头部」方法提取出来, 因为在get和put中都需要用, 一共用三次, 而链表的移动一定要考虑清楚, 步骤不要写丢了

https://leetcode-cn.com/problems/lru-cache/

  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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
// LRU缓存
// 需要随机删除链表, 需要用到哈希表(unordered_map)
// 随机删除链表必须使用双向链表:
// 方法1. 自己实现双向链表 方法2. 利用stl中的list
// 考虑使用方法1

struct double_list {
int key, value; // 保存键值对
double_list* next, *prev; // 前驱与后继
double_list(): // 成员初始化表
key(0),
value(0),
prev(nullptr),
next(nullptr) {}
};

class LRUCache {
public:
unordered_map<int, double_list*> hmap; // 记录键与链表结点的对应关系
double_list* head, *tail; // 链表的头尾
int sz; // 当前容量
int thresh; // 最大容量
LRUCache(int capacity): thresh(capacity), sz(0) {
// 虚拟头和虚拟尾
head = new double_list();
tail = new double_list();
head->next = tail, tail->prev = head; // 链接首尾
}

// 抽离出移动到头部这个方法
void add_head (double_list* now) {
// 先删除
if (now->next && now->prev) {
now->next->prev = now->prev;
now->prev->next = now->next;
}
// 再添加
now->next = head->next;
head->next->prev = now;
now->prev = head;
head->next = now;
}

// 作用:
// 如果key存在, 将其移动到链表首部并且返回value
// 如果key不存在, 返回-1
int get(int key) {
if (!hmap.count(key)) {
return -1;
} else {
double_list* now = hmap[key];
add_head(now);
return now->value;
}
}

// 作用:
// 如果key存在, 移动到链表首部并且更新值
// 如果key不存在, 在链表首部插入值并且更新哈希表
void put(int key, int value) {
if (!hmap.count(key)) {
++sz;
double_list* now = new double_list();
// value和key都要加入, 为了方便删除
now->value = value;
now->key = key;
add_head(now);
hmap[key] = now; // 加入到哈希表
// 超过上限, 删除链表尾部
if (sz > thresh) {
--sz;
double_list* pre = tail->prev;
tail->prev = tail->prev->prev;
pre->prev->next = tail;
hmap.erase(pre->key);
delete pre;
}
} else {
double_list* now = hmap[key];
now->value = value; // 更新value
add_head(now);
}
}
};

/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
  1. 使用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
class LRUCache {
public:
int sz; // 上限, 目前大小可以用cache.size()判断
unordered_map<int, list<pair<int, int>>::iterator> hmap;
list<pair<int, int>> cache;

// splice用法:
// void splice( const_iterator pos, list& other, const_iterator it );
// void splice( const_iterator pos, list& other, const_iterator first, const_iterator last);
LRUCache(int capacity): sz(capacity) {}

int get(int key) {
if (hmap.count(key)) {
cache.splice(cache.begin(), cache, hmap[key]);
return hmap[key]->second;
} else {
return -1;
}
}

void put(int key, int value) {
if (!hmap.count(key)) {
cache.emplace_front(key, value); // 在首部添加
hmap[key] = cache.begin();
if (cache.size() > sz) { // 大于了
hmap.erase(cache.back().first);
cache.pop_back();
}
} else {
hmap[key]->second = value;
cache.splice(cache.begin(), cache, hmap[key]);
}
}
};

/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/

4 | 数组中的第K个最大元素

https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

note:

此题考查的点:

  1. 快速排序 (复杂度为O(N)) => 如何证明?
  2. 堆排序 (复杂度O(NlogN))

堆排序写法:

    堆排序 + 删除k次最顶端元素: 
    堆排的方法: 

    1. 从 N / 2开始每次sink建立大顶堆
    2. 删除最顶端元素方法: 将最顶端和最后一个交换后sink一次
    总复杂度: O(nlogn)

快速排序写法

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:
int findKthLargest(vector<int>& nums, int k) {
srand(time(0));
random_shuffle(nums.begin(), nums.end());
int n = nums.size();
return select(nums, 0, n, n - k); // 第k大值是倒数第n - k个
}
int select (vector<int>& nums, int l, int r, int k) {
int idx = partition(nums, l, r); // 分割
if (idx == k) return nums[idx];
return idx < k ? select(nums, idx + 1, r, k) : select(nums, l, idx, k); // 左闭右开
}
int partition(vector<int>& nums, int l, int r) {
int i = l, j = r;
int x = nums[l]; // 哨兵
while (i < j) {
while (j > i && nums[--j] > x);
while (j > i && nums[++i] < x);
swap(nums[i], nums[j]);
}
swap(nums[l], nums[i]);
return i;
}
};

自建大顶堆, k次删除

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
class Solution {
public:
/*
堆排序 + 删除k次最顶端元素:
堆排的方法:
1. 从 N / 2开始每次sink建立大顶堆
2. 删除最顶端元素方法: 将最顶端和最后一个交换后sink一次
总复杂度: O(nlogn)
*/

void sink (vector<int>& x, int k, int n) {
while ((k << 1) <= n) {
int j = k << 1;
if (j < n && x[j] < x[j + 1]) ++j; // 选择叶子中较大者
if (x[k] >= x[j]) break; // 因为sink是自下而上进行的, 因此任何时刻k的儿子们都是大顶堆
swap(x[k], x[j]);
k = j;
}
}

// 建立大顶堆
void build (vector<int>& x, int n) {
for (int k = n >> 1; k >= 1; --k) {
sink(x, k, n);
}
}

// 进行k - 1次`pop`操作, 然后返回堆顶
int select (vector<int>& x, int k, int n) {
k--;
while (k--) {
swap(x[n], x[1]);
x.pop_back();
sink(x, 1, --n); // 将第一个下沉到底部
}
return x[1];
}
int findKthLargest(vector<int>& nums, int k) {
// 就不能从1开始嘛!
nums.insert(nums.begin(), 0);
int n = nums.size() - 1;
// 构造大顶堆
build(nums, n);
// 选择第k大
return select(nums, k, n);
}
};

5 | K 个一组翻转链表

寻觅的最简单的一种写法

变量定义个数: (prev, nex, tail, now)共四个

其中prev和now用于遍历和调换顺序

tail和head用于控制头尾

最后head指向「尾部」! prev指向「头部」! now和tail指向「下一组的头部」

https://leetcode-cn.com/problems/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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if (!head) return head;
ListNode* tail = head;
for (int i = 0; i < k; ++i) {
if (!tail) return head; // 这里不能调换顺序, tail是可以最后一次跑到空的!!
tail = tail->next;
}
ListNode* now = head;
ListNode* prev = tail, *nex = nullptr;
while (now != tail) {
nex = now->next, now->next = prev, prev = now, now = nex;
}
// 目前反转后头部为: prev, 尾部为: head
head->next = reverseKGroup(tail, k);
return prev;
}
};

6 | 排序数组

https://leetcode-cn.com/problems/sort-an-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
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
int l = 0, r = nums.size();
random_shuffle(nums.begin(), nums.end());
quick_sort(nums, l, r);
return nums;
}
void quick_sort(vector<int>& nums, int l, int r) {
if (l >= r) return;
int idx = partition(nums, l, r);
quick_sort(nums, l, idx);
quick_sort(nums, idx + 1, r);
}
int partition (vector<int>& nums, int l, int r) {
int i = l, j = r;
int x = nums[l];
while (i < j) {
while (j > i && nums[--j] > x);
while (j > i && nums[++i] < x);
swap(nums[i], nums[j]);
}
swap(nums[i], nums[l]);
return i;
}
};

归并排序

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:
vector<int> aux; // 辅助数组
// 归并排序
vector<int> sortArray(vector<int>& nums) {
int n = nums.size();
aux = nums;
int l = 0, r = nums.size();
merge_sort(nums, l, r - 1);
return nums;
}
void merge_sort(vector<int>& nums, int l, int r) {
if (l >= r) return;
int mid = l + r >> 1;
// 左半边排序
merge_sort(nums, l, mid);
// 右半边排序
merge_sort(nums, mid + 1, r);
// 归并
merge(nums, l, mid, r);
}
// 将l,r这一段归并
void merge(vector<int>&nums, int l, int mid, int r) {
int p1 = l, p2 = mid + 1, k = l;
while (p1 <= mid && p2 <= r) {
if (nums[p1] < nums[p2]) {
aux[k++] = nums[p1++];
} else {
aux[k++] = nums[p2++];
}
}
// 将剩余部分链接上
while (p1 <= mid) aux[k++] = nums[p1++];
while (p2 <= r) aux[k++] = nums[p2++];
// 将aux复制回nums
for (int i = l; i <= r; ++i) {
nums[i] = aux[i];
}
}

};

堆排序

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:
// 堆排序
// (起点为0) ==> 左边为2 * k + 1, 右边为 2 * k + 2
void sink (vector<int>& nums, int k, int n) {
while (k * 2 + 1 < n) {
int left = k * 2 + 1;
int right = k * 2 + 2;
int choice = left;
if (left < n - 1 && nums[right] > nums[left]) choice = right;
if (nums[choice] <= nums[k]) break;
swap(nums[choice], nums[k]);
k = choice;
}
}

void build(vector<int>& nums, int n) {
for (int i = n / 2; i >= 0; --i) {
sink(nums, i, n);
}
}

vector<int> sortArray(vector<int>& nums) {
// 不从1开始试试
int n = nums.size();
build(nums, n);
// 排序
int k = n - 1;
// 大小为n的数组维护(n - 1)次
for (int i = 0; i < n - 1; ++i) {
swap(nums[0], nums[k]); // 将堆顶和堆尾交换
sink(nums, 0, k--); // 维护堆
}
return nums;
}
};

7 | 两数之和

https://leetcode-cn.com/problems/two-sum/submissions/

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hmap;
int k = 0;
for (auto i : nums) {
if (hmap.count(target - i)) return {k, hmap[target - i]};
else hmap[i] = k++;
}
return {};
}
};

8 | 三数之和

https://leetcode-cn.com/problems/3sum/submissions/

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
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans; // 答案数组
sort(nums.begin(), nums.end());
int n = nums.size();
// 左边
for (int l = 0; l < n - 2; ++l) {
if (l != 0 && nums[l] == nums[l - 1]) continue; // 去重, 这样找到的一定重复(开头相同)
int r = n - 1, k = l + 1; // 内部使用双指针找target即可
int target = -nums[l]; // 加起来 == target
while (k < r) {
int cur = nums[k] + nums[r]; // 加起来的和
// 升序
if (cur > target) {
--r;
} else if (cur < target) {
++k;
} else if (cur == target) {
// 判断右边界是否重复
if (r == n - 1 || nums[r] != nums[r + 1])
ans.push_back({nums[l], nums[k], nums[r]}); // 加入答案
++k, --r; // 放外面
}
}
}
return ans;
}
};

9 | 最大子序和

https://leetcode-cn.com/problems/maximum-subarray/

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int maxSubArray(vector<int>& nums) {
// 子数组(连续)
// t代表的含义是 (以上一位置结尾的「最大子序和」)
int ans = INT_MIN, t = 0;
for (auto i : nums) {
t = max(t + i, i);
ans = max(ans, t);
}
return ans;
}
};

10 | 合并两个有序链表

https://leetcode-cn.com/problems/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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0, l1);
ListNode* now = dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
now->next = l1;
l1 = l1->next;
} else {
now->next = l2;
l2 = l2->next;
}
now = now->next;
}
if (l1) now->next = l1;
else now->next = l2;
return dummy->next;
}
};

11 | 环形链表

只需要判断fast是否到达null即可, 因为fast走的快

https://leetcode-cn.com/problems/linked-list-cycle/submissions/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if (!head) return false;
ListNode* slow = head, *fast = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow) return true;
}
return false;
}
};

12 | 相交链表

因为最后不管是否相交总会走到空, 故无需特判

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/submissions/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* p1 = headA, *p2 = headB;
while (p1 != p2) {
p1 = p1 == nullptr ? headB : p1->next;
p2 = p2 == nullptr ? headA : p2->next;
}
return p1;
}
};

13 | 二叉树的锯齿形层序遍历

https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-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
27
28
29
30
31
32
33
34
35
36
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
// 广搜每层反向就可以了
if (!root) return {};
int flag = true;
vector<vector<int>> ans;
queue<TreeNode*> q;
q.push(root);
while (q.size()) {
flag = !flag;
vector<int> now;
int sz = q.size();
while (sz--) {
auto k = q.front(); q.pop();
now.push_back(k->val);
if (k->left) q.push(k->left);
if (k->right) q.push(k->right);
}
if (flag) reverse(now.begin(), now.end());
ans.push_back(now);
}
return ans;
}
};

14 | 二叉树的层序遍历

上一题的简化版

https://leetcode-cn.com/problems/binary-tree-level-order-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
27
28
29
30
31
32
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if (!root) return {};
vector<vector<int>> ans;
queue<TreeNode*> q;
q.push(root);
while (q.size()) {
vector<int> now;
int sz = q.size();
while (sz--) {
auto k = q.front(); q.pop();
now.push_back(k->val);
if (k->left) q.push(k->left);
if (k->right) q.push(k->right);
}
ans.push_back(now);
}
return ans;
}
};

15 | 买卖股票的最佳时机

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int maxProfit(vector<int>& prices) {
int minn = INT_MAX >> 1;
int ans = 0;
for (auto i : prices) {
ans = max(ans, i - minn);
minn = min(minn, i);
}
return ans;
}
};

16 | 有效的括号

https://leetcode-cn.com/problems/valid-parentheses/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
bool isValid(string s) {
unordered_map<char, char> hmap = {{']', '['}, {')', '('}, {'}', '{'}};
stack<char> stk;
for (auto i : s) {
// 右括号
if (hmap.count(i)) {
if (stk.empty()) return false;
auto now = stk.top(); stk.pop();
if (now != hmap[i]) return false;
} else {
stk.push(i);
}
}
return stk.empty();
}
};

17 | 合并两个有序数组

https://leetcode-cn.com/problems/merge-sorted-array/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int k = m + n - 1; // 指向合并后的尾部
--m, --n; // 指向两个数组最后一个
while (m >= 0 && n >= 0) {
nums1[k--] = nums2[n] > nums1[m] ? nums2[n--] : nums1[m--];
}
// 如果nums2先空, nums1前面本身就是nums1不用管
// 如果nums1先空, 需要把nums2放到nums1前面
while (n >= 0) {
nums1[k--] = nums2[n--];
}
}
};

18 | 字符串相加

https://leetcode-cn.com/problems/add-strings/

模拟竖式加法后逆序

减少特判! 和T37「两数相加」的实现方法基本是一致的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
string addStrings(string nums1, string nums2) {
int carry = 0;
string res;
int p1 = nums1.size() - 1, p2 = nums2.size() - 1;
// 还有加法的三种情况
while (p1 >= 0 || p2 >= 0 || carry) {
int a = 0, b = 0;
if (p1 >= 0) a = nums1[p1--] - '0';
if (p2 >= 0) b = nums2[p2--] - '0';
res += (a + b + carry) % 10 + '0';
carry = (a + b + carry) / 10;
}
// 倒序
reverse(res.begin(), res.end());
return res;
}
};

19 | 二叉树的最近公共祖先

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

  1. 自底向上
  2. 不用担心重复更新res的问题, 因为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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* res;

// 1. 检查是否自己 + 左边 | 右边
// 2. 检查是否 左边 & 右边
bool check (TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root) return false;
// 以左儿子为根的树是否包含 p | q
bool lflag = check(root->left, p, q);
// 以右儿子为根的树是否包含 p | q
bool rflag = check(root->right, p, q);
if (lflag && rflag || (lflag || rflag) && (root == p || root == q)) {
res = root;
return true;
}
return lflag || rflag || root == p || root == q;
}

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
check(root, p, q);
return res;
}
};

20 | 环形链表2

https://leetcode-cn.com/problems/linked-list-cycle-ii/

需要利用的条件:

  1. 快指针走的是满指针2倍速
  2. 快指针比慢指针多走n圈
  3. 然后写出公式, 考虑a和c的关系

对快慢指针进行分析:

当快慢指针相遇时:

快指针走了: a + b + n * circle

慢指针走了: a + b

令 c = circle - b ==> b + c = circle

又已知快指针是满指针的两倍: 即: a + b = n * circle

由 a + b = n * circle 和 b + c = circle

相减得到a - c = (n - 1) * circle

即a - c是circle的整数倍

那么当快慢指针相遇时候, 让一个指针从起点开始和慢指针一起走, 当他走到a时候, 慢指针走了 c + k圈, 最后会在起点相遇

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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
// 本题考查数学知识
// 对快慢指针进行分析:
// 当快慢指针相遇时:
// 快指针走了: a + b + n * circle
// 慢指针走了: a + b
// 令 c = circle - b ==> b + c = circle
// 又已知快指针是满指针的两倍: 即: a + b = n * circle
// 由 a + b = n * circle 和 b + c = circle
// 相减得到a - c = (n - 1) * circle
// 即a - c是circle的整数倍
// 那么当快慢指针相遇时候, 让一个指针从起点开始和慢指针一起走, 当他走到a时候, 慢指针走了 c + k圈, 最后会在起点相遇
ListNode *detectCycle(ListNode *head) {
ListNode* slow = head, *fast = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow) break;
}
if (!fast || !fast->next) return nullptr;
ListNode* p = head;
while (p != slow) {
slow = slow->next;
p = p->next;
}
return slow;
}
};

21 | 搜索旋转排序数组

https://leetcode-cn.com/problems/search-in-rotated-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
class Solution {
public:
int search(vector<int>& nums, int target) {
// 二分的基础上加入分类讨论的思想
int n = nums.size();
int l = 0, r = n - 1;
while (l <= r) {
int mid = l + r >> 1;
if (nums[mid] == target) return mid;
if (nums[mid] >= nums[0]) {
// [0, mid)
if (target >= nums[0] && target < nums[mid]) {
r = mid - 1;
} else {
l = mid + 1;
}
} else {
if (target > nums[mid] && target <= nums[n - 1]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return -1;
}
};

22 | 全排列

https://leetcode-cn.com/problems/permutations/

利用标记数组的写法 (可以保证字典序):

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:
// dfs填充
vector<int> vis;
int n;
vector<vector<int>> ans;

void dfs (int k, vector<int> now, vector<int>& nums) {
if (k == n) {
ans.push_back(now);
return;
}
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
vis[i] = 1;
now.push_back(nums[i]);
dfs(k + 1, now, nums);
now.pop_back();
vis[i] = 0;
}
}
}

vector<vector<int>> permute(vector<int>& nums) {
n = nums.size();
vis.resize(n, 0);
vector<int> now;
dfs(0, now, nums);
return ans;
}
};

利用交换的写法, 减少了空间复杂度:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
// swap的写法
vector<vector<int>> ans;
vector<vector<int>> permute(vector<int>& nums) {
int n = nums.size();
dfs(nums, 0, n);
return ans;
}
void dfs(vector<int>& nums, int now, int n) {
if (now == n) {
ans.push_back(nums);
return;
}
for (int i = now; i < n; ++i) {
swap(nums[now], nums[i]);
dfs(nums, now + 1, n);
swap(nums[now], nums[i]);
}
}
};

23 | 二分查找

https://leetcode-cn.com/problems/binary-search/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int search(vector<int>& nums, int target) {
// 左闭右开
int l = 0, r = nums.size();
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] == target) return mid;
else if (nums[mid] < target) {
l = mid + 1;
} else {
r = mid;
}
}
return -1;
}
};

24 | 螺旋矩阵

https://leetcode-cn.com/problems/spiral-matrix/submissions/

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
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
// 收缩上写下左右边界
if (matrix.empty()) return {};
int n = matrix.size(), m = matrix[0].size();
int left = 0, right = m - 1, top = 0, bottom = n - 1;
vector<int> ans;
while (1) {
for (int i = left; i <= right; ++i) {
ans.push_back(matrix[top][i]);
}
if (++top > bottom) break; // 等于的时候还需要遍历一次bottom所以是 > 时候break
for (int i = top; i <= bottom; ++i) {
ans.push_back(matrix[i][right]);
}
if (--right < left) break;
for (int i = right; i >= left; --i) {
ans.push_back(matrix[bottom][i]);
}
if (--bottom < top) break;
for (int i = bottom; i >= top; --i) {
ans.push_back(matrix[i][left]);
}
if (++left > right) break;
}
return ans;
}
};

25 | 最长回文子串

https://leetcode-cn.com/problems/longest-palindromic-substring/submissions/

方案1: 动态规划 (注意考虑长度为1和长度为2的作为初始化)

初始化: dp[i][i]dp[i][i + 1]

转移: dp[i][j] = dp[i + 1][j - 1] && s[i] == s[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
class Solution {
public:
// 方法1. 动态规划
string longestPalindrome(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int> (n, 0));
// 状态转移方程:
// dp[i][j] 表示 s[i..j]为回文串
// dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j]
// 初始化:
// dp[i][i] = 1; 光这个不行, 相邻的情况无法覆盖到
// dp[i][i + 1] = s[i] == s[i + 1];
int ans = 1, idx = 0; // 记录长度和起始位置
for (int i = 0; i < n; ++i) {
dp[i][i] = 1;
if (i != n - 1 && s[i] == s[i + 1]) {
dp[i][i + 1] = 1;
ans = 2;
idx = i;
}
}
// 递推是从小往大, 所以第一层枚举字符串长度
for (int len = 2; len <= n; ++len) {
// 左
for (int i = 0; i < n; ++i) {
int j = i + len - 1;
if (j >= n) break;
if (dp[i + 1][j - 1] && (s[i] == s[j])) {
dp[i][j] = 1;
if (j - i + 1 > ans) {
ans = j - i + 1;
idx = i;
}
}
}
}
return s.substr(idx, ans);
}
};

方案2. 中心扩展(trick很多, 建议熟记!!)

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:
// 中心扩展
// 非常精妙的check, 同时处理了: {奇数情况, 偶数情况, 越界情况} 并且无需特判
int check (string s, int l, int r) {
while (l >= 0 && r <= s.size() - 1 && s[l] == s[r]) {
--l, ++r;
}
// 结束位置是字符串边界之外的地方
return r - l - 1;
}
string longestPalindrome(string s) {
int start = 0, len = 1;
for (int i = 0; i < s.size(); ++i) {
int now_len = max(check(s, i, i), check(s, i, i + 1));
if (now_len > len) {
// 奇数情况: xxyxx (i = 2, now_len = 5) => start = i - (now_len - 1) / 2;
// 偶数情况: xxyyxx (i = 2, now_len = 6) => start = i - (now_len - 1) / 2;
start = i - (now_len - 1) / 2;
len = now_len;
}
}
return s.substr(start, len);
}
};

26 | 岛屿数量

这里卡了一会, 注意bfs标记的时候要立即标记不要取出队列以后再标记

https://leetcode-cn.com/problems/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

class Solution {
public:
// 方法: 典型BFS计数
vector<int> dir = {-1, 0, 1, 0, -1};
void bfs (int i, int j, vector<vector<char>>& grid) {
queue<pair<int, int>> q;
q.emplace(i, j);
grid[i][j] = '3';
while (q.size()) {
auto [x, y] = q.front();
q.pop();
for (int k = 0; k < 4; ++k) {
int nx = x + dir[k], ny = y + dir[k + 1];
if (nx < 0 || nx >= grid.size() || ny < 0 || ny >= grid[0].size() || grid[nx][ny] != '1') continue;
if (grid[nx][ny] == '1') {
grid[nx][ny] = '3';
q.emplace(nx, ny);
}
}
}
};
int numIslands(vector<vector<char>>& grid) {
int ans = 0;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j] == '1') {
++ans;
bfs(i, j, grid);
}
}
}
return ans;
}
};

27 | 接雨水

https://leetcode-cn.com/problems/trapping-rain-water/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
// 双指针保存左右最大值, 不断更新
int trap(vector<int>& height) {
int n = height.size();
int leftmax = height[0], rightmax = height[n - 1];
int l = 0, r = n - 1;
int ans = 0;
while (l <= r) {
//可以接两边 最高的的更小值 那么多水
if (leftmax < rightmax) {
ans += max(leftmax - height[l], 0);
leftmax = max(leftmax, height[l++]);
} else {
ans += max(rightmax - height[r], 0);
rightmax = max(rightmax, height[r--]);
}
}
return ans;
}
};

28 | 最长上升子序列

https://leetcode-cn.com/problems/longest-increasing-subsequence/submissions/

  1. 动态规划解法:
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:
// 这题我可太熟了
// 1. 动态规划 O(n ^ 2)
// 2. 贪心 O(nlogn)
// 动态规划解法
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1);
// dp[i] = max(dp[i], dp[j] + 1);
int ans = 1;
for (int i = 1; i < n; ++i) {
for (int j = i - 1; j >= 0; --j) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
ans = max(ans, dp[i]);
}
}
}
return ans;
}
};
  1. 贪心解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
// 这题我可太熟了
// 1. 动态规划 O(n ^ 2)
// 2. 贪心 O(nlogn)
// 贪心解法
int lengthOfLIS(vector<int>& nums) {
vector<int> res;
for (auto i : nums) {
if (res.empty() || i > res.back()) res.push_back(i);
else {
auto it = lower_bound(res.begin(), res.end(), i);
*it = i;
}
}
return res.size();
}
};

29 | 反转链表2

所有链表反转类的题目基本类似

https://leetcode-cn.com/problems/reverse-linked-list-ii/submissions/

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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
if (!head) return head;
ListNode* dummy = new ListNode(0, head);
ListNode* slow = dummy, *fast = dummy;
for (int i = 0; i < right - left + 1; ++i) {
fast = fast->next;
}
for (int i = 1; i < left; ++i) {
slow = slow->next;
fast = fast->next;
}
ListNode* tail = fast->next, *before = slow;
ListNode* prev = tail, *nex = nullptr;
slow = slow->next;
while (slow != tail) {
nex = slow->next, slow->next = prev, prev = slow, slow = nex;
}
before->next = prev;
return dummy->next;
}
};

30 | 用栈实现队列

核心: 仅当有peek操作并且stk2为空的时候才将stk1中的内容放入stk2中

https://leetcode-cn.com/problems/implement-queue-using-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
42
43
44
45
46
class MyQueue {
private:
stack<int> stk1, stk2;
public:
/** Initialize your data structure here. */
// 核心思想: 仅当有peek操作并且stk2为空的时候才将stk1中的内容放入stk2中
MyQueue() {

}

/** Push element x to the back of queue. */
void push(int x) {
stk1.push(x);
}

/** Removes the element from in front of queue and returns that element. */
int pop() {
int x = peek();
stk2.pop();
return x;
}

/** Get the front element. */
int peek() {
if (stk2.size()) return stk2.top();
while (stk1.size()) {
stk2.push(stk1.top());
stk1.pop();
}
return stk2.top();
}

/** Returns whether the queue is empty. */
bool empty() {
return stk1.empty() && stk2.empty();
}
};

/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/

31 | 二叉树的中序遍历

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/

迭代写法 (morris暂时抛弃)

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> stk;
while (root || stk.size()) {
while (root) {
stk.push(root);
root = root->left;
}
root = stk.top(); stk.pop();
ans.push_back(root->val);
root = root->right;
}
return ans;
}
};

32 | 二叉树的右视图

bfs层序, 每次保存最后一个结点

https://leetcode-cn.com/problems/binary-tree-right-side-view/submissions/

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
// 利用bfs每次保存最后一个结点
vector<int> ans;
if (!root) return ans;
queue<TreeNode*> q;
q.push(root);
while (q.size()) {
int sz = q.size();
TreeNode* t = nullptr;
for (int i = 0; i < sz; ++i) {
auto now = q.front();
q.pop();
t = now;
if (now->left) q.push(now->left);
if (now->right) q.push(now->right);
}
ans.push_back(t->val);
}
return ans;
}
};

33 | 爬楼梯

基本递推

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int climbStairs(int n) {
vector<int> dp(n + 1, 0);
dp[0] = 1, dp[1] = 1;
for (int i = 2; i <= n; ++i) {
dp[i] += dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};

优化空间

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int climbStairs(int n) {
int a = 1, b = 1;
int ans = 1;
for (int i = 2; i <= n; ++i) {
ans = a + b;
a = b;
b = ans;
}
return ans;
}
};

34 | 合并k个排序链表

https://leetcode-cn.com/problems/merge-k-sorted-lists/

归并排序优化空间

次数没变(k - 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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
int n = lists.size();
return merge_list(lists, 0, n - 1);
}
ListNode* merge_list(vector<ListNode*>& lists, int l, int r) {
if (l > r) return nullptr;
if (l == r) return lists[r];
int mid = l + r >> 1;
ListNode* l1 = merge_list(lists, l, mid);
ListNode* l2 = merge_list(lists, mid + 1, r);
return merge(l1, l2);
}
ListNode* merge(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0, nullptr);
ListNode* now = dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
now->next = l1;
l1 = l1->next;
} else {
now->next = l2;
l2 = l2->next;
}
now = now->next;
}
if (l1) now->next = l1;
if (l2) now->next = l2;
return dummy->next;
}

};

优先队列写法

(不要一次性保存所有结点, 可以优化空间复杂度为O(k))

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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
// 优先队列的写法
priority_queue<pair<int, ListNode*>> q;
for (auto i : lists) {
if (i)
q.emplace(-i->val, i); // 小的在上
}
ListNode* dummy = new ListNode(0, nullptr);
ListNode* tail = dummy;
while (q.size()) {
auto [v, now] = q.top(); q.pop();
tail->next = now;
tail = tail->next;
if (now->next) q.emplace(-now->next->val, now->next);
}
return dummy->next;
}
};

35 | 链表中倒数第k个节点

https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode* slow = head, *fast = head;
for (int i = 0; i < k; ++i) fast = fast->next;
while (fast) {
fast = fast->next, slow = slow->next;
}
return slow;
}
};

36 | x的平方根

https://leetcode-cn.com/problems/sqrtx/submissions/

二分查找

注意爆int的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
// 二分
int mySqrt(int x) {
long long l = 0, r = (long long)x + 1;
while (l < r) {
long long mid = (l + r) >> 1;
if (mid * mid <= x) {
l = mid + 1;
} else {
r = mid;
}
}
return r - 1;
}
};

37 | 两数相加

https://leetcode-cn.com/problems/add-two-numbers/

减少特判! 和T18「字符串相加」的实现方法基本是一致的。

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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0, nullptr);
ListNode* now = dummy;
int carry = 0;
while (l1 || l2 || carry) {
int a = 0, b = 0;
if (l1) {
a += l1->val, l1 = l1->next;
}
if (l2) {
b += l2->val, l2 = l2->next;
}
int res = a + b + carry;
carry = res / 10;
ListNode* new_node = new ListNode(res % 10, nullptr);
now->next = new_node;
now = now->next;
}
return dummy->next;
}
};

38 | 删除链表的倒数第 N 个结点

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
// 快慢指针的基本用法
ListNode* dummy = new ListNode(0, head);
ListNode *slow = dummy, *fast = dummy;
for (int i = 0; i < n; ++i) {
fast = fast->next;
}
while (fast->next) {
fast = fast->next, slow = slow->next;
}
// 删除slow->next
slow->next = slow->next->next;
return dummy->next;
}
};

39 | 字符串转整数

https://leetcode-cn.com/problems/string-to-integer-atoi/

小细节比较多

  1. 前导0
  2. 正负号
  3. 忽略其他部分
  4. 判断是否溢出 (简便方法直接上long long)
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:
int myAtoi(string s) {
int p = 0, len = s.size();
long long ans = 0;
// 去除前导0
while (p < len && s[p] == ' ') ++p;
if (p >= len) return 0; // ?有这种情况吗
// 判断正负号
bool neg = false;
if (s[p] == '-') neg = true, ++p;
else if (s[p] == '+') ++p;
// 处理数字部分, 注意忽略其他部分
while (p < len && s[p] >= '0' && s[p] <= '9') {
long long cur = s[p++] - '0'; // 当前数位
if (neg) cur = -cur;
ans = ans * 10 + cur;
if (ans > INT_MAX) return INT_MAX;
if (ans < INT_MIN) return INT_MIN;
}
return static_cast<int>(ans);
}
};

40 | 重排链表

https://leetcode-cn.com/problems/reorder-list/

本题有两种做法:

  1. 双端队列
  2. 原地

双端队列很简单, 这里只记录原地的写法:

  1. 快慢指针找到链表中点将链表分开
  2. 反转后面的链表
  3. 按顺序合并链表

坑点:

  1. 快慢指针奇偶考虑清楚
  2. 分开后记得将l1末尾指向null
  3. 按顺序合并链表考虑l1和l2长度相等, 或者l1长度比l2多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
69
70
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
void reorderList(ListNode* head) {
// 这题可以原地做吗??
// 不用原地的方法很简单, 就是压到deque中就可以
// 可以寻找中点, 然后左右半边合并?
// 考虑下奇数和偶数的情况:
// 奇数 1->2->3 ==> 1->2 和 3
// 偶数 1->2->3->4 ==> 1->2 和 3->4 (3->4逆序变为4->3)
// 即奇数左半边比右半边多一个
if (!head) return;
ListNode* l1 = head;
ListNode* mid = split_list(head);
ListNode* l2 = mid->next;
mid->next = nullptr;
// cout << l1->val << ' ' << l2->val << endl;
l2 = reverse_list(l2);
// cout << l2->val << endl;
merge(l1, l2);
}

// return: 切断后第二个链表的头结点
ListNode* split_list(ListNode* head) {
ListNode* slow = head, *fast = head;
while (fast->next && fast->next->next) {
fast = fast->next->next;
slow = slow->next;
}
return slow;
}

// return: 反转后链表的头节点
ListNode* reverse_list(ListNode* head) {
// 反转链表
if (!head) return head;
ListNode* pre = nullptr, *nex;
while (head != nullptr) {
nex = head->next, head->next = pre, pre = head, head = nex;
}
return pre;
}

// return: 按顺序合并的两个链表
ListNode* merge(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0, nullptr);
ListNode* cur = dummy;
// l1的长度 == l2 / l2 + 1
while (l1 && l2) {
cur->next = l1;
l1 = l1->next;
cur = cur->next;
cur->next = l2;
l2 = l2->next;
cur = cur->next;
}
// 考虑到l1可能剩一个, 得接上
if (l1) cur->next = l1;
return dummy->next;
}
};

41 | 合并区间

https://leetcode-cn.com/problems/merge-intervals/submissions/

画个数组想想就出来了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
int n = intervals.size();
sort(intervals.begin(), intervals.end());
vector<vector<int>> ans;
int left = intervals[0][0], right = intervals[0][1];
for (auto inter : intervals) {
int l = inter[0], r = inter[1];
if (right < l) {
ans.push_back({left, right});
left = inter[0], right = inter[1];
} else {
right = max(right, r);
}
}
ans.push_back({left, right}); // 最后多push一次
return ans;
}
};

42 | 二叉树的最大深度

https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode* root) {
if (!root) return 0;
return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
};

43 | 反转字符串里的单词

https://leetcode-cn.com/problems/reverse-words-in-a-string/

非O(1)写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
// 非O(1)写法
string reverseWords(string s) {
stringstream ss(s);
vector<string> ans;
string x;
while (ss >> x) {
ans.push_back(x);
}
string res = "";
reverse(ans.begin(), ans.end());
for (auto i : ans) {
res += i + " ";
}
res.pop_back(); // 去除最后空格
return res;
}
};

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
class Solution {
public:
string reverseWords(string s) {
// O(1)解法
// 思路: 首先反转整个字符串, 然后指针搞搞搞反转每一个空格分割的单词
// 由于包含多个空格, 故需要用一个写指针
int n = s.size();
reverse(s.begin(), s.end());
int p = 0;
for (int l = 0; l < n; ++l) {
if (s[l] != ' ') {
if (p != 0) s[p++] = ' ';
int r = l;
while (r < n && s[r] != ' ') s[p++] = s[r++];
int len = r - l;
reverse(s.begin() + p - len, s.begin() + p);
l = r;
}
}
s.erase(s.begin() + p, s.end()); // 删除后面的一众空格
return s;
}
};

44 | 平衡二叉树

https://leetcode-cn.com/problems/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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool flag = true;
bool isBalanced(TreeNode* root) {
// 基本思路:
// 暴力的解法是对每个结点求深度, 但是没必要, 重复求了很多次
// 应该自底向上
// 判断自己是否是平衡二叉树, 再向上返回高度
check(root);
return flag;
}
int check (TreeNode* root) {
if (!root) return 0;
int right_depth = check(root->right), left_depth = check(root->left);
if (!flag) return -1; // 剪枝
if (abs(right_depth - left_depth) > 1) flag = false;
return max(left_depth, right_depth) + 1;
}
};

45 | 二叉树的前序遍历

一样只写递归版本

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> stk;
vector<int> ans;
while (root || stk.size()) {
while (root) {
stk.push(root);
ans.push_back(root->val);
root = root->left;
}
root = stk.top();
stk.pop();
root = root->right;
}
return ans;
}
};

46 | 二叉树中的最大路径和

https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/submissions/

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int ans = INT_MIN; // 全局ans
int maxPathSum(TreeNode* root) {
// 感觉和那个平衡二叉树的题很像
// 递归的时候可以自底向下, 维护一个全局的答案, 再分别向上更新自己的值
check(root);
return ans;
}
int check(TreeNode* root) {
if (!root) return 0;
int l = check(root->left);
int r = check(root->right);
// l, r可以选或者不选
l = max(0, l), r = max(0, r);
ans = max(ans, l + r + root->val);
// 向上返回左边或右边 + 当前节点的最大路径
return max(l, r) + root->val;
}
};

47 | 路径总和2

https://leetcode-cn.com/problems/path-sum-ii/submissions/

减弱版为:「64. 路经总和」(不需要记录路径)

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> ans;
int target;

void dfs(TreeNode* root, vector<int>& cur, int sum) {
if (!root) return;
cur.push_back(root->val);
sum += root->val;
// 叶子
if (!root->right && !root->left && target == sum) {
ans.push_back(cur);
}
dfs(root->left, cur, sum);
dfs(root->right, cur, sum);
cur.pop_back(); // 回来的时候pop掉
}

vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
// 基本的深搜
target = targetSum;
vector<int> now;
dfs(root, now, 0);
return ans;
}
};

48 | 下一个排列

https://leetcode-cn.com/problems/next-permutation/submissions/

(官方题解好像要短点, 思路是一样的)

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:
void nextPermutation(vector<int>& nums) {
// 这题其实是一个思维题
// 1. 从后向前找到 nums[k] < nums[k + 1], k就是要处理的标志点
// 2. 在[k, n - 1] (一个降序排列) 中找到大于nums[k]的最小值与k交换
// 3. 将[k + 1, n - 1] 这一段反序
int n = nums.size();
bool flag = false;
for (int k = n - 2; k >= 0; --k) {
if (nums[k] < nums[k + 1]) {
flag = true;
for (int j = n - 1; j > k; --j) {
if (nums[j] > nums[k]) {
swap(nums[j], nums[k]);
reverse(nums.begin() + k + 1, nums.end());
break;
}
}
}
if (flag) return;
}
if (!flag) reverse(nums.begin(), nums.end());
}
};

49 | 从前序与中序遍历序列构造二叉树

https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-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
27
28
29
30
31
32
33
34
35
36
37
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// 后序 / 前序 指示根节点
// 中序用于分治造树
// 1. 哈希表将中序的结点和序号一一对应方便分治 (inorder中)
// 2. 全局指针指示目前处理到的根节点 (preorder中)
int ptr = 0, n = 0;
unordered_map<int, int> idx;

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
n = preorder.size();
for (int i = 0; i < n; ++i) {
idx[inorder[i]] = i;
}
return build(0, n - 1, preorder, inorder);
}
TreeNode* build (int left, int right, vector<int>& preorder, vector<int>& inorder) {
if (left > right) return nullptr;
int now = preorder[ptr++]; // 当前根结点值
TreeNode* node = new TreeNode(now);
int mid = idx[now];
node->left = build(left, mid - 1, preorder, inorder);
node->right = build(mid + 1, right, preorder, inorder);
return node;
}
};

50 | 排序链表

自顶向下归并排序

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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
// 归并排序
if (!head) return head;
ListNode* t = head;
while (t->next) t = t->next;
return sortList(head, t); // 头, 尾
}
// 找到中点 (偶数在中左, 奇数在中)
ListNode* find_mid (ListNode* head) {
ListNode* slow = head, *fast = head;
while (fast->next && fast->next->next) {
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
ListNode* sortList(ListNode* head, ListNode* tail) {
if (head == tail) return head;
ListNode* mid = find_mid(head);
ListNode* nex = mid->next;
mid->next = nullptr; // 置空很重要
return merge(sortList(head, mid), sortList(nex, tail));
}
ListNode* merge(ListNode *l1, ListNode* l2) {
ListNode* dummy = new ListNode(0, nullptr), *now = dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
now->next = l1;
l1 = l1->next;
} else {
now->next = l2;
l2 = l2->next;
}
now = now->next;
}
if (l1) now->next = l1;
if (l2) now->next = l2;
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
// 尝试用自底向上归并
ListNode* sortList(ListNode* head) {
if (!head) return head;
int length = 0;
// 统计长度
ListNode* tmp = head;
while (tmp) tmp = tmp->next, ++length;
// 自底向上, 从长度1开始, 每次 x2开始归并
ListNode* dummy = new ListNode(0, head); // 第一次指向head
for (int len = 1; len < length; len <<= 1) {
ListNode* prev = dummy, *now = dummy->next; // now指向归并后第一个
while (now) {
ListNode* left = now;
for (int i = 0; i < len - 1 && now->next; ++i) {
now = now->next;
}
ListNode* right = now->next;
now->next = nullptr;
// 第一段就是left开头的
now = right;
// 再获取第二段, 方法一致
for (int i = 0; i < len - 1 && now && now->next; ++i) {
now = now->next;
}
// 剩余的链表取决于now->next现在是否指向空
ListNode* remain = now ? now->next : nullptr;
if (now) now->next = nullptr;
// 将left和right这两个链表归并了
prev->next = merge(left, right);
while (prev->next) prev = prev->next; // 将prev移动到归并后的链表末尾
now = remain;
}
}
return dummy->next;
}
ListNode* merge(ListNode *l1, ListNode* l2) {
ListNode* dummy = new ListNode(0, nullptr), *now = dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
now->next = l1;
l1 = l1->next;
} else {
now->next = l2;
l2 = l2->next;
}
now = now->next;
}
if (l1) now->next = l1;
if (l2) now->next = l2;
return dummy->next;
}
};

51 | 求根节点到叶节点数字之和

https://leetcode-cn.com/problems/sum-root-to-leaf-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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int sum = 0;
int sumNumbers(TreeNode* root) {
dfs(root, 0);
return sum;
}
// 自上而下dfs
void dfs(TreeNode* root, int now) {
if (!root) return;
now = now * 10 + root->val;
if (!root->left && !root->right) {
sum += now;
}
dfs(root->left, now);
dfs(root->right, now);
}
};

52 | 用 Rand7() 实现 Rand10()

https://leetcode-cn.com/problems/implement-rand10-using-rand7/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7

class Solution {
public:
// 拒绝采样思路:
// rand7()生成 1~7 之间的随机数
// 如果使用(rand7() - 1) * 7生成的就是 0, 7, 14, 21, 28, 35, 42 这些数
// 如果使用(rand7() - 1) * 7 + rand7()生成得就是 1~49 得随机数
// 取1~40之间的40个数, (x - 1) % 10 + 1就是1 ~ 10的随机数
int rand10() {
int res;
do {
res = (rand7() - 1) * 7 + rand7();
} while (res > 40);
return (res - 1) % 10 + 1;
}
};

53 | 编辑距离

https://leetcode-cn.com/problems/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
class Solution {
public:
// 首先想到的思路: 暴力检查所有操作, 取最小 ----> 不现实
// 观察发现对word1和word2的操作本质上是相同的
// 插入和删除互为相反, 而替换是同质的
// 故只需要将操作转化为对word1的操作就可以了
// 对于两个字符串, 如最长公共子串这样的问题, 考虑使用dp[i][j], 每一维度分别对应一个字符串来进行比较
// 如果用dp, 如何定义状态转移?
// 假设dp[i][j]表示word1的前i - 1个字符和word2的前j - 1个字符的编辑距离

// 状态转移:
// 如果word1[i - 1] == word2[j - 1] ==> dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1]) + 1)
// 如果word1[i - 1] != wrod2[j - 1] ==> dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1

// 可以归到上面
// 如果word1[i - 1] && (j >= word2.size()) ==> dp[i][word2.size() - 1] = dp[i - 1][word2.size() - 1] + 1
// 如果(i >= word1.size()) && word2[j - 1] ==> dp[word1.size() - 1][j] = dp[word1.size() - 1][j - 1] + 1

// 初始化:
// 对空串情况进行初始化

int minDistance(string word1, string word2) {
int n = word1.size(), m = word2.size();
vector<vector<int>> dp(n + 1, vector<int> (m + 1, 0));
for (int i = 0; i <= n; ++i) dp[i][0] = i;
for (int j = 0; j <= m; ++j) dp[0][j] = j;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
int a = dp[i - 1][j - 1], b = dp[i - 1][j], c = dp[i][j - 1];
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = min(a, min(b, c) + 1);
} else {
dp[i][j] = min(a, min(b, c)) + 1;
}
}
}
return dp[n][m];
}
};

54 | 寻找两个正序数组的中位数

这题起码再做3遍

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
class Solution {
public:
// 勇敢牛牛, 不怕困难, 抄一遍, 记得牢
int find_kth_element (vector<int>& nums1, vector<int>& nums2, int k) {
int n = nums1.size(), m = nums2.size();
// 两个数组分别取 nums[k / 2 - 1]的最小值, 我们要找第k小的, 而二者较小值之前最多只有 2 * (k / 2 - 1) = k - 2个比它小的
// 指示查找边界
int idx1 = 0, idx2 = 0;
while (1) {
// 边界条件1. 其中一个数组为空
if (idx1 == n) {
return nums2[idx2 + k - 1];
}
if (idx2 == m) {
return nums1[idx1 + k - 1];
}
// 边界条件2. k就是1, 那么直接返回更小的那一个
if (k == 1) {
return min(nums1[idx1], nums2[idx2]);
}
// 防止越界
int new_idx1 = min(idx1 + k / 2 - 1, n - 1);
int new_idx2 = min(idx2 + k / 2 - 1, m - 1);
int p1 = nums1[new_idx1], p2 = nums2[new_idx2];
if (p1 <= p2) {
k -= new_idx1 - idx1 + 1; // 减去排除数的个数
idx1 = new_idx1 + 1;
} else {
k -= new_idx2 - idx2 + 1;
idx2 = new_idx2 + 1;
}
}
}

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int len = nums1.size() + nums2.size();
// 如果是奇数, 找第 len / 2 + 1小的
// 如果是偶数, 找第 len / 2和len / 2 + 1小的 相加 / 2
if (len & 1) {
return static_cast<double> (find_kth_element(nums1, nums2, len / 2 + 1));
} else {
double left = static_cast<double> (find_kth_element(nums1, nums2, len / 2 + 1));
double right = static_cast<double> (find_kth_element(nums1, nums2, len / 2));
return (left + right) / 2.000;
}
}
};

55 | 最小覆盖子串

经典滑动窗口, 注意两个哈希表的用途

这里c在第一次找到后就不变了, 之后一直靠j维护count和source的冗余关系来维持窗口

https://leetcode-cn.com/problems/minimum-window-substring/submissions/

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
class Solution {
public:
// 滑窗吧..
// 用哈希表记录字符出现情况
unordered_map<char, int> count, source; // 一个是当前动态的, 一个是统计静态的

string minWindow(string s, string t) {
// 统计t的字符数
for (auto i : t) source[i]++;
string ans;
int c = 0; // 统计有多少个字符
// i, j分别为右, 左指针
for (int i = 0, j = 0; i < s.size(); ++i) {
++count[s[i]];
if (count[s[i]] <= source[s[i]]) c++; // 统计包含的个数
while (j <= i && count[s[j]] > source[s[j]]) --count[s[j++]]; // 收缩左边界, 这时候c的值不会减, 因为收缩的都是多余的
// 统计个数刚好为
if (c == t.size()) {
int len = i - j + 1;
if (ans.empty() || len < ans.size()) {
ans = s.substr(j, len);
}
}
}
return ans;
}
};

56 | 删除链表中的重复元素2

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/

是「74 | 删除排序链表中的重复元素」的加强版

用一个指在now前面的指针跑重复元素即可

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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (!head) return head;
ListNode* dummy = new ListNode(0, head);
ListNode* now = dummy;
while (now->next && now->next->next) {
ListNode* p = now->next;
if (p->val == p->next->val) {
while (p->next && p->val == p->next->val) p = p->next;
now->next = p->next;
} else {
now = now->next;
}
}
return dummy->next;
}
};

57 | 缺失的第一个正数

https://leetcode-cn.com/problems/first-missing-positive/

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:
// 常数级别额外空间..
// 首先
// 性质1. 最小正整数不会超过 nums.size() ==> 要在nums数组里一通操作
// 如果额外空间为N, 可以对这个空间进行标记, 然后遍历的第一个未标记就是答案
// 那么可以考虑将标记标在原数组上
// 但是如果进行了标记, 那么数就被覆盖了, 答案会不对
// 如何进行标记还保留原始数据?
// 考虑到我们用到的数是(0, 正无穷], 那么将数据标记为负数不就可以保留数据并且标记两个效果吗
// 需要考虑一个特殊情况: 如果一个数本来就是负数, 那么标记会将它变为正数, 但实际上它不应该被包含, 特判一下? 不可, 需要预处理
// 为了防止重复标记, 标记的时候需要用绝对值
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
// 第一次遍历预处理负数
for (auto& i : nums) {
if (i <= 0) i = n + 1;
}
// 第二遍
for (auto& i : nums) {
int k = abs(i);
if (k <= n) nums[k - 1] = -abs(nums[k - 1]);
}
// 求答案
for (int i = 0; i < n; ++i) {
if (nums[i] > 0) return i + 1;
}
return n + 1;
}
};

58 | 滑动窗口最大值

https://leetcode-cn.com/problems/sliding-window-maximum/submissions/

单调队列 => 双端队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
// 用双端队列维护一个单调递减
deque<int> q;
vector<int> ans;
for (int i = 0; i < nums.size(); ++i) {
// 先弹
while (i - k + 1 >= 0 && q.size() && q.front() < i - k + 1) {
q.pop_front();
}
// 再压
while (q.size() && nums[i] > nums[q.back()]) q.pop_back();
q.push_back(i);
// 返回队列首部就是目前的最大值
if (i >= k - 1) ans.push_back(nums[q.front()]);
}
return ans;
}
};

59 | 二叉树的直径

https://leetcode-cn.com/problems/diameter-of-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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int ans = 0;
int diameterOfBinaryTree(TreeNode* root) {
dfs(root);
return ans;
}
int dfs (TreeNode* root) {
if (!root) return 0;
int l = dfs(root->left), r = dfs(root->right);
ans = max(ans, l + r);
return max(l, r) + 1; // 向上返回的是深度
}
};

60 | 最小栈

两个栈, 保存最小值的栈「同步更新」

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 {
public:
/** initialize your data structure here. */
// 直接两个栈
stack<int> stk, min_stk;
MinStack() {

}

void push(int val) {
stk.push(val);
if (min_stk.empty() || val < min_stk.top()) min_stk.push(val);
else min_stk.push(min_stk.top());
}

void pop() {
stk.pop();
min_stk.pop();
}

int top() {
return stk.top();
}

int getMin() {
return min_stk.top();
}
};

/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/

61 | 最长重复子数组

https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
static const int N = 1005;
int dp[N][N];
// 复杂度O(N^2)
int findLength(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size(), m = nums2.size();
// dp[i][j]表示以i - 1, j - 1结尾的最长公共子数组长度
int ans = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = max(dp[i - 1][j - 1] + 1, dp[i][j]);
ans = max(ans, dp[i][j]);
}
}
}
return 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
32
33
class Solution {
public:
// 滑动窗口解法

int count (vector<int>& nums1, vector<int>& nums2, int offset1, int offset2, int len) {
int cnt = 0, ans = 0;
for (int i = 0; i < len; ++i) {
if (nums1[offset1 + i] == nums2[offset2 + i]) {
++cnt;
}
else {
cnt = 0;
}
ans = max(ans, cnt);
}
return ans;
}

int findLength(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size(), m = nums2.size();
int ans = 0;
// nums2相对于nums1偏移量
for (int i = 0; i < n; ++i) {
int len = min(n - i, m);
ans = max(ans, count(nums1, nums2, i, 0, len));
}
for (int i = 0; i < m; ++i) {
int len = min(m - i, n);
ans = max(ans, count(nums1, nums2, 0, i, len));
}
return ans;
}
};

62 | 最长公共子序列

https://leetcode-cn.com/problems/longest-common-subsequence/

动态规划, 注意子序列和子数组不同

子数组的dp[i][j]表示的是以i, j结尾的

子序列的dp[i][j]表示的是前i个, 前j个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
static const int N = 1005;
int dp[N][N];
int longestCommonSubsequence(string s1, string s2) {
int n = s1.size(), m = s2.size();
// dp[i][j]表示s1前i个字符和s2前j个字符的最长公共子序列
// state transition: --> dp[i][j] = max(max(dp[i - 1][j], dp[i - 1][j]), s1[i] == s2[j] ? dp[i - 1][j - 1] + 1, dp[i - 1][j - 1]);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
if (s1[i - 1] == s2[j - 1]) dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
}
}
return dp[n][m];
}
};

63 | 回文链表

https://leetcode-cn.com/problems/palindrome-linked-list/

  1. 快慢指针找中点
  2. 反转后面链表
  3. 挨个比对(以后面链表为边界, 前面长度可能会比后面多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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
// 找中点, 切断, 反向, 比对
if (!head) return false;
ListNode* slow = head, *fast = head;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* head2 = slow->next;
slow->next = nullptr;
// cout << head2->val << endl;
auto reverse_list = [](ListNode* h) {
ListNode* nex = nullptr, *prev = nullptr;
while (h) {
nex = h->next, h->next = prev, prev = h, h = nex;
}
return prev;
};
head2 = reverse_list(head2);
while (head2) {
if (head->val != head2->val) return false;
head = head->next, head2 = head2->next;
}
return true;
}
};

64 | 路经总和

https://leetcode-cn.com/problems/path-sum/

加强版为「47. 路经总和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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// 为什么我感觉昨天做过啊?
// 好家伙, 做了加强版
bool flag = false;
int tar;
void dfs(TreeNode* root, int sum) {
if (!root) return;
sum += root->val;
if (!root->left && !root->right) {
if (sum == tar) {
flag = true;
}
return;
}
dfs(root->left, sum), dfs(root->right, sum);
}

bool hasPathSum(TreeNode* root, int targetSum) {
tar = targetSum;
dfs(root, 0);
return flag;
}
};

65 | 多数元素

https://leetcode-cn.com/problems/majority-element/submissions/

摩尔投票法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int majorityElement(vector<int>& nums) {
int candidate = 3;
int count = 0;
for (int num : nums) {
if (num == candidate)
++count;
else if (--count < 0) {
candidate = num;
count = 1;
}
}
return candidate;
}
};

66 | 验证二叉搜索树

https://leetcode-cn.com/problems/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
24
25
26
27
28
29
30
31
32
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// 首先二叉搜索树一个性质: 中序遍历就是递增序列
// 保存中序遍历上一个元素, 比较每一个元素是否相同即可
long long pre = LLONG_MIN;
bool flag = true;
void dfs(TreeNode* root) {
if (!root) return;
dfs(root->left);
if (root->val <= pre) {
flag = false;
return;
}
pre = root->val;
dfs(root->right);
}
bool isValidBST(TreeNode* root) {
dfs(root);
return flag;
}
};

中序遍历迭代

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isValidBST(TreeNode* root) {
stack<TreeNode*> stk;
long long pre = LLONG_MIN;
while (root || stk.size()) {
while (root) {
stk.push(root);
root = root->left;
}
root = stk.top(); stk.pop();
if (root->val <= pre) return false;
pre = root->val;
root = root->right;
}
return true;
}
};

67 | 旋转图像

暴力的做法:

第一行 放到 最后一列

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
vector<vector<int>> help(n, vector(n, 0));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
help[j][n - 1 - i] = matrix[i][j];
}
}
matrix = move(help);
}
};

反转的做法:

  1. 上下翻转
  2. 沿主对角线翻转
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:
void rotate(vector<vector<int>>& matrix) {
// 这题我记得以前有一个贼有趣的图
// 就是把一个蛋黄派反转...
// 3/2 = 1, 4/2 = 2
int n = matrix.size();
// 上下翻转
for (int i = 0; i < n / 2; ++i) {
for (int j = 0; j < n; ++j) {
swap(matrix[i][j], matrix[n - 1 - i][j]);
}
}
// 对角线
// 对于上三角m[i][j]关于主对角线对称是m[j][i]
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
swap(matrix[i][j], matrix[j][i]);
}
}
}
};

68 | 对称二叉树

https://leetcode-cn.com/problems/symmetric-tree/submissions/

递归写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool check(TreeNode* a, TreeNode* b) {
if (!a && !b) return true;
if (a && !b || !a && b) return false;
return (a->val == b->val && check(a->left, b->right) && check(a->right, b->left));
}
bool isSymmetric(TreeNode* root) {
return check(root, root);
}
};

迭代写法

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool check(TreeNode* a, TreeNode* b) {
queue<TreeNode*> q;
q.push(a), q.push(b);
while (q.size()) {
auto u = q.front(); q.pop();
auto v = q.front(); q.pop();
if (!u && !v) continue;
if (!u && v || !v && u) return false;
if (u->val != v->val) return false;
q.push(u->left), q.push(v->right);
q.push(u->right), q.push(v->left);
}
return true;
}

bool isSymmetric(TreeNode* root) {
return check(root, root);
}
};

69 | 子集

二进制枚举法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
// 二进制枚举
int n = nums.size();
vector<vector<int>> ans;
for (int i = 0; i < (1 << n); ++i) {
vector<int> now;
for (int j = 0; j < n; ++j) {
if (i >> j & 1) {
now.push_back(nums[j]);
}
}
ans.push_back(now);
}
return ans;
}
};

回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
vector<vector<int>> ans;
vector<int> cur;
void dfs(vector<int>& nums, int now) {
if (now == nums.size()) {
ans.push_back(cur);
return;
}
cur.push_back(nums[now]);
dfs(nums, now + 1);
cur.pop_back();
dfs(nums, now + 1);
}

vector<vector<int>> subsets(vector<int>& nums) {
dfs(nums, 0);
return ans;
}
};

70 | 翻转二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (!root) return root;
TreeNode* tmp = root->left;
root->left = root->right, root->right = tmp;
invertTree(root->left), invertTree(root->right);
return root;
}
};

71 | 复原ip地址

回溯

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
class Solution {
public:
vector<string> ans;
vector<string> restoreIpAddresses(string s) {
if (s.size() > 12) return {};
dfs(s, "", 0);
return ans;
}

void dfs(string& s, string cur, int start) {
if (cur.size() == s.size() + 3) {
if (start == s.size()) ans.push_back(cur);
return;
}
string now = "";
for (int i = start; i < min((int)s.size(), start + 3); ++i) {
now += s[i];
if (valid(now)) {
dfs(s, cur.size() ? cur + "." + now : now, i + 1);
}
}
}
bool valid (string& x) {
if (x.size() < 1 || x.size() > 3) return false;
if (x.size() > 1 && x[0] == '0') return false;
int num = stoi(x);
return num >= 0 && num <= 255;
};
};

72 | 零钱兑换

典型的完全背包问题 (物品可以选择无数次)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
// 硬币的体积 ==> 1
// 硬币的价值 ==> coins[i]
// 硬币可重复次数 ==> 无限次
// 完全背包问题
const int inf = 0x3f3f3f3f;
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, inf);
dp[0] = 0;
for (int i = 0; i <= amount; ++i) {
for (auto j : coins) {
if (i - j >= 0) {
dp[i] = min(dp[i], dp[i - j] + 1);
}
}
}
return dp[amount] == inf ? -1 : dp[amount];
}
};

关于背包

  • 背包问题

关于初始化:

恰好装满 ==> dp[i] = inf

小于等于 ==> dp[i] = 0

0-1背包

有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

int f[1005];

int w[1005], v[1005];

int main () {
int N, V;
cin >> N >> V;
for (int i = 0; i < N; ++i) {
cin >> v[i] >> w[i];
}
for (int i = 0; i < N; ++i) {
for (int j = V; j >= v[i]; --j) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
cout << f[V] << endl;
return 0;
}

完全背包和0-1背包相比仅仅是第二层循环的顺序改了

完全背包

有 N 件物品和一个容量是 V的背包。每种物品都有无限件可用。

第 i 件物品的体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

int f[1005];

int v[1005], w[1005];

int main () {
int N, V;
cin >> N >> V;
for (int i = 0; i < N; ++i) {
cin >> v[i] >> w[i];
}
for (int j = 0; j <= V; ++j) {
for (int i = 0; i < N; ++i) {
if (j - v[i] >= 0) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
}
cout << f[V] << endl;
return 0;
}

多重背包

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

int f[1005];

int s[1005], v[1005], w[1005];

int main () {
int N, V;
cin >> N >> V;
for (int i = 0; i < N; ++i) {
cin >> v[i] >> w[i] >> s[i];
}
for (int i = 0; i < N; ++i) {
for (int j = V; j >= 0; --j) {
for (int k = 1; k <= s[i] && k * v[i] <= j; ++k) {
f[j] = max(f[j], f[j - k * v[i]] + k * w[i]);
}
}
}
cout << f[V] << endl;
return 0;
}

多重背包+二进制优化

题目同上, 但是由于多重背包复杂度N V S, 当数量比较大时会超, 故采用二进制优化的方式将多重背包转化成01背包的问题

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
#include <bits/stdc++.h>
using namespace std;

const int N = 2010;
int f[N];

int main () {
int nn, V;
int v, w, s;
cin >> nn >> V;
vector<pair<int, int>> all;
for (int i = 0; i < nn; ++i) {
cin >> v >> w >> s;
for (int k = 1; k <= s; k <<= 1) {
s -= k;
all.emplace_back(v * k, w * k);
}
if (s > 0) {
all.emplace_back(v * s, w * s);
}
}
for (auto& [v, w] : all) {
for (int j = V; j - v >= 0; --j) {
f[j] = max(f[j], f[j - v] + w);
}
}
cout << f[V] << endl;
return 0;
}

混合背包

有 N 种物品和一个容量是 V 的背包。

物品一共有三类:

  • 第一类物品只能用1次(01背包);
  • 第二类物品可以用无限次(完全背包);
  • 第三类物品最多只能用 si次(多重背包);

每种体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。

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
#include<bits/stdc++.h>
using namespace std;

vector<tuple<int, int, int>> all; // t, v, w
int f[1005];

int main()
{
int N, V;
cin >> N >> V;
for (int i = 0; i < N; ++i) {
int v, w, t;
cin >> v >> w >> t;
if (t == -1) { // 01背包
all.emplace_back(0, v, w);
} else if (t == 0) { // 完全背包
all.emplace_back(-1, v, w);
} else { // 多重背包
for (int k = 1; k <= t; k <<= 1) {
t -= k;
all.emplace_back(0, v * k, w * k);
}
if (t > 0) {
all.emplace_back(0, v * t, w * t);
}
}
}
for (auto& [t, v, w] : all) {
if (t == 0) {
for (int i = V; i - v >= 0; --i) {
f[i] = max(f[i], f[i - v] + w);
}
} else if (t == -1) {
for (int i = v; i <= V; ++i) {
f[i] = max(f[i], f[i - v] + w);
}
}
}
cout << f[V] << endl;
return 0;
}

二维费用背包

就是把0-1背包的限制条件扩展到了二维, 思路是一致的

有 N 件物品和一个容量是 V 的背包,背包能承受的最大重量是 M。

每件物品只能用一次。体积是 vi,重量是 mi,价值是 wi。

求解将哪些物品装入背包,可使物品总体积不超过背包容量,总重量不超过背包可承受的最大重量,且价值总和最大。

输出最大价值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1005;

int f[maxn][maxn];

int main () {
int N, V, M;
cin >> N >> V >> M;
int v, m, w;
for (int i = 0; i < N; ++i) {
cin >> v >> m >> w;
for (int i = V; i - v >= 0; --i) {
for (int j = M; j - m >= 0; --j) {
f[i][j] = max(f[i][j], f[i - v][j - m] + w);
}
}
}
cout << f[V][M];
return 0;
}

分组背包问题

有 N 组物品和一个容量是 V 的背包。

每组物品有若干个,同一组内的物品最多只能选一个。
每件物品的体积是 vij,价值是 wij,其中 i 是组号,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
#include<bits/stdc++.h>
using namespace std;

int f[105], v[105], w[105];

int main () {
int N, V;
cin >> N >> V;
int s;
while (N--) {
cin >> s;
for (int i = 0; i < s; ++i) {
cin >> v[i] >> w[i];
}
for (int i = V; i >= 0; --i) {
for (int j = 0; j < s; ++j) {
if (i - v[j] >= 0)
f[i] = max(f[i], f[i - v[j]] + w[j]);
}
}
}
cout << f[V] << endl;
return 0;
}

73 | 在排序数组中查找元素的第一个和最后一个位置

https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-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
28
29
30
31
32
33
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
// 二分
// 实质是: lower_bound - 1 - lower_bound
// 自己实现一个
int n = nums.size();
int l = 0, r = n;
// 实现upper_bound
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] <= target) {
l = mid + 1;
} else {
r = mid;
}
}
int up = r;
l = 0, r = n;
// 实现lower_bound
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] < target) {
l = mid + 1;
} else {
r = mid;
}
}
int lo = r;
if (up > lo) return {lo, up - 1};
else return {-1, -1};
}
};

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

是「56 | 删除链表中的重复元素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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (!head) return head;
ListNode* dummy = new ListNode(0, head);
ListNode* now = dummy;
while (now->next) {
ListNode* p = now->next;
if (p->next && p->val == p->next->val) {
while (p->next && p->val == p->next->val) {
p = p->next;
}
}
now->next = p;
now = now->next;
}
return dummy->next;
}
};

75 | 比较版本号

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:
int compareVersion(string version1, string version2) {
// 双指针比较
int num1 = 0, num2 = 0;
int n1 = version1.size(), n2 = version2.size();
int p1 = 0, p2 = 0;
while (p1 < n1 || p2 < n2) {
int t1 = 0, t2 = 0; // 存这一段的结果
while (p1 < n1 && version1[p1] != '.') {
t1 = t1 * 10 + version1[p1++] - '0';
}
++p1;
while (p2 < n2 && version2[p2] != '.') {
t2 = t2 * 10 + version2[p2++] - '0';
}
++p2;
if (t1 != t2) {
return t1 < t2 ? -1 : 1;
}
}
return 0;
}
};

76 | 最小路径和

https://leetcode-cn.com/problems/minimum-path-sum/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
// 只能dp了
// 由于只从左边或者上面转移
int n = grid.size(), m = grid[0].size();
vector<int> dp(m, INT_MAX);
dp[0] = grid[0][0];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (i != 0) dp[j] += grid[i][j];
if (j != 0) dp[j] = min(dp[j], dp[j - 1] + grid[i][j]);
}
}
return dp[m - 1];
}
};

77 | 只出现一次的数字

https://leetcode-cn.com/problems/single-number/

1
2
3
4
5
6
7
8
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = 0;
for (auto& i : nums) ans ^= i;
return ans;
}
};

78 | 括号生成

https://leetcode-cn.com/problems/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
class Solution {
public:
bool check (string s) {
int cnt = 0;
for (auto& i : s) {
if (i == '(') ++cnt;
if (i == ')') {
if (cnt <= 0) return false;
--cnt;
}
}
return cnt == 0;
}
vector<string> generateParenthesis(int n) {
// 二进制枚举, 检查序列是否可靠
n <<= 1;
vector<string> ans;
for (int i = 0; i < (1 << n); ++i) {
string now = "";
for (int j = 0; j < n; ++j) {
if (i >> j & 1) {
now += '(';
} else {
now += ')';
}
}
if (check(now)) ans.push_back(now);
}
return ans;
}
};

回溯带优化

  1. 左 + 右 = n终止
  2. 右 > 左 break
  3. 左 = 右 放左
  4. 左 > 右 放左, 右

回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
vector<string> ans;
vector<string> generateParenthesis(int n) {
dfs("", n, 0, 0);
return ans;
}
void dfs(string now, int n, int l, int r) {
if (l + r == n * 2) {
if (l == r)
ans.push_back(now);
return;
}
if (r > l) return;
if (r <= l) dfs(now + '(', n, l + 1, r);
dfs(now + ')', n, l, r + 1);
}
};

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

https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/

这个二分不太正常,既没有左闭右开,右边界又没有收缩到n - 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int findMin(vector<int>& nums) {
// 一样使用二分
int n = nums.size();
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] < nums[n - 1]) {
r = mid;
} else {
l = mid + 1;
}
}
return nums[r];
}
};

80 | 组合总和

https://leetcode-cn.com/problems/combination-sum/

一开始想的方法是枚举每个数被选取(1, 2, 3, … k)次, 直到sum + k * now >= target

但注意到这样会让now有很多份, 因为无法及时pop

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:
vector<vector<int>> ans;
void dfs (int idx, vector<int>& candidates, int target, vector<int> now, int sum) {
if (sum == target) {
ans.push_back(now);
return;
}
if (idx >= candidates.size() || sum > target) return;
// 枚举选0, 1, ...k次(k *)
int k = 0;
while (k * candidates[idx] + sum <= target) {
if (k) now.push_back(candidates[idx]);
dfs(idx + 1, candidates, target, now, sum + k * candidates[idx]);
++k;
}
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
// dfs 枚举每一个数被选到他大于target
vector<int> now;
dfs(0, candidates, target, now, 0);
return 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
class Solution {
public:
vector<vector<int>> ans;
void dfs (int idx, vector<int>& candidates, int target, vector<int>& now) {
if (idx >= candidates.size()) return;
if (target == 0) {
ans.push_back(now);
return;
}
// jump
dfs(idx + 1, candidates, target, now);
// select
if (target - candidates[idx] >= 0) {
now.push_back(candidates[idx]);
dfs(idx, candidates, target - candidates[idx], now);
now.pop_back(); // 回溯
}
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<int> now;
dfs(0, candidates, target, now);
return ans;
}
};

81 | 字符串相乘

https://leetcode-cn.com/problems/multiply-strings/

直接用数组保存, 然后对数组进行「竖式加法」

相当于模拟乘法竖式的时候将乘法时候的「进位」保留了, 最后相加时候一起进位

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:
// 本方法:
string multiply(string num1, string num2) {
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
int n = num1.size(), m = num2.size();
vector<int> c (n + m, 0);
int carry = 0;
// 模拟列竖式的过程 (不完全是)
for (int i = 0; i < n; ++i) {
int a = num1[i] - '0';
for (int j = 0; j < m; ++j) {
int b = num2[j] - '0';
c[i + j] += a * b;
}
}
for (int i = 0, t = 0; i < n + m; ++i) {
t += c[i];
c[i] = t % 10;
t /= 10;
}
// 去除前面的0
while (c.size() > 1 && c.back() == 0) c.pop_back();
string ans;
for (int i = c.size() - 1; i >= 0; --i) {
ans += (c[i] + '0');
}
return ans;
}
};

82 | 调整数组顺序使奇数位于偶数前面

https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
vector<int> exchange(vector<int>& nums) {
// 双指针
int p1 = 0, p2 = nums.size() - 1;
// 左边找到第一个偶数, 右边找到第一个奇数, 交换
while (p1 < p2) {
while (p1 < p2 && nums[p1] % 2 == 1) ++p1;
while (p1 < p2 && nums[p2] % 2 == 0) --p2;
if (p1 < p2)
swap(nums[p1], nums[p2]);
}
return nums;
}
};

83 | 二叉树的后序遍历

假的后序, 真的前序写法:

前序 中->右->左

翻转后成为左->右->中即为后序

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
// 左->右->中为后序
// 可以先 中->右->左, 然后结果reverse
stack<TreeNode*> stk;
vector<int> ans;
while (root || stk.size()) {
while (root) {
ans.push_back(root->val);
stk.push(root);
root = root->right;
}
root = stk.top();
stk.pop();
root = root->left;
}
reverse(ans.begin(), ans.end());
return 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
32
33
34
35
36
37
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> stk;
vector<int> ans;
TreeNode* prev = nullptr;
while (root || stk.size()) {
while (root) {
stk.push(root);
root = root->left;
}
root = stk.top();
stk.pop();
// 没有右边或者就是从右边上来的
if (!root->right || root->right == prev) {
ans.push_back(root->val);
prev = root;
root = nullptr; // 不能再访问左节点了
} else {
stk.push(root); // 有右边则当前还得入栈, 因为先右再中
root = root->right;
}
}
return ans;
}
};

84 | 对角线遍历

做这种题最重要的是:

  1. 找规律
  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
class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
// 真有你的
/*
找规律:

注意左下(+1, -1)和右上移动(-1, +1)不会改变当前(行 + 列)的和, 即判断方式为行 + 列的和
if (行 + 列)是偶数, 就是右上, 是奇数就是左下

左下 = [1, -1]
如果在最后一行 => 向右 [0, 1] (先判断行, 防止在左下角的时候向下则越界)
如果在第一列 => 向下 [1, 0]

右上 = [-1, 1]
如果在最后一列 => 向下 [1, 0] (先判断列, 防止在右上角时候向右则越界)
如果在第一行 => 向右 [0, 1]
*/
vector<int> ans;
int row = mat.size(), col = mat[0].size();
int all = row * col; // 元素个数
int x = 0, y = 0;
for (int i = 0; i < all; ++i) {
ans.push_back(mat[x][y]);
// 右上
if ((x + y) % 2 == 0) {
if (y == col - 1) ++x; // 最后一列
else if (x == 0) ++y; // 第一行
else --x, ++y; // 正常右上
} else {
if (x == row - 1) ++y;
else if (y == 0) ++x;
else ++x, --y;
}
}
return ans;
}
};

85 | 斐波那契数列

https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int fib(int n) {
int a = 0, b = 1;
int mod = (int) 1e9 + 7;
if (n == 0) return a;
if (n == 1) return b;
int ans = 0;
for (int i = 2; i <= n; ++i) {
ans = a + b;
ans %= mod;
a = b, b = ans;
}
return ans;
}
};

86 | 复制带随机指针的链表

https://leetcode-cn.com/problems/copy-list-with-random-pointer/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
unordered_map<Node*, Node*> mem; // 记录旧链表和新链表的对应关系
Node* copyRandomList(Node* head) {
if (!head) return head;
if (!mem.count(head)) {
// 没有对应的就新建
Node* new_node = new Node(head->val);
mem[head] = new_node;
new_node->next = copyRandomList(head->next);
new_node->random = copyRandomList(head->random);
}
return mem[head];
}
};

87 | 买卖股票的最佳时机2

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

由于不限交易次数, 我们将所有上升段统计即可

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int maxProfit(vector<int>& prices) {
// O(N)复杂度的dp
// 发现一件事: 那就是第二天就卖永远不会亏
// 我们跳过所有的下降段, 只收获上升段得到的值
int ans = 0;
for (int i = 1; i < prices.size(); ++i) {
ans += max(0, prices[i] - prices[i - 1]);
}
return ans;
}
};

dp的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int maxProfit(vector<int>& prices) {
// dp的写法
// dp[i][0] 表示 第i天没股票的最大收获
// dp[i][1] 表示 第i天有股票的最大收获
// 滚动数组优化
vector<vector<int>> dp(prices.size(), vector<int>(2, 0));
dp[0][0] = 0, dp[0][1] = -prices[0];
for (int i = 1; i < prices.size(); ++i) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return dp[prices.size() - 1][0];
}
};

加上滚动数组优化的dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int maxProfit(vector<int>& prices) {
// dp的写法
// dp[i][0] 表示 第i天没股票的最大收获
// dp[i][1] 表示 第i天有股票的最大收获
// 滚动数组优化
vector<vector<int>> dp(2, vector<int>(2, 0));
dp[0][0] = 0, dp[0][1] = -prices[0];
for (int i = 1; i < prices.size(); ++i) {
dp[i & 1][0] = max(dp[(i - 1) & 1][0], dp[(i - 1) & 1][1] + prices[i]);
dp[i & 1][1] = max(dp[(i - 1) & 1][1], dp[(i - 1) & 1][0] - prices[i]);
}
return dp[(prices.size() - 1) & 1][0];
}
};

88 | 数组中的逆序对

https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

归并排序求逆序对

这题还有个树状数组的解法, 但是面试肯定不会问, 就不写了

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:

int ans = 0;
vector<int> aux;
void count(vector<int>& nums, int l, int mid, int r) {
int p1 = l, p2 = mid + 1;
int k = p1;
while (p1 <= mid && p2 <= r) {
if (nums[p1] <= nums[p2]) { // 这里是小于等于, 不能搞成小于了!!
aux[k++] = nums[p1++];
} else {
aux[k++] = nums[p2++];
ans += (mid - p1 + 1);
}
}
while (p1 <= mid) aux[k++] = nums[p1++]; //?
while (p2 <= r) aux[k++] = nums[p2++];
for (int i = l; i <= r; ++i) nums[i] = aux[i];
}
void merge_count(vector<int>& nums, int l, int r) {
if (l >= r) return;
int mid = l + r >> 1;
merge_count(nums, l, mid);
merge_count(nums, mid + 1, r);
count(nums, l, mid, r);
}
int reversePairs(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
aux.resize(nums.size());
merge_count(nums, l, r);
return ans;
}
};

89 | 单词搜索

https://leetcode-cn.com/problems/word-search/

爆搜回溯

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:
vector<int> dir = {-1, 0, 1, 0, -1};
vector<vector<int>> vis;
bool dfs(int x, int y, int k, string s, vector<vector<char>>& board) {
if (board[x][y] != s[k]) return false;
if (k == s.size() - 1) return true; // 找到了
vis[x][y] = true;
bool f = false;
for (int i = 0; i < 4; ++i) {
int nx = x + dir[i], ny = y + dir[i + 1];
if (nx < 0 || nx >= board.size() || ny < 0 || ny >= board[0].size() || vis[nx][ny]) continue;
f = dfs(nx, ny, k + 1, s, board); // 找到一个就可
if (f) return true;
}
vis[x][y] = false; // 记得取消标记, 别的路还要搜呢
return f;
}
bool exist(vector<vector<char>>& board, string word) {
// 典型的dfs
// 找到所有前缀搜一遍就行了
int n = board.size(), m = board[0].size();
vis.resize(n, vector<int> (m, 0));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (board[i][j] == word[0]) {
vis.assign(n, vector<int> (m, 0));
if (dfs(i, j, 0, word, board)) return true;
}
}
}
return false;
}
};

90 | 长度最小的子数组

https://leetcode-cn.com/problems/minimum-size-subarray-sum/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
// 滑动窗口
int sum = 0;
int ans = INT_MAX;
for (int r = 0, l = 0; r < nums.size(); ++r) {
sum += nums[r];
while (sum >= target) {
ans = min(ans, r - l + 1);
sum -= nums[l++];
}
}
return ans == INT_MAX ? 0 : ans;
}
};

91 | 整数反转

https://leetcode-cn.com/problems/reverse-integer/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int reverse(int x) {
// ans = ans * 10 + x % 10; x /= 10;
// 如何判断ans是否溢出呢?
// 知道x的第一位只有可能是1 / 2开头 (INT_MAX = 24xxx)
// 故在判断最后一位的时候只需要 将 ans 和 INT_MAX / 10对比,
// ans * 10 + x > INT_MAX得条件是 (ans * 10 + x > (INT_MAX // 10) * 10 + 7)
// 而 x < 7 (x <= 2)
// 意思只需要ans * 10 > INT_MAX // 10即可
int ans = 0;
while (x) {
if (ans < INT_MIN / 10 || ans > INT_MAX / 10) {
return 0;
}
ans = ans * 10 + x % 10, x /= 10;
}
return ans;
}
};

92 | 螺旋矩阵2

https://leetcode-cn.com/problems/spiral-matrix-ii/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
int top = 0, bottom = n - 1, left = 0, right = n - 1, now = 1;
vector<vector<int>> g (n, vector<int>(n, 0));
while (1) {
for (int i = left; i <= right; ++i) g[top][i] = now++;
if (++top > bottom) return g;
for (int i = top; i <= bottom; ++i) g[i][right] = now++;
if (--right < left) return g;
for (int i = right; i >= left; --i) g[bottom][i] = now++;
if (--bottom < top) return g;
for (int i = bottom; i >= top; --i) g[i][left] = now++;
if (++left > right) return g;
}
return g;
}
};

93 | 最长有效括号

https://leetcode-cn.com/problems/longest-valid-parentheses/

栈得做法, 很巧妙

栈中(底部)保存得是「最后一个失配的右括号的下标」, 栈其他保存的是各个未匹配的左括号的下标

一旦产生括号匹配就先将匹配的左括号弹出, 再更新ans

边界条件是stk.push(-1), 先将栈中压入-1, 保证每个右括号到来时都可以更新ans

当栈为空时, 表示出现了)), 这时候更新栈底失配右括号的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int longestValidParentheses(string s) {
stack<int> stk; stk.push(-1);
int ans = 0;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '(') {
stk.push(i);
} else if (s[i] == ')') {
stk.pop();
if (!stk.empty()) {
ans = max(ans, i - stk.top());
} else {
stk.push(i);
}
}
}
return ans;
}
};

94 | 搜索二维矩阵2

https://leetcode-cn.com/problems/search-a-2d-matrix-ii/

将矩阵以右上角为根看成一颗二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
// 注意到以右上角开头的元素对应一个二叉搜索树
// 这样就好办了
int n = matrix.size(), m = matrix[0].size();
int x = 0, y = m - 1;
while (x >= 0 && x < n && y >= 0 && y < m) {
if (matrix[x][y] == target) return true;
// 搜索左子树
if (matrix[x][y] > target) {
--y;
} else { // 搜索右子树
++x;
}
}
return false;
}
};

95 | 最大正方形

https://leetcode-cn.com/problems/maximal-square/

动态规划:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int dp[310][310];
int maximalSquare(vector<vector<char>>& mat) {
memset(dp, 0, sizeof dp);
// 动态规划
// dp[i][j] = k表示以i, j为左下角的最大正方形的边长为k
// 状态转移: if (m[i][j] == '1') dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
int n = mat.size(), m = mat[0].size();
int ans = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (mat[i - 1][j - 1] == '1') {
dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
ans = max(ans, dp[i][j] * dp[i][j]);
}
}
}
return ans;
}
};

96 | 最长连续序列

https://leetcode-cn.com/problems/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
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
// 必然的动态规划
// 要求时间没要求空间
// 居然也没要求顺序
// 桶排的话数据量略大
// 哈希吧
int ans = 0;
unordered_set<int> hmap;
for (auto i : nums) {
hmap.insert(i);
}
while (hmap.size()) {
int now = *hmap.begin();
hmap.erase(now);
// 左右扩展?
int next = now + 1, prev = now - 1;
while (hmap.count(next)) {
hmap.erase(next);
next++;
}
while (hmap.count(prev)) {
hmap.erase(prev);
prev--;
}
ans = max(ans, next - prev - 1);
}
return ans;
}
};

97 | 验证IP地址

https://leetcode-cn.com/problems/validate-ip-address/

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
class Solution {
public:
// 将s分割成以spliter为分隔符的n份
vector<string> split(string s, string spliter) {
vector<string> ans;
int it;
int len =spliter.size();
while ((it = s.find(spliter)) && it != s.npos) {
ans.push_back(s.substr(0, it));
s = s.substr(it + len);
}
ans.push_back(s);
return ans;
}

// 检查: 长度, 整数范围, 是否有其他字符
bool check_ipv4 (string s) {
vector<string> ss = split(s, ".");
// 检查是否是4份
if (ss.size() != 4) return false;
for (string& str : ss) {
if (str.empty() || str.size() > 3 || str.size() != 1 && str[0] == '0') return false;
for (auto i : str) if (!isdigit(i)) return false;
if (stoi(str) < 0 || stoi(str) > 255) return false;
}
return true;
}

// 这里的ipv6时不带简写的
bool check_ipv6 (string s) {
vector<string> ss = split(s, ":");
// 检查是否是8份
if (ss.size() != 8) return false;
for (string& str : ss) {
if (str.empty()) return false;
// i是数字或者a ~ f A ~ F
for (auto i : str) {
if (! (isdigit(i) || (i >= 'a' && i <= 'f') || (i >= 'A' && i <= 'F'))) return false;
}
if (str.size() == 0 || str.size() > 4) return false;
}
return true;
}

string validIPAddress(string IP) {
return check_ipv4(IP) ? "IPv4" : check_ipv6(IP) ? "IPv6" : "Neither";
}
};

98 | 二叉树的完全性检验

二叉树(从1开始标记) 左边 2 x, 右边2 x + 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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isCompleteTree(TreeNode* root) {
// 标记法 + 层序
if (!root) return true;
queue<pair<TreeNode*, int>> q;
q.emplace(root, 1);
int cnt = 1;
while (q.size()) {
int sz = q.size();
for (int i = 0; i < sz; ++i) {
auto [now, idx] = q.front(); q.pop();
if (idx != cnt++) return false;
if (now->left) q.emplace(now->left, idx * 2);
if (now->right) q.emplace(now->right, idx * 2 + 1);
}
}
return true;
}
};

99 | 二叉搜索树与完全链表

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
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;

Node() {}

Node(int _val) {
val = _val;
left = NULL;
right = NULL;
}

Node(int _val, Node* _left, Node* _right) {
val = _val;
left = _left;
right = _right;
}
};
*/
class Solution {
public:
// 最后head指向第一个, prev指向最后一个
Node* prev = nullptr, *head = nullptr;
void dfs(Node* root) {
if (!root) return;
dfs(root->left);
if (prev) prev->right = root;
else head = root;
root->left = prev;
prev = root;
dfs(root->right);
}
Node* treeToDoublyList(Node* root) {
if (!root) return root;
dfs(root);
prev->right = head, head->left = prev;
return head;
}
};

100 | 不同路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int dp[110];
int uniquePaths(int m, int n) {
// 递推
dp[0] = 1;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (j) dp[j] += dp[j - 1];
}
}
return dp[n - 1];
}
};

「leetcode刷题」两天冲刺挑战(100题)
https://blog.roccoshi.top/posts/2486/
作者
RoccoShi
发布于
2021年8月23日
许可协议