[数据结构与算法] 【05-06】力扣每日一题

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【05-06】力扣每日一题 -> 正文阅读

[数据结构与算法]【05-06】力扣每日一题

我发现最近总有的题目不说人话，做个题目和做阅读理解一样，弄懂题目思路很简单。
本文首发于馆主君晓的博客，05-06

题目描述

??933. 最近的请求次数，题目截图如下：

题目分析

??这道题目弄懂了题目意思其实挺简单的，题目意思说人话就是，最开始你这里什么数都没有，然后我每次给你一个数 $t$ ，判断你所拥有的数，在范围 $[t ? 3000, t]$ 之内的个数。

??知道题目意思就很简单了，最暴力的方法就是每次给你一个数你存着，然后遍历你存着的数组，如果在范围 $[t ? 3000, t]$ 之内，那么计数器就加一，最后返回计数器的个数。这种肯定能做，但是不优雅。我们可以尝试下面两种思路：

思路一：使用队列进行模拟，我们知道队列是先进先出类型的，所以每次调用ping函数的时候，我们就将给的t入队列，然后从队头开始将小于t-3000的给拿出来，直到队头的值在[t-3000,t]之内。然后我们返回队列里元素的个数即可。
思路二：我们使用一个变量记录每次的左边界的下标，因为对ping函数调用，每次的t值都严格递增，那么下次t-3000肯定大于等于上次调用的边界。所以我们每次从上次的左边界开始找第一个满足[t-3000,t]范围的下标，之后返回数组大小减去该下标的值即可。

代码实现

??两种方式的c++代码实现：

class RecentCounter {
    queue<int> q;
public:
    RecentCounter() {}

    int ping(int t) {
        q.push(t);
        while (q.front() < t - 3000) {
            q.pop();
        }
        return q.size();
    }
};
/**
 * Your RecentCounter object will be instantiated and called as such:
 * RecentCounter* obj = new RecentCounter();
 * int param_1 = obj->ping(t);
 */

class RecentCounter {
private:
    vector<int> countList;
    int leftIndex = 0;
public:
    RecentCounter() {
    }
    
    int ping(int t) {
        countList.push_back(t);
        for(;countList[leftIndex]<t-3000;leftIndex++);
        return countList.size()-leftIndex;
    }
};

/**
 * Your RecentCounter object will be instantiated and called as such:
 * RecentCounter* obj = new RecentCounter();
 * int param_1 = obj->ping(t);
 */