20. 有效的括號(hào)

題目詳細(xì)：LeetCode.20

由題可知，有效字符串需滿足：

• 左括號(hào)必須用相同類型的右括號(hào)閉合。
• 左括號(hào)必須以正確的順序閉合。
• 每個(gè)右括號(hào)都有一個(gè)對(duì)應(yīng)的相同類型的左括號(hào)。

那么，我們可以利用棧后進(jìn)先出的特點(diǎn)：

• 當(dāng)遍歷到左括號(hào)時(shí)，將左括號(hào)字符依次進(jìn)棧
• 當(dāng)遍歷到右括號(hào)時(shí)，將棧頂?shù)淖罄ㄌ?hào)字符出棧
  • 左括號(hào)如果與閉括號(hào)屬于相同類型，則為有效括號(hào)，繼續(xù)遍歷下一個(gè)字符
  • 左括號(hào)如果與閉括號(hào)屬于不同類型，則為無效括號(hào)，棧內(nèi)剩余的左括號(hào)也無法以正確的順序閉合，返回false
  • 如果棧為空，則說明不存在與之匹配的左括號(hào)，返回false
• 當(dāng)遍歷完輸入的字符串后，注意需要判斷棧是否為空，進(jìn)而來判斷字符串內(nèi)的括號(hào)是否已完全匹配

Java解法（棧）：

class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for(char a: s.toCharArray()){if(a == '(' || a == '{' || a == '['){stack.push(a);}else if(stack.isEmpty()){return false;}else{char b = stack.pop();// 在ASCII碼中，左括號(hào)和右括號(hào)的差值 <= 2// 所以這里直接用 Math.abs(a-b) 來判斷左右括號(hào)是否匹配if(Math.abs(a-b) > 2){return false;}}}return stack.isEmpty();}
}

---

1047. 刪除字符串中的所有相鄰重復(fù)項(xiàng)

題目詳細(xì)：LeetCode.1047

這道題的實(shí)現(xiàn)方式不同，但解決思路是殊途同歸的，都是利用棧后進(jìn)先出的存儲(chǔ)特點(diǎn)來解題：

• 字符串中的字符依zg次進(jìn)棧，這樣就保證了出棧的字符一定與下一個(gè)字符是相鄰的
• 那么只需要比較棧頂元素和即將進(jìn)棧的元素是否重復(fù)
  • 如果重復(fù)，則彈出棧頂元素
  • 如果不重復(fù)，則將遍歷到字符進(jìn)棧
• 最后只需要將棧內(nèi)的字符重新組成字符串，即為無重復(fù)項(xiàng)的字符串。

Java解法（棧）：

class Solution {public String removeDuplicates(String s) {Stack<Character> stack = new Stack<>();for(char a : s.toCharArray()){if(stack.isEmpty()){stack.push(a);}else{char b = stack.pop();if(a != b){stack.push(b);stack.push(a);}}}StringBuffer sb = new StringBuffer();while(!stack.isEmpty()){sb.insert(0, stack.pop());}return sb.toString();}
}

無獨(dú)有偶，我們也可以用同樣具備后進(jìn)先出特點(diǎn)的雙向隊(duì)列來解決這道問題：

Java解法（雙向隊(duì)列）：

class Solution {public String removeDuplicates(String s) {Deque<Character> deque = new LinkedList<>();for(char a : s.toCharArray()){if(deque.isEmpty()){deque.add(a);}else{char b = deque.pollLast();if(a != b){deque.add(b);deque.add(a);}}}StringBuffer sb = new StringBuffer();while(!deque.isEmpty()){sb.append(deque.poll());}return sb.toString();}
}

還有更為效率的方法，就是將字符串轉(zhuǎn)為字符數(shù)組后，通過雙指針，來模擬棧進(jìn)棧和壓棧時(shí)棧頂指針的移動(dòng)，以及對(duì)重復(fù)字符的替換的過程，來解決這一問題：

Java解法（雙指針/模擬棧）：

class Solution {public String removeDuplicates(String s) {char[] ch = s.toCharArray();int top = 0;int next = 0;while(next < s.length()){ch[top] = ch[next];if(top > 0 && ch[top] == ch[top - 1]){top--;}else{top++;}next++;}return new String(ch,0,top);}
}

---

150. 逆波蘭表達(dá)式求值

題目詳細(xì)：LeetCode.150

波蘭表達(dá)式，其實(shí)就是將表達(dá)式用二叉樹的形式表示后，中序遍歷二叉樹得到的序列；而逆波蘭表達(dá)式，就是后序遍歷二叉樹得到的序列。

觀察逆波蘭表達(dá)式的數(shù)組，可以發(fā)現(xiàn)：

• 利用棧先進(jìn)后出的特點(diǎn)，能夠保證兩個(gè)數(shù)值計(jì)算的前后順序
• 當(dāng)遇到一個(gè)算術(shù)符號(hào)時(shí)，則在棧中彈出最近的兩個(gè)數(shù)
• 將這兩個(gè)數(shù)，按照算術(shù)符號(hào)進(jìn)行相應(yīng)的術(shù)式計(jì)算出結(jié)果
• 然后將計(jì)算結(jié)果再次壓入棧中，保證后續(xù)數(shù)值計(jì)算的前后順序
• 直到表達(dá)式遍歷完，棧中僅剩的計(jì)算結(jié)果即為最終結(jié)果

Java解法（雙指針/模擬棧）：

class Solution {public int evalRPN(String[] tokens) {Deque<Integer> deque = new LinkedList<>();for(String t: tokens){if(t.equals("+") || t.equals("-") || t.equals("*") || t.equals("/")){int a = 0, b = 0, c = 0;a = deque.pollLast();b = deque.pollLast();switch(t){case "+":c = b + a;break;case "-":c = b - a;break;case "*":c = b * a;break;case "/":c = b / a;break;}deque.add(c);}else{deque.add(Integer.parseInt(t));}}return deque.poll();}
}