X

LEETCODE 1348. Tweet Counts Per Frequency 解题思路分析

题目大意:

推文计数

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

  • recordTweet(string tweetName, int time)
    • 记录推文发布情况:用户 tweetName 在 time(以 秒 为单位)时刻发布了一条推文。
  • getTweetCountsPerFrequency(string freq, string tweetName, int startTime, int endTime)
    • 返回从开始时间 startTime(以 秒 为单位)到结束时间 endTime(以 秒 为单位)内,每 分 minute,时 hour 或者 日 day (取决于 freq)内指定用户 tweetName 发布的推文总数。
    • freq 的值始终为 分 minute,时 hour 或者 日 day 之一,表示获取指定用户 tweetName 发布推文次数的时间间隔。
    • 第一个时间间隔始终从 startTime 开始,因此时间间隔为 [startTime, startTime + delta1>,  [startTime + delta1, startTime + delta2>, [startTime + delta2, startTime + delta3>, … , [startTime + deltai, 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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1348

解题思路分析:

本题难度不大,我们可以将每个人的发帖按照时间升序顺序存储到map中,key为用户名,value为该用户发帖时间列表(升序排列)。统计发帖次数时,先看统计频率,如果是分,就将时间区间按照60秒分成n等份(最后一份可能会小于60秒),如果是小时,就按照60*60秒分,同理,如果是天,就按照 60*60*24秒来分。统计出每一区间的发帖数量即可。

实现代码:

Map<String, List<Integer>> map = new HashMap<>();
public TweetCounts() {

}

public void recordTweet(String tweetName, int time) {
    // 取出该用户的发帖列表
    List<Integer> list=map.getOrDefault(tweetName,new ArrayList<>());
    // 将当前发帖时间添加至列表
    list.add(time);
    // 将列表存入map
    map.put(tweetName, list);
}

public List<Integer> getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime) {
    // 根据题意,结束区间加一
    endTime++;
    // 取得该用户发帖列表
    List<Integer> list = map.get(tweetName);
    // 返回结果
    List<Integer> res = new ArrayList<>();
    // 如果当前用户没有发帖,返回res
    if(list==null) return res;
    // 排序用户发帖时间
    Collections.sort(list);
    // 时间间隔
    int f=0;
    if(freq.equals("minute")){
        f=60;
    }else if(freq.equals("hour")){
        f=3600;
    }else{
        f=3600*24;
    }
    // 遍历每一个发帖时间
    int i=0;
    while(startTime<endTime){
        // 当前开始区间
        int s = startTime;
        // 当前结束区间
        int e = Math.min(startTime+f, endTime);
        int count=0;
        // 时间区间内符合条件的帖子
        for(;i<list.size();i++){
            int time = list.get(i);
            if(time>=s&&time<e) count++;
            if(time>=e) break;
        }
        res.add(count);
        startTime=e;
    }
    return res;
}

本题解法执行时间为133ms。

Runtime: 133 ms, faster than 48.00% of Java online submissions for Tweet Counts Per Frequency.

Memory Usage: 51.9 MB, less than 100.00% of Java online submissions for Tweet Counts Per Frequency.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1348-tweet-counts-per-frequency-解题思路分析/
Categories: leetcode
kwantong: