关于队列:算法队列

队列是一种罕用的数据结构，它最大的特点是 先入先出，即先进入队列中的元素最先进去。

41. 滑动窗口的平均值

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

/**
 * Initialize your data structure here.
 * @param {number} size
 */
var MovingAverage = function(size) {
    this.size = size;
    this.arr = []
    this.sum = 0
};

/** 
 * @param {number} val
 * @return {number}
 */
MovingAverage.prototype.next = function(val) {this.arr.push(val)
    this.sum += val
    if(this.arr.length>this.size) {this.sum -= this.arr.shift()
    }
    return this.sum / this.arr.length
};

42. 最近申请次数

请实现如下类型 RecentCounter，它是统计过来 3000ms 内的申请次数的计数器。该类型的构造函数 RecentCounter 初始化计数器，申请数初始化为 0；函数 ping（int t）在工夫 t 增加一个新申请（t 示意以毫秒为单位的工夫），并返回过来 3000ms 内（工夫范畴为[t-3000，t]）产生的所有申请数。假如每次调用函数 ping 的参数 t 都比之前调用的参数值大。

var RecentCounter = function() {this.arr = []
};

/** 
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function(t) {this.arr.push(t)
    while(this.arr.length > 1 && this.arr[0] + 3000 < t) {this.arr.shift()
    }
    return this.arr.length
};

二叉树的广度优先遍历

应聘者在面试时常常须要应用队列来解决与广度优先搜寻相干的问题。图的广度优先遍历请看图的章节。

二叉树的广度优先搜寻是从上到下按层遍历二叉树，从二叉树的根节点开始，先遍历二叉树的第 1 层，再遍历第 2 层，接着遍历第 3 层，并以此类推。

通常基于队列来实现二叉树的广度优先搜寻。从二叉树的根节点开始，先把根节点放入一个队列之中，而后每次从队列中取出一个节点遍历。如果该节点有左右子节点，则别离将它们增加到队列当中。反复这个过程，直到所有节点都遍历完为止，此时队列为空。实现二叉树广度优先搜寻的经典代码如下所示：

43. 在齐全二叉树中增加节点

在齐全二叉树中，除最初一层之外其余层的节点都是满的（第 n 层有 2n- 1 个节点）。最初一层的节点可能不满，该层所有的节点尽可能向右边聚拢

要了解齐全二叉树的定义：除了最初一层节点不满，其余层节点都是满的

/**
 * @param {TreeNode} root
 */
var CBTInserter = function(root) {if(root == null) return [];
    this.root = root;
    this.queue = [];
    this.queue.push(root)
    while(this.queue[0].left&&this.queue[0].right) {const node = this.queue.shift();
        this.queue.push(node.left)
        this.queue.push(node.right)
    }   
};

/** 
 * @param {number} v
 * @return {number}
 */
CBTInserter.prototype.insert = function(v) {const parent = this.queue[0]
    const child = new TreeNode(v)
    if(parent.left == null) {parent.left = child} else {
        parent.right = child;
        this.queue.shift()
        this.queue.push(parent.left)
        this.queue.push(parent.right)
    }
    return parent.val;
};

/**
 * @return {TreeNode}
 */
CBTInserter.prototype.get_root = function() {return this.root};

最初剖析上述代码的效率。类型 CBTInserter 的构造函数从实质上来说是依照广度优先搜寻的程序找出二叉树中所有既有左子节点又有右子节点的节点，因而工夫复杂度是 O（n）。调用函数 insert 在齐全二叉树中每增加一个节点最多只须要在队列中删除一个节点并增加两个节点。通常，队列的插入、删除操作的工夫复杂度都是 O（1），因而函数 insert 的工夫复杂度是 O（1）。显然，函数 get_root 的工夫复杂度是 O（1）。

44. 二叉树中每层的最大值

输出一棵二叉树，请找出二叉树中每层的最大值

要害就在于遍历层的时候，晓得什么时候层开始，什么时候层完结。1 个方法就是计数。另一个方法是利用 2 个队列实现广度优先遍历

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var largestValues = function(root) {
  let current = 0;
  let next = 0;
  const queue = [];
  if(root != null) {queue.push(root)
    current = 1
  }

  const result = [] // 后果
  let max = -Infinity;
  while(queue.length) {const node = queue.shift();
    current--
    max = Math.max(max, node.val)

    if(node.left != null) {queue.push(node.left)
      next++
    }

    if(node.right != null) {queue.push(node.right)
      next++
    }

    if(current === 0) {result.push(max)
      current = next
      max = -Infinity
      next = 0
    }
  }
  return result
};

之前的想太简单了，没必要 2 **n，

• 双队列实现广度优先搜寻

45. 二叉树最低层最右边的值

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最右边 节点的值。

/**
 * @param {TreeNode} root
 * @return {number}
 */
var findBottomLeftValue = function(root) {let queue = []
    let next_queue = []
    queue.push(root)
    let temp = []
    while(queue.length) {const node = queue.shift()
        temp.push(node)
        if(node.left) {next_queue.push(node.left)
        }
        if(node.right) {next_queue.push(node.right)
        }

        if(queue.length == 0 && next_queue.length) {
            queue = next_queue
            temp = []
            next_queue = []}
    }
    return temp[0].val
};

46. 二叉树的右侧视图

如何在一棵二叉树中找出它最低层最右边节点的值？假如二叉树中起码有一个节点。例如，在如图 7.5 所示的二叉树中最低层最右边一个节点的值是 5。

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var rightSideView = function(root) {if(root == null) return []
    let queue = []
    let next_queue = []
    queue.push(root)
    let temp = []
    const result = []
    while(queue.length) {const node = queue.shift()
        temp.push(node)
        if(node.left) {next_queue.push(node.left)
        }
        if(node.right) {next_queue.push(node.right)
        }

        if(queue.length == 0 && next_queue.length) {
            queue = next_queue
            result.push(temp.pop().val)
            temp = []
            next_queue = []}
    }
    if(temp.length) {result.push(temp.pop().val)
    } 
    return result;
};