原文链接: https://leetcode-cn.com/problems/tweet-counts-per-frequency

英文原文

A social media company is trying to monitor activity on their site by analyzing the number of tweets that occur in select periods of time. These periods can be partitioned into smaller time chunks based on a certain frequency (every minute, hour, or day).

For example, the period [10, 10000] (in seconds) would be partitioned into the following time chunks with these frequencies:

• Every minute (60-second chunks): [10,69], [70,129], [130,189], ..., [9970,10000]
• Every hour (3600-second chunks): [10,3609], [3610,7209], [7210,10000]
• Every day (86400-second chunks): [10,10000]

Notice that the last chunk may be shorter than the specified frequency's chunk size and will always end with the end time of the period (10000 in the above example).

Design and implement an API to help the company with their analysis.

Implement the TweetCounts class:

• TweetCounts() Initializes the TweetCounts object.
• void recordTweet(String tweetName, int time) Stores the tweetName at the recorded time (in seconds).
• List<Integer> getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime) Returns a list of integers representing the number of tweets with tweetName in each time chunk for the given period of time [startTime, endTime] (in seconds) and frequency freq.
  • freq is one of "minute", "hour", or "day" representing a frequency of every minute, hour, or day respectively.

 

Example:

Input
["TweetCounts","recordTweet","recordTweet","recordTweet","getTweetCountsPerFrequency","getTweetCountsPerFrequency","recordTweet","getTweetCountsPerFrequency"]
[[],["tweet3",0],["tweet3",60],["tweet3",10],["minute","tweet3",0,59],["minute","tweet3",0,60],["tweet3",120],["hour","tweet3",0,210]]

Output
[null,null,null,null,[2],[2,1],null,[4]]

Explanation
TweetCounts tweetCounts = new TweetCounts();
tweetCounts.recordTweet("tweet3", 0);                              // New tweet "tweet3" at time 0
tweetCounts.recordTweet("tweet3", 60);                             // New tweet "tweet3" at time 60
tweetCounts.recordTweet("tweet3", 10);                             // New tweet "tweet3" at time 10
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 59); // return [2]; chunk [0,59] had 2 tweets
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 60); // return [2,1]; chunk [0,59] had 2 tweets, chunk [60,60] had 1 tweet
tweetCounts.recordTweet("tweet3", 120);                            // New tweet "tweet3" at time 120
tweetCounts.getTweetCountsPerFrequency("hour", "tweet3", 0, 210);  // return [4]; chunk [0,210] had 4 tweets

 

Constraints:

• 0 <= time, startTime, endTime <= 109
• 0 <= endTime - startTime <= 104
• There will be at most 104 calls in total to recordTweet and getTweetCountsPerFrequency.

中文题目

请你实现一个能够支持以下两种方法的推文计数类 TweetCounts：

1. recordTweet(string tweetName, int time)

• 记录推文发布情况：用户 tweetName 在 time（以 秒 为单位）时刻发布了一条推文。

2. getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime)

• 返回从开始时间 startTime（以 秒 为单位）到结束时间 endTime（以 秒 为单位）内，每 分 minute，时 hour 或者 日 day （取决于 freq）内指定用户 tweetName 发布的推文总数。
• freq 的值始终为 分 minute，时 hour 或者 日 day 之一，表示获取指定用户 tweetName 发布推文次数的时间间隔。
• 第一个时间间隔始终从 startTime 开始，因此时间间隔为 [startTime, startTime + delta*1>,  [startTime + delta*1, startTime + delta*2>, [startTime + delta*2, startTime + delta*3>, ... , [startTime + delta*i, min(startTime + delta*(i+1), endTime + 1)>，其中 i 和 delta（取决于 freq）都是非负整数。

 

示例：

输入：
["TweetCounts","recordTweet","recordTweet","recordTweet","getTweetCountsPerFrequency","getTweetCountsPerFrequency","recordTweet","getTweetCountsPerFrequency"]
[[],["tweet3",0],["tweet3",60],["tweet3",10],["minute","tweet3",0,59],["minute","tweet3",0,60],["tweet3",120],["hour","tweet3",0,210]]

输出：
[null,null,null,null,[2],[2,1],null,[4]]

解释：
TweetCounts tweetCounts = new TweetCounts();
tweetCounts.recordTweet("tweet3", 0);
tweetCounts.recordTweet("tweet3", 60);
tweetCounts.recordTweet("tweet3", 10);                             // "tweet3" 发布推文的时间分别是 0, 10 和 60 。
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 59); // 返回 [2]。统计频率是每分钟（60 秒），因此只有一个有效时间间隔 [0,60> - > 2 条推文。
tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 60); // 返回 [2,1]。统计频率是每分钟（60 秒），因此有两个有效时间间隔 1) [0,60> - > 2 条推文，和 2) [60,61> - > 1 条推文。 
tweetCounts.recordTweet("tweet3", 120);                            // "tweet3" 发布推文的时间分别是 0, 10, 60 和 120 。
tweetCounts.getTweetCountsPerFrequency("hour", "tweet3", 0, 210);  // 返回 [4]。统计频率是每小时（3600 秒），因此只有一个有效时间间隔 [0,211> - > 4 条推文。

 

提示：

• 同时考虑 recordTweet 和 getTweetCountsPerFrequency，最多有 10000 次操作。
• 0 <= time, startTime, endTime <= 10^9
• 0 <= endTime - startTime <= 10^4

通过代码

高赞题解

思路：

1. 使用 map<int, int> 来保存某时间点的推文数量

2. map 保证在乱序插入元素时，容器内保存的元素有序排列

3. 在查找数量时又可以使用 lower_bound 二分查找来迅速找到所求元素的区间

答题

[]
class TweetCounts {
public:
    TweetCounts() {}
    
    void recordTweet(string tweetName, int time) {
        record[tweetName][time]++;
    }
    
    vector<int> getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime) {
        int f = 1;
        f *= (freq == "minute") ? 60 : 1;
        f *= (freq == "hour") ? 60 * 60 : 1;
        f *= (freq == "day") ? 60 * 60 * 24 : 1;

        vector<int> ans;
        int t = startTime;
        while (t <= endTime) {
            auto bg = record[tweetName].lower_bound(t);
            auto ed = record[tweetName].upper_bound(min(t + f - 1, endTime));
            int cnt = 0;
            for (auto it = bg; it != ed; it++) {
                cnt += it->second;
            }
            ans.push_back(cnt);
            t += f;
        }
        return ans;
    }

private:
    unordered_map<string, map<int, int>> record;
};

致谢

感谢您的观看，希望对您有帮助，欢迎热烈的交流！

如果感觉还不错就点个赞吧~

这是 我的leetcode ，帮助我收集整理题目，可以方便的 visual studio 调试，欢迎关注，star

统计信息

通过次数	提交次数	AC比率
3460	11254	30.7%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言