資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++ 設計點選計數器
假設我們想要設計一個點選計數器，用於統計過去 5 分鐘內收到的點選次數。該計數器將包含一個函式，該函式接受以秒為單位的時間戳引數，並且我們可以假設對系統的呼叫是按時間順序進行的（因此，時間戳單調遞增）。我們還假設最早的時間戳從 1 開始。
可能會有多個點選幾乎同時到達。
因此，我們將呼叫 hit() 函式進行點選計數，並呼叫 getHits() 函式獲取點選次數。
為了解決這個問題，我們將遵循以下步驟：
定義一個大小為 300 的陣列 time
定義一個大小為 300 的陣列 hits
定義一個函式 hit()，它將接收時間戳作為引數：
idx := timestamp mod 300
如果 time[idx] 不等於 timestamp，則：
time[idx] := timestamp
hits[idx] := 1
否則
hits[idx] := hits[idx] + 1
定義一個函式 getHits()，它將接收時間戳作為引數：
ret := 0
從 i := 0 開始，當 i < 300 時，執行以下操作（i 增加 1）：
如果 timestamp - time[i] < 300，則：
ret := ret + hits[i]
返回 ret
示例
讓我們來看下面的實現，以便更好地理解：
#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
更新於：2020年11月19日
568 次瀏覽
廣告