棧與隊列系列② -- 删除字元串中的所有相鄰重複項

目錄

• ​​題目概述​​
• ​​解題思路​​

• ​​方法一​​
• ​​方法二​​

• ​​代碼實作​​

• ​​方法一​​
• ​​方法二（第一種）​​
• ​​方法二（第二種）​​
• ​​方法三（第三種）​​

• ​​做題反思​​

題目概述

此題對應力扣​​1047.删除字元串中的所有相鄰重複項​​

題目：

給出由小寫字母組成的字元串 S，重複項删除操作會選擇兩個相鄰且相同的字母，并删除它們。

在 S 上反複執行重複項删除操作，直到無法繼續删除。

在完成所有重複項删除操作後傳回最終的字元串。答案保證唯一。

示例：

輸入：“abbaca”

輸出：“ca”

解釋：

例如，在 “abbaca” 中，我們可以删除 “bb” 由于兩字母相鄰且相同，這是此時唯一可以執行删除操作的重複項。之後我們得到字元串 “aaca”，其中又隻有 “aa” 可以執行重複項删除操作，是以最後的字元串為 “ca”。

解題思路

此題有兩種方法：

• 雙指針法
• 利用棧結構解題

方法一

若使用雙指針法的話，其主要思想就是：遇到兩個一樣的，把他給覆寫掉！首先在建立快慢指針後，将字元串轉化為char[]型數組，讓快慢指針首先均指向數組的頭部，當慢指針所指内容與其前一位的内容相同時，慢指針後退一位，然後将快指針的内容覆寫到慢指針上。（為什麼不是慢指針所指内容與其後一位的内容相同時呢？如果這樣的話當快指針覆寫過來的内容與慢指針的前一位也相同了，這種情況就處理不了了。）就這樣直到快指針到數組的尾部。最後傳回慢指針所指部分的前面即可。

方法二

若使用棧的結構做這道題的話，思路就是把字元串的每一個字元往棧中添加，每次添加的時候與棧頂的元素比較，如果一樣的話就不加入并且把棧頂的元素給彈出來，如此下去。最後把棧中的字元拿出來拼接成字元串後，再reverse一下即可。

若直接将字元串作為棧，可以省去轉化為字元串的操作

還有第三種将字元串轉化為StringBuilder之後，向末尾添加一個空字元，将字元串的開頭依次彈出，并于字元串的末尾比較，如果相同則把末尾的字元也彈出，如果不相同則把開頭彈出的字元添加到字元串尾部，如此進行，直到第一個字元是開頭添加的那個空字元。不過此法效率較低，不是很推薦使用。

如圖：

代碼實作

方法一

public class LeetCode1047ProMax {
    // 此方法使用雙指針法
    public String removeDuplicates(String s) {
        //首先将String化為char型數組
        char[] ss = s.toCharArray();
        // 建立快慢指針
        int head = 0;
        int end = 0;
        while(end < ss.length){
            ss[head] = ss[end];
            if(head > 0 && ss[head] == ss [head-1]){
                head--;
            }else{
                head++;
            }
            end++;
        }
        return new String(ss).substring(0,head);
    }
}      

方法二（第一種）

ArrayDeque<Character> deque = new ArrayDeque<>();
        char ch;
        for (int i = 0; i < S.length(); i++) {
            ch = S.charAt(i);
            if (deque.isEmpty() || deque.peek() != ch) {
                deque.push(ch);
            } else {
                deque.pop();
            }
        }
        String str = "";
        //剩餘的元素即為不重複的元素
        while (!deque.isEmpty()) {
            str = deque.pop() + str;
        }
        return str;      

方法二（第二種）

public String removeDuplicates(String s) {
        // 将 res 當做棧
        StringBuffer res = new StringBuffer();
        // top為 res 的長度
        int top = -1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 當 top > 0,即棧中有字元時，目前字元如果和棧中字元相等，彈出棧頂字元，同時 top--
            if (top >= 0 && res.charAt(top) == c) {
                res.deleteCharAt(top);
                top--;
            // 否則，将該字元 入棧，同時top++
            } else {
                res.append(c);
                top++;
            }
        }
        return res.toString();
    }      

方法三（第三種）

public String removeDuplicates(String s) {
        StringBuilder ss = new StringBuilder(s);
        ss.append(' ');
        while(ss.charAt(0) != ' '){
            char head = ss.charAt(0);
            ss.deleteCharAt(0);
            if(ss.charAt(ss.length() - 1) == head){
                ss.deleteCharAt(ss.length() - 1);
            }else{
                ss.append(head);
            }
        }
        ss.deleteCharAt(0);
        return new String(ss);
    }      

做題反思

// 嘗試用雙指針
    public String removeDuplicates(String s) {
        if (s.length() < 2) {
            return s;
        }
        StringBuilder ss = new StringBuilder(s);
        // 建立雙指針
        // 前指針
        int head = 0;
        int end = 1;
        while (end < ss.length()) {
            if (ss.charAt(head) == ss.charAt(end)) {
                ss.delete(head, end + 1);
                head = 0;
                end = 1;
                continue;
            }
            head++;
            end++;
        }
        if (ss.length() < 2) {
            return new String(ss);
        } else if (ss.charAt(0) == ss.charAt(1)) {
            return "";
        }
        return new String(ss);
    }      

• 對雙指針法掌握的不透徹
• 對資料的底層結構加強探索