小红书 8.6 数据开发试卷

一、选择题

总计20道

408内容+大数据框架（Hadoop、Spark、Flink等）

有单选，也有多选

二、编程题

第一题：小红书推荐系统

统计热点词频；输入一个字符串，统计词频后，按照词频从高到低打印热搜单词（出现次数超过3，同时对于两个词频相同的单词，要按单词字典序打印

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    Map<String,Integer> map = new HashMap<>();
    String s = sc.nextLine();
    String[] st= s.split(" ");
    for(int i=0;i<st.length;i++){
        map.put(st[i],map.getOrDefault(st[i], 0) + 1);
    }
    // int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
    PriorityQueue<Map.Entry<String,Integer>> pd = new PriorityQueue<>(
            (o1,o2)->o1.getValue().equals(o2.getValue())?o1.getKey().compareTo(
                    o2.getKey()):o2.getValue()-o1.getValue());
    for(Map.Entry<String,Integer>entry:map.entrySet()){
        pd.offer(entry);
    }
    for(int i=0;!pd.isEmpty();i++){
        Map.Entry<String,Integer> entry = pd.poll();
         String name = entry.getKey();
         if(entry.getValue()>=3){
             System.out.println(name);
         }
    }
}

第二题：小红的分析日常

有n件事情，每件事情都有时间ti,精力hi,快乐值ai，如果小红做某件事情就会消耗对应的时间tj,精力hj,从而获得快乐值aj；求在消耗时间不超过 t,且精力不超过 h的情况下，小红所能获得的最大快乐值是多少；

双重限制的01背包，主要a的范围，开long

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//事件数
        int T = sc.nextInt();//时间限制
        int H = sc.nextInt();//精力限制
        int[] t = new int[n+1];
        int[] h = new int[n+1];
        long[] a = new long[n+1];
        for(int i =1;i<=n;i++){
            t[i] = sc.nextInt();
            h[i] = sc.nextInt();
            a[i] = sc.nextLong();
        }
        long [][][] value = new long[n+1][T+1][H+1];
        for(int i=1;i<n+1;i++){
            for(int j=1;j<T+1;j++){
                for(int k=1;k<H+1;k++){
                    if(j-t[i]>=0&&k-h[i]>=0){
                        value[i][j][k] = Math.max(value[i-1][j][k],
                                value[i-1][j-t[i]][k-h[i]]+a[i]);
                    }else {
                        value[i][j][k] =value[i-1][j][k];
                    }
                }
            }
        }
    System.out.println(value[n][T][H]);
    }

第三题：小红的小红书

小红有一颗树，每个结点有一个权值，初始时每个节点都是白色。小红每次操作可以选择两个相邻的结点，如果它们都是白色且权值的和是质数，小红就可以选择其中一个节点染红。

小红想知道最多可以染红多少个节点?

判断有多少条边满足质数，即可AC。

    static Set<Integer> primes = new HashSet<>();
    static boolean[] st;
    static int[] V;
    static void get_primes() {
        int n = 200000;
        for (int i = 2 ; i <= n ; i++) {
            if (!st[i]) {
                primes.add(i);
                for (int j = i+i ; j <= n ; j+=i) {
                    st[j] = true;
                }
            }
        }
    }
    public static void main(String[] args) {
        st = new boolean[200001];
        get_primes();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        V = new int[n+1];
        for (int i = 1; i <= n; i++) {
            V[i] = sc.nextInt();
        }
        int res = 0;
        for (int i = 0; i < n - 1; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            if (primes.contains(a + b)) {
                res++;
            }
        }
        System.out.println(res);
    }