LeetCode 1047: 移除字符串中的连续重复字符

我的公号中很少写算法相关的东西，我想了想，原因大致有：

1. 我本身没学过多少算法，一直不愿(也不敢)主动去看算法题。
2. 这几年的实际工作中，真正需要(高深)算法的地方并不多，而且真的需要时，也是让专业的算法同学来做，不需要我班门弄斧。
3. 这点也是最重要的，我觉得代码的逻辑清楚、可读性好，比把心思放在奇奇怪怪的复杂算法(尤其是性能优化)上，更有意义。毕竟维护这段代码的人可能比写这段代码的人更多，让维护人的人好懂，大家的路才会更好走。

并且，我想多数公司的业务都没有「复杂」到需要高级算法才能解决的地步，而有些同学一开始就把重心放在算法练习(或者其它高大上的技术)上，忽略了对语言基础的掌握，导致写出的代码虽能解决问题，但代码风格却不堪入目，让接手维护的人很是痛苦。想必你也都经历过！

所以，我的(可能不成熟的)看法是，逻辑清晰(可读性强)大于算法的高效。所以，接下来我写的一些 LeetCode 解析，会着重说明怎么将清晰的逻辑用代码表达出来，而不是讨论这样写是否高效。当然，和那些头脑厉害的人比，我的算法能力(真的)是不值一提的。

我们开始吧！

题目：LeetCode 1047: Remove All Adjacent Duplicates In String^[1]

要求：给定小写字母组成的 字符串 S，找到并移除其中两个连续重复的字符，直到最后结果中不再出现连续重复的字符。

示例：

输入："abbaca"
输出："ca"
解释："abbaca" => "aaca" => "ca"

注意：

1. 1 <= S.length <= 20000
2. S
   只包含小写的英文字母

分析：

仔细阅读该题，用代码思维可以将核心问题提炼为：

遍历字符串 S
，如果后一个元素和前一个相同，则移除这两个元素。

如此以来，代码就好写了：

public String removeDuplicates(String S) {

    char[] chars = S.toCharArray();
    int len = chars.length;

    // 用来收集不重复的字符
    // 因为第一个元素不需要和前边的元素比(前边的元素不存在)，所以直接加到结果集中
    StringBuilder result = new StringBuilder().append(chars[0]);

    for (int i = 1; i < len; i++) {
        int rlen = result.length();

        if (rlen != 0 && chars[i] == result.charAt(rlen - 1)) {
            // 当前元素和前一个元素相同，移除
            result.deleteCharAt(rlen - 1);
        } else {
            // 两个不同，则追加到结果集中
            result.append(chars[i]);
        }
    }

    return result.toString();
}

我们再观察上述代码对 result 变量的操作，是不是就只是 尾部追加 和 尾部删除？想到了什么？

对的，后入先出(last-in-first-out)的栈结构。所以代码可以利用 Java 内置的 Stack 类改写如下：

public String removeDuplicates(String S) {
    /* 只需删除重复项即可，因此可以使用栈实现
     * 每次添加时比较是否与栈顶元素相同
     *   - 若相同则删除栈顶元素且不插入
     *   - 若不相同则插入新元素
     */
    char[] s = S.toCharArray();
    int len = s.length;

    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < len; i++) {
        if (!stack.isEmpty() && s[i] == stack.peek()) {
            stack.pop();
        } else {
            stack.push(s[i]);
        }
    }

    StringBuilder str = new StringBuilder();
    for (Character c : stack) {
        str.append(c);
    }
    return str.toString();
}

使用 Stack 实现，代码是不是更清晰一些？

另外，打开 Stack类 的 Java 源码，可以看到如下一段注释：

A more complete and consistent set of LIFO stack operations is provided by the `Deque` interface and its implementations, which should be used in preference to this class.  For example:

Dequestack = new ArrayDeque();

即，在需要用到 Stack 的地方，建议使用 (Array)Deque 来替代，是不是又收获新知识了？

最后要说明的是，如果真的要考虑性能，经过我测试发现，上述代码中，性能从好到坏依次是：StringBuilder > ArrayDeque > Stack。

参考资料