【Weekly Algorithm】算法周记之《代码随想录》栈与队列与二叉树（一）
学习小结
本周跟随《代码随想录》学习栈与队列和二叉树遍历的一部分，学到了栈和队列在算法中的应用，以及优先级队列的使用；此外还有二叉树的前中后序的递归、迭代、统一迭代方法。
栈与队列
用栈实现队列
- 代码随想录 (programmercarl.com)
- 题意就是用栈实现队列的一部分功能
- 核心就是通过两栈，一个管输入，一个管输出，输出空了时，执行输出操作需从输入中把数字倒入输出的栈中
- 陆爻齐参考代码随想录思路的解法
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
44class MyQueue {
public:
stack<int> in;
stack<int> out;
MyQueue() {
}
void push(int x) {
in.push(x);
}
int pop() {
int num = this->peek();
out.pop();
return num;
}
int peek() {
// 这个判空很重要，意味着如果在两次push中有pop，下次pop不会得到刚push进去的数字，而是按队列下去
if (out.empty()) {
while(!in.empty()) {
out.push(in.top());
in.pop();
}
}
return out.top();
}
bool empty() {
return in.empty() && out.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();
*/
用队列实现栈
- 代码随想录 (programmercarl.com)
- 如题，用队列实现栈，强调是单向队列
- 乍一看，还想用 [[用栈实现队列]] 的方法，两个队列，一个模拟输入，一个模拟输出，但其实不行，因为队列先进先出，不会改变输入顺序，另一个队列只能起到备份作用，甚至乎，只要一个队列就行，在 pop（）时先获取队列长度 size，把前面 size-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
47class MyStack {
public:
queue<int> q;
queue<int> backup;
MyStack() {
}
void push(int x) {
q.push(x);
}
int pop() {
// 备份
while(q.size() > 1) {
backup.push(q.front());
q.pop();
}
int top = q.front();
q.pop();
// 恢复
while (!backup.empty()) {
q.push(backup.front());
backup.pop();
}
return top;
}
int top() {
int top = this->pop();
this->push(top);
return top;
}
bool empty() {
return q.empty();
}
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/
有效的括号
- 代码随想录 (programmercarl.com)
- 题意是给一个只有小中大括号的字符串，判断其是否正确地两两匹配
- 方法是利用栈，若两两匹配则弹出，后面的判断陆爻齐简单地判断栈是否空作为结果，毕竟陆爻齐是把无法匹配的括号也放进去了，代码随想录则分别判断了情况并处理，更为周全
- 陆爻齐的解法
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
38class Solution {
public:
stack<char> rec;
bool isValid(string s) {
if (s.size() % 2 != 0) return false;
for (auto c : s) {
char top_c = get_top();
// 匹配成功则弹栈，否则压栈
if ((c == ')' && '(' == top_c) ||
(c == ']' && '[' == top_c) ||
(c == '}' && '{' == top_c)) {
rec.pop();
}
else {
rec.push(c);
}
}
/*
if (rec.empty()) {
return true;
}
else {
return false;
}*/
// 若全部匹配成功，则有效
return rec.empty();
}
inline char get_top() {
if (!rec.empty()) {
return rec.top();
}
return ' ';
}
}; - 代码随想录的解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
bool isValid(string s) {
if (s.size() % 2 != 0) return false; // 如果s的长度为奇数，一定不符合要求
stack<char> st;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(') st.push(')');
else if (s[i] == '{') st.push('}');
else if (s[i] == '[') st.push(']');
// 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false
// 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以return false
else if (st.empty() || st.top() != s[i]) return false;
else st.pop(); // st.top() 与 s[i]相等，栈弹出元素
}
// 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false，否则就return true
return st.empty();
}
};
删除字符串中的所有相邻重复项
- 代码随想录 (programmercarl.com)
- 如题，比如“abbaac”，先去 “bb”，得 “aaac”，再去 “aa”，得 “ac”。
- 方法就是用栈，来了与栈顶相同的字符就弹栈，否则压栈
- 陆爻齐参考代码随想录思路的解法
1 | class Solution { |
逆波兰表达式求值
- 代码随想录 (programmercarl.com)
- 题意，就是对后缀表达式计算求值，比如 [“2”, “1”, “+”, “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
25class Solution {
public:
int evalRPN(vector<string>& tokens) {
// 力扣修改了后台测试数据，需要用longlong
stack<long long> st;
for (int i = 0; i < tokens.size(); i++) {
if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
long long num1 = st.top();
st.pop();
long long num2 = st.top();
st.pop();
if (tokens[i] == "+") st.push(num2 + num1);
if (tokens[i] == "-") st.push(num2 - num1);
if (tokens[i] == "*") st.push(num2 * num1);
if (tokens[i] == "/") st.push(num2 / num1);
} else {
st.push(stoll(tokens[i]));
}
}
int result = st.top();
st.pop(); // 把栈里最后一个元素弹出（其实不弹出也没事）
return result;
}
}; - 陆爻齐，判断少一次
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> s;
for (auto c : tokens) {
if (c == "+") {
int top1 = s.top();
s.pop();
int top2 = s.top();
s.pop();
s.push(top1 + top2);
}
else if (c == "-") {
int top1 = s.top();
s.pop();
int top2 = s.top();
s.pop();
s.push(top2 - top1);
}
else if (c == "*") {
int top1 = s.top();
s.pop();
int top2 = s.top();
s.pop();
s.push(top1 * top2);
}
else if (c == "/") {
int top1 = s.top();
s.pop();
int top2 = s.top();
s.pop();
s.push(top2 / top1);
}
else {
s.push(stoi(c));
}
}
return s.top();
}
};
滑动窗口最大值
- 代码随想录 (programmercarl.com)
- 题意，设定一个窗口大小，然后在 vector 上从左向右滑动，每次都计算一次窗口内最大值并保存
- 方法，最简单的暴力解法，O(n^2)，每次窗口都遍历下窗口内；想让时间复杂度变 O(n)，就需要一个叫做单调队列的数据结构，该队列保证内部数值按降序或升序排列，在 C++ 无标准库实现，本题中可让其按降序，每次找最大值仅需取 front 即可
- PS: 单调队列实现不唯一，本题只看最大值，故把较小的数值直接弹栈，不做保存
- 陆爻齐参考代码随想录思路的解法
1 | class Solution { |
前K个高频元素
题意就是给一个整型数组，要求给出其中出现频率最高的前 K 个元素
最直观的解法，就是用 map 记录频率，导入 vector 再用快速排序，但这么做时间复杂度就达到了 O(n*logn)，还有没有更快的方法呢？
这里就要引入优先级队列，在[[滑动窗口最大值]]其实就有所应用，这次不止要最大值，因此那次实现的优先级队列不好直接应用。
优先级队列在 C++ 的 STL 中就有实现，priority_queue，本质为堆，默认大顶堆。和
虽然直观上使用大顶堆来保存前 K 个元素比较合适，但是在本题中使用小顶堆更好，因为小顶堆意味着每次 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
26
27
28
29
30
31
32
33
34
35
36
37class Solution {
public:
// 自定义排序
class my_compare {
public:
bool operator() (const pair<int,int> &l, const pair<int,int> &r) {
return l.second > r.second;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
// 统计所有数字的频率
unordered_map<int, int> rec;
for (auto i : nums) {
rec[i]++;
}
// 小顶堆
priority_queue<pair<int,int>, vector<pair<int,int>>, my_compare> pri_que;
for (unordered_map<int,int>::iterator it = rec.begin(); it != rec.end(); it++) {
pri_que.push(*it);
// 对于小顶堆，总是保持非降序，故加入元素后弹出最小即可保持前 k 个最高频次元素
if (pri_que.size() > k) {
pri_que.pop();
}
}
vector<int> result(k);
for (int i = k-1; i >= 0; i--) {
result[i] = pri_que.top().first;
pri_que.pop();
}
return result;
}
};
二叉树
二叉树的递归遍历
- 代码随想录 (programmercarl.com)
- 如题，用递归的方式完成二叉树的遍历
- 本题更多的是引入递归的写法，首先确认递归的参数和返回值，然后定好终止条件，最后写好单层递归逻辑
- 本质上不同的是输出结果的顺序，前序时，先输出结果再遍历，中序时输出结果再遍历之间，后序时输出结果在遍历后
- 前序遍历：中序遍历：
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/**
* 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> result;
vector<int> preorderTraversal(TreeNode* root) {
pre_val(root);
return result;
}
void pre_val(TreeNode* n) {
if (n == nullptr) return;
result.push_back(n->val);
pre_val(n->left);
pre_val(n->right);
}
};后序遍历：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/**
* 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> result;
vector<int> inorderTraversal(TreeNode* root) {
mid_val(root);
return result;
}
void mid_val(TreeNode *n) {
if (n == nullptr) return;
mid_val(n->left);
result.push_back(n->val);
mid_val(n->right);
}
};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/**
* 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> result;
vector<int> postorderTraversal(TreeNode* root) {
back_val(root);
return result;
}
void back_val(TreeNode *root) {
if (root == nullptr) return;
back_val(root->left);
back_val(root->right);
result.push_back(root->val);
}
};
二叉树的迭代遍历
如题，要用迭代的方式来解决遍历二叉树的问题
不同于递归遍历的简洁明了，迭代方式需要用栈来模拟递归的方式
前序遍历则简单点，由于搜寻的点就是马上要处理的点，但中序遍历则要分两部分，一部分是一味地搜寻左子树，另一部分开始处理栈积攒的点并切换到右子树；后序遍历则把前序遍历的 “中右左” 换成 “中左右” 再反转成 “右左中” 即可
前序遍历
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:
vector<int> result;
vector<int> preorderTraversal(TreeNode* root) {
TreeNode *p = root;
stack<TreeNode*> rec;
if(root != nullptr) rec.push(root);
while(!rec.empty()) {
p = rec.top();
rec.pop();
result.push_back(p->val);
// 由于是栈，所以先入右，就会有遍历时先左后右的效果
if (p->right != nullptr) rec.push(p->right);
if (p->left != nullptr) rec.push(p->left);
}
return result;
}
};中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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> result;
vector<int> inorderTraversal(TreeNode* root) {
TreeNode *cur = root;
stack<TreeNode *> rec;
while (cur!= nullptr || !rec.empty()) {
if (cur != NULL) {
rec.push(cur);
cur = cur->left;
}
else {
cur = rec.top();
rec.pop();
result.push_back(cur->val);
cur = cur->right;
}
}
return result;
}
};后序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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> result;
vector<int> postorderTraversal(TreeNode* root) {
TreeNode *cur = root;
stack<TreeNode*> rec;
if (cur != nullptr) rec.push(cur);
while(!rec.empty()) {
cur = rec.top();
rec.pop();
result.push_back(cur->val);
if (cur->left != nullptr) rec.push(cur->left);
if (cur->right != nullptr) rec.push(cur->right);
}
reverse(result.begin(), result.end());
return result;
}
};
二叉树的统一迭代遍历法
- 代码随想录 (programmercarl.com)
- 如题，就是用类似递归那样可比较通用的迭代遍历法
- 方法就是在压栈遍历过的节点时，再压入一个空指针，遍历到空指针就意味着要输出这个值了
- 前序遍历中序遍历
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:
vector<int>result;
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
if (root != nullptr) st.push(root);
while (!st.empty()) {
TreeNode *cur = st.top();
st.pop();
// 给遍历过的点一个标记，即在后面压一个空指针，遍历到则说明该读取了
if (cur != nullptr) {
if (cur->right != nullptr) st.push(cur->right);
if (cur->left != nullptr) st.push(cur->left);
st.push(cur);
st.push(nullptr);
}
else {
cur = st.top();
st.pop();
result.push_back(cur->val);
}
}
return result;
}
};后序遍历1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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> result;
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
if (root != nullptr) st.push(root);
while (!st.empty()) {
TreeNode *cur = st.top();
st.pop();
// 给遍历过的点一个标记，即在后面压一个空指针，遍历到则说明该读取了
if (cur != nullptr) {
if (cur->right != nullptr) st.push(cur->right);
st.push(cur);
st.push(nullptr);
if (cur->left != nullptr) st.push(cur->left);
}
else {
cur = st.top();
st.pop();
result.push_back(cur->val);
}
}
return result;
}
};1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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:
vector<int> result;
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> st;
if (root != nullptr) st.push(root);
while (!st.empty()) {
TreeNode *cur = st.top();
st.pop();
// 给遍历过的点一个标记，即在后面压一个空指针，遍历到则说明该读取了
if (cur != nullptr) {
st.push(cur);
st.push(nullptr);
if (cur->right != nullptr) st.push(cur->right);
if (cur->left != nullptr) st.push(cur->left);
}
else {
cur = st.top();
st.pop();
result.push_back(cur->val);
}
}
return result;
}
};
本博客所有文章除特别声明外，均采用 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>...
系列文章