当前位置：首页 > news >正文

刷题训练之栈

news 2024/9/22 1:47:07

> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。

> 目标：熟练掌握字符串算法。

> 毒鸡汤：学习，学习，再学习 ! 学，然后知不足。

> 专栏选自：刷题训练营

> 望小伙伴们点赞👍收藏✨加关注哟💕💕

🌟前言分析

最早博主续写了牛客网130道题，这块的刷题是让同学们快速进入C语言，而我们学习c++已经有一段时间了，知识储备已经足够了但缺少了实战，面对这块短板博主续写刷题训练，针对性学习，把相似的题目归类，系统的刷题，而我们刷题的官网可以参考：

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推，求职就业一站解决_牛客网

⭐知识讲解

基本思想：

采用模拟

🌙topic-->1

题目链接：5. - 力扣（LeetCode）

题目分析：

给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

算法原理：

解法：采用栈模拟

图解：

代码演示：

class Solution {
public:string removeDuplicates(string s) {string ret; // 搞⼀个数组，模拟栈结构即可for (auto ch : s) {if (ret.size() && ch == ret.back())ret.pop_back(); // 出栈elseret += ch; // ⼊栈}return ret;}
};

🌙topic-->2

题目链接：6. - 力扣（LeetCode）

题目分析：

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

算法原理：

解法：采用栈模拟

图解：

代码演示：

class Solution {
public:bool backspaceCompare(string s, string t) {return changeStr(s) == changeStr(t);}string changeStr(string& s) {string ret; // ⽤数组模拟栈结构for (char ch : s) {if (ch != '#')ret += ch;else {if (ret.size())ret.pop_back();}}return ret;}
};

🌙topic-->3

题目链接：7. - 力扣（LeetCode）

题目分析：

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

算法原理：

解法：采用栈模拟

图解：

代码演示：

class Solution {
public:int calculate(string s) {vector<int> st; // ⽤数组来模拟栈结构int i = 0, n = s.size();char op = '+';while (i < n) {if (s[i] == ' ')i++;else if (s[i] >= '0' && s[i] <= '9') {// 先把这个数字给提取出来int tmp = 0;while (i < n && s[i] >= '0' && s[i] <= '9')tmp = tmp * 10 + (s[i++] - '0');if (op == '+')st.push_back(tmp);else if (op == '-')st.push_back(-tmp);else if (op == '*')st.back() *= tmp;elsest.back() /= tmp;} else {op = s[i];i++;}}int ret = 0;for (auto x : st)ret += x;return ret;}
};

🌙topic-->4

题目链接：8. - 力扣（LeetCode）

题目分析：

给定一个经过编码的字符串，返回它解码后的字符串。

算法原理：

解法：采用栈模拟

图解：

代码演示：

class Solution {
public:string decodeString(string s) {stack<int> nums;stack<string> st;st.push("");int i = 0, n = s.size();while (i < n) {if (s[i] >= '0' && s[i] <= '9') {int tmp = 0;while (s[i] >= '0' && s[i] <= '9') {tmp = tmp * 10 + (s[i] - '0');i++;}nums.push(tmp);} else if (s[i] == '[') {i++; // 把括号后⾯的字符串提取出来string tmp = "";while (s[i] >= 'a' && s[i] <= 'z') {tmp += s[i];i++;}st.push(tmp);} else if (s[i] == ']') {string tmp = st.top();st.pop();int k = nums.top();nums.pop();while (k--) {st.top() += tmp;}i++; // 跳过这个右括号} else {string tmp;while (i < n && s[i] >= 'a' && s[i] <= 'z') {tmp += s[i];i++;}st.top() += tmp;}}return st.top();}
};

🌙topic-->5

题目链接：5. - 力扣（LeetCode）

题目分析：

给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。

算法原理：

解法：采用栈模拟

图解：

代码演示：

class Solution {
public:bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {stack<int> st;int i = 0, n = popped.size();for (auto x : pushed) {st.push(x);while (st.size() && st.top() == popped[i]) {st.pop();i++;}}return i == n;}
};