24.总结

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

---

1047.1 题目

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

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

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

示例：

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

提示：

• 1 <= S.length <= 20000
• S 仅由小写英文字母组成。

---

1047.2 题解

StringBuilder模拟栈

// 方法一：StringBuilder模拟栈
// 使用 StringBuilder 模拟栈，遍历字符串，将不重复的字符依次入栈，重复则出栈。
static string RemoveDuplicates1(string s)
{
    // 创建 StringBuilder 对象，用于模拟栈的操作
    StringBuilder stack = new StringBuilder();

    // 遍历输入字符串的每个字符
    foreach (char c in s)
    {
        // 如果栈不为空且当前字符与栈顶字符相同，执行出栈操作
        if (stack.Length > 0 && stack[stack.Length - 1] == c)
        {
            stack.Remove(stack.Length - 1, 1); // 出栈
        }
        else
        {
            stack.Append(c); // 入栈
        }
    }

    // 将 StringBuilder 转换为字符串并返回
    return stack.ToString();
}

字符数组模拟栈

// 方法二：字符数组模拟栈
// 使用字符数组模拟栈，遍历字符串，将不重复的字符依次入栈，重复则出栈。
static string RemoveDuplicates2(string s)
{
    // 创建字符数组作为栈，top 表示栈顶位置
    char[] stack = new char[s.Length];
    int top = 0;

    // 遍历输入字符串的每个字符
    foreach (char c in s)
    {
        // 如果栈不为空且当前字符与栈顶字符相同，执行出栈操作
        if (top > 0 && stack[top - 1] == c)
        {
            top--; // 出栈
        }
        else
        {
            stack[top++] = c; // 入栈
        }
    }

    // 将字符数组转换为字符串并返回，只取栈中有效元素部分
    return new string(stack, 0, top);
}

---

1047.3 代码

using System;
using System.Text;

class Program
{
    static void Main()
    {
        #region 题目

        // 给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
        // 在 S 上反复执行重复项删除操作，直到无法继续删除。
        // 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

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

        // 提示：
        // 1 <= S.length <= 20000
        // S 仅由小写英文字母组成。

        #endregion

        #region 测试

        // 示例测试
        string str1 = "abbaca";
        string result1_1 = RemoveDuplicates1(str1);
        Console.WriteLine($"示例1 方法1 输出：{result1_1}");
        string result1_2 = RemoveDuplicates2(str1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 添加更多测试用例...

        #endregion
    }

    #region 答案

    // 方法一：StringBuilder模拟栈
    // 使用 StringBuilder 模拟栈，遍历字符串，将不重复的字符依次入栈，重复则出栈。
    static string RemoveDuplicates1(string s)
    {
        // 创建 StringBuilder 对象，用于模拟栈的操作
        StringBuilder stack = new StringBuilder();

        // 遍历输入字符串的每个字符
        foreach (char c in s)
        {
            // 如果栈不为空且当前字符与栈顶字符相同，执行出栈操作
            if (stack.Length > 0 && stack[stack.Length - 1] == c)
            {
                stack.Remove(stack.Length - 1, 1); // 出栈
            }
            else
            {
                stack.Append(c); // 入栈
            }
        }

        // 将 StringBuilder 转换为字符串并返回
        return stack.ToString();
    }

    // 方法二：字符数组模拟栈
    // 使用字符数组模拟栈，遍历字符串，将不重复的字符依次入栈，重复则出栈。
    static string RemoveDuplicates2(string s)
    {
        // 创建字符数组作为栈，top 表示栈顶位置
        char[] stack = new char[s.Length];
        int top = 0;

        // 遍历输入字符串的每个字符
        foreach (char c in s)
        {
            // 如果栈不为空且当前字符与栈顶字符相同，执行出栈操作
            if (top > 0 && stack[top - 1] == c)
            {
                top--; // 出栈
            }
            else
            {
                stack[top++] = c; // 入栈
            }
        }

        // 将字符数组转换为字符串并返回，只取栈中有效元素部分
        return new string(stack, 0, top);
    }

    #endregion
}

---

1047.4 运行结果

示例1 方法1 输出：ca
示例1 方法2 输出：ca

---

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com