【Weekly Algorithm】算法周记之《代码随想录》二叉树（二）
学习小结
本周跟随《代码随想录》学习二叉树的层序遍历，以及对于二叉树的翻转、对称，深度问题等。
二叉树
二叉树的层序遍历
- 代码随想录 (programmercarl.com)
- 102. 二叉树的层序遍历 - 力扣（LeetCode）
- 题意就是一层层地从左到右遍历二叉树
- 方法就是利用队列，把一层层排进去，一层层遍历，陆爻齐用两个队列实现这个操作，不过通过 for 循环，其实只要一个队列就行
- 陆爻齐的解法代码随想录的解法
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/**
* 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) {
vector<vector<int>> result;
queue<TreeNode*> rec; // 记录当前要遍历的层
if (root != nullptr) rec.push(root);
while(!rec.empty()) {
vector<int> rec_val;
queue<TreeNode*> rec_nextlevel;
// 遍历一层
while(!rec.empty()) {
TreeNode *cur = rec.front();
rec.pop();
if (cur->left != nullptr) rec_nextlevel.push(cur->left); // 存储下一层
if (cur->right != nullptr) rec_nextlevel.push(cur->right);
rec_val.push_back(cur->val); // 记录当前层遍历的数值
}
result.push_back(rec_val); // 记录一层
rec = rec_nextlevel; // 准备遍历下一层
}
return result;
}
};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) {
queue<TreeNode*> que;
if (root != NULL) que.push(root);
vector<vector<int>> result;
while (!que.empty()) {
int size = que.size();
vector<int> vec;
// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
result.push_back(vec);
}
return result;
}
}; 二叉树的层次遍历 II
- 107. 二叉树的层序遍历 II - 力扣（LeetCode）
- 题意，在层序遍历的基础上，要求从下向上遍历
- 方法，在层序遍历后，把结果翻转下就可以了
- 陆爻齐的解法（和代码随想录差不多）
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/**
* 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>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> result;
queue<TreeNode*> rec; // 记录当前要遍历的层
if (root != nullptr) rec.push(root);
while(!rec.empty()) {
vector<int> rec_val;
queue<TreeNode*> rec_nextlevel;
// 遍历一层
while(!rec.empty()) {
TreeNode *cur = rec.front();
rec.pop();
if (cur->left != nullptr) rec_nextlevel.push(cur->left); // 存储下一层
if (cur->right != nullptr) rec_nextlevel.push(cur->right);
rec_val.push_back(cur->val); // 记录当前层遍历的数值
}
result.push_back(rec_val); // 记录一层
rec = rec_nextlevel; // 准备遍历下一层
}
reverse(result.begin(),result.end());
return result;
}
}; 二叉树的右视图
- 199. 二叉树的右视图 - 力扣（LeetCode）
- 题意，要求输出一个二叉树右边看到的第一层数值，从上往下
- 方法，层序遍历时，只保留最后一个值即可
- 陆爻齐的解法（代码随想录也差不多）
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/**
* 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) {
vector<int> result;
queue<TreeNode*> rec; // 记录当前要遍历的层
if (root != nullptr) rec.push(root);
while(!rec.empty()) {
vector<int> rec_val;
queue<TreeNode*> rec_nextlevel;
// 遍历一层
while(!rec.empty()) {
TreeNode *cur = rec.front();
rec.pop();
if (cur->left != nullptr) rec_nextlevel.push(cur->left); // 存储下一层
if (cur->right != nullptr) rec_nextlevel.push(cur->right);
rec_val.push_back(cur->val); // 记录当前层遍历的数值
}
result.push_back(rec_val.back()); // 记录一层的最后一个
rec = rec_nextlevel; // 准备遍历下一层
}
return result;
}
}; 二叉树的层平均值
- 637. 二叉树的层平均值 - 力扣（LeetCode）
- 题意，即求每一层的均值
- 方法，层序遍历基础上，记录每层均值保存即可
- 陆爻齐解法（和代码随想录差不多）
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/**
* 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<double> averageOfLevels(TreeNode* root) {
vector<double> result;
queue<TreeNode*> rec; // 记录当前要遍历的层
if (root != nullptr) rec.push(root);
while(!rec.empty()) {
vector<int> rec_val;
queue<TreeNode*> rec_nextlevel;
double sum = 0;
double count = 0;
// 遍历一层
while(!rec.empty()) {
TreeNode *cur = rec.front();
rec.pop();
if (cur->left != nullptr) rec_nextlevel.push(cur->left); // 存储下一层
if (cur->right != nullptr) rec_nextlevel.push(cur->right);
//rec_val.push_back(cur->val); // 记录当前层遍历的数值
sum += cur->val;
count++;
}
result.push_back(sum / count); // 记录一层
rec = rec_nextlevel; // 准备遍历下一层
}
return result;
}
}; N 叉树的层序遍历
- 题意，如题
- 方法，把普通二叉树的层序遍历，中下一层的添加，换成遍历其孩子就行
- 陆爻齐的解法（和代码随想录相近）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> result;
queue<Node*> rec; // 记录当前要遍历的层
if (root != nullptr) rec.push(root);
while(!rec.empty()) {
vector<int> rec_val;
queue<Node*> rec_nextlevel;
// 遍历一层
while(!rec.empty()) {
Node *cur = rec.front();
rec.pop();
// 存储下一层
for (Node *tmp : cur->children) {
if (tmp != nullptr) {
rec_nextlevel.push(tmp);
}
}
rec_val.push_back(cur->val); // 记录当前层遍历的数值
}
result.push_back(rec_val); // 记录一层
rec = rec_nextlevel; // 准备遍历下一层
}
return result;
}
}; 在每个树行中找最大值
- 515. 在每个树行中找最大值 - 力扣（LeetCode）
- 题意，找出二叉树中每层的最大值
- 方法，就是在层序遍历的基础上，去记录每层的最大值
- 陆爻齐的解法（与代码随想录差不多）
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/**
* 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> largestValues(TreeNode* root) {
vector<int> result;
queue<TreeNode*> rec; // 记录当前要遍历的层
if (root != nullptr) rec.push(root);
while(!rec.empty()) {
vector<int> rec_val;
queue<TreeNode*> rec_nextlevel;
int max_num = INT32_MIN;
// 遍历一层
while(!rec.empty()) {
TreeNode *cur = rec.front();
rec.pop();
if (cur->left != nullptr) rec_nextlevel.push(cur->left); // 存储下一层
if (cur->right != nullptr) rec_nextlevel.push(cur->right);
//rec_val.push_back(cur->val); // 记录当前层遍历的数值
if (cur->val > max_num) {
max_num = cur->val;
}
}
result.push_back(max_num); // 记录一层
rec = rec_nextlevel; // 准备遍历下一层
}
return result;
}
}; 填充每个节点的下一个右侧节点指针
- 116. 填充每个节点的下一个右侧节点指针 - 力扣（LeetCode）
- 题意，让二叉树的每个节点都指向其右侧节点，无则指空
- 方法，在层序遍历中，取点让其指右即可，代码随想录中用 for 循环看着挺复杂的样子，其实只是他专门区分了第一个点和其它点
- 陆爻齐的解法（这次和代码随想录有点差别）代码随想录的解法
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/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;
Node() : val(0), left(NULL), right(NULL), next(NULL) {}
Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
Node(int _val, Node* _left, Node* _right, Node* _next)
: val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
public:
Node* connect(Node* root) {
//vector<vector<int>> result;
queue<Node*> rec; // 记录当前要遍历的层
if (root != nullptr) rec.push(root);
while(!rec.empty()) {
vector<int> rec_val;
queue<Node*> rec_nextlevel;
// 遍历一层
while(!rec.empty()) {
Node *cur = rec.front();
rec.pop();
if (cur->left != nullptr) rec_nextlevel.push(cur->left); // 存储下一层
if (cur->right != nullptr) rec_nextlevel.push(cur->right);
rec_val.push_back(cur->val); // 记录当前层遍历的数值
// 让每个节点指右边（无则指空）
if (!rec.empty()) {
cur->next = rec.front();
}
else {
cur->next = nullptr;
}
}
//result.push_back(rec_val); // 记录一层
rec = rec_nextlevel; // 准备遍历下一层
}
return 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
30class Solution {
public:
Node* connect(Node* root) {
queue<Node*> que;
if (root != NULL) que.push(root);
while (!que.empty()) {
int size = que.size();
// vector<int> vec;
Node* nodePre;
Node* node;
for (int i = 0; i < size; i++) {
if (i == 0) {
nodePre = que.front(); // 取出一层的头结点
que.pop();
node = nodePre;
} else {
node = que.front();
que.pop();
nodePre->next = node; // 本层前一个节点next指向本节点
nodePre = nodePre->next;
}
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
nodePre->next = NULL; // 本层最后一个节点指向NULL
}
return root;
}
}; 填充每个节点的下一个右侧节点指针II
- 题意，和上一题差不多，不过面对的二叉树不是完美二叉树
- 方法，和上一题一样，不知此题有何意义
- 解法略，同上
二叉树的最大深度
- 题意，即找出二叉树的根节点与其最远叶节点的距离
- 方法，层序遍历时，记录层数即可
- 陆爻齐的解法（和代码随想录差不多）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40/**
* 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) {
int depth = 0;
queue<TreeNode*> rec; // 记录当前要遍历的层
if (root != nullptr) {
rec.push(root);
}
while(!rec.empty()) {
vector<int> rec_val;
queue<TreeNode*> rec_nextlevel;
depth++;
// 遍历一层
while(!rec.empty()) {
TreeNode *cur = rec.front();
rec.pop();
if (cur->left != nullptr) rec_nextlevel.push(cur->left); // 存储下一层
if (cur->right != nullptr) rec_nextlevel.push(cur->right);
}
rec = rec_nextlevel; // 准备遍历下一层
}
return depth;
}
}; 二叉树的最小深度
- 111. 二叉树的最小深度 - 力扣（LeetCode）
- 题目要求，找到最小深度，即第一个叶子节点出现的层数
- 方法，每个点检测下，若是叶子节点，则返回当前层数，代码随想录的解法相对陆爻齐的解法重复检测孩子是否为空，陆爻齐 win ：）
- 陆爻齐的解法代码随想录的解法
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/**
* 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 minDepth(TreeNode* root) {
int depth = 0;
queue<TreeNode*> rec; // 记录当前要遍历的层
if (root != nullptr) {
rec.push(root);
}
while(!rec.empty()) {
vector<int> rec_val;
queue<TreeNode*> rec_nextlevel;
depth++;
// 遍历一层
while(!rec.empty()) {
TreeNode *cur = rec.front();
rec.pop();
int count = 0; // 记录有无孩子
// 存储下一层
if (cur->left != nullptr) {
rec_nextlevel.push(cur->left);
count++;
}
if (cur->right != nullptr) {
rec_nextlevel.push(cur->right);
count++;
}
// 找到了第一个叶子节点
if (count == 0) {
return depth;
}
}
rec = rec_nextlevel; // 准备遍历下一层
}
return depth;
}
};1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public:
int minDepth(TreeNode* root) {
if (root == NULL) return 0;
int depth = 0;
queue<TreeNode*> que;
que.push(root);
while(!que.empty()) {
int size = que.size();
depth++; // 记录最小深度
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
if (!node->left && !node->right) { // 当左右孩子都为空的时候，说明是最低点的一层了，退出
return depth;
}
}
}
return depth;
}
};
翻转二叉树
- 代码随想录
- 226. 翻转二叉树 - 力扣（LeetCode）
- 题意，把整个二叉树左右翻转
- 方法，其实把每个节点的左右子树交换即可
- 陆爻齐的方法（类似前序）代码随想录补充的类中序方法
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 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 == nullptr) return root;
// 交换左右子树
TreeNode *tmp = root->left;
root->left = root->right;
root->right = tmp;
// 递归翻转
if (root->left != nullptr) invertTree(root->left);
if (root->right != nullptr) invertTree(root->right);
return root;
}
};1
2
3
4
5
6
7
8
9
10class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return root;
invertTree(root->left); // 左
swap(root->left, root->right); // 中
invertTree(root->left); // 注意 这里依然要遍历左孩子，因为中间节点已经翻转了
return root;
}
};
对称二叉树
- 代码随想录
- 101. 对称二叉树 - 力扣（LeetCode）
- 题意，判断二叉树是否沿中间水平对称
- 方法，注意不是判断一个节点的左右子树是否相等，而是判断左子树的右子树与右子树的左子树以及左子树的左子树和右子树的右子树是否相等。
- 陆爻齐参照代码随想录的解法
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() : 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 isSymmetric(TreeNode* root) {
if (root == nullptr) return true;
return compare(root->left, root->right);
}
bool compare(TreeNode *left, TreeNode *right) {
// 判断两节点是否空的相同情况或值不同的情况
if (left == nullptr && right == nullptr) return true;
else if (left != nullptr && right == nullptr) return false;
else if (left == nullptr && right != nullptr) return false;
else if (left->val != right->val) return false;
// 剩下已是两个节点存在且数值相同，因此要判断他们子树情况
bool inSide = compare(left->right, right->left);
bool outSide = compare(left->left, right->right);
bool isSame = inSide && outSide;
return isSame;
}
};
浅谈二叉树的深度和高度
二叉树的深度指根节点到叶子节点的最大距离，计算时相当于从上往下，1、2、3……这么数；
二叉树的高度，指一个节点到叶子节点的最大距离，计算时相当于从下往上数
易得，深度适合用前序遍历，而高度适合用后序遍历
根节点的高度就是二叉树的深度
二叉树的最大深度
- 104. 二叉树的最大深度 - 力扣（LeetCode）
- 题意，即求根节点到叶节点的最长距离
- 方法，此题在[[二叉树的层序遍历]]有所描述，用层序遍历即可解决，但这里再介绍下递归方法
- 陆爻齐参照代码随想录的解法
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:
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
int left_depth = maxDepth(root->left);
int right_depth = maxDepth(root->right);
int max_depth = max(left_depth,right_depth);
return 1+max_depth;
}
};
N 叉树的最大深度
- 题意，求 N 叉树的最大深度
- 方法，和上题类似，只要把遍历孩子时用循环遍历完即可
- 陆爻齐的解法（和代码随想录类似）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
int max_depth = 0;
int maxDepth(Node* root) {
search_depth(root, 0);
return max_depth;
}
void search_depth(Node *root, int depth) {
if (root == nullptr) return;
depth++; // 当前层非零，深度加一
// 遍历孩子，算 DFS
for (Node *child : root->children) {
search_depth(child, depth);
}
// 更新层数
if (depth > max_depth) {
max_depth = depth;
}
}
};
二叉树的最小深度
- 代码随想录
- 111. 二叉树的最小深度 - 力扣（LeetCode）
- 题意：求二叉树的最小深度，最小深度就是根节点到叶子节点（无左子树和右子树的节点）
- 方法：也可用层序遍历解决，[[二叉树的层序遍历]]，这里也要介绍下递归方法，与[[二叉树的最大深度]]有些许差别，在于对待非叶子节点的方式需要单独设置，尤其是有一侧空的节点，只要另一侧的深度即可
- 陆爻齐参考代码随想录的解法
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:
int minDepth(TreeNode* root) {
return getDepth(root);
}
int getDepth(TreeNode *root) {
if (root == nullptr) return 0;
int left_depth = getDepth(root->left);
int right_depth = getDepth(root->right);
// 对于有一个点位空的点，不算叶节点，故只传另一侧的深度
if (left_depth == 0 && right_depth > 0) return 1 + right_depth;
if(left_depth > 0 && right_depth == 0) return 1 + left_depth;
int min_depth = min(left_depth, right_depth);
return 1 + min_depth; // 加上本层的点（+1）
}
};
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 LuYaoQi's Blogs！
相关推荐
2024-11-17
【Weekly Algorithm】算法周记之《代码随想录》动态规划（一）
学习小结本周跟随《代码随想录》开始学习动态规划的相关题目，从基础的斐波那契数到爬楼梯，再到 01 背包问题，慢慢熟悉动态规划的五步法。《代码随想录》还提醒，调试重点是检查递推公式是否举例，检查打印 dp 数组是否和自己设想一致。 分析 dp 数组及其下标含义 确定递推公式 确定 dp 数组初始化 确定遍历顺序 举例分析 dp 数组是否如所想迭代 此外除了寻常的二维数组动态规划，也尝试做滚动数组的练习。 动态规划 斐波那契数 题意，给一个数字 n，求斐波那契数中的第 n 个数 方法，虽然就算不看代码随想录也能轻易写出，但简单题的重点在于熟悉套路方法，下面按五步分析 确定 dp 数组及其下标含义，这里的 dp[i] 代表斐波那契数中的第 i 个数 确认递推公式，题目给出 dp[i]=dp[i-1]+dp[i-2] dp 数组初始化，题目也给出dp[0]=0;dp[1]=1; 确定遍历顺序，从递推公式可见，就是从前向后（0-n）遍历 举例推导 dp 公式，0 1 1 2 3 5 8 13 21 …… 陆爻齐的解 1234567891011121314class...
2024-11-24
【Weekly Algorithm】算法周记之《代码随想录》动态规划（二）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，由于期末月的到来，以及题目难度的增加，暂且将动态规划的学习进度放慢一点。下面继续巩固五步法。 分析 dp 数组及其下标含义 确定递推公式 确定 dp 数组初始化 确定遍历顺序 举例分析 dp 数组是否如所想迭代 只能感叹，这动态规划真是一百道题才入门啊。 动态规划 分割等和子集 代码随想录 416. 分割等和子集 - 力扣（LeetCode） 题意，给一个数组，返回判断该数组是否能平分为和相等的两部分 方法，直觉上，可以用回溯遍历树，找到那个子节点，但复杂度太高。本题其实就是 01 背包的应用，nums[i] 本身，是物品，重量，以及价值。数组能否平分和的本质，就是平分和的大小的背包能否被刚好装满，也就是下标与值相等。 参考代码随想录思路的代码 1234567891011121314151617class Solution {public: bool canPartition(vector<int>& nums) { int sum =...
2024-12-01
【Weekly Algorithm】算法周记之《代码随想录》动态规划（三）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，主要是完全背包的入门，体会其与 01 背包的不同与关联。 下周两门考试，教务脑子真是进了水，搞这么紧干嘛。 动态规划 完全背包理论 代码随想录 52. 携带研究材料（第七期模拟笔试） 题目，与 [[01背包理论]]的差别在于一个物品可携带多次，求最大价值 方法， dp[j]，在遍历物品时，截止到空间为 j，可装入的最大价值 递推公式，dp[j]=max(dp[j],dp[j-weigh[i]]+val[i]) 初始化，全 0 遍历方向，重点，这是与 01 背包区别最大的地方，01 的滚动数组强调倒序遍历就是为了避免重复，在完全背包中，恰恰需要正序从而利用重复装入物品 举例，…… 参考代码随想录思路的解法 12345678910111213141516171819202122232425262728#include <iostream>#include <vector>using namespace std;int main() { int n, v; ...
2024-12-15
【Weekly Algorithm】算法周记之《代码随想录》动态规划（五）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，本周主要学会了完全背包的应用，多重背包的理论，打劫打家劫舍问题，和股票买卖问题的入门版。认识到了所存储的状态并不只有 整数 这一种形式，还能有多个整数并成的 vector 作为状态使用。 不得不说，动态规划十分的灵活，一百道题入门还不是说说而已啊。 动态规划 完全平方数 代码随想录 279. 完全平方数 - 力扣（LeetCode） 题意，给一个整数 n，求其被完全平方数组成的最小个数。 方法，就是[[零钱兑换II]]的变体，给的零钱变成了自己找小于 n 的完全平方数，背包容量为 n dp[j] 含义为 在背包容量为 j 的情况下，完全平方数的最小组合 递推公式，dp[i]=min(dp[i],dp[i-j*j]+1)，也就是要么保持不变，要么就在已有的组合上加一 初始化，dp[0]=0,这是为了递推公式才这么初始化，也能理解，完全平方数不算...
2025-01-12
【Weekly Algorithm】算法周记之《代码随想录》动态规划（六）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，本周主要学习完买卖股票相关内容，并初步探索子序列的部分。 买卖股票的题有明显的状态转换，但子序列就没那么明显。 动态规划 买卖股票的最佳时机II 代码随想录 122. 买卖股票的最佳时机 II - 力扣（LeetCode） 题意，在[[买卖股票的最佳时机]]的基础上，要求可以多次购买股票，但同一时段只能持有一支股票，也就是再卖出上一支股票前，不允许购入下一支股票。 方法，与[[买卖股票的最佳时机]]的差别，在于考虑购入当前股票时，是在上一支股票考虑购入和卖出的两个情况中取最大，并非直接取历史最便宜股票和当前股票对比。 参考代码随想录思路解法 123456789101112131415161718class Solution {public: int maxProfit(vector<int>& prices) { // dp[i][0] 考虑第i支股票时，考虑买入的情况；dp[i][1] 考虑第i支股票时，卖出的情况 int len =...
2025-02-09
【Weekly Algorithm】算法周记之《代码随想录》单调栈和图论（一）
学习小结本周跟随《代码随想录》学习关于单调栈的知识，同时开启图论。 单调栈通过保持一个栈从栈顶到栈底的递增或是递减序列，来解决找一个元素左/右的“第一个”更大/更小元素。 图论则是初窥dfs的门路，虽然道理一年前早在算法课学过考过，但现在也得复习才能捡回来。 单调栈 每日温度 代码随想录 739. 每日温度 - 力扣（LeetCode） 题意：给一个整数数组，求每个数字右侧比该数字更大的间距 方法：暴力解法就是O(n^2)的遍历。更高效率的方法是使用单调栈，所谓的单调栈就是从栈顶到栈底递增或递减的，如此排列，就能方便找任意元素的左右第一个更大更小的元素。 比如本题是找右边更大的，那么遍历数组时，遇到更小或相等的元素就直接入栈，而遇到更大的元素就弹栈，直到触底或碰到大元素再入栈，其中弹栈的元素就能记录本元素的下标与当时元素下标之差。 参考代码随想录思路的解法 12345678910111213141516171819202122232425class Solution {public: vector<int>...
系列文章