代码随想录Day11|[20.有效括号](20. 有效的括号 - 力扣（LeetCode）)|[1047.删除字符串的所有相邻重复项](1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）)|150.逆波兰表达式求值

20.

思路

依次压栈直到开始第一次匹配，开始出栈，栈空后再此循环。

解法

错误1

从字符串中间开始分割进行出入栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isValid(string s) {
        stack<char> SS;
        if(s.size()%2!=0)return false;
        for(int i=0;i<s.size()/2;i++){
            SS.push(s[i]);
        }
        for(int j=s.size()/2,i=s.size()/2;j>0,i<s.size();j--,i++){
            if((SS.top()=='{'&&s[i]=='}')||(SS.top()=='('&&s[i]==')')||(SS.top()=='['&&s[i]==']')){
                SS.pop();
            }
            else{
                return false;
            }
        }
        return true;
    }
};

错误2

虽然依次处理了所有情况但是对于，入栈不出的元素没有进行处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    bool isValid(string s) {
        stack<char> SS;
        for(char c:s){
            switch (c){
            case '{':
                SS.push(c);
                break;
            case '[':
                SS.push(c);
                break;
            case '(':
                SS.push(c);
                break;
            case '}':
                if(SS.empty()==true||SS.top()!='{') return false;
                else SS.pop();
                break;
            case ']':
                if(SS.empty()==true||SS.top()!='[') return false;
                else SS.pop();
                break;
            case ')':
                if(SS.empty()==true||SS.top()!='(') return false;
                else SS.pop();
                break;
            }
        }
        return true;			//错误在此 --》应该改为return SS.empty();
    }
};

正确解法

1047

思路

  • 思路 1

使用earse函数进行删除，前方元素不断压栈，进行递归；

这个题没有想像中那么简单，实操起来是有一定问题的，一个是边界条件，何时中止和全部删除空的话如何处理，另外一个是递归中止条件

  • 思路2

使用字符串拼接技术进行删除

解法

错误1

  1. 越界访问: 在循环中，您使用 s[i+1] 来检查下一个字符。这在字符串末尾时会导致越界访问，因为当 i 等于 s.size() - 1 时，s[i+1] 不存在。
  2. 栈的使用: 使用了一个栈，但实际上没有有效地利用它。栈应该用来存储当前没有被删除的字符，以便于处理重复字符的删除。
  3. 不正确地修改迭代器: 在遍历字符串的过程中，您尝试使用 s.erase(i, 2) 来删除字符。这会改变字符串的大小和迭代器的有效性，可能导致未定义行为。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> SS;
        for(int i=0;i<s.size();i++){
            SS.push(s[i]);
            if(s[i+1]==s[i]){
                s.erase(i,2);
                SS.pop();
            }
        }
        return s;
    }
};

改进

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <stack>
#include <string>

using namespace std;

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> SS;
        for(char c : s) {
            if(SS.empty() || SS.top() != c) {
                SS.push(c);
            } else {
                SS.pop(); // 删除重复的字符
            }
        }

        string result = "";
        while(!SS.empty()) {
            result = SS.top() + result;
            SS.pop();
        }

        return result;
    }
};

int main() {
    Solution solution;
    string testStr = "abbaca";
    cout << "Result: " << solution.removeDuplicates(testStr) << endl;
    return 0;
}

解法 -递归 -超时（自己编译器测试正确）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    string removeDuplicates(string s) {
        for (size_t i = 0; i < s.size() - 1; ) {
            if (s[i] == s[i + 1]) {
                s.erase(i, 2);  // 删除两个相邻且相同的字符
                // 回退一步以处理连续的重复项
                i = (i > 0) ? i - 1 : 0;
            } else {
                ++i;
            }
        }
        return s;
    }
};

正确解法 -简单的遍历压栈出栈即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string removeDuplicates(string s) {
        string result;
        for(char SS:s){
            if(result.empty()||result.back()!=SS){
                result.push_back(SS);
            }
            else{
                result.pop_back();
            }

        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
lass Solution {
public:
    string removeDuplicates(string s) {
        stack<char> SS;
        for(char SL:s){
            if(SS.empty()||SL!=SS.top()){
                SS.push(SL);
            }
            else{
                SS.pop();
            }
        }
        string result ="";
        while(!SS.empty()){
            result+=SS.top();
            SS.pop();
        }
        reverse(result.begin(),result.end());
        return result;
    }
};

150. 逆波兰表达式求值

思路

弹出栈里的元素，并且按照反方向顺序进行字符加载和后缀运算符判断，最后再判断一下非空条件

错误1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<long long> SS;
        for(string& c:tokens){  //C++字符串迭代器的处理
            if(c!="+"&&c!="-"&&c!="*"&&"/"){    //脱离后缀表达式范围的值直接进行字符串转整形
                SS.push(std::stoll(c));
            }
            else{
                long long sum=0;
                long long a=SS.top();
                SS.pop();
                long long b=SS.top();
                switch(c){      
                    case '+':
                        sum=a+b;
                        break;
                    case '-':
                        sum=a-b;
                        break;
                    case '*':
                        sum=a*b;
                        break;
                    case '/':       //除法要做特殊处理 
                        sum=b/a;
                        break;
                }
                SS.push(sum);
            }
        }
        return SS.top();
    }
};
  1. 没有进行除法防0判断
  2. switch语句不能对string类型起作用，需要修正

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<long long> SS;
        try{
        for(string& c:tokens){  //C++字符串迭代器的处理
            if(c!="+"&&c!="-"&&c!="*"&&c!="/"){    //脱离后缀表达式范围的值直接进行字符串转整形
                SS.push(stoll(c));
            }
            else{
                //long long sum=0;
                long long a=SS.top();
                SS.pop();
                long long b=SS.top();
                SS.pop();
                if(c == "+")SS.push(b+a);
                else if(c=="-")SS.push(b-a);
                else if(c=="*")SS.push(b*a);
                else if(c=="/"){
                    if(a==0){
                        throw std::runtime_error("Division by zero");
                    }
                    SS.push(b/a);
                }
            }

        }
        }
        catch(const std::runtime_error&e){
            std::cerr<<"运行错误"<<e.what()<<'\n';
            return 0;
        }
        return SS.top();
    }
};
赏