用react和ant.d做的网站例子,做期货要关注哪些网站,wordpress播放网盘,商城网站前端更新商品天天做吗每日偷偷刷题933和队列有关
思路
每来一次ping就记录时间#xff0c;并返回3000s内ping的次数#xff0c;本题数据量很大#xff0c;正向暴力肯定是不行的。
初步思路#xff1a;反向暴力#xff0c;不删列表数据。从ping的下标往前推#xff0c;并统计3000s的数据。 …每日偷偷刷题933和队列有关
思路
每来一次ping就记录时间并返回3000s内ping的次数本题数据量很大正向暴力肯定是不行的。
初步思路反向暴力不删列表数据。从ping的下标往前推并统计3000s的数据。
反向暴力做出来耗时6000多秒
差点超时根本原因就是后面大数据量时每次都要统计3000次。
class RecentCounter(object):def __init__(self):self.ping_req list()def ping(self, t)::type t: int:rtype: intcount 0self.ping_req.append(t)ping_lens len(self.ping_req)for i in range(ping_lens - 1, -1, -1):if (t - self.ping_req[i] 3000):count 1else:breakreturn count队列入列出列形式
由于3000s前的数据无效我们可以直接将它删掉。那么每次队列里面所剩下的ping数就是3000s的ping数 用再用内部函数len()统计地址的特性快速完成长度统计。
class RecentCounter(object):def __init__(self):self.ping_req list()self.count 0def ping(self, t)::type t: int:rtype: intself.ping_req.append(t)while(t - self.ping_req[0] 3000):self.ping_req.pop(0)ping_lens len(self.ping_req)return ping_lens使用queue扩展包
class RecentCounter:def __init__(self):self.q deque()def ping(self, t: int) - int:self.q.append(t)while self.q[0] t - 3000:self.q.popleft()return len(self.q)c代码学习queue队列类的使用
class RecentCounter {queueint ping_req;
public:RecentCounter() {}int ping(int t) {ping_req.push(t);while(t - ping_req.front() 3000) {ping_req.pop();}return ping_req.size();}
};
C语言要自己实现队列类比较麻烦用链表来实现。
队列实现可以参考 https://gitee.com/RodneyLOVE/advanced_course/tree/master/C_block/day_07_queue 完整的样例 和 C/C队列原理 为了节约空间C语言应该采用循环队列较为合适。 暂时就不做了工作量太大。直接放上参考答案
typedef struct {int *queue;int capability;int head;int tail;
} RecentCounter;RecentCounter* recentCounterCreate() {RecentCounter *obj (RecentCounter *)malloc(sizeof(RecentCounter));obj-capability 10001;obj-queue (int *)malloc(sizeof(int) * obj-capability);obj-head 0;obj-tail 0;return obj;
}int recentCounterPing(RecentCounter* obj, int t) {obj-queue[obj-tail] t;while (obj-queue[obj-head] t - 3000) {obj-head;}return obj-tail - obj-head;
}void recentCounterFree(RecentCounter* obj) {free(obj-queue);free(obj);
}
