跳到主要内容

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]