queue | 队列

最近的请求次数

LeetCode 933.最近请求次数

写一个 RecentCounter 类来计算特定时间范围内最近的请求。

请你实现 RecentCounter 类：

• RecentCounter() 初始化计数器，请求数为 0 。
• int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。

保证 每次对 ping 的调用都使用比之前更大的 t 值。

说人话

每次去掉当前队列中小于当前 t - 3000 的请求，队列是递增的

Q & A

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

RecentCounter.prototype.ping = function(t) {
  this.queue.push(t)
  var first = this.queue[0]
  var ignore = t - 3000
  while(first < ignore) {
    this.queue.shift()
    first = this.queue[0]
  }
  return this.queue.length
};

二叉树的层序遍历

LeetCode 102. 二叉树的层序遍历

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

使用队列遍历

其中 createTree 是层序生成树

var levelOrder = function(root) {
  const ret = []
  if (!root) return ret
  const queue = [root]

  while (queue.length) {
    let len = queue.length
    const child = []

    // 处理当前层
    while(len --) {
      const current = queue.shift()
      child.push(current.val) // 分层 push

      current.left && queue.push(current.left)
      current.right && queue.push(current.right)
    }
    ret.push(child)
  }
  return ret
};

var root = createTree([1,2,3,4,5,6,7])
levelOrder(root) // [[1],[2,3],[4,5,6,7]]
levelOrder(root).flat() // [1,2,3,4,5,6,7]