Leetcode 剑指 Offer II 042. 最近的请求次数

这篇具有很好参考价值的文章主要介绍了Leetcode 剑指 Offer II 042. 最近的请求次数。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目难度: 简单

原题链接

今天继续更新 Leetcode 的剑指 Offer(专项突击版)系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

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

请实现 RecentCounter 类:

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

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

示例:

  • 输入:
    • inputs = [“RecentCounter”, “ping”, “ping”, “ping”, “ping”]
    • inputs = [[], [1], [100], [3001], [3002]]
  • 输出:
    • [null, 1, 2, 3, 3]
  • 解释:
    • RecentCounter recentCounter = new RecentCounter();
    • recentCounter.ping(1); // requests = [1],范围是 [-2999,1],返回 1
    • recentCounter.ping(100); // requests = [1, 100],范围是 [-2900,100],返回 2
    • recentCounter.ping(3001); // requests = [1, 100, 3001],范围是 [1,3001],返回 3
    • recentCounter.ping(3002); // requests = [1, 100, 3001, 3002],范围是 [2,3002],返回 3

提示:

  • 1 <= t <= 10^9
  • 保证每次对 ping 调用所使用的 t 值都 严格递增
  • 至多调用 ping 方法 10^4 次

题目思考

  1. 可以使用什么数据结构模拟整个过程?

解决方案

思路
  • 分析题目, 要想动态维护过去 3000 毫秒内发生的所有请求数, 需要支持一端添加新元素, 另一端移除老元素, 显然可以使用双端队列来模拟这个过程
  • 每次调用 ping 函数时:
    • 先将新请求添加到队列末尾
    • 然后循环判断队列开头请求是否不在时间窗口内, 不在的话移除它并继续循环
    • 循环结束时, 队列里存储的就是时间窗口内的所有请求, 返回队列长度即可
  • 下面的代码就对应了上面的整个过程, 并且有详细的注释, 方便大家理解
复杂度
  • 时间复杂度 O(1): 每个请求最多入队和出队各一次, 所以每次操作的均摊时间复杂度为 O(1)
  • 空间复杂度 O(N): 双端队列最多存储全部 N 个元素
代码
class RecentCounter:
    def __init__(self):
        # 初始化一个双端队列
        self.q = collections.deque()

    def ping(self, t: int) -> int:
        # 将当前元素加入队尾
        self.q.append(t)
        # 这里由于刚入队一个元素, 且其一定不满足循环条件
        # 所以可以保证队列至少有一个元素(t), 无需判断q是否为空
        while self.q[0] < t - 3000:
            # 队头元素不在时间窗口[t-3000,t]内了, 将其出队
            self.q.popleft()
        # 最终队列剩余的元素个数即为时间窗口内的总请求数
        return len(self.q)

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊

Leetcode 剑指 Offer II 042. 最近的请求次数,Leetcode,leetcode,算法,职场和发展文章来源地址https://www.toymoban.com/news/detail-690466.html

到了这里,关于Leetcode 剑指 Offer II 042. 最近的请求次数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode:剑指 Offer 58 - II. 左旋转字符串

    🍎道阻且长,行则将至。🍓 🌻算法,不如说它是一种思考方式🍀 算法专栏: 👉🏻123 题目描述 :字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如,输入字符串\\\"abcdefg\\\"和数字2,该函数将返回左旋

    2024年02月02日
    浏览(49)
  • 【LeetCode75】第二十七题(933)最近的请求次数

    目录 题目: 示例: 分析: 代码+运行结果: 首先这是LeetCode75里第一道设计类的题目,这种类型的题目会比较新颖,就是按照题目要求来设计一个类。然后测试用例是模拟真实调用类的成员函数的。 这道题也算是简单题,整个类除了构造函数以外就一个成员函数,测试用例

    2024年02月13日
    浏览(44)
  • Leetcode-每日一题【剑指 Offer II 010. 和为 k 的子数组】

    给定一个整数数组和一个整数 k ,请找到该数组中和为 k 的连续子数组的个数。 示例 1: 输入: nums = [1,1,1], k = 2 输出: 2 解释: 此题 [1,1] 与 [1,1] 为两种不同的情况 示例 2: 输入: nums = [1,2,3], k = 3 输出: 2 提示: 1 = nums.length = 2 * 104 1000 = nums[i] = 1000 107 = k = 107 前置知识 前缀和

    2024年02月15日
    浏览(47)
  • Leetcode-每日一题【剑指 Offer 32 - II. 从上到下打印二叉树 II】

    从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行。 例如: 给定二叉树:  [3,9,20,null,null,15,7] ,     3    /   9  20     /     15   7 返回其层次遍历结果: [   [3],   [9,20],   [15,7] ] 提示: 节点总数 = 1000 1.题目要求我们从上到下按层打印二

    2024年02月12日
    浏览(45)
  • (字符串 ) 剑指 Offer 58 - II. 左旋转字符串 ——【Leetcode每日一题】

    难度:简单 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如,输入字符串\\\"abcdefg\\\"和数字2,该函数将返回左旋转两位得到的结果\\\"cdefgab\\\"。 示例 1: 输入: s = “abcdefg”, k = 2 输出: “cdefgab” 示例 2:

    2024年02月08日
    浏览(48)
  • 【LeetCode: 剑指 Offer II 089. 房屋偷盗(打家窃舍) | 暴力递归=>记忆化搜索=>动态规划】

    🍎作者简介:硕风和炜,CSDN-Java领域新星创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎 🍎座右铭:人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯🎯 剑指 Offer II 089. 房屋偷盗

    2024年02月02日
    浏览(46)
  • 【LeetCode: 剑指 Offer II 090. 环形房屋偷盗(打家窃舍) | 暴力递归=>记忆化搜索=>动态规划】

    🍎作者简介:硕风和炜,CSDN-Java领域新星创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎 🍎座右铭:人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯🎯 大家再看这道题目之前,

    2023年04月14日
    浏览(46)
  • 剑指 Offer 34. 二叉树中和为某一值的路径 / LeetCode 113. 路径总和 II(深度优先搜索)

    链接:剑指 Offer 34. 二叉树中和为某一值的路径;LeetCode 113. 路径总和 II 难度:中等 给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 示例 1: 输入:root = [5,4,8,11,null,1

    2024年02月03日
    浏览(41)
  • 剑指 Offer 56 - II. 数组中数字出现的次数 II(位运算 / 哈希表 / 排序)

    链接:剑指 Offer 56 - II. 数组中数字出现的次数 II 难度:中等 在一个数组 nums 中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。 示例 1: 输入:nums = [3,4,3,3] 输出:4 示例 2: 输入:nums = [9,1,7,9,7,9,7] 输出:1 限制: 1 = nums.length = 10000 1

    2024年02月13日
    浏览(41)
  • 【LeetCode】剑指 Offer(28)

    目录 题目:剑指 Offer 54. 二叉搜索树的第k大节点 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 题目:剑指 Offer 55 - I. 二叉树的深度 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 题目:剑指 Offer 55 - II. 平衡二叉树 - 力扣(Leetcode) 题目的接

    2023年04月24日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包