0509

232.用棧實現隊列

class MyQueue {Deque<Integer> inStack;Deque<Integer> outStack;public MyQueue() {inStack = new ArrayDeque<Integer>();outStack = new ArrayDeque<Integer>();}public void push(int x) {inStack.push(x);}public int pop() {if (outStack.isEmpty()) {in2Out();}return outStack.pop();}public int peek() {if (outStack.isEmpty()) {in2Out();}return outStack.peek();}public boolean empty() {return inStack.isEmpty() && outStack.isEmpty();}private void in2Out() {while (!inStack.isEmpty()) {outStack.push(inStack.pop());}}}

225. 用隊列實現棧

20.有效的括號

class Solution {private static final Map<Character,Character> map=new HashMap<Character,Character>(){{put('{','}');put('(',')');put('[',']');put('?','?');}};public boolean isValid(String s) {if(s.length()>0&&!map.containsKey(s.charAt(0))) return false;LinkedList<Character> stack=new LinkedList<Character>() {{add('?');}};for(Character c:s.toCharArray()){if(map.containsKey(c)) stack.addLast(c);else if(map.get(stack.removeLast()) !=c) return false;}return stack.size()==1;}
}

0510

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

public String removeDuplicates(String s) {char[] s1=s.toCharArray();int top=-1;for(int i=0;i<s.length();i++){if(top==-1||s1[top]!=s1[i]){s1[++top]=s1[i];}else{top--;}}return String.valueOf(s1,0,top+1);}

150.逆波蘭表達式求值

public int evalRPN(String[] tokens) {Stack<Integer> numStack=new Stack<>();Integer op1,op2;for(String s:tokens){switch(s){case "+":op2=numStack.pop();op1=numStack.pop();numStack.push(op1+op2);break;case "-":op2=numStack.pop();op1=numStack.pop();numStack.push(op1-op2);break;case "*":op2=numStack.pop();op1=numStack.pop();numStack.push(op1*op2);break;case "/":op2=numStack.pop();op1=numStack.pop();numStack.push(op1/op2);break;default:numStack.push(Integer.valueOf(s));break;}}return numStack.pop();}

347.前k個高頻元素

public int[] topKFrequent(int[] nums, int k) {// 優先級隊列，為了避免復雜 api 操作，pq 存儲數組// lambda 表達式設置優先級隊列從大到小存儲 o1 - o2 為從小到大，o2 - o1 反之PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);int[] res = new int[k]; // 答案數組為 k 個元素Map<Integer, Integer> map = new HashMap<>(); // 記錄元素出現次數for (int num : nums) map.put(num, map.getOrDefault(num, 0) + 1);for (var x : map.entrySet()) { // entrySet 獲取 k-v Set 集合// 將 kv 轉化成數組int[] tmp = new int[2];tmp[0] = x.getKey();tmp[1] = x.getValue();pq.offer(tmp);// 下面的代碼是根據小根堆實現的，我只保留優先隊列的最后的k個，只要超出了k我就將最小的彈出，剩余的k個就是答案if(pq.size() > k) {pq.poll();}}for (int i = 0; i < k; i++) {res[i] = pq.poll()[0]; // 獲取優先隊列里的元素}return res;}