网站导航
> 技术文档 > 每日算法刷题Day50:7.20:leetcode 栈8道题，用时2h30min

每日算法刷题Day50:7.20:leetcode 栈8道题，用时2h30min

网友: 技术文档 2025-07-30 11:41:43

一.基础

1.套路

用字符串来模拟栈:

class Solution {public: string removeStars(string s) { string st; for (auto& ch : s) { // 入栈 if (ch != \'*\') st.push_back(ch); // 栈不为空则出栈 else if (!st.empty()) st.pop_back(); } return st; }};

用列表来模拟栈

class Solution {public: int calPoints(vector& operations) { int n = operations.size(); int res = 0; vector st; for (auto& op : operations) { switch (op[0]) { case \'+\': // 与前两个元素有关 st.push_back(st.back() + st[st.size() - 2]); break; case \'D\': // 与前一个元素有关 st.push_back(st.back() * 2); break; case \'C\': // 出栈 st.pop_back(); break; default: // 转成整数入栈 st.push_back(stoi(op)); } } for (auto& x : st) res += x; return res; }};

显示栈:

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

注意:
1.任何出栈操作前先判断栈不为空
2.string/vector是.push_back(x)和.pop_back(),获取栈顶元素为.back()因为本身是顺序的，
而stack是.push(x)和.pop()，获取栈顶元素为.top()因为只用来出栈和入栈

2.题目描述

1.给你一个数组 target 和一个整数 n。
给你一个空栈和两种操作：

  • \"Push\"：将一个整数加到栈顶。
  • \"Pop\"：从栈顶删除一个整数。
    同时给定一个范围 [1, n] 中的整数流。
    使用两个栈操作使栈中的数字（从底部到顶部）等于 target。你应该遵循以下规则：
  • 如果整数流不为空，从流中选取下一个整数并将其推送到栈顶。
  • 如果栈不为空，弹出栈顶的整数。
  • 如果，在任何时刻，栈中的元素（从底部到顶部）等于 target，则不要从流中读取新的整数，也不要对栈进行更多操作。
    请返回遵循上述规则构建 target 所用的操作序列(答案)。如果存在多个合法答案，返回 任一 即可。
    2.给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
    注意：如果对空文本输入退格字符，文本继续为空。
    3(学习字符串与整数之间的相互转化).你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成，过去几回合的得分可能会影响以后几回合的得分。
    比赛开始时，记录是空白的。你会得到一个记录操作的字符串列表 ops，其中 ops[i] 是你需要记录的第 i 项操作，ops 遵循下述规则：
  1. 整数 x - 表示本回合新获得分数 x
  2. \"+\" - 表示本回合新获得的得分是前两次得分的总和。题目数据保证记录此操作时前面总是存在两个有效的分数。
  3. \"D\" - 表示本回合新获得的得分是前一次得分的两倍。题目数据保证记录此操作时前面总是存在一个有效的分数。
  4. \"C\" - 表示前一次得分无效，将其从记录中移除。题目数据保证记录此操作时前面总是存在一个有效的分数。
    请你返回记录中所有得分的总和(答案)。
    4.给你一个包含若干星号 * 的字符串 s 。
    在一步操作中，你可以：
  • 选中 s 中的一个星号。
  • 移除星号 左侧 最近的那个 非星号 字符，并移除该星号自身。
    返回移除 所有 星号之后的字符串(答案)。
    注意：
  • 生成的输入保证总是可以执行题面中描述的操作。
  • 可以证明结果字符串是唯一的。
    5(学习在动态删除时不能直接用st.size()作为退出条件).你有一个只支持单个标签页的 浏览器 ，最开始你浏览的网页是 homepage ，你可以访问其他的网站 url ，也可以在浏览历史中后退 steps 步或前进 steps 步。
    请你实现 BrowserHistory 类：
  • BrowserHistory(string homepage) ，用 homepage 初始化浏览器类。
  • void visit(string url) 从当前页跳转访问 url 对应的页面  。执行此操作会把浏览历史前进的记录全部删除。
  • string back(int steps) 在浏览历史中后退 steps 步。如果你只能在浏览历史中后退至多 x 步且 steps > x ，那么你只后退 x 步。请返回后退 至多 steps 步以后的 url 。
  • string forward(int steps) 在浏览历史中前进 steps 步。如果你只能在浏览历史中前进至多 x 步且 steps > x ，那么你只前进 x 步。请返回前进 至多 steps步以后的 url 。
    6(学习显式栈模拟).给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false(答案) 。
    7.给你一个字符串 s。
    英文字母中每个字母的 镜像 定义为反转字母表之后对应位置上的字母。例如，\'a\' 的镜像是 \'z\'，\'y\' 的镜像是 \'b\'。
    最初，字符串 s 中的所有字符都 未标记 。
    字符串 s 的初始分数为 0 ，你需要对其执行以下过程：
  • 从左到右遍历字符串。
  • 对于每个下标 i ，找到距离最近的 未标记 下标 j，下标 j 需要满足 j < i 且 s[j] 是 s[i] 的镜像(条件)。然后 标记 下标 i 和 j，总分加上 i - j 的值。
  • 如果对于下标 i，不存在满足条件的下标 j，则跳过该下标，继续处理下一个下标，不需要进行标记。
    返回最终的总分(答案)。
    8(学习istringstream用/分割字符串).给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 \'/\' 开头），请你将其转化为 更加简洁的规范路径。
    在 Unix 风格的文件系统中规则如下：
  • 一个点 \'.\' 表示当前目录本身。
  • 此外，两个点 \'..\' 表示将目录切换到上一级（指向父目录）。
  • 任意多个连续的斜杠（即，\'//\' 或 \'///\'）都被视为单个斜杠 \'/\'。
  • 任何其他格式的点（例如，\'...\' 或 \'....\'）均被视为有效的文件/目录名称。
    返回的 简化路径 必须遵循下述格式：
  • 始终以斜杠 \'/\' 开头。
  • 两个目录名之间必须只有一个斜杠 \'/\' 。
  • 最后一个目录名（如果存在）不能 以 \'/\' 结尾。
  • 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 \'.\' 或 \'..\'）。
    返回简化后得到的 规范路径(答案) 。
3.学习经验

1.用字符串/列表(整数或字符串)/stack来模拟
2.遇到题目当前元素取决于前几个元素/根据当前元素删去前一个元素想到栈
3.任何出栈操作前先判断栈不为空
4.列表获取最后一个元素(栈顶元素)st.back(),更通用的为st[st.size()-1]
5.字符串和数组转化函数stoi,to_string
6.列表的resize(n)方法可以直接保留列表的前n个元素，快速实现删去后面的元素

1. 1441.用栈操作构建数组(中等)

1441. 用栈操作构建数组 - 力扣（LeetCode）

思想

1.给你一个数组 target 和一个整数 n。
给你一个空栈和两种操作：

  • \"Push\"：将一个整数加到栈顶。
  • \"Pop\"：从栈顶删除一个整数。
    同时给定一个范围 [1, n] 中的整数流。
    使用两个栈操作使栈中的数字（从底部到顶部）等于 target。你应该遵循以下规则：
  • 如果整数流不为空，从流中选取下一个整数并将其推送到栈顶。
  • 如果栈不为空，弹出栈顶的整数。
  • 如果，在任何时刻，栈中的元素（从底部到顶部）等于 target，则不要从流中读取新的整数，也不要对栈进行更多操作。
    请返回遵循上述规则构建 target 所用的操作序列。如果存在多个合法答案，返回 任一 即可。
    2.我的想法是遍历整数流，然后维护一个target指针id和栈顶元素topV来模拟栈,最终循环结束结果为id==m,然后按照题目逻辑:
  • (1)字符流进入，Push,更新栈顶元素
  • (2)若栈顶元素不是当前期待的target[id],则Pop,更新栈顶元素(可加可不加)
  • (3)若是期待的，++id,若满足循环结束条件，结束循环
    3.优化:可以遍历target,因为整数流和target都是单调递增的，而target的是跳跃的，整数流式连续的，遍历target更快，需维护target前一个数字pre,对于当前数字now,[pre+1,now)都是不满足条件的，先Push再Pop,然后当前数字now只有Push,然后更新pre,再遍历下一个数字
代码
class Solution {public: vector buildArray(vector& target, int n) { int m = target.size(); int topV = -1; // 栈顶元素 vector res; int id = 0; for (int i = 1; i =0) topV=target[id-1]; // else topV=-1; } else { ++id; if (id == m)  break; } } return res; }};

优化遍历target:

class Solution {public: vector buildArray(vector& target, int n) { int m = target.size(); int pre = 0; // pre+1从1开始,pre从0开始 vector res; for (auto& x : target) { for (int i = pre + 1; i < x; ++i) { res.push_back(\"Push\"); res.push_back(\"Pop\"); } res.push_back(\"Push\"); pre = x; } return res; }};
2. 844.比较含退格的字符串(简单)

844. 比较含退格的字符串 - 力扣（LeetCode）

思想

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

代码
class Solution {public: string build(string str) { string res; for (auto& c : str) { if (c != \'#\') res.push_back(c); else if (!res.empty()) res.pop_back(); } return res; } bool backspaceCompare(string s, string t) { if (build(s) == build(t)) return true; else return false; }};
3. 682.棒球比赛(简单,学习字符串与整数之间的相互转化)

682. 棒球比赛 - 力扣（LeetCode）

思想

1.你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成，过去几回合的得分可能会影响以后几回合的得分。
比赛开始时，记录是空白的。你会得到一个记录操作的字符串列表 ops，其中 ops[i] 是你需要记录的第 i 项操作，ops 遵循下述规则：

  1. 整数 x - 表示本回合新获得分数 x
  2. \"+\" - 表示本回合新获得的得分是前两次得分的总和。题目数据保证记录此操作时前面总是存在两个有效的分数。
  3. \"D\" - 表示本回合新获得的得分是前一次得分的两倍。题目数据保证记录此操作时前面总是存在一个有效的分数。
  4. \"C\" - 表示前一次得分无效，将其从记录中移除。题目数据保证记录此操作时前面总是存在一个有效的分数。
    请你返回记录中所有得分的总和。
    2.用字符串列表vector st来模拟出栈和入栈，但是会面临多次字符串变整数stoi(str)和整数变字符串to_string(num)的操作，效率太慢
    3.优化为整数列表vector st来模拟，只有x时才要字符串变成整数，且用switch更直观
代码

字符串列表

class Solution {public: // stoi,to_string int calPoints(vector& operations) { int n = operations.size(); int res = 0; vector st; for (auto& str : operations) { if (str[0] == \'+\') { if (st.size() >= 2) {  int a = stoi(st[st.size() - 1]);  int b = stoi(st[st.size() - 2]);  int c = a + b;  st.push_back(to_string(c)); } } else if (str[0] == \'D\') { if (st.size() >= 1) {  int a = stoi(st[st.size() - 1]);  int c = 2 * a;  st.push_back(to_string(c)); } } else if (str[0] == \'C\') { if (!st.empty()) {  st.pop_back(); } } else { st.push_back(str); } } for (auto& str : st) { res += stoi(str); } return res; }};

整数列表

class Solution {public: int calPoints(vector& operations) { int n = operations.size(); int res = 0; vector st; for (auto& op : operations) { switch (op[0]) { case \'+\': st.push_back(st.back() + st[st.size() - 2]); break; case \'D\': st.push_back(st.back() * 2); break; case \'C\': st.pop_back(); break; default: st.push_back(stoi(op)); } } for (auto& x : st) res += x; return res; }};
4. 2390.从字符串中移除星号(中等)

2390. 从字符串中移除星号 - 力扣（LeetCode）

思想

1.给你一个包含若干星号 * 的字符串 s 。
在一步操作中，你可以：

  • 选中 s 中的一个星号。
  • 移除星号 左侧 最近的那个 非星号 字符，并移除该星号自身。
    返回移除 所有 星号之后的字符串**。**
    注意：
  • 生成的输入保证总是可以执行题面中描述的操作。
  • 可以证明结果字符串是唯一的。
    2.拿字符串来模拟栈，进行入栈和出栈，字符串string本来就有push_back和pop_back操作
代码
class Solution {public: string removeStars(string s) { string st; for (auto& ch : s) { if (ch != \'*\') st.push_back(ch); else if (!st.empty()) st.pop_back(); } return st; }};
5. 1472.设计浏览器历史记录(中等,学习在动态删除时不能直接用st.size()作为退出条件)

1472. 设计浏览器历史记录 - 力扣（LeetCode）

思想

1.你有一个只支持单个标签页的 浏览器 ，最开始你浏览的网页是 homepage ，你可以访问其他的网站 url ，也可以在浏览历史中后退 steps 步或前进 steps 步。
请你实现 BrowserHistory 类：

  • BrowserHistory(string homepage) ，用 homepage 初始化浏览器类。
  • void visit(string url) 从当前页跳转访问 url 对应的页面  。执行此操作会把浏览历史前进的记录全部删除。
  • string back(int steps) 在浏览历史中后退 steps 步。如果你只能在浏览历史中后退至多 x 步且 steps > x ，那么你只后退 x 步。请返回后退 至多 steps 步以后的 url 。
  • string forward(int steps) 在浏览历史中前进 steps 步。如果你只能在浏览历史中前进至多 x 步且 steps > x ，那么你只前进 x 步。请返回前进 至多 steps步以后的 url 。
    2.用一个id来维护当前位置，字符串列表模拟栈,可以用resize()方法实现把浏览历史前进的记录全部删除
代码
class BrowserHistory {private: vector st; int id = 0; // 当前位置public: BrowserHistory(string homepage) { st.push_back(homepage); id = 0; } void visit(string url) { // [id+1,st.size()) pop int t = st.size(); // 保留原始st.size()值，不然下面写pop后，st.size()在变 for (int i = id + 1; i < t; ++i) { if (!st.empty()) st.pop_back(); } ++id; st.push_back(url); } string back(int steps) { // [0,id] if (id - steps  st.size() - 1) { id = st.size() - 1; } else { id += steps; } return st[id]; }};/** * Your BrowserHistory object will be instantiated and called as such: * BrowserHistory* obj = new BrowserHistory(homepage); * obj->visit(url); * string param_2 = obj->back(steps); * string param_3 = obj->forward(steps); */

visit错误样例:

void visit(string url) {// [id+1,st.size()) pop// st.size()在变for (int i = id + 1; i < st.size(); ++i) {if (!st.empty())st.pop_back();}++id;st.push_back(url);}

visit用resize方法:

void visit(string url) {// [id+1,st.size()) pop++id;st.resize(id);st.push_back(url);}
6. 946.验证栈序列(中等,学习显式栈模拟)

946. 验证栈序列 - 力扣（LeetCode）

思想

1.给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。]
2.可以用一个显式栈模拟pushed入栈，然后栈顶元素等于当前popped[id],则++id,直到不相等为止，最终遍历完pushed判断显式栈为不为空，因为如果不能出栈则显式栈不为空,popped也遍历不到最后

代码

两个指针判断:

class Solution {public: bool validateStackSequences(vector& pushed, vector& popped) { int n = pushed.size(); map mp; // 值,下标 int preId = -1; vector tag(n, false); // 是否出栈 for (int i = 0; i < n; ++i) { mp[pushed[i]] = i; } for (auto& x : popped) { int curId = mp[x]; // 当前出栈元素下标 int t = preId; tag[curId] = true; preId = curId; if (t == -1) { continue; } if (curId < t) { // [curId+1,preId)均出栈 for (int i = curId + 1; i < t; ++i) {  if (!tag[i]) return false; } } } return true; }};

显式栈模拟:

class Solution {public: bool validateStackSequences(vector& pushed, vector& popped) { stack stk; int n = pushed.size(); int id = 0; for (int i = 0; i < n; ++i) { stk.push(pushed[i]); while (!stk.empty() && stk.top() == popped[id]) { stk.pop(); ++id; } } return stk.empty(); }};
7. 3412. 计算字符串的镜像分数(中等)

3412. 计算字符串的镜像分数 - 力扣（LeetCode）

思想

1.给你一个字符串 s。
英文字母中每个字母的 镜像 定义为反转字母表之后对应位置上的字母。例如，\'a\' 的镜像是 \'z\'，\'y\' 的镜像是 \'b\'。
最初，字符串 s 中的所有字符都 未标记 。
字符串 s 的初始分数为 0 ，你需要对其执行以下过程：

  • 从左到右遍历字符串。
  • 对于每个下标 i ，找到距离最近的 未标记 下标 j，下标 j 需要满足 j < i 且 s[j] 是 s[i] 的镜像。然后 标记 下标 i 和 j，总分加上 i - j 的值。
  • 如果对于下标 i，不存在满足条件的下标 j，则跳过该下标，继续处理下一个下标，不需要进行标记。
    返回最终的总分。
    2.难点在于对于每个下标 i ，找到距离最近的 未标记 下标 j，这个是哈希查找，但最难点在于距离最近，所以是后人先出，想到栈，可以用map<int,stack来构造，因为是26个字母，所以可以直接构造26个栈，每个栈维护当前字母的下标
代码
class Solution {public: long long calculateScore(string s) { int n = s.size(); map<int, stack> mp; // 字母,下标栈 long long res = 0; for (int i = 0; i < n; ++i) { int id = s[i] - \'a\'; if (!mp[25 - id].empty()) { res += 1LL * (i - mp[25 - id].top()); mp[25 - id].pop(); } else { mp[id].push(i); } } return res; }};

26个栈

class Solution {public: long long calculateScore(string s) { int n = s.size(); vector<stack> stk(26); long long res = 0; for (int i = 0; i < n; ++i) { int id = s[i] - \'a\'; if (!stk[25 - id].empty()) { res += 1LL * (i - stk[25 - id].top()); stk[25 - id].pop(); } else { stk[id].push(i); } } return res; }};
8. 71. 简化路径(中等,学习istringstream用/分割字符串)

71. 简化路径 - 力扣（LeetCode）

思想

1.给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 \'/\' 开头），请你将其转化为 更加简洁的规范路径。
在 Unix 风格的文件系统中规则如下：

  • 一个点 \'.\' 表示当前目录本身。
  • 此外，两个点 \'..\' 表示将目录切换到上一级（指向父目录）。
  • 任意多个连续的斜杠（即，\'//\' 或 \'///\'）都被视为单个斜杠 \'/\'。
  • 任何其他格式的点（例如，\'...\' 或 \'....\'）均被视为有效的文件/目录名称。
    返回的 简化路径 必须遵循下述格式：
  • 始终以斜杠 \'/\' 开头。
  • 两个目录名之间必须只有一个斜杠 \'/\' 。
  • 最后一个目录名（如果存在）不能 以 \'/\' 结尾。
  • 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 \'.\' 或 \'..\'）。
    返回简化后得到的 规范路径 。
    2.题目意思翻译为给你一组用/分割的字符串(忽略空串和.),从左遍历这些字符串，遇到..则删去左侧的字符串,最终将这些串再用/拼接起来
    3.所以难点就是先得到/分割的字符串，用输入字符流istringstream(path) ss,用path初始化输入字符流,然后while(getline(ss,s,\'/\'))表示遍历这个字符流，一遇到/就把左侧内容赋值给/,然后跳过s，重复此过程，注意:
    (1)/xxx刚开头有个/,所以第一个s=\"\"
    (2)//，这个s=\"\"
代码
class Solution {public: string simplifyPath(string path) { istringstream ss(path); string s; vector stk; while (getline(ss, s, \'/\')) { if (s.empty() || s == \".\") continue; else if (s == \"..\") { if (!stk.empty())  stk.pop_back(); } else stk.push_back(s); } string res; for (auto str : stk) { res += \"/\"; res += str; } if (stk.empty()) return \"/\"; else return res; }};
网络标签：

相关问题