代码随想录算法训练营第九天 | 20. 有效的括号、1047. 删除字符串中的所有相邻重复项、150. 逆波兰表达式求值

2024-01-21 11:44
文章标签 算法 随想录 代码 字符串 求值 括号 表达式 相邻 删除 波兰 重复 有效 所有 训练营 150 20 1047 第九天

本文主要是介绍代码随想录算法训练营第九天 | 20. 有效的括号、1047. 删除字符串中的所有相邻重复项、150. 逆波兰表达式求值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

代码随想录算法训练营第九天 | 20. 有效的括号、1047. 删除字符串中的所有相邻重复项、150. 逆波兰表达式求值

文章目录

  • 代码随想录算法训练营第九天 | 20. 有效的括号、1047. 删除字符串中的所有相邻重复项、150. 逆波兰表达式求值
    • 1 LeetCode 20. 有效的括号
    • 2 LeetCode 1047. 删除字符串中的所有相邻重复项
      • 2.1 模拟栈实现
      • 2.2 双指针法
    • 3 LeetCode 150. 逆波兰表达式求值

1 LeetCode 20. 有效的括号

题目链接：https://leetcode.cn/problems/valid-parentheses/description/

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

提示：

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成

这道题这种情形，平时我们应该很常见，也就是括号匹配问题，比如我们在VsCode里面写代码，如果忘记加反括号的话，编译器就会识别错误，这个过程其实也就是括号匹配机制，都是用栈来实现的。

一般来说出现错误就三种情况：

  • 左括号多了
  • 右括号多了
  • 左右括号不匹配

这三种情况其实也就对应题目要求的有效字符串条件，我们可以采取从左到右依次遍历，如果遇见左括号就存对应的右括号，也就是压栈保存，如果遇见与之对应的右括号就弹出栈中的括号，如果最后栈为空，也就代表括号匹配，反之则不匹配。

另外，我们还可以进行剪枝操作，首先先判断一下字符串的长度是奇数还是偶数，如果是奇数，则一定不匹配，直接返回。

（1）Python版本代码

class Solution:def isValid(self, s: str) -> bool:if len(s) % 2 != 0:  # 如果字符串长度为奇数，则直接返回Falsereturn Falsestack = []  # 使用列表作为栈for char in s:if char == '(':  # 如果字符是左括号stack.append(')')    # 将右括号添加到栈中elif char == '{':   stack.append('}')elif char == '[':stack.append(']')elif not stack or stack[-1] != char:  # 如果栈为空或栈顶元素不匹配，则返回Falsereturn Falseelse:stack.pop()  # 如果栈顶元素匹配，则弹出栈顶元素return not stack  # 如果栈为空，则所有括号有效匹配；否则返回Falseif __name__ == "__main__":s = input()solution = Solution()print(solution.isValid(s))

（2）C++版本代码

#include <iostream>
#include <stack>
#include <string>
using namespace std;class 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(']');else if (st.empty() || st.top() != s[i]) return false;  // 栈为空或栈顶字符不匹配else st.pop();  // st.top() 与 s[i]相等，栈弹出元素}return st.empty();  // 栈为空，说明括号有效闭合}
};int main() {string s;getline(cin, s);  // 读取一行字符串Solution solution;cout << (solution.isValid(s) ? "true" : "false") << endl;return 0;
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

2 LeetCode 1047. 删除字符串中的所有相邻重复项

题目链接：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/description/

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

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：

  1. 1 <= S.length <= 20000
  2. S 仅由小写英文字母组成。

2.1 模拟栈实现

看这个题目要求，是不是很像我们小时候玩的消消乐小游戏，相邻相同元素互相消除，如果消除之后又出现相邻相同元素，则继续消除，直到没有为止，俄罗斯方块的消除可能也是这样实现的。

那现在好说了，这题就是栈的最好应用，栈是很好解决元素匹配问题的，在这题中我们可以设置一个栈（可用列表来模拟栈），然后遍历所给字符串，遇见元素就把它和栈顶元素进行比较，若栈为空或者栈顶元素与当前元素不相同，则将当前元素入栈，如果栈不为空，且栈顶元素与当前元素相同，则弹出栈顶元素，这样就达到了消除操作，最后我们再将栈中元素输出成字符串返回即可。

（1）Python版本代码

class Solution:def removeDuplicates(self, s: str) -> str:stack = []  # 用栈来存储for i in s:  # 遍历字符串if stack and stack[-1] == i:    stack.pop()  # 如果栈不为空，且栈顶元素与当前元素相同，则弹出栈顶元素else:               stack.append(i)     # 如果栈为空或栈顶元素与当前元素不相同，则将当前元素入栈return "".join(stack)       if __name__ == "__main__":s = input()print(Solution().removeDuplicates(s))

（2）C++版本代码

#include <iostream>
#include <string>
#include <stack>
using namespace std;class Solution {
public:string removeDuplicates(string s) {stack<char> st;  // 使用栈来存储字符for (char i : s) {  // 遍历字符串if (!st.empty() && st.top() == i) {st.pop();  // 如果栈不为空且栈顶元素与当前元素相同，则弹出栈顶元素} else {st.push(i);  // 如果栈为空或栈顶元素与当前元素不相同，则将当前元素入栈}}string result;while (!st.empty()) {result = st.top() + result;  // 从栈中取出元素构建结果字符串st.pop();}return result;}
};int main() {string s;getline(cin, s);  // 读取一行字符串Solution solution;cout << solution.removeDuplicates(s) << endl;return 0;
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

我学习了一下卡哥的代码，我们还可以直接拿字符串作为栈，就节省了栈转字符串的操作，减少了空间复杂度。

class Solution {
public:string removeDuplicates(string S) {string result;for(char s : S) {if(result.empty() || result.back() != s) {result.push_back(s);}else {result.pop_back();}}return result;}
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)，返回值不计空间复杂度

2.2 双指针法

通过学习，我发现卡哥的代码随想录下面扩展部分对于这题还有其他解法，也就是防止面试时面试官给你说：解决这题但不使用栈，你应该如果解决？

下面就是另一种实现思路，那就是掏出我们非常熟悉的双指针法了，虽然这题用栈非常的好理解，但这种方法也最好学习一下，以防万一。

我们初始化两个指针i 和 j，其中 i 用于遍历字符串，j 用于指向结果字符串的末尾（初始时设为 -1，表示空栈），然后我们使用 i 遍历整个字符串，如果 j 指向的元素与 i 指向的元素相同，则 j--（相当于栈弹出），否则将 i 指向的元素复制到 j+1 的位置，并且 j++（相当于栈压入），最后根据 j 指针的最终位置，提取字符串的前 j + 1 个字符作为结果。

（1）Python版本代码

class Solution:def removeDuplicates(self, s: str) -> str:s = list(s)  # 将字符串转换为列表以便原地修改j = -1  # 初始化j为-1，表示空栈for i in range(len(s)):if j != -1 and s[j] == s[i]:j -= 1  # 相同则弹出else:j += 1s[j] = s[i]  # 不同则压入return ''.join(s[:j+1])  # 返回结果字符串if __name__ == "__main__":s = input()print(Solution().removeDuplicates(s))

（2）C++版本代码

#include <iostream>
#include <string>
using namespace std;class Solution {
public:string removeDuplicates(string s) {int j = -1;  // 初始化j为-1，表示空栈for (int i = 0; i < s.size(); i++) {if (j != -1 && s[j] == s[i]) {j--;  // 相同则弹出} else {s[++j] = s[i];  // 不同则压入}}return s.substr(0, j + 1);  // 返回结果字符串}
};int main() {string s;getline(cin, s);  Solution solution;cout << solution.removeDuplicates(s) << endl;return 0;
}
  • 时间复杂度：O(n)，其中 n 是字符串 s 的长度，我们只需要遍历一次字符串，每个字符只处理一次。
  • 空间复杂度：O(1)，虽然我们将字符串转换为列表来进行原地修改，但这仅占用与输入字符串相等的空间，在双指针操作过程中，我们没有使用额外的栈或数组，因此除了输入和输出之外，我们只使用了常数级别的额外空间。

这种方法的优点在于它利用了字符串本身的空间来模拟栈的操作，避免了使用额外的数据结构，在实际操作中，它通过移动 j 指针来表示栈顶位置，并在字符串的同一位置进行弹出和压入操作。

3 LeetCode 150. 逆波兰表达式求值

题目链接：https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

  • 有效的算符为 '+'、'-'、'*' 和 '/' 。
  • 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
  • 两个整数之间的除法总是 向零截断 。
  • 表达式中不含除零运算。
  • 输入是一个根据逆波兰表示法表示的算术表达式。
  • 答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

提示：

  • 1 <= tokens.length <= 104
  • tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

  • 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
  • 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

  • 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
  • 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

看见这道题目，相信学过408的朋友一定不陌生，虽然好像没有考过代码题，但是选择题已经考察过很多次了，大家也要防一手它考察算法题，因为408的算法题最难也就力扣中等题的样子，这题刚好就是，然后这题还非常能体现出人和计算机的思考方式的差异，我们一般写的算术表达式都是中缀表达式，是方便人看的，但是计算机却看不懂，在底层中还需要将其转换为逆波兰式（即后缀表达式）才能正常识别和计算。

回到这题来，我们解决的思路大致就是，遍历字符串，然后如果遇见数字就压栈保存，如果遇见了运算符就弹出栈中的栈顶元素以及次栈顶元素做相应的运算，然后在把计算结果压入栈中，然后继续遍历，直到最后栈中只剩下一个数，即为最后表达式所求结果。（因为题目所说所给逆波兰表达式都为合法表达式，因此我们就不用进行异常处理）

（1）Python版本代码

class Solution:def evalRPN(self, tokens):stack = []  # 用栈来存储for i in tokens:    if i == "+":a, b = stack.pop(), stack.pop()stack.append(a + b)elif i == "-":a, b = stack.pop(), stack.pop()stack.append(b - a)elif i == "*":a, b = stack.pop(), stack.pop()stack.append(a * b)elif i == "/":a, b = stack.pop(), stack.pop()stack.append(int(b / a))else:stack.append(int(i))return stack[0]if __name__ == "__main__":tokens = input().split()print(Solution().evalRPN(tokens))

（2）C++版本代码

#include <iostream>
#include <stack>
#include <vector>
#include <string>
#include <sstream>
using namespace std;class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int> stack;  // 使用栈来存储for (string& token : tokens) {if (token == "+") {int a = stack.top(); stack.pop();int b = stack.top(); stack.pop();stack.push(b + a);} else if (token == "-") {int a = stack.top(); stack.pop();int b = stack.top(); stack.pop();stack.push(b - a);} else if (token == "*") {int a = stack.top(); stack.pop();int b = stack.top(); stack.pop();stack.push(b * a);} else if (token == "/") {int a = stack.top(); stack.pop();int b = stack.top(); stack.pop();stack.push(b / a);  // 注意：在C++中，整数除法会自动向下取整} else {stack.push(stoi(token));  // 将字符串转换为整数}}return stack.top();}
};int main() {vector<string> tokens;string input;while (cin >> input) {tokens.push_back(input);if (cin.peek() == '\n') break;  // 检测到换行符则结束输入}Solution solution;cout << solution.evalRPN(tokens) << endl;return 0;
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

这篇关于代码随想录算法训练营第九天 | 20. 有效的括号、1047. 删除字符串中的所有相邻重复项、150. 逆波兰表达式求值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/629426。

相关文章

Spring Security 基于表达式的权限控制

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权，允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true （Spring security默认会带有ROLE_前缀）,去
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
电脑桌面文件删除了怎么找回来？别急，快速恢复攻略在此

电脑桌面文件删除了怎么找回来？别急，快速恢复攻略在此

在日常使用电脑的过程中，我们经常会遇到这样的情况：一不小心，桌面上的某个重要文件被删除了。这时，大多数人可能会感到惊慌失措，不知所措。 其实，不必过于担心，因为有很多方法可以帮助我们找回被删除的桌面文件。下面，就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件，并且还没有进行其他操作，那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
poj2406（连续重复子串）

poj2406（连续重复子串）

题意:判断串s是不是str^n，求str的最大长度。 解题思路：kmp可解，后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后，自动跳转到next[i]，所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下； #include<iostream>#include<algorithm>#include<stdio.h>#include<math.
阅读更多...
poj3261（可重复k次的最长子串）

poj3261（可重复k次的最长子串）

题意：可重复k次的最长子串 解题思路：求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N，但实际复杂度很低。题目数据也比较水，不然估计过不了。 代码入下： #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2