[toc]

Stack

  1. What is a stack?

    • Answer: A stack is a linear data structure that follows the Last In, First Out (LIFO) principle, where the last element added to the stack is the first one to be removed. Common operations include push (to add an element), pop (to remove the top element), and peek (to view the top element without removing it).

  2. What are the primary operations of a stack?

    • Answer:

      The primary operations of a stack are:

      • push(x): Add element x to the top of the stack.
      • pop(): Remove the element from the top of the stack.
      • peek() or top(): Return the top element without removing it.
      • isEmpty(): Return true if the stack is empty, false otherwise.

  3. How is a stack different from a queue?

    • Answer: A stack follows the LIFO (Last In, First Out) principle, where the last element added is the first to be removed. A queue follows the FIFO (First In, First Out) principle, where the first element added is the first to be removed.

232. Implement Queue using Stacks

Easy

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class MyQueue {

    Stack<Integer> in;
    Stack<Integer> out;
    public MyQueue() {
        in = new Stack<>();
        out = new Stack<>();
    }
    
    void push(int x) {
        in.push(x);
    }
    
    int pop() {
        if(!out.isEmpty()){
            return out.pop();
        }else{
            while(!in.isEmpty()){ // it would be better to make it a function since both pop and peek will need to do this!
                int temp = in.pop();
                out.push(temp);
            }  
        }
        return out.pop();
    }
    
    int peek() {
        if(!out.isEmpty()){
            return out.peek();
        }else{
            while(!in.isEmpty()){
                int temp = in.pop();
                out.push(temp);
            }  
        }
        return out.peek();
    }
    
    public boolean empty() {
        return(in.isEmpty() && out.isEmpty());
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

improve:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class MyQueue {
    Stack<Integer> stackIn;  //！！！！
    Stack<Integer> stackOut; //！！！！
    public MyQueue() {
        stackIn = new Stack<>();//负责进栈
        stackOut = new Stack<>();//负责出栈
    }
    
    public void push(int x) {
        stackIn.push(x);
    }
    
    public int pop() {
        clearStack();
        return stackOut.pop();
    }
    
    public int peek() {
        clearStack();
        return stackOut.peek();
    }
    
    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }
	
	//notice！！！！！
    private void clearStack(){  // double stacks, inmotating queue
    //在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。
        if(stackOut.isEmpty()) { //important!!! stackout 全部搬空了以后再进数据，不然顺序会乱
            while(!stackIn.isEmpty()){ //important
                //make sure stackIn is always emtpy, everytime there's new element added to the stack it will be added to stackOut imediately
                stackOut.push(stackIn.pop());
            }
        }

    }
}

225. Implement Stack using Queues

Easy

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).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class MyStack {
    Queue<Integer> que;
    public MyStack() {
        que = new LinkedList<>(); //！！ notice here, is LinkedList
    }
    
    public void push(int x) {
        Queue<Integer> temp = new LinkedList<>();
        while(!que.isEmpty()){
            temp.offer(que.poll());
        }
        que.offer(x);
        while(!temp.isEmpty()){
            que.offer(temp.poll());
        }
    }
    
    public int pop() {
        return que.poll();
    }
    
    public int top() {
        return que.peek();
    }
    
    public boolean empty() {
        return que.isEmpty();

    }
}

/**
 * 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();
 */

improve:

queue biting its tail

1
2
3
4
5
6
7
8
9
10
11
//每 offer 一个数（A）进来，都重新排列，把这个数（A）放到队列的队首, notic 每字
    public void push(int x) {
        que.offer(x);
        int size = que.size();
        size = size - 1; //!!!!!
        //移动除了 A 的其它数
        while(size > 0){
            que.offer(que.poll());
            size--;
        }
    }

232 & 255 wrap up

232 拿另外一个stack来装之前stack里面的数，这样另外这个stack里面最上面的数就是新加的数

all previous elements are removed from the stack, and the new element to be added is placed at the front of the stack.

255 把之前所有的数都拿出来，把要加的数放到最前面

all previous elements are removed from the stack, and the new element to be added is placed at the front of the stack.

20. Valid Parentheses

Easy

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:

1
2
Input: s = "()"
Output: true

Example 2:

1
2
Input: s = "()[]{}"
Output: true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        char[] ss = s.toCharArray();
        for(char i: ss){
            if(i == '(' || i == '[' || i == '{' ){
                stack.add(i);
            }else{
                if(stack.isEmpty()) return false;
                char temp = stack.pop();
                if(i == ')'){
                    if(temp != '(') return false;
                }else if( i == '}'){
                    if(temp != '{') return false;
                }else{
                    if(temp != '[') return false;
                }
            }
        }
        if(stack.isEmpty())
            return true;
        return false;

    }
}

1047. Remove All Adjacent Duplicates In String

Easy

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:

1
2
3
4
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".
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();
        char[] ss = s.toCharArray();
        for(char i: ss){
            if(!stack.isEmpty()){
                char temp = stack.peek();
                if(temp == i){
                    stack.pop();
                }else{
                    stack.add(i);
                }
            }else{
                stack.add(i);
            }
        }
        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()){
            sb.append(stack.pop());
        }
        return sb.reverse().toString(); //!!!!!
    }
}

150. Evaluate Reverse Polish Notation

Medium

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:

1
2
3
Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(String i: tokens){
            if(i.equals("+")){
               int res = stack.pop()  + stack.pop() ;
               stack.push(res);
            }else if(i.equals("-")){
                int res = -stack.pop()  + stack.pop() ;
                stack.push(res);
            }else if(i.equals("*")){
                int res =  (stack.pop() ) * (stack.pop() );
                stack.push(res);
            }else if(i.equals("/")){
                int devider = stack.pop() ;
                int devident = stack.pop() ;
                stack.push(devident/devider);
            }else {
                stack.push(Integer.valueOf(i)); //!!!!
            }
        }
        return stack.pop();

    }
}

In my initial attempt, I mistakenly converted the tokens array into a char array, which was incorrect.

wrap up the application of using stack

  1. Deal with Nesting: Like checking if parentheses or brackets are balanced, or navigating nested structures like folders in a directory.

  2. Need to Explore Possibilities: For example, finding a path through a maze or searching for solutions in a game.

  3. Manage Function Calls or Recursion: When you’re evaluating expressions, tracking function calls, or handling undo/redo actions.

  4. Handle Parsing or Syntax Checking: Such as converting expressions between different formats or making sure they follow the right rules.

  5. Keep Track of State or History: Like tracking your browsing history or managing the state of a game.

239. Sliding Window Maximum

😭Hard

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:

1
2
3
4
5
6
7
8
9
10
11
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

https://www.bilibili.com/video/BV1XS4y1p7qj/?vd_source=7cf01a4cc731f5d6335bce33c114b60c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 1) return nums;
        int len = nums.length - k + 1;
        int[] res = new int[len];
        Myque myque = new Myque();

        for(int i = 0 ; i < k; i++){
            // res[0] = Math.max(res[0], nums[i]);
            myque.add(nums[i]);           
        }
        int count = 0;
        res[count ++] = myque.peek();
        for(int i = k ; i < nums.length; i++){
            myque.add(nums[i]);
            myque.poll(nums[i - k]);
            res[count ++ ] = myque.peek();
        }
        return res;
    }
}

class Myque{
    Deque<Integer> deque = new LinkedList<>();
    void add (int add){
        while(!deque.isEmpty() && deque.peekLast() < add){
            deque.removeLast();
        }
        deque.addLast(add);
    }
    void poll(int rem){
        if(!deque.isEmpty() && deque.peekFirst() == rem) deque.removeFirst(); 
    }
    int peek(){
        return deque.peekFirst();
    }
}

  • max heap: 元素加进来，顺序会改变，所以不可以用

  • min heap: 元素加进来，顺序会改变，所以不可以用

  • monotonic queue (单调队列)

add: 如果要加的数比myque尾巴上的数大，那就把尾巴上比 要add的数 小的数全部移掉

poll: 如果要移除的数和myque最前面的数字一样，那就把myque最前面的数移除掉，否则就不管。

为什么这么做？因为我们想把不会出现在答案里的数趁早给remove掉。这样myque的最前面永远是最大的。

347. Top K Frequent Elements

😭Medium

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:

1
2
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/*Comparator接口说明:
 * 返回负数，形参中第一个参数排在前面；返回正数，形参中第二个参数排在前面
 * 对于队列：排在前面意味着往队头靠
 * 对于堆（使用PriorityQueue实现）：从队头到队尾按从小到大排就是最小堆（小顶堆），
 *                                从队头到队尾按从大到小排就是最大堆（大顶堆）--->队头元素相当于堆的根节点
 * */
class Solution {
    //解法1：基于大顶堆实现
    public int[] topKFrequent1(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>(); //key为数组元素值,val为对应出现次数
        for (int num : nums) {
            map.put(num, map.getOrDefault(num,0) + 1);
        }
        //在优先队列中存储二元组(num, cnt),cnt表示元素值num在数组中的出现次数
        //出现次数按从队头到队尾的顺序是从大到小排,出现次数最多的在队头(相当于大顶堆)
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair2[1] - pair1[1]);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {//大顶堆需要对所有元素进行排序
            pq.add(new int[]{entry.getKey(), entry.getValue()});
        }
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) { //依次从队头弹出k个,就是出现频率前k高的元素
            ans[i] = pq.poll()[0];
        }
        return ans;
    }

 
    
    
    
    
    
    
    
    
//解法2：基于小顶堆实现 less time complexity
    public int[] topKFrequent2(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>(); //key为数组元素值,val为对应出现次数
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        //在优先队列中存储二元组(num, cnt),cnt表示元素值num在数组中的出现次数
        //出现次数按从队头到队尾的顺序是从小到大排,出现次数最低的在队头(相当于小顶堆)
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1]);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) { //小顶堆只需要维持k个元素有序
            if (pq.size() < k) { //小顶堆元素个数小于k个时直接加
                pq.add(new int[]{entry.getKey(), entry.getValue()});
            } else {
                if (entry.getValue() > pq.peek()[1]) { //当前元素出现次数大于小顶堆的根结点(这k个元素中出现次数最少的那个)
                    pq.poll(); //弹出队头(小顶堆的根结点),即把堆里出现次数最少的那个删除,留下的就是出现次数多的了
                    pq.add(new int[]{entry.getKey(), entry.getValue()});
                }
            }
        }
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) { //依次弹出小顶堆,先弹出的是堆的根,出现次数少,后面弹出的出现次数多
            ans[i] = pq.poll()[0];
        }
        return ans;
    }

n log k

✨ how to loop a hashmap

1
2
3
4
5
6
7
8
Map<Integer, String> map = new HashMap<>();
// Add some key-value pairs to the map...

for (Integer key : map.keySet()) {
    String value = map.get(key);
    System.out.println("Key: " + key + ", Value: " + value);
}

✨ min heap and max heap

1
2
3
4
5
6
7
8
9


// Create a min heap
PriorityQueue<int[]> minHeap = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1]);

// Create a max heap
PriorityQueue<int[]> maxHeap = new PriorityQueue<>((pair1, pair2) -> pair2[1] - pair1[1]);


wrap up 6/5/2024

  1. 统计元素出现的频率，这一类的问题可以使用map来进行统计。

对频率进行排序，这里我们可以使用一种 容器适配器就是 PriorityQue。

  1. use max heap/ min heap to sort multi dimension array

PriorityQueue<int[]>

this data structure is good at get the most/least frequently occuring elements in the set.

3.

In Java, the Deque, PriorityQueue, Queue, and Stack classes and interfaces share several methods, ensuring a consistent and predictable interface for common operations like adding, removing, and examining elements. Here’s a summary of how these methods align across these different data structures:

Common Methods Across Deque, PriorityQueue, and Queue

  • add(E e): Inserts the specified element into the queue/deque.
  • offer(E e): Inserts the specified element into the queue/deque if possible.
  • remove(): Retrieves and removes the head of the queue/deque.
  • poll(): Retrieves and removes the head of the queue/deque, or returns null if empty.
  • element(): Retrieves, but does not remove, the head of the queue/deque.
  • peek(): Retrieves, but does not remove, the head of the queue/deque, or returns null if empty.

Methods Specific to Deque

  • addFirst(E e): Inserts the specified element at the front of the deque.
  • addLast(E e): Inserts the specified element at the end of the deque.
  • pollFirst(): Retrieves and removes the first element, or returns null if empty.
  • pollLast(): Retrieves and removes the last element, or returns null if empty.
  • removeFirst(): Retrieves and removes the first element, throws NoSuchElementException if empty.
  • removeLast(): Retrieves and removes the last element, throws NoSuchElementException if empty.
  • push(E e): Pushes an element onto the stack represented by the deque.
  • pop(): Pops an element from the stack represented by the deque.

Methods Specific to PriorityQueue

  • comparator(): Returns the comparator used to order the elements in this queue, or null if the queue uses the natural ordering of its elements.

Methods Specific to Stack

  • push(E e): Pushes an element onto the stack.
  • pop(): Removes and returns the element at the top of the stack.
  • peek(): Returns the element at the top of the stack without removing it.
  • empty(): Tests if the stack is empty.

Summary

Java’s Deque, PriorityQueue, Queue, and Stack share several common methods that facilitate standard queue and stack operations. The Deque interface extends Queue, adding methods for stack-like behavior (e.g., push(), pop(), addFirst(), addLast()), whereas PriorityQueue provides priority-based ordering. The Stack class has methods specifically tailored for stack operations. This uniformity in method names and functionality across these collections simplifies their usage and enhances code readability and maintainability.

4o