代码随想录算法训练营第九天 | 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 Boot 集成 Quartz并使用Cron 表达式实现定时任务

Spring Boot 集成 Quartz并使用Cron 表达式实现定时任务

《SpringBoot集成Quartz并使用Cron表达式实现定时任务》本篇文章介绍了如何在SpringBoot中集成Quartz进行定时任务调度,并通过Cron表达式控制任务... 目录前言1. 添加 Quartz 依赖2. 创建 Quartz 任务3. 配置 Quartz 任务调度4. 启动 Sprin
阅读更多...
Java字符串操作技巧之语法、示例与应用场景分析

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字
阅读更多...
使用Java将DOCX文档解析为Markdown文档的代码实现

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown（MD）因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析
阅读更多...
一文详解如何在Python中从字符串中提取部分内容

一文详解如何在Python中从字符串中提取部分内容

《一文详解如何在Python中从字符串中提取部分内容》：本文主要介绍如何在Python中从字符串中提取部分内容的相关资料,包括使用正则表达式、Pyparsing库、AST（抽象语法树）、字符串操作... 目录前言解决方案方法一：使用正则表达式方法二：使用 Pyparsing方法三：使用 AST方法四：使用字
阅读更多...
Java字符串处理全解析(String、StringBuilder与StringBuffer)

Java字符串处理全解析(String、StringBuilder与StringBuffer)

《Java字符串处理全解析(String、StringBuilder与StringBuffer)》：本文主要介绍Java字符串处理全解析(String、StringBuilder与StringBu... 目录Java字符串处理全解析：String、StringBuilder与StringBuffer一、St
阅读更多...
C++使用printf语句实现进制转换的示例代码

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符（formatspecifier）快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指
阅读更多...
openCV中KNN算法的实现

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库，它提供了各
阅读更多...
使用Python实现全能手机虚拟键盘的示例代码

使用Python实现全能手机虚拟键盘的示例代码

《使用Python实现全能手机虚拟键盘的示例代码》在数字化办公时代,你是否遇到过这样的场景：会议室投影电脑突然键盘失灵、躺在沙发上想远程控制书房电脑、或者需要给长辈远程协助操作？今天我要分享的Pyth... 目录一、项目概述：不止于键盘的远程控制方案1.1 创新价值1.2 技术栈全景二、需求实现步骤一、需求
阅读更多...
Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

《Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码》：本文主要介绍Java中日期时间转换的多种方法,包括将Date转换为LocalD... 目录一、Date转LocalDateTime二、Date转LocalDate三、LocalDateTim
阅读更多...
MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2