代碼隨想錄_棧與隊列

棧與隊列

232.用棧實現隊列

232. 用棧實現隊列

使用棧實現隊列的下列操作：

push(x) – 將一個元素放入隊列的尾部。
pop() – 從隊列首部移除元素。
peek() – 返回隊列首部的元素。
empty() – 返回隊列是否為空。

思路: 定義兩個棧: 入隊棧, 出隊棧, 控制出入棧順序, 進入的元素倒兩次就是原順序

代碼:

class MyQueue {Stack<Integer> in;Stack<Integer> out;public MyQueue() {in = new Stack<>();out = new Stack<>();}public void push(int x) {in.push(x);}public int pop() {inToOut();return out.pop();}public int peek() {inToOut();return out.peek();}private void inToOut() {// out非空時不能往里面倒, 出的時候要先把out里的出完, 再倒入// 否則原來的數據會被覆蓋if(!out.isEmpty()) return;while(!in.isEmpty()) {out.push(in.pop());}}public boolean empty() {return in.isEmpty() && out.isEmpty();}
}

225. 用隊列實現棧

使用隊列實現棧的下列操作：

push(x) – 元素 x 入棧
pop() – 移除棧頂元素
top() – 獲取棧頂元素
empty() – 返回棧是否為空

思路: 每次pop, peek都要reposition

代碼:

class MyStack {Queue<Integer> queue;public MyStack() {queue = new LinkedList<>();}public void push(int x) {queue.offer(x);}public int pop() {reposition();// 每次pop時將隊列前size - 1個放到隊列末尾return queue.poll();}public int top() {reposition();// 每次pop時將隊列前size - 1個放到隊列末尾int n = queue.poll();queue.offer(n);return n;}public boolean empty() {return queue.isEmpty();}private void reposition() {int size = queue.size();size--;while(size-- > 0) {queue.offer(queue.poll());}}
}

20. 有效的括號

給定一個只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串，判斷字符串是否有效。

有效字符串需滿足：

左括號必須用相同類型的右括號閉合。
左括號必須以正確的順序閉合。
注意空字符串可被認為是有效字符串。

思路:

一共有三種情況:

字符串里左方向的括號多余了，所以不匹配。
括號沒有多余，但是括號的類型沒有匹配上。
字符串里右方向的括號多余了，所以不匹配。

每一個左括號, 壓入對應的右括號, 當開始遍歷右括號時, 按照如下方式和棧中元素進行對比

代碼:

class Solution {public boolean isValid(String s) {// 0. 剪枝int len = s.length();if(len % 2 != 0) return false;// 長度為奇數, 則一定不能匹配// 1. 初始化棧Stack<Character> stack = new Stack<>();// 2. 遍歷每一個字符for(int i = 0;i < len;i++) {// 2.1 每一個左括號, 壓入對應的右括號if(s.charAt(i) == '(') {stack.push(')');}else if(s.charAt(i) == '[') {stack.push(']');}else if(s.charAt(i) == '{') {stack.push('}');// 2.2 每一個右括號, 查看棧中對應的右括號是否相等}else if(stack.isEmpty() || s.charAt(i) != stack.peek()) {// 不能是s.pop,否則在判斷時就會將元素彈出return false;}else {// 右括號匹配, 出棧stack.pop();}}// 3. 遍歷完后, 查看棧中是否還有右括號(左括號多余)return stack.isEmpty();}
}

1047. 刪除字符串中的所有相鄰重復項

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

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

在完成所有重復項刪除操作后返回最終的字符串。答案保證唯一。

示例：

輸入：“abbaca”
輸出：“ca”
解釋：例如，在 “abbaca” 中，我們可以刪除 “bb” 由于兩字母相鄰且相同，這是此時唯一可以執行刪除操作的重復項。之后我們得到字符串 “aaca”，其中又只有 “aa” 可以執行重復項刪除操作，所以最后的字符串為 “ca”。

法一: 棧

思路: 用字符串模擬棧(也可以直接用棧, 需要再轉為字符串)進行"消消樂", 留下的就是最終的字符串

代碼:

class Solution {public String removeDuplicates(String s) {// 1. 定義字符串模擬棧StringBuilder sb = new StringBuilder();// 2. 遍歷s的每一位, 與棧進行消除int top = -1;for(int i = 0;i < s.length();i++) {if(top >= 0 && s.charAt(i) == sb.charAt(top)) {sb.deleteCharAt(top--);}else {sb.append(s.charAt(i));top++;}}// 3. 返回return sb.toString();}
}

法二:雙指針

思路: 快指針指向原字符串要處理的字符, 慢指針指向新的字符串, 當新字符串出現相鄰相等的情況, 則將兩個同時排除, 回退到第一次出現該字符的位置, 繼續遍歷原字符串的下一個字符, 否則, 快慢指針同時往前走.

代碼:

class Solution {public String removeDuplicates(String s) {// 1. 初始化char[] str = s.toCharArray();int fast = 0,slow = 0;// 2. 遍歷原字符串while(fast < str.length) {str[slow] = str[fast++];// 2.1 新的字符串出現成對可消除, 走到第一次出現的位置, 覆蓋(同時消除)if(slow > 0 && str[slow] == str[slow - 1]) {slow--;}else{// 2.2 沒有可消除的字符, fast slow都往后走slow++;}}// 3. 返回return new String(str,0,slow);}
}

150. 逆波蘭表達式求值

根據逆波蘭表示法，求表達式的值。

有效的運算符包括 + , - , * , / 。每個運算對象可以是整數，也可以是另一個逆波蘭表達式。

說明：

整數除法只保留整數部分。給定逆波蘭表達式總是有效的。換句話說，表達式總會得出有效數值且不存在除數為 0 的情況。

示例 1：

輸入: [“2”, “1”, “+”, “3”, " * "]
輸出: 9
解釋: 該算式轉化為常見的中綴算術表達式為：((2 + 1) * 3) = 9

思路: 棧, 每遇到一個操作符, 就對棧中的兩個數組進行計算, 注意: 棧中的順序與原來后綴表達式計算順序相反, 因此彈出來的兩個數字運算時交換順序注意: 棧中的順序與原來后綴表達式計算順序相反, 因此彈出來的兩個數字運算時交換順序.

代碼:

class Solution {public int evalRPN(String[] tokens) {// 0. 剪枝if(tokens.length == 1) return Integer.valueOf(tokens[0]);// 1. 定義棧Stack<Integer> sk = new Stack<>();// 2. 逐個處理for(String s : tokens) {// 2.1 處理運算符if("+".equals(s) || "-".equals(s) || "*".equals(s) || "/".equals(s)) {// 注意: 棧中的順序與原來后綴表達式計算順序相反, 因此彈出來的兩個數字運算時交換順序int n = sk.pop();int m = sk.pop();if("+".equals(s)) {sk.push(m + n);}else if("-".equals(s)) {sk.push(m - n);}else if("*".equals(s)) {sk.push(m * n);}else if("/".equals(s)) {sk.push(m / n);}}else {// 2.2 處理數字sk.push(Integer.valueOf(s));}}// 3. 返回return sk.pop();}
}

239. 滑動窗口最大值

給定一個數組 nums，有一個大小為 k 的滑動窗口從數組的最左側移動到數組的最右側。你只可以看到在滑動窗口內的 k 個數字。滑動窗口每次只向右移動一位。

返回滑動窗口中的最大值。

進階：

你能在線性時間復雜度內解決此題嗎？

提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

思路: 單調隊列, 保證隊頭為窗口內最大值, 保證每次隊列內有不多于k個元素

代碼:

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {// 1. 定義容器ArrayDeque<Integer> q = new ArrayDeque<>();int n = nums.length,index = 0;int[] ans = new int[n - k + 1];// 2. 循環遍歷for(int i = 0;i < n;i++) {// 2.1 出: 將不符合窗口范圍的移出while(!q.isEmpty() && q.peek() < (i - k + 1)) q.poll();// 2.2 入: 先將比該數值小的從后往前依次移出(保證單調), 再放入while(!q.isEmpty() && nums[q.peekLast()] < nums[i]) q.pollLast();q.offer(i);// 2.3 收集: 當窗口中走夠k個元素時, 開始收集if(i >= k - 1) ans[index++] = nums[q.peek()];}// 3. 返回return ans;}
}

347.前 K 個高頻元素

347. 前 K 個高頻元素

給定一個非空的整數數組，返回其中出現頻率前 k 高的元素。

示例 1:

輸入: nums = [1,1,1,2,2,3], k = 2
輸出: [1,2]

示例 2:

輸入: nums = [1], k = 1
輸出: [1]

思路: map統計num及其出現次數, PriorityQueue用作小頂堆, 維護前k個出現次數最多的entry

代碼:

class Solution {public int[] topKFrequent(int[] nums, int k) {// 1. 定義容器int[] ans = new int[k];Map<Integer,Integer> map = new HashMap<>();PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2) -> o1[1] - o2[1]);// 2. 填充mapfor(int num : nums) {map.put(num,map.getOrDefault(num,0) + 1);}// 3. 填充pqSet<Map.Entry<Integer,Integer>> entries = map.entrySet();for(Map.Entry<Integer,Integer> e : entries) {int[] t = new int[2];t[0] = e.getKey();t[1] = e.getValue();pq.offer(t);// 維持小頂堆中3個出現次數最多元素if(pq.size() > k) pq.poll();}// 4. 返回for(int i = 0;i < k;i++) {ans[i] = pq.poll()[0];}return ans;}
}