362. Design Hit Counter

做题历程：

1. 本题应该做了不止一遍，本次独立解出，大概耗时8分钟

先说一个我自己解出来的解法，就是用queue<int>来存储timestamp，这样就相当直观。如果Hit的话，就往里面放，如果是要得Hit数的话，就pop()5分钟之前的就行，代码如下：

class HitCounter {
public:
    /** Initialize your data structure here. */
    HitCounter() {
    }

    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    void hit(int timestamp) {
        time_queue.push(timestamp);
    }

    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    int getHits(int timestamp) {
        while (!time_queue.empty() && (timestamp - time_queue.front() >= 300)) {
            time_queue.pop();
        }
        return time_queue.size();
    }
private:
    queue<int> time_queue;
};

/**
 * Your HitCounter object will be instantiated and called as such:
 * HitCounter obj = new HitCounter();
 * obj.hit(timestamp);
 * int param_2 = obj.getHits(timestamp);
 */

当然本题还有一个Follow up，就是解决每秒内Hit过多 其实这就是一个选择时间上更快，还是空间上更省的trade-off 这个方法开始我没有想到，看答案看到的。挺巧妙的：就是建立两个vector<int>： hit_vector和time_vector都是有300个元素，index都是指当前的timestamp % 300的值， hit_vector保存的是hit数,time_vector存储的是hit_vector对应的真实时间，大体思路就是这样，看代码会更加清晰，代码如下：

class HitCounter {
public:
    /** Initialize your data structure here. */
    HitCounter() {
        time_vector.resize(300);
        hit_vector.resize(300);
    }

    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    void hit(int timestamp) {
        int mod_time = timestamp % 300;
        if (timestamp != time_vector[mod_time]) {
            time_vector[mod_time] = timestamp;
            hit_vector[mod_time] = 1;
        }
        else {
            ++hit_vector[mod_time];
        }
    }

    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    int getHits(int timestamp) {
        int res = 0;
        for (int i = 0; i < 300; ++i) {
            if (timestamp - time_vector[i] < 300) {
                res += hit_vector[i];
            }
        }
        return res;
    }
private:
    vector<int> time_vector;
    vector<int> hit_vector;
};

/**
 * Your HitCounter object will be instantiated and called as such:
 * HitCounter obj = new HitCounter();
 * obj.hit(timestamp);
 * int param_2 = obj.getHits(timestamp);
 */