当前位置：首页 > article >正文

栈（5题）

article 2025/2/4 23:08:02

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

2.比较含退格的字符串

3.基本计算器2

4.字符串解码

5.验证栈序列

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

1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）

我们只需要用一个string的字符串模拟一下这个栈就可以了

如果ret为空则入栈，否则进行判断，如果遍历到的那个字母与栈顶字母相同，就把栈顶那个字母出栈，否则就继续入栈

class Solution {
public:
    string removeDuplicates(string s) {
        int n = s.size();
        string ret;
        for(int i = 0; i < n; i++)
        {
            if(ret.empty())
            {
                ret.push_back(s[i]);
            }
            else
            {
                if(s[i] == ret.back())
                {
                    ret.pop_back();
                }
                else
                {
                    ret.push_back(s[i]);
                }
            }
        }
        return ret;
    }
};

2.比较含退格的字符串

844. 比较含退格的字符串 - 力扣（LeetCode）

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        string ret1;
        string ret2;
        int m = s.size();
        int n = t.size();
        for(int i = 0; i < m; i++)
        {
            if(s[i] == '#' && !ret1.empty())
            {
                ret1.pop_back();
            }
            else if(s[i] != '#')
            {
                ret1.push_back(s[i]);
            }
        }
        for(int i = 0; i < n; i++)
        {
            if(t[i] == '#' && !ret2.empty())
            {
                ret2.pop_back();
            }
            else if(t[i] != '#')
            {
                ret2.push_back(t[i]);
            }
        }
        if(ret1 == ret2)return true;
        else return false;
    }
};

3.基本计算器2

227. 基本计算器 II - 力扣（LeetCode）

这题我们用一个数组模拟栈，再创建一个字符变量 op来保存 + - * /。因为这道题比较简单，没有引入括号，因此算数符的优先级是确定的。

当我们遇到 + - 的符号的时候，我们先要把接下来的数字入栈，因为如果后面有 * /运算符，这个数就要和后面的数进行运算。当遇到* / 符号的时候，直接把这个数和栈顶的数进行运算。

对于计算数，我们用一个while循环即可每次把我们已经存下的数 * 10 再加上新的一位即可。

值得注意的是，我们需要更改一下计算顺序tmp = tmp * 10 + (s[i] - '0');先计算后面的，防止溢出，因为字符的阿斯克码值比较大

class Solution {
public:
    int calculate(string s) {
        vector<int> st;
        char op = '+';
        int n = s.size();
        for(int i = 0; i < n; )
        {
            if((s[i] > '9' || s[i] < '0'))
            {
                if(s[i] != ' ')
                {
                    op = s[i];
                }
                i++;
            }
            else
            {
                int tmp = 0;
                while(i < n && s[i] >= '0' && s[i] <= '9')
                {
                    tmp  = tmp * 10 + (s[i] - '0');
                    i++;
                }
                if(op == '+')
                {
                    st.push_back(tmp);
                }
                else if(op == '-')
                {
                    st.push_back(-tmp);
                }
                else if(op == '*')
                {
                    tmp = st.back() * tmp;
                    st.pop_back();
                    st.push_back(tmp);
                }
                else if(op == '/')
                {
                    tmp = st.back() / tmp;
                    st.pop_back();
                    st.push_back(tmp);
                }
            }
        }
        int ret = 0;
        for(int i = 0; i < st.size(); i++)
        {
            ret += st[i];
        }
        return ret;
    }
};

4.字符串解码

394. 字符串解码 - 力扣（LeetCode）

这种括号改变运算优先级的题目一般都是用栈解决

我们先准备两个栈，一个存数字，一个存字符串

这道题目需要我们分情况讨论：

1.如果遇到数字，提取出这个数字，放入数字栈

2.如果遇到‘[’：把后面的字符提取出来，放到字符串栈中

3.如果遇到‘]’：把数字栈栈顶的元素和字符串栈栈顶的元素分别出栈，并且拿出来进行运算，然后把运算出来的结果插入到新的字符串栈栈顶元素的后面（因为我们得出的运算结果可能是在另一对括号中的）

4.如果遇到单独的字符，一个一个放在字符串栈栈顶元素的后面，形成一个新的栈顶元素。

值得注意的点是，我们需要事先把字符串栈中加入一个空字符串，避免当栈里面只有一个元素的时候，把原栈顶元素加入新栈顶元素的时候栈为空。例如3[a]这种情况。

class Solution {
public:
    string decodeString(string s) {
        vector<int> ist;
        vector<string> sst;
        sst.push_back("");
        int n = s.size();
        for(int i = 0; i < n;)
        {
            if(s[i] >= '0' && s[i] <= '9')
            {
                int tmp = 0;
                while(i < n && s[i] >= '0' && s[i] <= '9')
                {
                    tmp  = tmp * 10 + (s[i] - '0');
                    i++;
                }
                ist.push_back(tmp);
            }
            else if(s[i] == '[')
            {
                i++;
                string tmpstring1;
                while(i < n && s[i] >= 'a' && s[i] <= 'z')
                {
                    tmpstring1 += s[i];
                    i++;
                }
                sst.push_back(tmpstring1);
            }
            else if(s[i] ==']')
            {
                i++;
                string tmpstring2;
                for(int k = 0; k < ist.back(); k++)
                {
                    tmpstring2 += sst.back();
                }
                ist.pop_back();
                sst.pop_back();
                tmpstring2 = sst.back() + tmpstring2;
                sst.pop_back();
                sst.push_back(tmpstring2);
            }
            else
            {
                string tmpstring3;
                while( i < n && s[i] >= 'a' && s[i] <= 'z')
                {
                    tmpstring3 += s[i];
                    i++;
                }
                tmpstring3 = sst.back() + tmpstring3;
                sst.pop_back();
                sst.push_back(tmpstring3);
            }
        }
        return sst.back();
    }
};

5.验证栈序列

946. 验证栈序列 - 力扣（LeetCode）

这题我们让push里面的元素一直进栈，同时pop中的元素也一直进行出栈判断。

等到循环结束判断其是否为空即可。

不过出栈之前要判断栈是否为空，如果为空就不要出栈。

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        int n = pushed.size();
        stack<int> st;
        int i = 0;
        int j = 0;
        while(i < n)
        {
            st.push(pushed[i]);
            while(st.size() && popped[j] == st.top())
            {
                st.pop();
                j++;
            }
            i++;
        }
        if(st.empty())return true;
        else return false;
    }
};

查看全文

http://www.kler.cn/a/531671.html