专栏首页机器学习入门LWC 109: 933.Number of Recent Calls

LWC 109: 933.Number of Recent Calls

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/83786026

LWC 109: 933.Number of Recent Calls

传送门:933.Number of Recent Calls

Problem:

Write a class RecentCounter to count recent requests. It has only one method: ping(int t), where t represents some time in milliseconds. Return the number of pings that have been made from 3000 milliseconds ago until now. Any ping with time in [t - 3000, t] will count, including the current ping. It is guaranteed that every call to ping uses a strictly larger value of t than before.

Example 1:

Input: K = 0 Output: 5 Explanation: 0!, 1!, 2!, 3!, and 4! end with K = 0 zeroes.

Example 2:

Input: inputs = [“RecentCounter”,“ping”,“ping”,“ping”,“ping”], inputs = [[],1,[100],[3001],[3002]] Output: [null,1,2,3,3]

Note:

  • Each test case will have at most 10000 calls to ping.
  • Each test case will call ping with strictly increasing values of t.
  • Each call to ping will have 1 <= t <= 10^9.

思路: 暴力解法,先把一个个时间戳记录下来,每当新来一个时间戳时统计[t - 3000, t]范围内的个数。

Version 1:

public class RecentCounter {
	
	List<Integer> ans;
	public RecentCounter() {
        ans = new ArrayList<>();
    }
    
    public int ping(int t) {
    	ans.add(t);
    	int cnt = 0;
    	int s = t - 3000;
    	int e = t;
    	for (int v : ans) {
    		if (v >= s && v <= e) cnt ++;
    	}
    	return cnt;
    }
}

优化一下,传入新的时间戳后可以保持记录数组的有序性,采用二分快速查找find the last value x in array where x + 3000 < t

Version2:

public class RecentCounter {
	
	int[] mem;
	int n;
	public RecentCounter() {
		mem = new int[10000 + 12];
		n = 0;
	}
    
    public int ping(int t) {
    	mem[n++] = t;
    	int c = n - bs(mem, t, 0, n) - 1;
    	return c;
    }
    
    public int bs(int[] mem, int t, int s, int e) {
    	int lf = s;
    	int rt = e - 1;
    	// x + 3000 < t
    	while (lf < rt) {
    		int mid = lf + (rt - lf + 1) / 2;
    		int val = mem[mid] + 3000;
    		if (val < t) {
    			lf = mid;
    		}
    		else { // >= t
    			rt = mid - 1;
    		}
    	}
    	if (mem[lf] + 3000 >= t) return -1;
    	return lf;
    }
}

当然我们还可以维护一个单调递增的队列,并实时过滤头部元素~

Version3:

import java.util.ArrayDeque;
import java.util.Deque;

public class RecentCounter {
	
	Deque<Integer> pq;
	public RecentCounter() {
		pq = new ArrayDeque<>();
	}
    
    public int ping(int t) {
    	while (!pq.isEmpty() && pq.peekFirst() + 3000 < t) {
    		pq.pollFirst();
    	}
    	pq.addLast(t);
    	return pq.size();
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 1062. 昂贵的聘礼

    思路: 实际上是一个图模型,采用递归,物品之间的交换有一条关系边,比如国王需要物品2,那么可以用8000来交换,此时子问题就变成了从物品2出发,所需要的最少...

    用户1147447
  • 4.7后缀数组

    第一次接触后缀数组,采用《挑战》P378的后缀算法,时间复杂度为O(nlog2n)O(n\log^2n),基本思想如下:

    用户1147447
  • 挑战程序竞赛系列(30):3.4矩阵的幂

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • LeetCode 137 Single Number II

    ShenduCC
  • Leetcode Golang 1. Two Sum.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/88866806

    anakinsun
  • 一篇文章搞懂面试中leetcode位操作算法题Single Number落单的数落单的数 IISingle Number IISingle Number III落单的数 IIINumber of 1

    本文将根据题目总结常用的位操作常用的解决算法问题的技巧 如读者对基本的位操作概念还不熟悉,可以先参考笔者的文章浅谈程序设计中的位操作http://www.ji...

    desperate633
  • Dimple在左耳听风ARTS打卡(第一期)

    参加了左耳听风的ARTS打卡,坚持一个月,对自己会有什么情况呢,我不知道,但我会照着这个目标坚持下去,坚持100天。一个习惯养成是21天,那如果坚持100天,效...

    程序员小跃
  • 玩具谜题 未完成

    #include<iostream> #include<cstdio> using namespace std; struct node { int zt;/...

    attack
  • gradeview可拖动效果实现

    下面先上这次实现功能的效果图:(注:这个效果图没有拖拽的时候移动动画,DEMO里面有,可以下载看看) ? 一、开发心里历程 刚开始接触这个的时候,不知道要如何实...

    xiangzhihong
  • 1265. [NOIP2012] 同余方程

    1265. [NOIP2012] 同余方程 ★☆   输入文件:mod.in   输出文件:mod.out 简单对比 时间限制:1 s   内存限制:128 M...

    attack

扫码关注云+社区

领取腾讯云代金券