侧边栏壁纸
博主头像
SeaDream乄造梦

Dream,Don't stop a day of hard and don't give up a little hope。 ——不停止一日努力&&不放弃一点希望。

  • 累计撰写 40 篇文章
  • 累计创建 20 个标签
  • 累计收到 13 条评论

目 录CONTENT

文章目录

经典算法3 java 算法 蓝桥杯——日志统计 解题过程记录

SeaDream乄造梦
2022-03-30 / 0 评论 / 0 点赞 / 411 阅读 / 2,157 字
温馨提示:
亲爱的,如果觉得博主很有趣就留下你的足迹,并收藏下链接在走叭

这一个题,就这一个 猿猿太菜了,整整花费了一天半才把他搞明白,感觉内心受到了打击,被虐的真难受。一天半啥也没干,想思路想半天,代码实现半天,最后还没实现成功,分析别人代码小半天,最后抄别人代码一遍,才真正理解其中规律。
至于图解分析,猿猿累了,心情好了以后有空在来补充图解分析吧,暂时先贴上我的解决过程,都在代码注释中哦。

题目


日志统计
时间限制: 1.0s 内存限制: 512.0MB
【问题描述】
小明维护着一个程序员论坛。现在他收集了一份"点赞"日志,日志共有N行。其中每一行的格式是:
ts id
表示在ts时刻编号id的帖子收到一个"赞"。

现在小明想统计有哪些帖子曾经是"热帖"。如果一个帖子曾在任意一个长度为D的时间段内收到不少于K个赞,小明就认为这个帖子曾是"热帖"。
具体来说,如果存在某个时刻T满足该帖在[T, T+D)这段时间内(注意是左闭右开区间)收到不少于K个赞,该帖就曾是"热帖"。

给定日志,请你帮助小明统计出所有曾是"热帖"的帖子编号。
【输入格式】
第一行包含三个整数N、D和K。
以下N行每行一条日志,包含两个整数ts和id。

对于50%的数据,1 <= K <= N <= 1000
对于100%的数据,1 <= K <= N <= 100000 0 <= ts <= 100000 0 <= id <= 100000

【输出格式】
按从小到大的顺序输出热帖id。每个id一行。

【输入样例】
7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3

【输出样例】
1
3


代码及解决思路过程


import java.util.*;
/**
 * 在ts时刻,编号id收到1个赞
 * 一个帖子只要在任意一个D时间内有过>=k个赞   ==》热帖
 * 从小到大顺序输出热帖id
 * N=7  D=10   K=2
 */
public class 日志统计 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n=scanner.nextInt(),d=scanner.nextInt(),k= scanner.nextInt();
        int ts,id;
        ArrayList <Integer> [] arr= new ArrayList[100001];//数组型容器
        HashMap <Integer,Integer> hm  = new HashMap<Integer,Integer>();//键值对
        TreeSet <Integer> trs  = new TreeSet<>();//去重并自动排序

        //初始化arr   不然装不进去东西
        for (int i=0;i<arr.length;i++) {
            arr[i] = new ArrayList<>();
        }
        for (int i=0;i<n;i++) {
            ts= scanner.nextInt();
            id= scanner.nextInt();
            arr[ts].add(id);
        }

        long star = System.currentTimeMillis();
        for (int i=0;i<arr.length;i++) {
            //在某个d时间段   id的赞超过k个,则此id被认为是热帖===>存进map中
            /**
             * 从0-d  时间段,对于id的增加是累加的
             * 超过(题目大于等于)d这个时间,id的赞  会继续累加,但是它前面的已经不在这个新d范围,需要减掉   比如i==11的时候,需要减去i=i-d==1时候的id赞
             */
            //遍历所有的 ts对应的容器
            // System.out.println(arr[i]);
            if(i>=d) {  //从d开始扔掉前面的所有数据,使始终只剩下d个数据,   d始终是个动态区间,扔到d区间之前的数据
                for (Integer ids:arr[i-d]) {//i-d是动态去除i-d之前所有的数据,使剩下的数据只有区间d
                    if(hm.get(ids)>=k) {
                        trs.add(ids);//自动去重且自动排序
                    }

                    hm.put(ids,hm.get(ids)-1);
                }
            }
            for (Integer ids : arr[i]) {  //输出秒数ts对应的id,看懂这个关键在于i-d  i-d==》退出d之前的,比如i==11  退出ts=i-d=1,时的id次数
                //遍历有数据的ts对应的id
                // System.out.println(ids);
                /** 输入  7 10 2  
                 *   ts    ids
                 *   0    [1,10]
                 *   9    [1]
                 *   10   [10,1]
                 *   100  [3,3]
                 */
                if(hm.containsKey(ids)) {  //如果hashmap中有这个帖子id,点赞数+1
                    hm.put(ids,hm.get(ids)+1);
                }else {   //如果hashmap中没有这个帖子id,存进去
                    hm.put(ids,1);
                }

            }
        }
        for (Integer tr : trs) {
            System.out.println(tr);
        }
        long end = System.currentTimeMillis();
        //System.out.println(end-star);
    }
}
0

评论区