算法刷题
算法基础
本笔记总结了常见算法与数据结构的基础知识与典型题目，适合用于复习与面试准备。
一、数组与链表
1. 排序
📘 复杂度与应用场景
| 算法 | 平均复杂度 | 最坏复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | ✅ | 数据量小、稳定性要求高 |
| 选择排序 | O(n²) | O(n²) | ❌ | 数据量小，交换次数少 |
| 插入排序 | O(n²) | O(n²) | ✅ | 基本有序数组 |
| 希尔排序 | O(n¹·³)~O(n²) | O(n²) | ❌ | 中等规模数组 |
| 快速排序 | O(n log n) | O(n²) | ❌ | 工业界通用排序 |
| 归并排序 | O(n log n) | O(n log n) | ✅ | 稳定排序、外部排序 |
| 堆排序 | O(n log n) | O(n log n) | ❌ | 需要原地排序、Top K 场景 |
🔸 快速排序(分治思想，原地划分，适合 Top-K、排序优化等)
-
1
2
3
4
5
6
7
8
9
10
11
12
13
14int quickFind(vector<int>& nums, int l, int r, int k) {
if (l == r) return nums[l];
int i = l - 1, j = r + 1, pivot = nums[ l + r >> 1];
while(i < j) { // 均不含等于号
while(nums[++i] < pivot);
while(nums[--j] > pivot);
if (i < j) swap(nums[i], nums[j]);
} // 划分为[l, j]与[j+1, r],注意是J
if (k <= j) return quickFind(nums, l, j, k); // 这里是小于等于
return quickFind(nums, j+1, r, k);
}
int findKthLargest(vector<int>& nums, int k) {
return quickFind(nums, 0, nums.size() - 1, nums.size() - k);
}
🔸 归并排序
-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23using LL = long long;
LL merge_sort(vector<int>& record, vector<int>& tmp, int l, int r){
if (l >= r) return 0;
int mid = l + r >> 1;
LL res = merge_sort(record, tmp, l, mid) + merge_sort(record, tmp, mid + 1, r);
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <=r) { // 合并两个有序的数组，这里合并的是两边的值
if(record[i] <= record[j]) tmp[ k++ ] = record[ i++ ];
else { // 可以产生逆序对的情况
tmp[ k++ ] = record[ j++ ];
res += mid - i + 1;
}
}
while( i <= mid ) tmp[k++] = record[i++];
while( j <= r ) tmp[k++] = record[j++];
for(int i = l, j = 0; i <= r; i++, j++) record[i] = tmp[j];
return res;
}
int reversePairs(vector<int>& record) {
int N = record.size();
vector<int> tmp(N);
return merge_sort(record, tmp, 0, record.size() - 1);
}
2. 双指针
🚀 快慢指针
典型应用：遍历、过滤、删除重复元素、判断链表特性等。
数组移动删除元素
这种问题一般需要从一端开始，设立两个指针i，j；j走的快一些，循环终止条件为j走到列表末尾。i一般用来控制删除后元素应该放在的正确位置
-
1
2
3
4
5
6
7
8
9
10
11
12int removeDuplicates(vector<int>& nums) {
int N = nums.size();
int i = 1, j = 1; // 根据判断条件要求，需要从下标1开始,为0时不会产生重复项，不考虑
while(j < N) {
if (nums[j] != nums[j - 1]) {
nums[i] = nums[j];
i++;
}
j++;
}
return i;
} -
1
2
3
4
5
6
7
8
9
10
11
12int removeElement(vector<int>& nums, int val) {
int N = nums.size();
int i = 0, j = 0; // 需要从0开始，不然开头重复删除不了
while(j < N) {
if (nums[j] != val) {
nums[i] = nums[j];
i++;
}
j++;
}
return i;
} -
1
2
3
4
5
6
7
8
9
10
11void moveZeroes(vector<int>& nums) {
int N = nums.size();
int i = 0, j = 0; // 下标从0开始,
while (j < N) {
if (nums[j] != 0) {
swap(nums[i], nums[j]);
i++;
}
j++;
}
}
- 链表的删除合并
-
1
2
3
4
5
6
7
8ListNode* deleteDuplicates(ListNode* head) {
auto cur = head;
while (cur && cur->next) { // 如果cur->next为空，说明已经到最后一个节点，不需要判断重复了
if (cur->val == cur->next->val) { cur->next = cur->next->next; }
else { cur = cur->next; }
}
return head;
} -
设置一个快指针，先走N次，此时fast相较于slow为倒数第N个节点，fast走到最后，此时slow的位置为倒数第N个节点的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14ListNode* removeNthFromEnd(ListNode* head, int n) {
auto dummy = new ListNode(-1, head);
auto slow = dummy, fast = dummy;
while (n--) {
fast = fast->next;
if (!fast) return nullptr; // 长度不够长
}
while(fast->next) {
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
return dummy->next;
} -
设置一个slow和fast指针，slow一次走一格，fast一次走两格，如果有环必会相遇。需要找到节点位置的情况，这时从头节点开始，slow与head相遇的位置为环的入口
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16ListNode* detectCycle(ListNode* head) {
auto slow = head, fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
auto start = head;
while (start != slow) { // 找环入口的方式
slow = slow->next;
start = start->next;
}
return start;
}
}
return nullptr;
} -
p1从headA出发走到末尾，再走一遍链表B，这里不相交会分别从链表A和链表B走一轮，最后在末尾nullptr结束，相交的情况会同时达到相交的节点
1
2
3
4
5
6
7
8ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
auto p1 = headA, p2 = headB;
while(p1 != p2) {
p1 = p1 ? p1->next : headA;
p2 = p2 ? p2->next : headB;
}
return p1;
} -
从两个虚拟头节点出发，分别比较节点值，小于则加入新的链表。合并K个可两两合并。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17ListNode* merge(ListNode* list1, ListNode* list2){
auto dummy = new ListNode(-1);
auto cur = dummy;
while(list1 && list2){
if (list1->val < list2->val){ cur->next = list1; list1 = list1->next; }
else { cur->next = list2; list2 = list2->next; }
cur = cur->next;
}
if (list1) cur->next = list1; // 处理没有完全走完某个列表的情况
if (list2) cur->next = list2;
return dummy->next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* list = nullptr;
for(int i = 0; i < lists.size(); i++){ list = merge(list, lists[i]); }
return list;
} 分隔链表(一分为二)
与上面类似，这里是反过来，从一个链表出发，小于值加入到新的链表，大于加入到另外一个。这里有个坑，会成环，因此第二个链表末尾要置空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19ListNode* partition(ListNode* head, int x) {
auto dummy1 = new ListNode(-1);
auto dummy2 = new ListNode(-1);
auto p1 = dummy1, p2 = dummy2, cur = head;
while (cur) {
if (cur->val < x) {
p1->next = cur;
p1 = p1->next;
}
else {
p2->next = cur;
p2 = p2->next;
}
cur = cur->next;
}
p2->next = nullptr; // 去除环, 重要！！
p1->next = dummy2->next; // 两个有序链表拼接起来
return dummy1->next;
}-
很简单给两个指针，一个一次走一个节点，一个走两次，慢的为中间节点
1
2
3
4
5
6
7
8ListNode* middleNode(ListNode* head) {
auto slow = head, fast = head;
while(fast && fast->next){ // 需要控制走两次的边界条件，一般都是这种形式
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
⚖️ 左右指针
典型应用：区间搜索、反转、回文、二分查找。
-
从两边向中间走，交换值即可
1
2
3
4void reverseString(vector<char>& s) {
int i = 0, j = s.size() - 1;
while(i < j) { swap(s[i++], s[j--]); }
} -
从两边走，验证是否相等
1
2
3
4
5
6
7
8
9
10
11
12bool isPalindrome(string s) {
std::string sraw;
for (auto c : s) {
if (isalnum(c)) sraw += tolower(c); //用到一些判断的api可以记住
}
int n = sraw.size();
int l = 0, r = n - 1;
while(l < r) {
if (sraw[l++] != sraw[r--]) return false;
}
return true;
}回文链表可以先存储值再判断是否是回文，这里可使用递归写法。
-
需要从每个位置向两边扩散找最大子串，这里有子串为奇数和偶数两种可能，因此需要选两者较大的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19int expand(string& s, int i, int j) {
while (i >= 0 && j < s.size()) {
if (s[i] != s[j]) break; // 这里i--不能直接写进来，计数值公式会改变
i--;
j++;
}
return j - i - 1; // l与r是不满足条件后的值，实际长度是((r-1)-(l+1))+1 = r -l -1
}
string longestPalindrome(string s) {
int max_len = 0, start = 0;
for (int i = 0; i < s.size(); i++) {
int len = max(expand(s, i, i), expand(s, i, i+1));
if (len > max_len) {
max_len = len;
start = i - (len - 1 >> 1); // 注意实际开始位置的计算方式
}
}
return s.substr(start, max_len);
} 二分查找：
-
需要注意是左侧、右侧边界的查找方案是有所不同的，下面是最通用的版本，左侧右侧边界的查找需要拓展，这一部分内容在第2题体现。
1
2
3
4
5
6
7
8
9
10int search(vector<int>& nums, int target) {
int i = 0, j = nums.size() - 1;
while (i <= j) { // 注意边界条件和取舍
int mid = (j - i) / 2 + i; // 防止溢出
if (nums[mid] < target) i = mid + 1;
else if (nums[mid] > target) j = mid - 1;
else return mid;
}
return -1;
} 在排序数组中查找元素的第一个和最后一个位置（左边界 / 右边界）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26class Solution {
public:
int binary_search(vector<int>& nums, int target, bool lower) {
int left = 0, right = (int)nums.size() - 1, ans = (int)nums.size();
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] > target || (lower && nums[mid] >= target)) {
right = mid - 1;
ans = mid;
} else {
left = mid + 1;
}
}
return ans;
}
vector<int> searchRange(vector<int>& nums, int target) {
int leftIdx = binarySearch(nums, target, true);
int rightIdx = binarySearch(nums, target, false) - 1;
if (leftIdx <= rightIdx && rightIdx < nums.size() &&
nums[leftIdx] == target && nums[rightIdx] == target) {
return vector<int>{leftIdx, rightIdx};
}
return vector<int>{-1, -1};
}
};
-
滑动窗口
这种题一般用到单调队列和单调栈
-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
int lengthOfLongestSubstring(string s) {
const int N = s.size();
unordered_set<char> st; // 使用集合记录即可
int i = 0, j = 0;
int ans = 0;
while(j < N) {
while(j < N && !st.count(s[j])) {
st.insert(s[j]);
j++;
}
ans = max(ans, j - i);
st.erase(s[i]);
i++;
}
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
25class Solution {
public:
vector<int> findAnagrams(string s, string p) {
const int s_len = s.size(), p_len = p.size();
if (s_len < p_len) return {};
vector<int> ans;
vector<int> pCnt(26, 0), sCnt(26, 0);
for (int i = 0; i < p_len; ++i) {
++sCnt[s[i] - 'a'];
++pCnt[p[i] - 'a'];
}
// 重载的==判断，维护p_len大小窗口，计算每个字符的个数即可，这里使用的是数组的下标
// 这里使用的是数组的下标, 表示个数
if (sCnt == pCnt) ans.push_back(0);
for (int i = 0; i < s_len - p_len; i++) {
--sCnt[s[i] - 'a'];
++sCnt[s[i + p_len] - 'a'];
if (sCnt == pCnt) { ans.emplace_back(i + 1); }
}
return ans;
}
}; -
与上题一致, 判断每个字符出现的次数是否一致即可
-
3. 前缀差分
📊 前缀和（应用：查询区间和、子数组和）
-
给一个左边界left和右边界right，计算left到right的和，前缀和为一个数组，s[j]记录0到j-1的和。
1
2
3
4
5
6
7
8
9
10
11
12
13class NumArray {
private:
std::vector<int> sums;
public:
NumArray(vector<int>& nums) {
sums.resize(nums.size() + 1);
sums[0] = 0;
for (int i = 1; i <= nums.size(); i++)
sums[i] = sums[i - 1] + nums[i - 1]; // S[i] = S[i-1] + nums[i-1],从1开始
}
int sumRange(int left, int right) { return sums[right + 1] - sums[left]; }
// S[right+1]才是从0到right的和
}; -
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class NumMatrix {
public:
vector<vector<int>> sums;
NumMatrix(vector<vector<int>>& matrix) {
int m = matrix.size();
if (m > 0) {
int n = matrix[0].size();
sums.resize(m, vector<int>(n + 1));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
sums[i][j + 1] = sums[i][j] + matrix[i][j];
}
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
int sum = 0;
for (int i = row1; i <= row2; i++) { sum += sums[i][col2 + 1] - sums[i][col1]; }
return sum;
}
};
⚙️ 差分（应用：批量更新区域值，同时加减）
-
差分是为了批量更新，比如某区间，同时加上某个数，同时减去某个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
using namespace std;
const int N = 1e6 + 10;
int a[N], s[N];
int main(){
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
s[i] = a[i] - a[i-1];
}
while (m--){
int l, r, c;
scanf("%d%d%d", &l, &r, &c);
s[l] += c; s[r + 1] -= c; // 更新操作
}
for(int i = 1; i <= n; i++) a[i] = a[i-1] + s[i]; // 还原公式，从1开始
for(int i = 1; i <= n; i++) printf("%d ", a[i]);
return 0;
}
二、栈与队列
1. 基础特性应用
-
用两个栈，一个栈控制入，一个栈控制出，每当要出队，把控制入的栈元素依次从栈顶到栈尾出栈放入到另外一个栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class MyQueue {
public:
MyQueue() {}
void push(int x) { st1.push(x); }
int pop() {
auto res = peek();
st2.pop();
return res;
}
int peek() {
if (st2.empty()) {
while (!st1.empty()) {
st2.push(st1.top());
st1.pop();
}
}
return st2.top();
}
bool empty() { return st1.empty() && st2.empty(); }
private:
std::stack<int> st1,st2;
}; -
只需要用一个队列，加入元素时，先获得当前元素个数n，这个数入队后，将前n个元素依次出队再入队
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class MyStack {
public:
std::queue<int> q;
MyStack() {}
void push(int x) {
int n = q.size();
q.push(x);
while (n--) {
auto front = q.front();
q.pop();
q.push(front);
}
}
int pop() {
auto res = q.front();
q.pop();
return res;
}
int top() { return q.front(); }
bool empty() { return q.empty(); }
}; -
用辅助栈记录最小值即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class MinStack {
public:
std::stack<int> stk;
std::stack<int> min_stk;
MinStack() {}
void push(int val) {
stk.push(val);
min_stk.push(min(min_stk.top(), val));
}
void pop() {
stk.pop();
min_stk.pop();
}
int top() { return stk.top(); }
int getMin() { return min_stk.top(); }
}; -
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
32class Solution {
public:
int calculate(string s) {
vector<int> stk;
char preSign = '+';
int num = 0;
int n = s.length();
for (int i = 0; i < n; ++i) {
if (isdigit(s[i])) {
num = num * 10 + int(s[i] - '0');
}
if (!isdigit(s[i]) && s[i] != ' ' || i == n - 1) {
switch (preSign) {
case '+':
stk.push_back(num);
break;
case '-':
stk.push_back(-num);
break;
case '*':
stk.back() *= num;
break;
default:
stk.back() /= num;
}
preSign = s[i];
num = 0;
}
}
return accumulate(stk.begin(), stk.end(), 0);
}
}; -
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
27class Solution {
public:
int calculate(string s) {
stack<int> ops;
ops.push(1);
int sign = 1;
int ret = 0;
int n = s.length();
int i = 0;
while (i < n) {
if (s[i] == ' ') { i++;}
else if (s[i] == '+') { sign = ops.top(); i++; }
else if (s[i] == '-') { sign = -ops.top(); i++; }
else if (s[i] == '(') { ops.push(sign); i++; }
else if (s[i] == ')') { ops.pop(); i++; }
else {
long num = 0;
while (i < n && s[i] >= '0' && s[i] <= '9') {
num = num * 10 + s[i] - '0';
i++;
}
ret += sign * num;
}
}
return ret;
}
};
2. 单调栈
et. 给一个序列，找出每一个数左边/右边，离它最近的数
-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int N = temperatures.size();
vector<int> ans(N);
stack<int> st;
for (int i = N - 1; i >= 0; i--) { // 右往左
while(!st.empty() && temperatures[i] >= temperatures[st.top()]) {
st.pop(); // 大于栈顶元素，栈顶出栈，保持栈的单调
}
ans[i] = st.empty() ? 0 : (st.top() - i); //栈空:没有值，不空:第i天到栈顶天数
st.push(i);
}
return ans;
}
}; -
nums1是子集，先遍历nums2，并记录所有的数，然后根据nums1的值找结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
int N = nums2.size();
stack<int> st;
unordered_map<int, int> ans_mp;
for (int i = N - 1; i >= 0; i--){
int num = nums2[i];
while(!st.empty() && num >= st.top()) {
st.pop();
}
ans_mp[num] = st.empty() ? -1 : st.top();
st.push(num);
}
vector<int> ans(nums1.size());
for (int i = 0; i < nums1.size(); ++i) {
ans[i] = ans_mp[nums1[i]];
}
return ans;
}
}; -
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n, -1);
stack<int> stk;
for (int i = 0; i < n * 2 - 1; i++) {
while (!stk.empty() && nums[stk.top()] < nums[i % n]) {
ans[stk.top()] = nums[i % n];
stk.pop();
}
stk.push(i % n);
}
return ans;
}
};
3. 单调队列
这种题一般采用双端队列，因为要操作尾部的删减
-
从头部到尾部递减，头部是最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> ans;
deque<int> dq;
int n = nums.size();
for(int i = 0; i < n; i++){
while(!dq.empty() && nums[dq.back()] <= nums[i] ){
dq.pop_back();
}
dq.push_back(i);
if (i >= dq.front() + k) dq.pop_front(); // 去除窗口已经过了的数据
if (i >= k - 1) ans.push_back(nums[dq.front()]); // 满足k个输出依次
}
return ans;
}
}; -
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Checkout {
public:
deque<int> dq;
queue<int> q;
Checkout() {}
int get_max() {
if (dq.empty()) return -1;
return dq.front();
}
void add(int value) { // 保持递减，注意这里是小于
q.push(value);
while(!dq.empty() && dq.back() < value) { dq.pop_back(); }
dq.push_back(value);
}
int remove() { // dq是否pop,根据是否最大值是队列最前面，由于递减，因此删除后dq还是存的最大值
if (q.empty()) return -1;
int ans = q.front();
if (ans == dq.front()) { dq.pop_front(); }
q.pop();
return ans;
}
};
三、二叉树
1. 遍历方式
-
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public:
void preOrder(TreeNode* root, vector<int>& order) { // 换顺序即可完成前、中、后序
if (root == nullptr) return;
order.push_back(root->val);
preOrder(root->left, order);
preOrder(root->right, order);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
preOrder(root, ans);
return ans;
}
}; -
使用队列记录辅助
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (root == nullptr) return ans;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) { // 可记录访问层数获得最大深度
auto sz = q.size();
vector<int> level;
while (sz--) {
auto nd = q.front();
if (nd->left) q.push(nd->left);
if (nd->right) q.push(nd->right);
level.push_back(nd->val);
q.pop();
}
ans.push_back(level);
}
return ans;
}
}; -
1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
public:
void traversal(Node* root, vector<int>& ans) {
if(root == nullptr) return;
ans.push_back(root->val); // 控制访问位置可实现前序后序的遍历
for (auto child : root->children) { traversal(child, ans);}
}
vector<int> preorder(Node* root) {
vector<int> ans;
traversal(root, ans);
return ans;
}
}; -
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> ans;
if (root == nullptr) return ans;
queue<Node*> q;
q.push(root);
while(!q.empty()) {
auto size = q.size();
vector<int> level;
for(auto i = 0; i < size; i++){
auto node = q.front();
level.push_back(node->val);
for (auto child : node->children){ q.push(child); }
q.pop();
}
ans.push_back(level);
}
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
38
39
40
41
42class Solution {
public:
bool hasPathSum(TreeNode *root, int sum) {
if (root == nullptr) {
return false;
}
if (root->left == nullptr && root->right == nullptr) {
return sum == root->val;
} // 叶子节点
return hasPathSum(root->left, sum - root->val) ||
hasPathSum(root->right, sum - root->val);
}
};
// 队列做法
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if(root == nullptr) return false;
queue<TreeNode*> q_node;
queue<int> q_sum;
q_node.push(root);
q_sum.push(root->val);
while(!q_node.empty()) {
auto node = q_node.front();
auto val = q_sum.front();
q_node.pop();
q_sum.pop();
if (node->left == nullptr && node->right == nullptr && val == targetSum) {
return true;
}
if (node->left) {
q_node.push(node->left);
q_sum.push(node->left->val + val);
}
if (node->right) {
q_node.push(node->right);
q_sum.push(node->right->val + val);
}
}
return false;
}
};
2. 树的特性
-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
int ans;
int depth(TreeNode* root) {
if (root == nullptr) return 0;
auto l_dep = depth(root->left); //左子树的深度
auto r_dep = depth(root->right); //右子树子树的深度
ans = max(ans, l_dep + r_dep + 1); // 直径最大值，记录下来
return max(l_dep, r_dep) + 1; // 当前节点深度
}
int diameterOfBinaryTree(TreeNode* root) {
ans = 1;
depth(root);
return ans - 1;
}
}; -
1
2
3
4
5
6
7
8
9
10class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr || root == p || root == q) return root; //满足条件，往上返回
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left && right) return root; // 左右都找到的情况，当前节点是最近公共祖先
return left ? left : right;
}
}; -
上题可解，利用二叉搜索树性质优化
-
1
2
3
4
5
6
7
8
9class Solution {
public:
int countNodes(TreeNode* root) {
if (root == nullptr) return 0; // 空节点返回0
int left_num = countNodes(root->left);
int right_num = countNodes(root->right);
return left_num + right_num + 1; // 左子树个数加右子树个数
}
};
3. 树的构造与操作
-
先序遍历，然后将每个节点记录并连接起来
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
void flatten(TreeNode* root) {
vector<TreeNode*> order;
preorder(root, order);
int N = order.size();
for(int i = 1; i < N; i++){
auto pre = order[i-1], cur = order[i];
pre->left = nullptr;
pre->right = cur;
}
}
void preorder(TreeNode* root, vector<TreeNode*>& order) {
if (root == NULL) return;
order.push_back(root);
preorder(root->left, order);
preorder(root->right, order);
}
}; -
层次遍历后补一下右边的节点
-
递归翻转即可，先翻转左子树，再翻转右子树
1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
public:
void invert(TreeNode* root) {
if (root == nullptr) return;
invertTree(root->left);
invertTree(root->right);
swap(root->left, root->right);
}
TreeNode* invertTree(TreeNode* root) {
invert(root);
return root;
}
}; 构造二叉树
4. 树的序列化与反序列化
5. 二叉搜索树
- 98. 验证二叉搜索树
- 701. 二叉搜索树中的插入操作/450. 删除二叉搜索树中的节点
- 700. 二叉搜索树中的搜索
- 230. 二叉搜索树中第K小的元素
- 1038. 从二叉搜索树到更大和树/538. 把二叉搜索树转换为累加树
四、BFS与DFS
1. 广度优先
1 |
|
1 | class Solution { |
2. 深度优先
3. 树的DFS与BFS
4. 回溯
可参考代码随想录
1 | class Solution { |
五、图论
1. 图遍历
785. 判断二分图/AcWing 860. 染色法判定二分图
2. 最小生成树
3. 最短路径
AcWing 850. Dijkstra求最短路 I/AcWing 850. Dijkstra求最短路 II
1 |
|
1 |
|
并查集（Union-Find）
1
2
3
4
5
6
7
8
9
10
11
12
13
14struct DSU {
unordered_map<string,string> p;
string find(const string& x){
if(!p.count(x)) p[x]=x;
if(p[x]==x) return x;
return p[x]=find(p[x]);
}
void unite(const string&a,const string&b){
string pa=find(a), pb=find(b);
if(pa!=pb) p[pb]=pa;
}
};拓扑排序（检测有向图环）
六、动态规划与贪心
1. 背包问题
背包/完全背包/多重背包
2. 线性DP
3. 贪心算法
七、其他常见题目
区间合并
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> ans; // 先排序然后比较是否能合并
std::sort(intervals.begin(), intervals.end(),
[](vector<int>& a, vector<int>& b) { return b[0] > a[0]; });
for (auto& interval : intervals) {
if (ans.empty()) { ans.push_back(interval); continue; }
if (interval[0] <= ans.back()[1]) {
ans.back()[1] = max(interval[1], ans.back()[1]);
} else { ans.push_back(interval); }
}
return ans;
}
};反转链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = nullptr;
auto cur = head;
while (cur) {
auto nxt = cur->next;
cur->next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
};遍历问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
string reverseWords(string s) {
reverse(s.begin(), s.end());
int i = 0, j = 0;
while (i < s.size()) {
while (s[j] != ' ') { j++; }
int l = i, r = j - 1;
while (l < r) {
swap(s[l], s[r]);
l++;
r--;
}
i = j;
}
return s;
}
};LRU缓存机制
数的和
1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
auto n = nums.size();
std::unordered_map<int, int> st;
for (auto i = 0; i < n; i++) { // 边添加边枚举
if (st.count(target - nums[i])) { return {st[target - nums[i]], i}; }
else { st.insert({nums[i], i}); }
}
return {};
}
};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
29class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
const int N = nums.size();
vector<vector<int>> ans;
for (int i = 0; i < N; i++) {
if (nums[i] > 0) break;
if (i > 0 && nums[i] == nums[i-1]) continue;
int j = i+1, k = N - 1;
while (j < k) {
if (nums[i] + nums[j] + nums[k] < 0) {
j++;
}
else if (nums[i] + nums[j] + nums[k] > 0) {
k--;
}
else {
ans.push_back({nums[i], nums[j], nums[k]});
while(j < k && nums[j] == nums[j+1]) { j++; }
while(j < k && nums[k] == nums[k-1]) { k--;}
j++;
k--;
}
}
}
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
31class Solution {
public:
void dfs(vector<vector<char>>& grid, int x, int y){
grid[x][y] = '0';
int m = grid.size(), n = grid[0].size();
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
for(int i = 0; i < 4; i++){
for(int j = 0; j < 4; j++){
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 & nx < m && ny >= 0 && ny < n && grid[nx][ny] == '1'){
dfs(grid, nx, ny);
}
}
}
}
int numIslands(vector<vector<char>>& grid) {
int ans = 0;
int m = grid.size(), n = grid[0].size();
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if (grid[i][j] == '1'){
dfs(grid, i, j);
ans++;
}
}
}
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
32class Solution {
public:
int dfs(vector<vector<int>>& grid, int x, int y){
grid[x][y] = 0;
int m = grid.size(), n = grid[0].size();
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int ans = 1;
for(int i = 0; i < 4; i++){
for(int j = 0; j < 4; j++){
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 & nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1){
ans += dfs(grid, nx, ny);
}
}
}
return ans;
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
int ans = 0;
int m = grid.size(), n = grid[0].size();
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if (grid[i][j] == 1){
ans = max(ans, dfs(grid, i, j));
}
}
}
return ans;
}
};接雨水
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public:
int maxArea(vector<int>& height) {
int l = 0, r = height.size() - 1;
int ans = 0;
while (l < r) { // 双指针向内部移动，面积为两边的最短高度乘以宽度
int area = min(height[l], height[r]) * (r - l);
ans = max(ans, area);
if (height[l] < height[r]) { l++; }
else { r--; }
}
return ans;
}
};动态规划求解，盛水的容量=两边最高柱子高度-当前柱子的高度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution {
public:
int trap(vector<int>& height) {
const int N = height.size();
vector<int> leftMax(N, 0);
vector<int> rightMax(, 0);
leftMax[0] = height[0];
for (int i = 1; i < N; i++) { leftMax[i] = max(leftMax[i - 1], height[i]);}
rightMax[N - 1] = height[N - 1];
for (int i = N - 2; i >= 0; i--) { rightMax[i] = max(rightMax[i + 1], height[i]); }
int ans = 0;
for (int i = 0; i < N; i++) { ans += min(leftMax[i], rightMax[i]) - height[i]; }
return ans;
}
};打家劫舍
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public:
int rob(vector<int>& nums) {
if (nums.size() == 0) return 0;
if (nums.size() == 1) return nums[0];
vector<int> dp(nums.size());
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < nums.size(); i++) {
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[nums.size() - 1];
}
};测试结果
只需要考虑三种情况，1. 不包含首尾 2. 包含首元素 3. 包含尾元素。 2和3会包含一，只需要考虑后面两种即可ß
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution {
public:
int robRange(vector<int>& nums, int l, int r) {
if ( l >= r) return nums[l];
const int N = nums.size();
vector<int> dp(N);
dp[l] = nums[l];
dp[l+1] = max(nums[l], nums[l+1]);
for (int i = l + 2; i <= r; i++) {
dp[i] = max(dp[i-2] + nums[i], dp[i-1]);
}
return dp[r];
}
int rob(vector<int>& nums) {
if (nums.size() == 0) return 0;
if (nums.size() == 1) return nums[0];
int result1 = robRange(nums, 0, nums.size() - 2);
int result2 = robRange(nums, 1, nums.size() -1);
return max(result1, result2);
}
};