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

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

给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 s 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

  • 输入：“abbaca”
  • 输出：“ca”
  • 解释：
    例如，在 “abbaca” 中，我们可以删除 “bb” 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”，其中又只有 “aa” 可以执行重复项删除操作，所以最后的字符串为 “ca”。

提示：

  1. 1 <= s.length <= 105
  2. s 仅由小写英文字母组成。

解题思路

利用栈去模拟这个字母消消乐的过程，没有必要真的去用数据结构的栈stack，直接使用一个数组模拟即可，在本道题适合用string，因为字母消除完后。栈里剩余的字母就是最终答案。

遍历字符串并栈模拟的过程：

  1. 如果当前栈不为空：
    • 当前字符与栈顶元素相等，弹出栈顶元素。
    • 当前字符与栈顶元素不相等，将当前字符加入栈。
  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
class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> st;
        st.push(s[0]);
        int index = 1, n = s.size();
        while(index < n)
        {
            if(st.empty()) st.push(s[index++]);
            if(index == n) break; 
            char ch = st.top();
            if(ch == s[index])
                st.pop();
            else
                st.push(s[index]);
            
            index++;
        }

        string ret;
        while(!st.empty())
        {
            char ch = st.top();
            st.pop();
            ret += ch;
        }
        reverse(ret.begin(), ret.end());

        return ret;
    }
};

优雅代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    // 函数：移除字符串中的所有相邻重复字符
    string removeDuplicates(string s) {
        string ret;  // 创建一个空字符串 ret，用于存储处理后的结果
        
        // 遍历字符串 s 中的每个字符
        for(auto ch : s) {
            // 如果 ret 不为空且当前字符与 ret 最后一个字符相同，删除 ret 最后一个字符
            if(ret.size() && ch == ret.back()) {
                ret.pop_back();  // 移除最后一个字符
            }
            // 否则，将当前字符添加到 ret 的末尾
            else {
                ret += ch;
            }
        }
        
        // 返回处理后的字符串
        return ret;
    }
};

  • 时间复杂度：$O(n)$，其中 n 是字符串 s 的长度。
  • 空间复杂度：$O(1)$，返回值的空间不计入。

比较含退格的字符串

题目：比较含退格的字符串

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

注意： 如果对空文本输入退格字符，文本继续为空。

示例 1：

  • 输入： s = “ab#c”, t = “ad#c”
  • 输出： true
  • 解释： s 和 t 都会变成 “ac”。

示例 2：

  • 输入： s = “ab##”, t = “c#d#”
  • 输出： true
  • 解释： s 和 t 都会变成 “”。

示例 3：

  • 输入： s = “a#c”, t = “b”
  • 输出： false
  • 解释： s 会变成 “c”，但 t 仍然是 “b”。

提示：

  • 1 <= s.length, t.length <= 200
  • s 和 t 只含有小写字母以及字符 '#'

解法一：栈模拟

利用栈去模拟字母串退格的过程，遍历字符串，分情况讨论：

  1. 如果当前字符是'#'：
    • 栈不为空，弹出栈顶元素。
    • 栈为空，直接跳过不做处理（退格符'#'可能含有多个，栈不能存储'#'）。
  2. 如果当前字符是小写字母：将其加入栈。

最后我们只需要比较退格处理后得到的两个字符串是否相等即可（不需要真的使用stack，这样还需再做处理，所以用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
class Solution {
public:
    
    // 该函数用于处理字符串，模拟退格操作，返回处理后的结果
    string GetStr(string& str)
    {
        string ret;
        // 遍历字符串中的每个字符
        for(auto ch : str)
        {
            // 如果字符是 '#' 且 ret 非空，弹出栈顶元素（模拟退格键）
            if(ret.size() && ch == '#') ret.pop_back();
            // 如果字符是字母，则将其添加到 ret
            else if(isalpha(ch)) ret += ch;
        }

        return ret;  // 返回处理后的字符串
    }
    
    // 比较两个字符串经过处理后的结果是否相同
    bool backspaceCompare(string s, string t) {
        return GetStr(s) == GetStr(t);  // 比较两个处理后的字符串
    }
};
  • 时间复杂度：$O(m + n)$，m和n分别为两个字符串的长度。
  • 空间复杂度：$O(m + n)$，用于存储退格处理后的字符串。

解法二：双指针

具体可参考这个：御三五佬的题解

退格处理消去左边的字符，对右边的字符没有影响，所以我们可以有一个大致的思路：从后遍历字符串，遇到'#'时就用变量记录下有多少个，遇到字母时指针向前移动消去多少个字符。

接着来看具体的分析，我们可以利用双指针i和j从后遍历字符串同时用两个变量skipS和skipT去记录遍历中两个字符串'#'的数量，首先得对字符串s做退格处理，如果当前字符为'#'，skipS++, i--；如果当前字符为字母且skipS不为空，说明该字符需要被消去，skipS--, i--，由于可能有多个字符需要被消去，故退格处理需要写成循环；如果当前字符为字母且skipS为空，这时候就不需要退格处理，退出循环。对字符串t同样需要做退格处理。

当两个字符串都经过退格处理后，需要比较i和j位置的字符串是否相等，不相等直接返回false；当一个指针越界后但另外一个没有走完，也需要返回false。比较完之后双指针再同时向前移动，整个大循环结束后说明能够一一匹配，返回true。

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
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int i = s.size() - 1, j = t.size() - 1;  // 初始化指针 i 和 j，分别指向 s 和 t 的末尾
        int skipS = 0, skipT = 0;  // 用来记录需要跳过的字符数，模拟退格操作

        // 当 i 或 j 指向的索引还在有效范围内时，继续遍历
        while(i >= 0 || j >= 0)
        {
            // 处理字符串 s
            while(i >= 0) {
                if(s[i] == '#')  // 如果字符是 '#'，则增加跳过字符的计数器
                    skipS++, i--;  // 退格，跳过当前字符
                else if(skipS > 0) {  // 如果有跳过字符的计数，减少计数器并继续向前扫描
                    skipS--;
                    i--;
                }
                else break;  // 如果没有退格操作，则停下
            }

            // 处理字符串 t
            while(j >= 0) {
                if(t[j] == '#')  // 如果字符是 '#'，则增加跳过字符的计数器
                    skipT++, j--;  // 退格，跳过当前字符
                else if(skipT > 0) {  // 如果有跳过字符的计数，减少计数器并继续向前扫描
                    skipT--;
                    j--;
                }
                else break;  // 如果没有退格操作，则停下
            }

            // 比较当前字符，若都有效并且不相同则返回 false
            if(i >= 0 && j >= 0) {
                if(s[i] != t[j]) return false;  // 如果对应字符不相同，返回 false
            }
            else {
                // 如果有一个字符串已经遍历完，但另一个字符串还未遍历完，说明不相同
                if(i >= 0 || j >= 0) return false;  // 如果其中一个字符串没有完全匹配到末尾，返回 false
            }
            i--;  // 向前移动指针
            j--;  // 向前移动指针
        }
        return true;  // 如果所有字符都匹配，返回 true
    }
};
  • 时间复杂度：$O(m + n)$，m和n分别为两个字符串的长度。
  • 空间复杂度：$O(1)$

基本计算器 II

题目：227. 基本计算器 II

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。

注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：

  • 输入： s = “3+2*2”
  • 输出： 7

示例 2：

  • 输入： s = “ 3/2 “
  • 输出： 1

示例 3：

  • 输入： s = “ 3+5 / 2 “
  • 输出： 5

提示：

  • 1 <= s.length <= 3 * 105
  • s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
  • s 表示一个 有效表达式
  • 表达式中的所有整数都是非负整数，且在范围 [0, 231 - 1] 内
  • 题目数据保证答案是一个 32-bit 整数

解题思路：栈模拟

用一个数组st去模拟栈，然后遍历字符串：

  1. 遇到空格时，跳过。
  2. 遇到数字时，提取完整的数字（支持多位数字），根据当前运算符对数字进行操作：
    • 如果是加号，数字直接加入 st。
    • 如果是减号，数字作为负数加入 st。
    • 如果是乘号或除号，则更新 st 中最后一个元素的值（因为乘除是优先级更高的运算）。
  3. 遇到运算符时，更新 Operator。

所有的乘法和除法已经在 st 中通过修改最后一个元素完成了，最后只需要对 retArr 进行求和，得到最终的结果。

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public:
    int calculate(string s) {
        int n = s.size();  // 获取表达式字符串的长度
        vector<int> st;  // 使用栈来存储中间结果

        int i = 0;  // 字符串索引
        char Operator = '+';  // 默认操作符是加法

        // 遍历整个字符串
        while (i < n) {
            char ch = s[i];  // 获取当前字符

            // 跳过空格
            if (ch == ' ') {
                i++;
            } 
            // 如果是数字
            else if (isdigit(ch)) {
                int num = 0;
                // 构建数字，处理多位数字
                while (i < n && isdigit(s[i])) {
                    num = num * 10 + (s[i++] - '0');
                }

                // 根据前一个操作符对栈进行处理
                switch (Operator) {
                case '+':
                    st.push_back(num);  // 加法直接将数字推入栈
                    break;
                case '-':
                    st.push_back(-num);  // 减法将负数推入栈
                    break;
                case '*':
                    st.back() *= num;  // 乘法与栈顶元素相乘
                    break;
                case '/':
                    st.back() /= num;  // 除法与栈顶元素相除
                    break;
                }
            } 
            // 如果是操作符，更新当前操作符
            else {
                Operator = s[i++];  // 更新操作符，并继续遍历下一个字符
            }
        }

        // 最后计算栈中所有数字的总和
        int ret = 0;
        for (auto x : st) {
            ret += x;  // 累加栈中的所有元素
        }
        
        return ret;  // 返回最终结果
    }
};
  • 时间复杂度：$O(n)$，$n$ 为字符串 $s$ 长度。
  • 空间复杂度：$O(n)$，模拟栈的数组 $st$ 的空间开销。

字符串解码

题目：394. 字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：

  • 输入： s = “3[a]2[bc]”
  • 输出：“aaabcbc”

示例 2：

  • 输入： s = “3[a2[c]]”
  • 输出：“accaccacc”

示例 3：

  • 输入： s = “2[abc]3[cd]ef”
  • 输出：“abcabccdcdcdef”

示例 4：

输入： s = “abc3[cd]xyz”
输出：“abccdcdcdxyz”

提示：

  • 1 <= s.length <= 30
  • s 由小写英文字母、数字和方括号 '[]' 组成
  • s 保证是一个 有效 的输入。
  • s 中所有整数的取值范围为 [1, 300]

解题思路：栈模拟

利用两个栈ret和nums去存储最近的字符串与数字，遍历原始字符串，分情况处理：

  1. 如果当前字符是数字，将数字提取出来，加入nums。
  2. 如果当前字符是'['，将后面的字符串提取出来，加入ret。
  3. 如果当前字符是']'，两个栈同时出栈，获取需要重复的次数cnt和字符串str，将str追加到ret的栈顶元素的末尾，重复cnt次。
  4. 如果当前字符是字母，提取当前位置及其往后的字符串，将其加入ret。

注意：由于步骤3可能会对空栈进行操作，所以将ret初始化带有一个空字符串的栈。

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
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
    string decodeString(string s) {
        // ret 用于存储当前解码过程中构建的字符串。初始化为一个空字符串的 vector。
        vector<string> ret(1, "");
        // nums 用于存储数字，记录需要重复的次数
        vector<int> nums;

        int i = 0, n = s.size(); // 初始化指针 i 和字符串长度 n
        while (i < n) { // 遍历字符串的每个字符
            if (isdigit(s[i])) { // 如果当前字符是数字
                int x = 0;
                // 处理多位数数字
                while (isdigit(s[i]))
                    x = x * 10 + (s[i++] - '0'); // 构建完整的数字
                nums.push_back(x); // 将数字压入 nums 栈中
            } else if (s[i] == '[') { // 如果当前字符是 '['，表示开始一个新的编码段
                string str;
                i++; // 跳过 '['
                // 将 '[' 后面的字母收集到 str 中
                while (isalpha(s[i]))
                    str += s[i++];
                ret.push_back(str); // 将收集到的字符串压入 ret 栈中
            } else if (s[i] == ']') { // 如果当前字符是 ']'，表示一个编码段结束
                int cnt = nums.back(); // 获取需要重复的次数
                nums.pop_back(); // 弹出栈中的重复次数
                string tmp = ret.back(); // 获取最近的字符串
                ret.pop_back(); // 弹出栈中的字符串

                // 将 tmp 字符串重复 cnt 次，追加到 ret 栈顶的字符串后
                while (cnt--)
                    ret.back() += tmp;
                i++; // 跳过 ']'
            } else { // 如果当前字符是字母
                string tmp;
                // 收集字母字符
                while (i < n && isalpha(s[i]))
                    tmp += s[i++];
                ret.back() += tmp; // 将字母追加到 ret 栈顶的字符串后
            }
        }

        return ret.back(); // 返回最终解码后的字符串
    }
};
  • 时间复杂度：$O(n)$，其中 n 是输入字符串的长度。
  • 空间复杂度：$O(n)$，主要用于存储解码过程中构建的字符串。

验证栈序列

题目链接：946. 验证栈序列

给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。

示例 1：

  • 输入： pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
  • 输出： true
  • 解释： 我们可以按以下顺序执行：
    push(1), push(2), push(3), push(4), pop() -> 4,
    push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2：

  • 输入： pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
  • 输出： false
  • 解释： 1 不能在 2 之前弹出。

提示：

  • 1 <= pushed.length <= 1000
  • 0 <= pushed[i] <= 1000
  • pushed 的所有元素 互不相同
  • popped.length == pushed.length
  • popped 是 pushed 的一个排列

解题思路：栈模拟

通过模拟栈的操作，验证最终是否以popped 数组的顺序进行所有出栈操作。遍历pushed数组，将元素一个个压入栈中。每次压入栈后，检查栈顶元素是否与popped[i]相等。如果相等，表示我们可以进行出栈操作，i自增，继续进行下一步操作，直到栈顶元素与popped[i]不相等。

遍历完pushed数组，检查栈是否为空。如果栈为空，表示出栈操作成功完成了所有元素的匹配，返回true；如果栈不为空，表示有些元素没有按popped的顺序出栈，返回false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        int i = 0; // 定义一个变量 i 来记录当前在 popped 数组中的位置
        stack<int> st; // 使用栈来模拟进栈和出栈操作
        
        // 遍历 pushed 数组中的元素
        for(auto x : pushed) {
            st.push(x); // 将当前元素进栈
            
            // 当栈不为空，并且栈顶元素和 popped 中当前位置的元素相等时
            while(!st.empty() && st.top() == popped[i]) {
                st.pop(); // 出栈
                i++; // 移动到下一个要出栈的元素
            }
        }
        
        // 如果栈为空，说明所有的出栈操作都成功匹配了
        return st.empty();
    }
};
  • 时间复杂度：$O(n)$，，其中 n 是数组 pushed 和 popped 的长度。
  • 空间复杂度：$O(n)$，使用了一个栈来保存最多 n 个元素。