目录

力扣 346. 数据流中的移动平均值

力扣 362. 敲击计数器

循环数组是一种简单的数据结构，通过id的mod实现循环。

力扣 346. 数据流中的移动平均值

给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算其所有整数的移动平均值。

实现 MovingAverage 类：

MovingAverage(int size) 用窗口大小 size 初始化对象。
double next(int val) 计算并返回数据流中最后 size 个值的移动平均值。
 

示例：

输入：
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
输出：
[null, 1.0, 5.5, 4.66667, 6.0]

解释：
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // 返回 1.0 = 1 / 1
movingAverage.next(10); // 返回 5.5 = (1 + 10) / 2
movingAverage.next(3); // 返回 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // 返回 6.0 = (10 + 3 + 5) / 3
 

提示：

1 <= size <= 1000
-105 <= val <= 105
最多调用 next 方法 104 次

      class MovingAverage {
      public:
     	MovingAverage(int size) {
     		while (size--)v.push_back(0);
      		loc = 0, flag = 0;;
      	}
     	double next(int val) {
      		v[loc++] = val;
     		if (loc == v.size())flag = 1, loc = 0;
     		double ans = 0;
     		for (auto &vi : v)ans += vi;
     		return ans / (flag == 1 ? v.size() : loc);
      	}
      	vector<int>v;
     	int loc;
     	int flag;
      };
  
 

力扣 362. 敲击计数器

设计一个敲击计数器，使它可以统计在过去 5 分钟内被敲击次数。（即过去 300 秒）

您的系统应该接受一个时间戳参数 timestamp (单位为 秒 )，并且您可以假定对系统的调用是按时间顺序进行的(即 timestamp 是单调递增的)。几次撞击可能同时发生。

实现 HitCounter 类:

HitCounter() 初始化命中计数器系统。
void hit(int timestamp) 记录在 timestamp ( 单位为秒 )发生的一次命中。在同一个 timestamp 中可能会出现几个点击。
int getHits(int timestamp) 返回 timestamp 在过去 5 分钟内(即过去 300 秒)的命中次数。
 

示例 1:

输入：
["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"]
[[], [1], [2], [3], [4], [300], [300], [301]]
输出：
[null, null, null, null, 3, null, 4, 3]

解释：
HitCounter counter = new HitCounter();
counter.hit(1);// 在时刻 1 敲击一次。
counter.hit(2);// 在时刻 2 敲击一次。
counter.hit(3);// 在时刻 3 敲击一次。
counter.getHits(4);// 在时刻 4 统计过去 5 分钟内的敲击次数, 函数返回 3 。
counter.hit(300);// 在时刻 300 敲击一次。
counter.getHits(300); // 在时刻 300 统计过去 5 分钟内的敲击次数，函数返回 4 。
counter.getHits(301); // 在时刻 301 统计过去 5 分钟内的敲击次数，函数返回 3 。
 

提示:

1 <= timestamp <= 2 * 109
所有对系统的调用都是按时间顺序进行的（即 timestamp 是单调递增的）
hit and getHits 最多被调用 300 次
 

进阶: 如果每秒的敲击次数是一个很大的数字，你的计数器可以应对吗？

      class HitCounter {
      public:
     	HitCounter() {
     		int size = 300;
     		while (size--)v.push_back(0);
      		loc = 0;
      	}
     	void hit(int timestamp) {
     		if (timestamp != loc) {
     			if (timestamp - loc >= 300)for (int i = 0; i < v.size(); i++)v[i] = 0;
     			else for (int i = loc + 1; i <= timestamp; i++)v[i % 300] = 0;
      		}
      		v[timestamp % 300]++;
      		loc = timestamp;
      	}
     	int getHits(int timestamp) {
     		int ans = 0;
     		for (int i = timestamp - 299; i <= timestamp && i<=loc; i++) {
      			ans += v[(i + 300) % 300];
      		}
     		return ans;
      	}
      	vector<int>v;
     	int loc;
      };
  
 

文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nameofcsdn/article/details/124768024