算法：（七）队列

7.1 队列的应用

面试题41：滑动窗口的平均值

题目：请实现如下类型MovingAverage，计算滑动窗口中所有数字的平均值，该类型构造函数的参数确定滑动窗口的大小，每次调用成员函数next时，会在滑动窗口中添加一个整数，并返回滑动窗口中所有数字的平均值。

class MovingAverage{

​ public MovingAverage(int size);

​ public double next(int val);

}

public class MovingAverage {
    private int size;
    private Queue<Integer> queue;
    public MovingAverage(int size){
        this.size = size;
        queue = new ArrayDeque<>(size);
    }
    public double next(int val){
        if(queue.size() == size){
            queue.poll();
        }
        queue.offer(val);
        int sum = 0;
        for (Integer integer : queue) {
            sum += integer;
        }
        return (double) sum / queue.size();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

面试题42：最近请求次数

题目：请实现如下类型：RecentCounter，它是统计过去3000ms以内请求次数的计数器。该类型的构造函数初始化计数器，请求数初始化为0；函数ping(int t)在时间t内添加一个新请求（t表示以毫秒为单位的时间），并返回过去3000ms内（时间范围[t-3000, t]）所发生的的所有请求的次数。假设每次条用函数ping的参数t都比之前调用的参数值大。

class RecentCounter{

​ public RecentCounter();

​ public int ping(int t);

}

public class RecentCounter {
    private int count;
    Queue<Integer> queue = new LinkedList<>();
    public RecentCounter(){
        this.count = 0;
    }
    public int ping(int t){
        queue.offer(t);
        while(queue.peek() < t - 3000){
            queue.poll();
        }
        return queue.size();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

7.2 二叉树的广度优先搜索

面试题43：在完全二叉树中添加节点

题目：在完全二叉树中，除最后一层之外的其它层的节点都是满的，最后一层的节点可能不满，该层所有的节点尽可能的向左边靠拢。实现数据结构CBTInserter，有如下三种方法。

• 构造函数CBTInserter(TreeNode root)：用一颗完全二叉树的根节点初始化该数据结构。
• 函数insert(int v)：在完全二叉树中添加一个值为v的节点，并返回被插入节点的父节点。
• 函数get_root()：返回完全二叉树的根节点。

public class CBTInserter {
    private TreeNode root;
    private Queue<TreeNode> queue;

    public CBTInserter(TreeNode root) {
        // 通过队列广度优先遍历
        // 在初始化的时候就将遍历完成，提高插入的性能
        this.root = root;
        this.queue = new LinkedList<>();
        queue.offer(root);
        // 找到一地个没有左孩子或者右孩子的节点，此节点就是带插入的节点，跳出循环后待插入的节点为队列的第一个元素
        while(queue.peek().leftChild != null && queue.peek().rightChild!= null){
            queue.offer(queue.peek().leftChild);
            queue.offer(queue.peek().rightChild);
            queue.poll();
        }
    }
    public int insert(int v){
        TreeNode parent = queue.peek();
        TreeNode newNode = new TreeNode(v);
        if(parent.leftChild == null){
            parent.leftChild = newNode;
        } else {
            parent.rightChild = newNode;
            // 维持队列的第一个元素是待插入的节点
            queue.poll();
            queue.offer(parent.leftChild);
            queue.offer(parent.rightChild);

        }
        return parent.value;

    }
    public TreeNode get_root(){
        return this.root;
    }

    private class TreeNode{
        private TreeNode leftChild;
        private TreeNode rightChild;
        private int value;

        public TreeNode(int value) {
            this.value = value;
        }
    }
}
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

面试题44：二叉树中每层的最大值

题目：输入一颗二叉树，请找出二叉树中每层的最大值。例如，下图中的二叉树，返回每层节点的最大值[3, 4, 9]。

public int[] findMaxInEveryLayer(TreeNode root){
    // 用广度优先搜索进行树的遍历
    // current和next表示当前层和下一层的元素个数，用于层级判断
    // 当current为0的时候，输出当前层最值，并将current设置成下一层的元素个数，next置为0
    int current = 1;
    int next = 0;
    ArrayList<Integer> result = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();
    if(root != null){
        queue.offer(root);
    }
    int maxEveryLayer = Integer.MIN_VALUE;
    while(!queue.isEmpty()){
        TreeNode node = queue.poll();
        current--;
        maxEveryLayer = Math.max(maxEveryLayer, node.value);
        if(node.rightChild != null){
            queue.offer(node.leftChild);
            queue.offer(node.rightChild);
            next +=2;
        } else if(node.leftChild != null){
            queue.offer(node.leftChild);
            next++;
        }
        if(current == 0){
            result.add(maxEveryLayer);
            maxEveryLayer = Integer.MIN_VALUE;
            current = next;
            next = 0;
        }
    }
    return result.stream().mapToInt(i -> i).toArray();
}
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

可以使用双队列来解决广度优先遍历二叉树需要分层的问题。本题恰好适用，代码如下：

public int[] findMaxInEveryLayer(TreeNode root){
    ArrayList<Integer> result = new ArrayList<>();
    Queue<TreeNode> queue1 = new LinkedList<>();
    Queue<TreeNode> queue2 = new LinkedList<>();
    if(root != null){
        queue1.offer(root);
    }
    int maxEveryLayer = Integer.MIN_VALUE;
    while(!queue1.isEmpty()){
        TreeNode node = queue.poll();
        maxEveryLayer = Math.max(maxEveryLayer, node.value);
        if(node.rightChild != null){
            queue2.offer(node.leftChild);
            queue2.offer(node.rightChild);
        } else if(node.leftChild != null){
            queue2.offer(node.leftChild);
        }
        if(queue1.isEmpty() == 0){
            result.add(maxEveryLayer);
            maxEveryLayer = Integer.MIN_VALUE;
            queue1 = queue2;
            queue2 = new LinkedList<>();
        }
    }
    return result.stream().mapToInt(i -> i).toArray();
}
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

面试题45: 二叉树最底层最左边的值

题目：如何在一颗二叉树中找到它最底层最左边的值？假设二叉树中最少有一个节点。

public int findBottomLeftValue(TreeNode root) {
    /**
     * 使用双队列currentLine和nextLine来进行求解
     * 在遍历currentLine之前都用targetNode记录其最左端的节点
     * 每遍历currentLine中一个节点，将其弹出，并将其左右孩子放入nextLine中
     * 若currentLine为空，即遍历结束，判断nextLine是否为空：
     *  	1. 不为空则将currentLine置为nextLine继续遍历下一行；
     *  	2. 为空则说明遍历结束，返回targetNode
     */
    Queue<TreeNode> currentLine = new LinkedList<>();
    Queue<TreeNode> nextLine = new LinkedList<>();
    TreeNode targetNode = null;
    if (root != null) {
        currentLine.offer(root);
        targetNode = root;
    }
    while (!currentLine.isEmpty()) {
        TreeNode temp = currentLine.poll();
        if (temp.leftChild != null) {
            nextLine.offer(temp.leftChild);
        }
        if (temp.rightChild != null) {
            nextLine.offer(temp.rightChild);
        }
        if (currentLine.isEmpty() && !nextLine.isEmpty()) {
            currentLine = nextLine;
            nextLine = new LinkedList<>();
            targetNode = currentLine.peek();
        }
    }
    return targetNode.value;
}
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

面试题46：二叉树的右侧视图

题目：给定一颗二叉树，如果站在该二叉树的右侧，那么从上到下看到的节点构成二叉树的右侧视图，例如下图的二叉树的右侧视图包含节点8、节点10和节点7。请写出一个函数返回二叉树的右侧视图节点的值。

public int[] rightSideView(TreeNode root){
    // 广度优先遍历二叉树 ——> 用队列
    // 分层 ——> 双队列
    // 在当前层遍历结束的时候记录一下最右端的节点即可
    Queue<TreeNode> currentLine = new LinkedList<>();
    Queue<TreeNode> nextLine = new LinkedList<>();
    ArrayList<Integer> result = new ArrayList<>();
    if(root != null){
        currentLine.offer(root);
    }
    while(!currentLine.isEmpty()){
        TreeNode node = currentLine.poll();
        if(node.leftChild != null){
            nextLine.offer(node.leftChild);
        }
        if(node.rightChild != null){
            nextLine.offer(node.rightChild);
        }
        if(currentLine.isEmpty()){
            result.add(node.value);
            currentLine = nextLine;
            nextLine = new LinkedList<>();
        }
    }
    return result.stream().mapToInt(i -> i).toArray();
}
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