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

相关文章

使用Python删除Excel中的行列和单元格示例详解

使用Python删除Excel中的行列和单元格示例详解

《使用Python删除Excel中的行列和单元格示例详解》在处理Excel数据时,删除不需要的行、列或单元格是一项常见且必要的操作,本文将使用Python脚本实现对Excel表格的高效自动化处理,感兴... 目录开发环境准备使用 python 删除 Excphpel 表格中的行删除特定行删除空白行删除含指定
阅读更多...
Linux下删除乱码文件和目录的实现方式

Linux下删除乱码文件和目录的实现方式

《Linux下删除乱码文件和目录的实现方式》：本文主要介绍Linux下删除乱码文件和目录的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux下删除乱码文件和目录方法1方法2总结Linux下删除乱码文件和目录方法1使用ls -i命令找到文件或目录
阅读更多...
Python中反转字符串的常见方法小结

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函
阅读更多...
Mysql实现范围分区表(新增、删除、重组、查看)

Mysql实现范围分区表(新增、删除、重组、查看)

《Mysql实现范围分区表(新增、删除、重组、查看)》MySQL分区表的四种类型（范围、哈希、列表、键值）,主要介绍了范围分区的创建、查询、添加、删除及重组织操作,具有一定的参考价值,感兴趣的可以了解... 目录一、mysql分区表分类二、范围分区（Range Partitioning1、新建分区表：2、分
阅读更多...
MySQL 删除数据详解(最新整理)

MySQL 删除数据详解(最新整理)

《MySQL删除数据详解(最新整理)》：本文主要介绍MySQL删除数据的相关知识,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、前言二、mysql 中的三种删除方式1.DELETE语句✅ 基本语法： 示例：2.TRUNCATE语句✅ 基本语
阅读更多...
MySQL中查找重复值的实现

MySQL中查找重复值的实现

《MySQL中查找重复值的实现》查找重复值是一项常见需求,比如在数据清理、数据分析、数据质量检查等场景下,我们常常需要找出表中某列或多列的重复值,具有一定的参考价值,感兴趣的可以了解一下... 目录技术背景实现步骤方法一：使用GROUP BY和HAVING子句方法二：仅返回重复值方法三：返回完整记录方法四：
阅读更多...
MySQL查询JSON数组字段包含特定字符串的方法

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案（推荐）2. 模糊匹配方案参数化查询示例使用场景建议性能优
阅读更多...
Java中的雪花算法Snowflake解析与实践技巧

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.
阅读更多...
C++20管道运算符的实现示例

C++20管道运算符的实现示例

《C++20管道运算符的实现示例》本文简要介绍C++20管道运算符的使用与实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录标准库的管道运算符使用自己实现类似的管道运算符我们不打算介绍太多，因为它实际属于c++20最为重要的
阅读更多...
一文详解Git中分支本地和远程删除的方法

一文详解Git中分支本地和远程删除的方法

《一文详解Git中分支本地和远程删除的方法》在使用Git进行版本控制的过程中,我们会创建多个分支来进行不同功能的开发,这就容易涉及到如何正确地删除本地分支和远程分支,下面我们就来看看相关的实现方法吧... 目录技术背景实现步骤删除本地分支删除远程www.chinasem.cn分支同步删除信息到其他机器示例步骤
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2