สมมติว่าเราต้องการออกแบบตัวนับจำนวนการโจมตีที่นับจำนวนครั้งที่ได้รับในช่วง 5 นาทีที่ผ่านมา จะมีฟังก์ชันและยอมรับพารามิเตอร์การประทับเวลาในหน่วยที่สอง และเราอาจถือว่ามีการเรียกไปยังระบบตามลำดับเวลา (ดังนั้น การประทับเวลาจึงเพิ่มขึ้นอย่างซ้ำซากจำเจ) เรายังถือว่าการประทับเวลาที่เร็วที่สุดเริ่มต้นที่ 1
เป็นไปได้ที่การตีหลายครั้งจะมาถึงพร้อมกันอย่างคร่าวๆ
ดังนั้นเราจะเรียกฟังก์ชัน hit() เพื่อตี และฟังก์ชัน getHits() เพื่อรับจำนวนครั้งของการโจมตี
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดเวลาอาร์เรย์ขนาด 300
-
กำหนดอาร์เรย์ขนาด 300
-
กำหนดฟังก์ชัน hit() ซึ่งจะใช้เวลาประทับ
-
idx :=ตัวดัดแปลงประทับเวลา 300
-
หาก time[idx] ไม่เท่ากับการประทับเวลา −
-
เวลา[idx] :=การประทับเวลา
-
hits[idx] :=1
-
-
มิฉะนั้น
-
hits[idx] :=hits[idx] + 1
-
-
กำหนดฟังก์ชัน getHits() ซึ่งจะใช้เวลาประทับ
-
ยกเลิก :=0
-
สำหรับการเริ่มต้น i :=0 เมื่อ i <300 อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -
-
ถ้าประทับเวลา - time[i] <300 แล้ว −
-
ret :=ret + hits[i]
-
-
-
รีเทิร์น
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h>
using namespace std;
class HitCounter {
public:
vector<int< time;
vector<int< hits;
HitCounter(){
time = vector<int<(300);
hits = vector<int<(300);
}
void hit(int timestamp){
int idx = timestamp % 300;
if (time[idx] != timestamp) {
time[idx] = timestamp;
hits[idx] = 1;
}
else {
hits[idx] += 1;
}
}
int getHits(int timestamp){
int ret = 0;
for (int i = 0; i < 300; i++) {
if (timestamp - time[i] < 300) {
ret += hits[i];
}
}
return ret;
}
};
main(){
HitCounter ob;
ob.hit(1);
ob.hit(2);
ob.hit(3);
cout << (ob.getHits(4)) << endl;
ob.hit(300);
cout << (ob.getHits(300)) << endl;
cout << (ob.getHits(301));
} อินพุต
ob.hit(1); ob.hit(2); ob.hit(3); ob.getHits(4); ob.hit(300); ob.getHits(300); ob.getHits(301);
ผลลัพธ์
3 4 3
