leetCode notes - Exploring queues & stacks

Explore queue & Stack

Queue: first in first out data structure

  • Queue implementation
    Do what you want
#include <iostream>

class MyQueue {
    private:
        // store elements
        vector<int> data;       
        // a pointer to indicate the start position
        int p_start;            
    public:
        MyQueue() {p_start = 0;}
        /** Insert an element into the queue. Return true if the operation is successful. */
        bool enQueue(int x) {
            data.push_back(x);
            return true;
        }
        /** Delete an element from the queue. Return true if the operation is successful. */
        bool deQueue() {
            if (isEmpty()) {
                return false;
            }
            p_start++;
            return true;
        };
        /** Get the front item from the queue. */
        int Front() {
            return data[p_start];
        };
        /** Checks whether the queue is empty or not. */
        bool isEmpty()  {
            return p_start >= data.size();
        }
};

int main() {
    MyQueue q;
    q.enQueue(5);
    q.enQueue(3);
    if (!q.isEmpty()) {
        cout << q.Front() << endl;
    }
    q.deQueue();
    if (!q.isEmpty()) {
        cout << q.Front() << endl;
    }
    q.deQueue();
    if (!q.isEmpty()) {
        cout << q.Front() << endl;
    }
}

Similar to the above, several basic operations are implemented with vector

  • Circular queue
    If you know what's wrong with the above one, then the following code is optimization
    If the tail pointer and the head pointer coincide, the queue is empty
    If there is a gap between the head pointer and the tail pointer, the queue is full
  • Design cycle queue
class MyCircularQueue {
private:
    vector<int> arr;
    int front;  //Point to the location of the first valid data in the queue header
    int rear;   //Points to the next position at the end of the queue (that is, the last valid data).
    int capacity;//queue length 
public:
    /** Initialize your data structure here. Set the size of the queue to be k. */
    MyCircularQueue(int k) {
        capacity = k + 1;
        arr.assign(capacity,0); //Assign initial value to 0
        front = 0;
        rear = 0;
    }
    
    /** Insert an element into the circular queue. Return true if the operation is successful. */
    bool enQueue(int value) {
        if(isFull()){
            return false;
        }
        arr[rear] = value;
        rear = (rear + 1) % capacity;
        return true;
    }
    
    /** Delete an element from the circular queue. Return true if the operation is successful. */
    bool deQueue() {
        if(isEmpty()){
            return false;
        }
        front = (front + 1) % capacity;
        return true;
    }
    
    /** Get the front item from the queue. */
    int Front() {
        if(isEmpty()){
            return -1;
        }
        return arr[front];
    }
    
    /** Get the last item from the queue. */
    int Rear() {
        if(isEmpty()){
            return -1;
        }
        return arr[(rear - 1 + capacity) % capacity];
    }
    
    /** Checks whether the circular queue is empty or not. */
    bool isEmpty() {
        return front == rear;
    }
    
    /** Checks whether the circular queue is full or not. */
    bool isFull() {
        return (rear + 1) % capacity == front;
    }
};

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue* obj = new MyCircularQueue(k);
 * bool param_1 = obj->enQueue(value);
 * bool param_2 = obj->deQueue();
 * int param_3 = obj->Front();
 * int param_4 = obj->Rear();
 * bool param_5 = obj->isEmpty();
 * bool param_6 = obj->isFull();
 */

If you really don't understand, you can refer to:
Original title

  • Circular queue implementation
    Template
class MyCircularQueue {
private:
    vector<int> data;
    int head;
    int tail;
    int size;
public:
    /** Initialize your data structure here. Set the size of the queue to be k. */
    MyCircularQueue(int k) {
        data.resize(k);
        head = -1;
        tail = -1;
        size = k;
    }
    
    /** Insert an element into the circular queue. Return true if the operation is successful. */
    bool enQueue(int value) {
        if (isFull()) {
            return false;
        }
        if (isEmpty()) {
            head = 0;
        }
        tail = (tail + 1) % size;
        data[tail] = value;
        return true;
    }
    
    /** Delete an element from the circular queue. Return true if the operation is successful. */
    bool deQueue() {
        if (isEmpty()) {
            return false;
        }
        if (head == tail) {
            head = -1;
            tail = -1;
            return true;
        }
        head = (head + 1) % size;
        return true;
    }
    
    /** Get the front item from the queue. */
    int Front() {
        if (isEmpty()) {
            return -1;
        }
        return data[head];
    }
    
    /** Get the last item from the queue. */
    int Rear() {
        if (isEmpty()) {
            return -1;
        }
        return data[tail];
    }
    
    /** Checks whether the circular queue is empty or not. */
    bool isEmpty() {
        return head == -1;
    }
    
    /** Checks whether the circular queue is full or not. */
    bool isFull() {
        return ((tail + 1) % size) == head;
    }
};

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue obj = new MyCircularQueue(k);
 * bool param_1 = obj.enQueue(value);
 * bool param_2 = obj.deQueue();
 * int param_3 = obj.Front();
 * int param_4 = obj.Rear();
 * bool param_5 = obj.isEmpty();
 * bool param_6 = obj.isFull();
 */
  • Queue usage
    emmmmmmm. . . .

Queue and breadth first search

  • Breadth first search template
    Template omitted
  • Number of islands
    Traverse every point. If this point is an island, search widely from this point. Record the number of islands at the same time.
    When all the points are traversed, the result is returned.
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int nr = grid.size();
        if (!nr) return 0;
        int nc = grid[0].size();

        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    grid[r][c] = '0';
                    queue<pair<int, int>> neighbors;
                    neighbors.push({r, c});
                    while (!neighbors.empty()) {
                        auto rc = neighbors.front();
                        neighbors.pop();
                        int row = rc.first, col = rc.second;
                        if (row - 1 >= 0 && grid[row-1][col] == '1') {
                            neighbors.push({row-1, col});
                            grid[row-1][col] = '0';
                        }
                        if (row + 1 < nr && grid[row+1][col] == '1') {
                            neighbors.push({row+1, col});
                            grid[row+1][col] = '0';
                        }
                        if (col - 1 >= 0 && grid[row][col-1] == '1') {
                            neighbors.push({row, col-1});
                            grid[row][col-1] = '0';
                        }
                        if (col + 1 < nc && grid[row][col+1] == '1') {
                            neighbors.push({row, col+1});
                            grid[row][col+1] = '0';
                        }
                    }
                }
            }
        }

        return num_islands;
    }
};
  • Open the turntable lock
    The most annoying part of this topic is character and number conversion, so I decided to do it in java. If each digit of a number can be added or subtracted, there are eight ways. But there are death numbers, so save the numbers in the death numbers with set. If you can't walk to all positions, it returns -1. Otherwise, it returns the minimum number of times.
class Solution {
    public int openLock(String[] deadends, String target) {
        Set<String> dead = new HashSet();
        for (String d: deadends) dead.add(d);

        Queue<String> queue = new LinkedList();
        queue.offer("0000");
        queue.offer(null);

        Set<String> seen = new HashSet();
        seen.add("0000");

        int depth = 0;
        while (!queue.isEmpty()) {
            String node = queue.poll();
            if (node == null) {
                depth++;
                if (queue.peek() != null)
                    queue.offer(null);
            } else if (node.equals(target)) {
                return depth;
            } else if (!dead.contains(node)) {
                for (int i = 0; i < 4; ++i) {
                    for (int d = -1; d <= 1; d += 2) {
                        int y = ((node.charAt(i) - '0') + d + 10) % 10;
                        String nei = node.substring(0, i) + ("" + y) + node.substring(i+1);
                        if (!seen.contains(nei)) {
                            seen.add(nei);
                            queue.offer(nei);
                        }
                    }
                }
            }
        }
        return -1;
    }
}


  • Perfect square
    I have no idea about this topic. So I used others' ideas and diagrams for reference.
    Author answers
    Imagine the search process as a search tree, and you can find the shortest path from the tree. We find it layer by layer, and put the repeated ones into the set, and then until we find 0, the final result is.
class Solution {
    public int numSquares(int n) {
        Queue<Integer> queue = new LinkedList<>();
        HashSet<Integer> visited = new HashSet<>();
        int level = 0;
        queue.add(n);
        while(!queue.isEmpty()){
            int size = queue.size();
            level++;
            for(int i = 0; i < size; ++i){
                int cur = queue.poll();
                for(int j = 1; j * j <= cur; j++){
                    int next = cur - j*j;
                    if(next == 0){
                        return level;
                    }
                    if(!visited.contains(next)){
                        queue.offer(next);
                        visited.add(next);
                    }
            }
        }
    }
    return -1;
}
}

Stack: last in first out data structure

  • Stack - Usage
    emmmmmmm. . . .
  • Minimum stack

Throw out the big ones and keep the small ones

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        
    }
    stack<int> s;
    stack<int> Min;

    void push(int x) {
        s.push(x);
        if(Min.empty() || x <= Min.top())
        Min.push(x);    
    }
    
    void pop() {
        if(!s.empty()){
            if(s.top() == Min.top()) Min.pop();
            s.pop();
        }
    }
    
    int top() {
        return s.top();
    }
    
    int getMin() {
        return Min.top();
    }
};
  • Valid parentheses
    There are many solutions to this problem. My solution is: if it is a valid sequence of parentheses, put all the left parentheses on the stack. As long as you encounter the right parentheses, you can match them. If they do not match, you will return false. Until all parentheses are matched, if the stack is empty, return true; otherwise, return false.
class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for(int i = 0; i < s.size(); i++)
        {
            if(s[i] == '(' || s[i] == '[' || s[i] == '{')
                st.push(s[i]);
            else if(s[i] == ')')
            {
                if(!st.empty() && st.top() == '(')
                    st.pop();
                else
                    return false;
            }
            else if(s[i] == ']')
            {
                if(!st.empty() &&st.top() == '[')
                    st.pop();
                else
                    return false;
            }
            else if(s[i] == '}')
            {
                if(!st.empty() &&st.top() == '{')
                    st.pop();
                else 
                    return false;
            }
        }
        if(st.empty())
            return true;
        else
            return false;
    }
};

  • Daily temperature
    This problem has touched my knowledge blind spot again - a thing called diminishing occupation, which is also called monotone stack. I can only use it, but I can't explain it.
    You can look it up on the Internet by yourself.
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        int n = T.size();
        vector<int> res(n,0);
        stack<int> st;
        for(int i = 0; i < T.size(); ++i){
            while(!st.empty() && T[i] > T[st.top()]){
                auto t = st.top();
                st.pop();
                res[t] = i - t;
            }
            st.push(i);
        }
        return res;
    }
};
  • Reverse Polish notation
    The data structure is a classic topic, needless to say
class Solution {
    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();
    }
}

Stack and DFS

In my opinion, the essence of recursion is stack. In fact, DFS is to search recursively, so DFS uses stack to search. You can use built-in stack, but there is a big disadvantage: if the recursion depth is too high, you will suffer stack overflow. In this case, you might want to implement DFS using BFS or using an explicit stack.

  • DFS template I
    -Omitted
  • Number of islands
    Omitted (same as bfs)
  • Clone graph
    (the figure has not been reviewed, so it is omitted first)
  • Objectives and
    The difficulty of this topic lies in how to write the function parameters of search. If you can think of a search method, you should be able to think of a dynamic planning method. Here we only introduce the solution of search.
class Solution {
public:
    int count = 0;
    int findTargetSumWays(vector<int>& nums, int S) {
        calculate(nums, 0, 0, S);
        return count;
    }
    void calculate(vector<int>& nums, int i , int num, int S){
        if(i == nums.size()){
            if(S == num){
                count++;
            }
        } else{
            calculate(nums, i + 1, num + nums[i], S);
            calculate(nums, i + 1, num - nums[i], S);
        }
    }
};
  • DFS template II
    slightly
  • Middle order traversal of binary tree
    The essence of recursion is stack, and the binary tree is recursively searched, so the traversal of the binary tree can be regarded as search. Therefore, the pre order, the middle order, and the post order are nothing more than the order of entering and leaving the stack. If you write this question well, then the pre order and post order just change the access order.
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;    //Save results
        stack<TreeNode*> call;  //Call stack
        if(root == nullptr)
        return res;
        call.push(root);
        while(!call.empty()){
            TreeNode* t = call.top();
            call.pop();
            if(t != nullptr){
                if(t->right) call.push(t->right);   //Right node stack
                call.push(t);   //Current node stack
                call.push(nullptr); //Pressing an empty node indicates that it has been accessed
                
                if(t->left) call.push(t->left); //Left node stack
                
            }else{
                res.push_back(call.top()->val);
                call.pop();
            }
        }
        return res;
    }
};

subject

  • Implementing queues with stacks
    slightly
  • Implementing stack with queue
    slightly
  • String decoding
    The difficulty of this problem lies in the nested parentheses in the parentheses. It is necessary to generate and splice strings from the inside out, which corresponds to the first in first out feature of the stack. It is a bit like the problem of bracket matching, and it is necessary to convert the numbers encountered into multiples, and then multiply the string to be doubled. It's brain burning.
    Can't write, please see Boss's thinking

You can learn that from the inside out, it corresponds to the first in then out, which corresponds to the stack.

class Solution {
    public String decodeString(String s) {
        StringBuilder res = new StringBuilder();
        int multi = 0;
        LinkedList<Integer> stack_multi = new LinkedList<>();
        LinkedList<String> stack_res = new LinkedList<>();
        for(Character c : s.toCharArray()) {
            if(c == '[') {
                stack_multi.addLast(multi);
                stack_res.addLast(res.toString());
                multi = 0;
                res = new StringBuilder();
            }
            else if(c == ']') {
                StringBuilder tmp = new StringBuilder();
                int cur_multi = stack_multi.removeLast();
                for(int i = 0; i < cur_multi; i++) tmp.append(res);
                res = new StringBuilder(stack_res.removeLast() + tmp);
            }
            else if(c >= '0' && c <= '9') multi = multi * 10 + Integer.parseInt(c + "");
            else res.append(c);
        }
        return res.toString();
    }
}


  • Image rendering

It's very simple. You can write when you understand it.

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        int color = image[sr][sc];
        if (color == newColor) {
            return image;
        }
        dfs(image, sr, sc, newColor, color);
        return image;
    }

    void dfs(vector<vector<int>>& image, int r, int c, int newColor, int color) {
        if (r >= image.size() || c >= image[0].size()) {
            return;
        }
        if (image[r][c] != color) {
            return;
        }
        image[r][c] = newColor;
        int vx[] = {0, 0, 1, -1};
        int vy[] = {1, -1, 0, 0};
        for (int i = 0; i < 4; i++) {
            int newr = r + vy[i];
            int newc = c + vx[i];
            dfs(image, newr, newc, newColor, color);
        }
    }

};

  • 01 matrix
    At first glance, I know that dynamic programming can be used, but I can't, so let's introduce bfs.
    The nearest distance from a number to zero and the nearest distance from zero to this number actually mean the same thing. You might as well start from zero.
    So put zero in the queue. Then perform bfs, and finally return the result.
class Solution {
 private:
     int dirs[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> dist(m,vector<int>(n)); //A few steps
        vector<vector<int>> seen(m,vector<int>(n));  //Judge whether to walk
        queue<pair<int,int>> q;
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(matrix[i][j] == 0){
                    q.emplace(i,j);
                    seen[i][j] = 1;
                }
            }
        }
        //Breadth first search
        while(!q.empty()){
            auto[i,j] = q.front();
            q.pop();
            for(int d = 0; d < 4; ++d){
                int ni = i + dirs[d][0];
                int nj = j + dirs[d][1];
                if(ni >= 0 && ni < m && nj >= 0 && nj < n && !seen[ni][nj]){
                    dist[ni][nj] = dist[i][j] + 1;
                    q.emplace(ni, nj);
                    seen[ni][nj] = 1;
                }
            }
        }
        return dist;
    }
};
  • Keys and rooms

Access all the rooms. If you have accessed them, you will be thrown into the collection until all the accessible rooms have been accessed. Then you can determine whether there are rooms that have not been accessed. If there are rooms that have not been accessed, you will return false. Otherwise, you will return true.

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        if(rooms[0].empty()){
            if(rooms.size() == 1)
                return true;
            return false;
        } 
        queue<int> keys;
        vector<int> entered(rooms.size(), 0);
        unordered_set<int> visited;
        
        keys.push(0);
        
        while(!keys.empty()) {
            int index = keys.front();
            keys.pop();
            visited.insert(index);
            entered[index]++;
            
            for(int i = 0; i < rooms[index].size(); i++) {
                int next = rooms[index][i];
                if(visited.find(next) == visited.end()){
                    keys.push(next);
                }
            }
        }
        
        for(int i = 0; i < entered.size(); i++) {
            if(entered[i] == 0)
                return false;
        }
        return true;
    }
};

Posted by phenley on Tue, 31 May 2022 15:26:43 +0530