代码随想录：栈和队列

[TOC]

栈和队列

一开始小登自己认为，栈和队列不就是特殊一点的数组嘛，就是闭合了一端的数组。还不能通过下标索引进行检索（这个时候完全没想到，栈和队列里面的元素存储并不是连续的内存）

225. Implement Stack using Queues

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

• void push(int x) Pushes element x to the top of the stack.
• int pop() Removes the element on the top of the stack and returns it.
• int top() Returns the element on the top of the stack.
• boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

• You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
• Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue’s standard operations.

Example 1:

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

两个队列实现栈

public class _225 {
    static class MyStack {
        Queue<Integer> queue = new LinkedList<>();
        Queue<Integer> secQueue = new LinkedList<>();

        public MyStack() {

        }

        public void push(int x) {
            queue.offer(x);
        }

        public int pop() {
            while (queue.size() != 1) {
                Integer poll = queue.poll();
                secQueue.offer(poll);
            }
            Integer top = queue.poll();
            while(!secQueue.isEmpty()){
                Integer poll = secQueue.poll();
                queue.offer(poll);
            }
            return top;
        }

        public int top() {
            while (queue.size() != 1) {
                Integer poll = queue.poll();
                secQueue.offer(poll);
            }
            Integer peek = queue.poll();
            while(!secQueue.isEmpty()){
                Integer poll = secQueue.poll();
                queue.offer(poll);
            }
            queue.offer(peek);
            return peek;
        }

        public boolean empty() {
            return queue.isEmpty();

        }
    }

    public static void main(String[] args) {
        MyStack myStack = new MyStack();
        myStack.push(1);
        myStack.push(2);
        System.out.println(myStack.top());
        System.out.println(myStack.pop());
    }
/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */
}

一个队列实现栈(使用逻辑长度)

其实完全不需要 使用额外一个队列进行备份。

完全可以弹出后再加入到队尾就行

使用size实现逻辑长度为1时弹出的就是栈顶

class MyStack {
       Queue<Integer> queue = new LinkedList<>();

       public MyStack() {

       }

       public void push(int x) {
           queue.offer(x);
       }

       public int pop() {
           int size = queue.size();
           while(size!=1){
               int poll = queue.poll();
               queue.offer(poll);
               size--;
           }
           int pop = queue.poll();
           return pop;
       }

        public int top() {
        int top =  this.pop();
       queue.offer(top);
        return top;
       }

       public boolean empty() {
           return queue.isEmpty();

       }
   }

20. Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = “()”

Output: true

Example 2:

Input: s = “()[]{}”

Output: true

Example 3:

Input: s = “(]”

Output: false

Example 4:

Input: s = “([])”

Output: true

显而易见版

class Solution {
        public boolean isValid(String s) {

            int length = s.length();
            LinkedList<Character> list =new LinkedList<>();
            for (int i = 0; i < length; i++) {
                char c = s.charAt(i);
                if(c=='('||c=='{'||c=='['){
                    list.add(c);
                }
                Character top = list.getLast();
                if(c==')'){
                    if(top=='('){
                        list.removeLast();
                    }else {
                        return false;
                    }
                }
                if(c=='}'){
                    if(top=='{'){
                        list.removeLast();
                    }else {
                        return false;
                    }
                }
                if(c==']'){
                    if(top=='['){
                        list.removeLast();
                    }else {
                        return false;
                    }
                }
            }
            return list.isEmpty();
        }
    }

优化

显而易见版明显看着很多，代码感觉也很冗余。尤其是是要判断右括号的添加

class Solution {
        public boolean isValid(String s) {

            int length = s.length();
            LinkedList<Character> list =new LinkedList<>();
            for (int i = 0; i < length; i++) {
                char c = s.charAt(i);
                if(c=='('){
                    list.push(')');
                }else if(c=='{'){
                    list.push('}');
                }else if(c=='['){
                    list.push(']');
                }else{
                    if(list.isEmpty()||list.pop()!=c){
                        return false;
                    }
                }
            }
            return list.isEmpty();
        }
    }

1047. Remove All Adjacent Duplicates In String

You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.

We repeatedly make duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.

Example 1:

Input: s = "abbaca"
Output: "ca"
Explanation: 
For example, in "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move.  The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca".

Example 2:

Input: s = "azxxzy"
Output: "ay"

难受版（列表转字符串）

class Solution {
       public String removeDuplicates(String s) {
           LinkedList<Character> list = new LinkedList<>();
           for (int i = 0; i < s.length(); i++) {
               char c = s.charAt(i);
               if(!list.isEmpty()){
                   if(list.getLast()==c){
                       list.removeLast();
                   }else{
                       list.addLast(c);
                   }
               }else{
                   list.addLast(c);
               }
           }
           StringBuilder sb = new StringBuilder();
           for (Character character : list) {
               sb.append(character);
           }
           return sb.toString();
       }
   }

使用StringBuilder作为栈

class Solution {
        public String removeDuplicates(String s) {
           StringBuilder sb =new StringBuilder();
           for (int i = 0; i < s.length(); i++) {
               char c = s.charAt(i);
               if(!sb.isEmpty()){
                   if(sb.charAt(sb.length()-1)==c){
                       sb.deleteCharAt(sb.length()-1);
                   }else{
                       sb.append(c);
                   }
               }else{
                   sb.append(c);
               }
           }
           return sb.toString();
       }
   }

150. Evaluate Reverse Polish Notation

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

• The valid operators are '+', '-', '*', and '/'.
• Each operand may be an integer or another expression.
• The division between two integers always truncates toward zero.
• There will not be any division by zero.
• The input represents a valid arithmetic expression in a reverse polish notation.
• The answer and all the intermediate calculations can be represented in a 32-bit integer.

Example 1:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

class Solution {
      public int evalRPN(String[] tokens) {
            Stack<Integer> stack = new Stack<>();
            for (String token : tokens) {
             if (token.equals("+")) {
                    stack.push(stack.pop() + stack.pop());
                } else if (token.equals("-")) {
                    stack.push(-stack.pop() + stack.pop());
                } else if (token.equals("*")) {
                    stack.push(stack.pop() * stack.pop());
                } else if (token.equals("/")) {
                    int num1 = stack.pop();
                    int num2 = stack.pop();
                    stack.push(num2 / num1);
                } else {
                    stack.push(Integer.parseInt(token));
                }
            }
            return stack.pop();
        }
}

239. Sliding Window Maximum

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

首先滑动窗口就完全可以看作是一种队列。我们这个题要做到的就是，每次移动的时候都要弹出元素、放入元素、报告最大元素。

那我们可以维护一个队列用于存储最大值以及候选值。当很小的值弹出时这个队列不需要进行操作，只有当最大元素弹出或加入较大的元素时需要维护（通过比较放入到最大值/候选值）

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation: 
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Example 2:

Input: nums = [1], k = 1
Output: [1]

class Solution {
       LinkedList<Integer> queue =new LinkedList<>();
       public int[] maxSlidingWindow(int[] nums, int k) {
           ArrayList<Integer> list=new ArrayList<>();
           if(k==1){
               return nums;
           }
           for (int i = 0; i < k; i++) {
               push(nums[i]);
           }
           list.add(getFront());
           int len = nums.length;
           for (int i = k; i < len; i++) {
               if(getFront()==nums[i-k]){
                   pop();;
               }
               push(nums[i]);
               list.add(getFront());
           }
           return list.stream().mapToInt(Integer::valueOf).toArray();
       }
       public int getFront(){
           return queue.getFirst();
       }
       public void pop(){
           queue.removeFirst();
       }
       public void push(int x){
           while(!queue.isEmpty()&&queue.getLast()<x){
               queue.removeLast();
           }
           queue.add(x);
       }
   }

347. Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• k is in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer is unique.

Follow up: Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

使用哈希表

class Solution {
       public int[] topKFrequent(int[] nums, int k) {
           HashMap<Integer,Integer> map = new HashMap<>();
           for (int num : nums) {
              map.put(num,map.getOrDefault(num,0)+1);
           }
           return map.entrySet().stream().sorted((m1, m2) -> m2.getValue() - m1.getValue())
                   .limit(k).mapToInt(Map.Entry::getKey).toArray();
       }
   }

使用小顶堆

优化点就是，我们不需要将全部元素都进行排序，只需要维护一个k大小的堆就行了。

使用小顶堆是因为我们每次淘汰的都是频率最小的元素。

有兴趣的可以了解一下堆的加入和去除元素（虽然一般数据结构课肯定会讲解的）

class Solution {
      public int[] topKFrequent(int[] nums, int k) {
          HashMap<Integer,Integer> map = new HashMap<>();
          for (int num : nums) {
             map.put(num,map.getOrDefault(num,0)+1);
          }
          // 使用小顶堆 (频率比较大小)
          PriorityQueue<int[]> queue =new PriorityQueue<>((prior1,prior2)->prior1[1]-prior2[1]); 
          for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
              if(queue.size()<k){
                  queue.add(new int[]{entry.getKey(), entry.getValue()});
              }else{
                  if(queue.peek()[1]<entry.getValue()){
                      queue.poll();
                      queue.add(new int[]{entry.getKey(), entry.getValue()});
                  }
              }
          }
          int[] result = new int[k];
          for (int i = 0; i < k; i++) {
              result[i] = queue.poll()[0];
          }
          return result;
      }
  }

71. Simplify Path

You are given an absolute path for a Unix-style file system, which always begins with a slash '/'. Your task is to transform this absolute path into its simplified canonical path.

The rules of a Unix-style file system are as follows:

• A single period '.' represents the current directory.
• A double period '..' represents the previous/parent directory.
• Multiple consecutive slashes such as '//' and '///' are treated as a single slash '/'.
• Any sequence of periods that does not match the rules above should be treated as a valid directory or file name. For example, '...' and '....' are valid directory or file names.

The simplified canonical path should follow these rules:

• The path must start with a single slash '/'.
• Directories within the path must be separated by exactly one slash '/'.
• The path must not end with a slash '/', unless it is the root directory.
• The path must not have any single or double periods ('.' and '..') used to denote current or parent directories.

Return the simplified canonical path.

class Solution {
      public String simplifyPath(String path) {
          String[] split = path.split("/");
          // 去除空字符串 和 空格得到新的数组
          String[] newSplit = Arrays.stream(split).map(String::trim).filter(s -> !s.equals("") && !s.equals(" ")).toArray(String[]::new);
          LinkedList<String> stack = new LinkedList<>();
          for (String s : newSplit) {
              if(s.equals("..")){
                  if(!stack.isEmpty()){
                      stack.removeLast();
                  }
              }else if(!s.equals(".")){
                  stack.add(s);
              }
          }
          StringBuilder sb = new StringBuilder();
          for (String s : stack) {
              sb.append("/").append(s);
          }
          return sb.length()==0?"/":sb.toString();
      }
  }