代码随想录算法训练营第九天 | 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。

相关文章

macOS无效Launchpad图标轻松删除的4 种实用方法

macOS无效Launchpad图标轻松删除的4 种实用方法

《macOS无效Launchpad图标轻松删除的4种实用方法》mac中不在appstore上下载的应用经常在删除后它的图标还残留在launchpad中，并且长按图标也不会出现删除符号，下面解决这个问... 在 MACOS 上，Launchpad（也就是「启动台」）是一个便捷的 App 启动工具。但有时候，应
阅读更多...
Java实现时间与字符串互相转换详解

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串（一）使用预定义格式（二）自定义格式二、字符串解析为日期（一）解析ISO格式字符串（二）解析自定义
阅读更多...
Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE？1.2 SSE 的优点1.3 适用场景2. Spring WebFlu
阅读更多...
java之Objects.nonNull用法代码解读

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》：本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN
阅读更多...
SpringBoot实现MD5加盐算法的示例代码

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.
阅读更多...
Mysql删除几亿条数据表中的部分数据的方法实现

Mysql删除几亿条数据表中的部分数据的方法实现

《Mysql删除几亿条数据表中的部分数据的方法实现》在MySQL中删除一个大表中的数据时,需要特别注意操作的性能和对系统的影响,本文主要介绍了Mysql删除几亿条数据表中的部分数据的方法实现,具有一定... 目录1、需求2、方案1. 使用 DELETE 语句分批删除2. 使用 INPLACE ALTER T
阅读更多...
python+opencv处理颜色之将目标颜色转换实例代码

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,：本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV： 关于颜色总是要转HSV的掩膜再标注总结 目标：将红色的部分滤
阅读更多...
在C#中调用Python代码的两种实现方式

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》：本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调
阅读更多...
Java时间轮调度算法的代码实现

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组（时间轮）和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时
阅读更多...
Python实现将MySQL中所有表的数据都导出为CSV文件并压缩

Python实现将MySQL中所有表的数据都导出为CSV文件并压缩

《Python实现将MySQL中所有表的数据都导出为CSV文件并压缩》这篇文章主要为大家详细介绍了如何使用Python将MySQL数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到... python将mysql数据库中所有表的数据都导出为CSV文件到一个目录，并压缩为zip文件到另一个
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2