文章目錄
- 前言
- 題目
- 題解
-
- NO1：棧解決
- NO2：字元串作棧
- NO3、雙指針(原數組上操作)
- 參考文章
前言
哈喽，我是長路，目前剛剛大三，方向是後端也偶爾搗鼓下前端，現在的主語言是Java。之前一大段時間都是在學習web開發的一些技術，就很久沒有進行類似于資料結構、算法之類的學習與刷題，打算這段時間拾起來好好學一學、搞一搞。
這段時間也是機緣巧合看到草帽路飛的部落格，加了自學群，正巧看到部落客組織在群裡組織了leetcode刷題打卡活動，我也就參與進來，為期一個月，打算堅持每天都花一些時間做一些題目，并通過部落格的方式來進行記錄。
目前跟着一個Github倉庫刷題(leetcode)：代碼随想錄leetcode刷題，目前為棧與隊列專題。
題目來源leetcode
leetcode位址：1047. 删除字元串中的所有相鄰重複項，難度：簡單。
題目描述(摘自leetcode)：
給出由小寫字母組成的字元串 S，重複項删除操作會選擇兩個相鄰且相同的字母，并删除它們。
在 S 上反複執行重複項删除操作，直到無法繼續删除。
在完成所有重複項删除操作後傳回最終的字元串。答案保證唯一。
示例：
輸入："abbaca"
輸出："ca"
解釋：
例如，在 "abbaca" 中，我們可以删除 "bb" 由于兩字母相鄰且相同，這是此時唯一可以執行删除操作的重複項。之後我們得到字元串 "aaca"，其中又隻有 "aa" 可以執行重複項删除操作，是以最後的字元串為 "ca"。
提示：
1 <= S.length <= 20000
S 僅由小寫英文字母組成。
本地調試代碼：
class Solution {
public String removeDuplicates(String s) {
...
}
public static void main(String[] args) {
System.out.println(new Solution().removeDuplicates("abbaca"));
}
}
思路：周遊字元時，每次先判斷目前棧頂元素是否與要入棧的元素相同，如果相同出棧，不相同入棧。最後将棧中的字元進行一一拼接傳回。
示例："abbaca" stack=[]
① 字元'a'，目前棧為空直接入棧 stack=['a']
② 字元'b'，棧不為空，與棧頂元素a比較，不相同入棧 stack=['a','b']
③ 字元'b'，棧不為空，與棧頂元素b比較，相同出棧 stack=['a']
④ 字元'a'，棧不為空，與棧頂元素b比較，相同出棧 stack=[]
⑤ 字元'c'，目前棧為空直接入棧 stack=['c']
⑥ 字元'a'，棧不為空，與棧頂元素c比較，不相同入棧 stack=['a','c']
最終從前往往後将元素移出進行拼接，傳回"ac"
代碼：
class Solution {
public String removeDuplicates(String s) {
Deque<Character> stack = new LinkedList<>();
for (char c : s.toCharArray()) {
//目前棧不為空，且棧頂與目前字元相同出棧
if(!stack.isEmpty() && stack.peek() == c){
stack.pop();
}else{//否則直接入棧
stack.push(c);
}
}
StringBuilder str = new StringBuilder();
while(!stack.isEmpty()){
str = str.append(stack.pollLast());
}
return str.toString();
}
}
思路：使用字元串作棧的好處就是可以省去上面送出中拼接的操作，最終留在字元串裡的就是要傳回出去的。
示例："abbaca" str="" top=-1
① 字元'a' 字元串(棧)為空，直接拼接 str="a" top=0
② 字元'b' 字元串(棧)不為空，與棧頂不相同，直接拼接 str="ab" top=1
③ 字元'b' 字元串(棧)不為空，與棧頂相同，删除指定元素 str="a" top=0
④ 字元'a' 字元串(棧)不為空，與棧頂相同，删除指定元素 str="" top=-1
⑤ 字元'c' 字元串(棧)為空，直接拼接 str="c" top=0
⑥ 字元'b' 字元串(棧)不為空，與棧頂不相同，直接拼接 str="ca" top=1
最終直接傳回str="ca"
class Solution {
//目的是拿到不重複的字元拼接内容
public String removeDuplicates(String s) {
//直接來拿字元串來作為棧進行操作，最終剩下來的就是不重複的
StringBuilder str = new StringBuilder();
int top = -1;
for (char c : s.toCharArray()) {
if(top >= 0 && c == str.charAt(top)){
str.deleteCharAt(top--);
}else{
str.append(c);
top++;
}
}
return str.toString();
}
}
思路：直接對原數組進行操作，不相鄰的重複元素直接覆寫舊元素，最終直接截取原數組指定長度内容傳回。
fast指針用來進行周遊一遍字元串的，[0,slow)永遠表示的是非相鄰重複項
示例：s="abbaca" slow=0,fast=0
① 字元'a' s[0]=s[0] (s="abbaca") slow=1,fast=1 | [0,slow)=> "a"
② 字元'b' s[1]=s[1] (s="abbaca") slow=2,fast=2 | [0,slow)=> "ab"
③ 字元'b' s[2]=s[2] (s="abbaca")(s[2]==s[1] => b=b重複，slow-1) slow=1,fast=3 | [0,slow)=> "a"
④ 字元'a' s[1]=s[3] (s="aabaca")(s[1]==s[0] => a=a重複，slow-1) slow=0,fast=4 | [0,slow)=> ""
⑤ 字元'c' s[0]=s[4] (s="cabaca")(slow=0，slow+1) slow=1,fast=5 | [0,slow)=> "c"
⑥ 字元'a' s[1]=s[5] (s="cabaca")(s[1]!=s[0]，slow++) slow=1,fast=4 | [0,slow)=> "ca"
最終直接傳回"ca"即可
//快慢指針，時間複雜度O(n)，空間複雜度O(1)
public String removeDuplicates(String s) {
//定義雙指針
int slow = 0;//左指針的目的是①檢測是否有相等，有後退，無前進。②實時更新目前最新位置值(友善下次進行對比以及舊值的覆寫，舊的值已無用)
int fast = 0;//右指針負責的工作是進行周遊作用
char[] chars = s.toCharArray();
while(fast < s.length()){
chars[slow] = chars[fast];
if(slow > 0 && chars[slow]==chars[slow-1]){
slow--;
}else{
slow++;
}
fast++;
}
//[0,slow)區間值
return new String(chars,0,slow);
}