• 【代码随想录】算法训练营 第十一天 第五章 栈与队列 Part 2


    20. 有效的括号

    题目

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

    有效字符串需满足:

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

    思路

    用栈来匹配是最好的选择,将字符串的每个字符与栈顶元素匹配,如果栈为空或者不匹配,就将字符进栈,每次匹配成功就可以将栈顶元素弹出,如果字符串有效,那么栈里最后是不会有元素的。

    代码

    1. class Solution {
    2. public:
    3. bool isValid(string s) {
    4. stack<char> st;
    5. if (s.size() % 2)
    6. return false;
    7. for (int i = 0; i < s.size(); i++) {
    8. if (st.empty()) {
    9. st.push(s[i]);
    10. continue;
    11. }
    12. if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
    13. st.push(s[i]);
    14. }
    15. else if ((s[i] == ')' && st.top() == '(') || (s[i] == '}' && st.top() == '{') || (s[i] == ']' && st.top() == '[')) {
    16. st.pop();
    17. }
    18. else {
    19. st.push(s[i]);
    20. }
    21. }
    22. if (st.empty())
    23. return true;
    24. else
    25. return false;
    26. }
    27. };

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

    题目

    思路

    和上一题一样,只不过这题要注意最后留下的字符串是要输出的,所以我们一开始遍历原字符串时就要从最后一个遍历,这样塞进栈里的字符串顺序是反的,最后再把栈里的字符串输出到一个新定义的字符串即可,注意定义字符串的格式是 string str(length, '  ') 括号中前一个参数是字符串的长度,后一个是用什么字符填充这个字符串。

    代码

    1. class Solution {
    2. public:
    3. string removeDuplicates(string s) {
    4. stack<int> st;
    5. int len = 0;
    6. for (int i = s.size() - 1; i >= 0; i--) {
    7. if (st.empty()) {
    8. st.push(s[i]);
    9. len++;
    10. }
    11. else if (s[i] == st.top()) {
    12. st.pop();
    13. len--;
    14. }
    15. else {
    16. st.push(s[i]);
    17. len++;
    18. }
    19. }
    20. string ss(len, ' ');
    21. int k = 0;
    22. while (len--) {
    23. ss[k] = st.top();
    24. st.pop();
    25. k++;
    26. }
    27. return ss;
    28. }
    29. };

    150. 逆波兰表达式求值

    题目

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

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

    注意:

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

    思路

    理解了逆波兰式的输入就很好办了,和上面两题异曲同工,而且这道题不会有需要特判的情况,所以只需要遇到符号就取栈顶元素计算即可,唯一要注意的是这里面的数据类型转换,把string类型变成int型用stoll。

    代码

    1. class Solution {
    2. public:
    3. int evalRPN(vector& tokens) {
    4. stack<long long> st;
    5. for (int i = 0; i < tokens.size(); i++) {
    6. if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
    7. int num2 = st.top();
    8. st.pop();
    9. int num1 = st.top();
    10. st.pop();
    11. if (tokens[i] == "+") st.push(num1 + num2);
    12. if (tokens[i] == "-") st.push(num1 - num2);
    13. if (tokens[i] == "*") st.push(num1 * num2);
    14. if (tokens[i] == "/") st.push(num1 / num2);
    15. }
    16. else {
    17. st.push(stoll(tokens[i]));
    18. }
    19. }
    20. int result = st.top();
    21. st.pop();
    22. return result;
    23. }
    24. };

  • 相关阅读:
    保姆级教程:Linux (Ubuntu) 部署流光卡片开源 API
    fastboot 找不到设备
    IDEA利用maven建立javaWeb项目(IDEA 2021.3.3)
    谁说.NET没有GC调优?只改一行代码就让程序不再占用内存
    信号完整性:反射
    一文搞定 Spring事务
    【Dotnet 工具箱】推荐一个使用 C# 开发的轻量级压测工具
    【Golang | Gin】net/http和Gin起web服务时的简单对比
    论信息系统项目的整体管理
    【虹科方案】虹科数字化仪——机械测量的最佳方案!(二)
  • 原文地址:https://blog.csdn.net/Summerison/article/details/133966386