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

2024-01-08 17:58:15

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

目录

一、问题描述

二、栈解法

三、双指针解法

总结


提示:以下是本篇文章正文内容,下面案例可供参考

一、问题描述

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

输入:"abbaca"
输出:"ca"

str 仅由小写英文字母组成

二、栈解法

解题思路:

可以将要比较的对象压栈,然后用将要比较的对象和栈顶元素比较,相同的话,栈顶元素出栈,不相同,则把将要比较的对象入栈,作为新的栈顶元素。当栈顶元素弹出后,前一个元素就变成了新的栈顶元素。

代码示例:

public void test() {
    // 存储遍历到不相同的字符
    Stack<Character> stack = new Stack<>();
    String str = "abbaca";
    int i = 0;
    while(i++ < str.length()) {
        // 从第一个字符开始
        char charAt = str.charAt(i - 1);
        // 如果栈是空的或者当前字符与栈顶元素不相同, 则入栈, 要注意, stack的peek操作, 如果栈是空的则抛异常
        if (stack.isEmpty() || !Objects.equals(charAt, stack.peek())) {
            stack.push(charAt);
            continue;
        }
        // 如果栈非空且当前字符与栈顶元素相同, 则出栈
        stack.pop();
    }
    StringBuffer sb = new StringBuffer();
    while(!stack.isEmpty()) {
        sb.append(stack.pop());
    }
    // 字符反转, 并输出
    System.out.println(sb.reverse());
}

三、双指针解法

解题思路:

对于对称的字符串来说,有一个规律,从中间开始,向左移动一位和向右移动一位的元素是相同的,可以成对的删除。正常情况下,每次左右指针都从同一个位置出发,然后右指针先行一步,然后再对比两个指针元素的值。这个过程中有特殊情况需要处理,首先是左指针已经移动到头了;其次是怎么删除元素。因为在整个过程中,有可能删除的是整个字符串的某些部分,然后就将字符串分割为好几段,最终我们需要的恰恰又是一个完整的字符串。

代码示例:

public void test() {
    int left = 0;
    int right = 0;
    String str = "abbaca";
    char[] chars = str.toCharArray();
    while(right < str.length() - 1) {
        // 右指针向右移动, 和left拉开距离
        right++;
        // 如果值相同, 则进行删除
        if (chars[right] == chars[left]) {
            // 对应位置打标记, 随后删除
            chars[right] = 0;
            // 对应位置打标记, 随后删除
            chars[left] = 0;
            // 如果left已经到左边尽头了, 则重置left, 将left设为和right一样的起点
            if (left == 0) {
                left = ++right;
                continue;
            }
            // left未到左边尽头, left向左移动一位
            left = left - 1;
            continue;
        }
        // 元素不相同, left向右移动, 和right保持相同的起始位置
        left = right;
    }
    // 最终输出的内容里, 替换掉标记
    System.out.println(JSON.toJSONString(chars).replace("\\u0000", ""));
}

总结

注释已添加,多想多练,简单到有手就行!

文章来源:https://blog.csdn.net/ql_gome/article/details/135461353
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。