Sword finger offer2: queue summary

The basics of queues ： fifo

queue Queue Is an internal element characteristic that conforms to ” fifo “ Data set for . If data deletion and insertion operations are met when solving the problem " fifo " Characteristics , Then consider using queues to store this data .

• frequently-used API

operation	No abnormal protection	With abnormal protection
Add an element to the end of the team	add(node)	offer(node )
Remove an element from the team leader	remove(node)	poll(node)
Returns the first element	element()	peek()

Java The commonly used queue implementation classes in LinkedList, ArrayDeque, PriorityQueue. however PriorityQueue Not a queue data structure , It's a pile .

application

The sliding window

The finger of the sword Offer II 041. Average value of sliding window

Please implement the following types MovingAverage, Calculate the average of all numbers in the sliding window , The parameters of this type constructor determine the size of the sliding window , Every time a member function is called next An integer will be added to the sliding window , And returns the average of all the numbers in the sliding window .

Their thinking

This topic is mainly divided into two parts ：

1. Maintain sliding windows ：
   After adding the elements of the window , If the number of window elements is greater than the limit , You need to delete the element you first added .
   This is consistent with the first in, first out feature . So we can think about it queue To maintain the sliding window as a data set .
2. Calculate average ：
   Calculate the sum of window elements , Just add the value of one element at a time , Then subtract the value of the deleted element , The time complexity is O(1）.

The specific code is as follows ：

Code

class MovingAverage {
    
    private Queue<Integer> queue;
    private int capacity = 0;
    private int sum = 0;
    /** Initialize your data structure here. */
    public MovingAverage(int size) {
    
        this.capacity = size;
        queue = new LinkedList<>();
    }
    
    public double next(int val) {
    
        queue.offer(val);
        sum += val;
        if(queue.size() > this.capacity) {
    
            sum -= queue.poll();
        } 
       return (double)sum / queue.size();
    }
}

The finger of the sword Offer II 042. Number of recent requests

subject ： Please implement the following types RecentCounter, It counts the past 3000ms A counter for the number of requests within . Constructor of this type RecentCounter Initialize counter , The number of requests is initialized to 0; function ping（int t） In time t Add a new request （t Represents the time in milliseconds ）, And go back to the past 3000ms Inside （ The time frame is [t-3000,t]） Number of all requests that occurred . Suppose every time you call a function ping Parameters of t Is larger than the parameter value of the previous call .

Their thinking

1. Select the data structure ： Subject requirements 3000 Milliseconds to the current time t Number of requests in , Then we need to use a data container to store the time points of historical requests , At the same time, delete the interval 【3000-t,t] Time point outside .

2. The sliding window ： Because of the logic of Statistics , In line with the characteristics of first in first out , So queues can be used as data sets , Maintain a sliding window , Every time ping New requests , Move the window forward .

The specific code is as follows ：

Code

class RecentCounter {
    private Queue<Integer> times;
    private int windowSize;
    public RecentCounter() {
        windowSize = 3000;
        times = new LinkedList<>();
    }
    
    public int ping(int t) {
        times.offer(t);
        while((times.peek() + windowSize) < t) {
            times.poll();
        }
        return times.size();
    }
}

/**
 * Your RecentCounter object will be instantiated and called as such:
 * RecentCounter obj = new RecentCounter();
 * int param_1 = obj.ping(t);
 */

Breadth first search

Problem solving skills ： If the interview question of binary tree , Encounter the concept of layer , You can try to use breadth first search to solve such problems .
Breadth first search traversal steps ：

1. Define the queue , hold root Queue .
2. Traverse the current layer . According to the current queue length , Get the number of nodes in the current layer , Start traversing the nodes of the current layer .
3. Record the nodes of the next layer , When traversing the current layer node , We can save the left and right nodes at the next level of the node to the queue .

The finger of the sword Offer II 043. Add nodes to a complete binary tree

subject ： A complete binary tree is every layer （ Except for the last floor ） All completely filled （ namely , The number of nodes reaches the maximum , The first n Layer has a 2n-1 Nodes ） Of , And all nodes are concentrated on the left as much as possible .

Design a data structure initialized with a complete binary tree CBTInserter, It supports the following operations ：

CBTInserter(TreeNode root) Use root node as root Initialize the data structure for the given tree ;
CBTInserter.insert(int v) Insert a new node into the tree , The node type is TreeNode, The value is v . Keep the tree in the state of a complete binary tree , And return the value of the parent node of the inserted new node ;
CBTInserter.get_root() Will return the root node of the tree .

Their thinking

To solve this problem, we should master two knowledge points

1. The characteristics of complete binary tree
   A binary tree , From top to bottom , Add nodes from left to right .
2. Breadth first search , Find the parent node where you can add nodes .
   Use the queue to traverse the binary tree by layer , When the left or right child nodes of the traversal node are empty , Then the pointer to the node that can be added is found .

The specific implementation is as follows ：

Code

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class CBTInserter {
    
    private Queue<TreeNode> queue;
    private boolean isLeft;
    private TreeNode root;


    public CBTInserter(TreeNode root) {
    
        queue = new ArrayDeque<>();
        this.root = root;
        queue.offer(root);
        //1.  Initialize queue , Find the parent node where the child node can be inserted .
        while(!queue.isEmpty()) {
    
           TreeNode node = queue.peek();
            if(node.left == null) {
    
                isLeft = true;
                break;
            } else {
    
                queue.offer(node.left);
            }

            if(node.right == null) {
    
                isLeft = false;
                break;
            } else {
    
                queue.offer(node.right);
                queue.poll();// It's full on both sides , Then this node cannot insert child nodes , So remove it from the queue .
            }
        }
    }
    
    public int insert(int v) {
    
        //queue The queue head node of is the parent node to be inserted 
        TreeNode parent = queue.peek();
        TreeNode newNode = new TreeNode(v);
        if(isLeft) {
    
            parent.left  = newNode;
        } else {
    
            parent.right = newNode;
            queue.poll();
            isLeft = false;
        }
        isLeft = !isLeft;
        queue.offer(newNode);
        return parent.val;
    }
    
    public TreeNode get_root() {
    
        return root;
    }
}

/** * Your CBTInserter object will be instantiated and called as such: * CBTInserter obj = new CBTInserter(root); * int param_1 = obj.insert(v); * TreeNode param_2 = obj.get_root(); */

The finger of the sword Offer II 044. Maximum value of each layer of binary tree

Given the root node of a binary tree root , Please find the maximum value of each layer in the binary tree .

Their thinking

If there are layers in the binary tree , You can try to use breadth first search to traverse a binary tree , Calculate the maximum value of each layer .
In two steps ：

1. Define data container queues , Traversing the binary tree .
2. Count the maximum value of each layer .

Use for Loop through each layer , At the same time, you can join the next layer of nodes .

The specific code is as follows ：

Code

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
    
    public List<Integer> largestValues(TreeNode root) {
    
        if(root == null) {
    
            return new ArrayList<Integer>();
        }
        // To a binary tree , Sequence traversal 
        // Find out the maximum value of each layer 
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> result = new ArrayList();
        queue.offer(root);
        while(!queue.isEmpty()) {
    
          int max = Integer.MIN_VALUE;
          int size = queue.size();// The number of nodes in each layer 
          for(int i = 0; i < size; i++) {
    
           TreeNode node = queue.poll(); 
            max = node.val > max ? node.val : max;// Count the maximum value of each layer 
            if(node.left !=null ) queue.offer(node.left);// Record the nodes of the next layer 
            if(node.right !=null ) queue.offer(node.right);// Record the nodes of the next layer 
          }
          result.add(max);
        }
        return result;
    }
}

summary

A queue is a first in, first out data structure , It is generally used to deal with sliding window problems and breadth first search problems . When encountering the problem of binary tree layer , Try using breadth first search to traverse .