双端队列,求解《933. 最近的请求次数》

Python 双端队列

Java 双端队列

例题

933. 最近的请求次数

写一个 RecentCounter 类来计算特定时间范围内最近的请求。
请你实现 RecentCounter 类:
RecentCounter() 初始化计数器,请求数为 0 。
int ping(int t) 在时间 t 添加一个新请求,其中 t 表示以毫秒为单位的某个时间,并返回过去 3000 毫秒内发生的所有请求数(包括新请求)。确切地说,返回在 [t-3000, t] 内发生的请求数。
保证 每次对 ping 的调用都使用比之前更大的 t 值。

答案

队列

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

RecentCounter.prototype.ping = function(t) {
  this.q.push(t)
  while (this.q[0] < t - 3000) this.q.shift()
  return this.q.length
};
class RecentCounter {
  q: number[] = []
  constructor() {
  }

  ping(t: number): number {
    this.q.push(t)
    while (this.q[0] < t - 3000) this.q.shift()
    return this.q.length
  }
}
type RecentCounter struct {
  q []int
}

func Constructor() RecentCounter {
  return RecentCounter{q: []int{}}
}

func (this *RecentCounter) Ping(t int) int {
  this.q = append(this.q, t)
  for this.q[0] < t - 3000 {
    this.q = this.q[1:]
  }
  return len(this.q)
}
class RecentCounter {
  private $q;
  function __construct() {
    $this->q = [];
  }
  function ping($t) {
    $this->q []= $t;
    while ($this->q[0] < $t - 3000) array_shift($this->q);
    return count($this->q);
  }
}
class RecentCounter(object):
    def __init__(self):
      self.q = deque()

    def ping(self, t):
      self.q.append(t)
      while self.q[0] < t - 3000: self.q.popleft()
      return len(self.q)
class RecentCounter {
  private Deque<Integer> q;
  public RecentCounter() {
    q = new ArrayDeque<>();
  }

  public int ping(int t) {
    q.offerLast(t);
    while (q.getFirst() < t - 3000) q.pollFirst();
    return q.size();
  }
}
class RecentCounter {
  private Deque<Integer> q;
  public RecentCounter() {
    q = new ArrayDeque<>();
  }

  public int ping(int t) {
    q.offer(t);
    while (q.peek() < t - 3000) q.poll();
    return q.size();
  }
}

代码
广度优先遍历+双端队列:求解《433. 最小基因变化》
广度优先遍历+双端队列,求解《433. 最小基因变化》
代码
哈希表、队列、约瑟夫环的迭代和递归,动态规划求解《1823. 找出游戏的获胜者》和《剑指 Offer 62. 圆圈中最后剩下的数字》
哈希表、队列、递归、迭代,用约瑟夫环的递推公式,求解《1823. 找出游戏的获胜者》和《剑指 Offer 62. 圆圈中最后剩下的数字》
代码
反向搜索:深度优先搜索和广度优先搜索,三状态标记法,求解《417. 太平洋大西洋水流问题》
有一种热爱是双向奔赴。反向搜索,深度优先搜索和广度优先搜索,三状态标记法,求解《417. 太平洋大西洋水流问题》