[leetcode 优先队列] 2512. 奖励最顶尖的 K 名学生 M

简介: [leetcode 优先队列] 2512. 奖励最顶尖的 K 名学生 M

给你两个字符串数组 positive_feedback 和 negative_feedback ,分别包含表示正面的和负面的词汇。不会 有单词同时是正面的和负面的。

一开始,每位学生分数为 0 。每个正面的单词会给学生的分数 加 3 分,每个负面的词会给学生的分数 减 1 分。

给你 n 个学生的评语,用一个下标从 0 开始的字符串数组 report 和一个下标从 0 开始的整数数组 student_id 表示,其中 student_id[i] 表示这名学生的 ID ,这名学生的评语是 report[i] 。每名学生的 ID 互不相同。

给你一个整数 k ,请你返回按照得分 从高到低 最顶尖的 k 名学生。如果有多名学生分数相同,ID 越小排名越前。

示例 1:

输入:positive_feedback = [“smart”,“brilliant”,“studious”], negative_feedback = [“not”], report = [“this student is studious”,“the student is smart”], student_id = [1,2], k = 2

输出:[1,2]

解释:

两名学生都有 1 个正面词汇,都得到 3 分,学生 1 的 ID 更小所以排名更前。

示例 2:

输入:positive_feedback = [“smart”,“brilliant”,“studious”], negative_feedback = [“not”], report = [“this student is not studious”,“the student is smart”], student_id = [1,2], k = 2

输出:[2,1]

解释:

  • ID 为 1 的学生有 1 个正面词汇和 1 个负面词汇,所以得分为 3-1=2 分。
  • ID 为 2 的学生有 1 个正面词汇,得分为 3 分。
    学生 2 分数更高,所以返回 [2,1] 。

提示:

1 <= positive_feedback.length, negative_feedback.length <= 104

1 <= positive_feedback[i].length, negative_feedback[j].length <= 100

positive_feedback[i] 和 negative_feedback[j] 都只包含小写英文字母。

positive_feedback 和 negative_feedback 中不会有相同单词。

n == report.length == student_id.length

1 <= n <= 1 0 4 10^4104

report[i] 只包含小写英文字母和空格 ’ ’ 。

report[i] 中连续单词之间有单个空格隔开。

1 <= report[i].length <= 100

1 <= student_id[i] <= 1 0 9 10^9109

student_id[i] 的值 互不相同 。

1 <= k <= n


class Solution {
    public List<Integer> topStudents(String[] positive_feedback, String[] negative_feedback, String[] report, int[] student_id, int k) {
        Map<String, Integer> words = new HashMap<>();
        for (String word : positive_feedback) {
            words.put(word, 3);
        }
        for (String word : negative_feedback) {
            words.put(word, -1);
        }
        int n = report.length;
        int[] scores = new int[n];
        int[][] A = new int[n][2];
        for (int i = 0; i < n; i++) {
            int score = 0;
            for (String word : report[i].split(" ")) {
                score += words.getOrDefault(word, 0);
            }
            A[i] = new int[]{-score, student_id[i]};
        }
        Arrays.sort(A, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        List<Integer> topK = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            topK.add(A[i][1]);
        }
        return topK;
    }
}

class Solution {
    public List<Integer> topStudents(String[] positive_feedback, String[] negative_feedback, String[] report, int[] student_id, int k) {
            PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[1] == b[1] ? a[0] - b[0] : b[1] - a[1]);
            HashSet<String> pos = new HashSet<>(Arrays.asList(positive_feedback));
            HashSet<String> nav = new HashSet<>(Arrays.asList(negative_feedback));
            int n = report.length;
            for(int i=0; i<n; i++) {
                String[] s = report[i].split(" ");
                int cnt = 0;
                int length = s.length;
                for(int j = 0; j < length; j++) {
                    if(pos.contains(s[j])) cnt += 3;
                    else if (nav.contains(s[j])) {
                        cnt -= 1;
                    }
                }
                q.offer(new int[]{student_id[i], cnt});
            }
            ArrayList<Integer> ans = new ArrayList<>();
            for(int i=0; i<k; i++) {
                ans.add(q.poll()[0]);
            }
            return ans;
        }
}
相关文章
|
13天前
【Leetcode 2583】二叉树中的第K大层和 —— 优先队列 + BFS
解题思路: - 使用队列保存节点,按层序依次保存该层节点 - 使用优先队列保存每层节点值的总和,最后剔除前k个大数即可得到
|
C++
【力扣·每日一题】630. 课程表 III (C++ 贪心 优先队列)
【力扣·每日一题】630. 课程表 III (C++ 贪心 优先队列)
50 0
【力扣·每日一题】630. 课程表 III (C++ 贪心 优先队列)
【力扣·每日一题】1005. K 次取反后最大化的数组和 (贪心 优先队列)
【力扣·每日一题】1005. K 次取反后最大化的数组和 (贪心 优先队列)
34 0
【力扣·每日一题】1005. K 次取反后最大化的数组和 (贪心 优先队列)
|
机器学习/深度学习 算法
【刷穿 LeetCode】502. IPO : 详解优先队列实现贪心算法
【刷穿 LeetCode】502. IPO : 详解优先队列实现贪心算法
|
机器学习/深度学习 算法 Java
【刷穿 LeetCode】面试题 17.14. 最小K个数:「优先队列(堆)」&「全排序」&「数组划分」
【刷穿 LeetCode】面试题 17.14. 最小K个数:「优先队列(堆)」&「全排序」&「数组划分」
|
机器学习/深度学习 存储
【刷穿 LeetCode】求「第 n 个超级丑数」的两种方式 :「优先队列」&「多路归并」
【刷穿 LeetCode】求「第 n 个超级丑数」的两种方式 :「优先队列」&「多路归并」
|
存储 索引
【刷穿 LeetCode】一题双解 :「朴素解法」&「二分 + 优先队列(堆)」| 8月更文挑战
【刷穿 LeetCode】一题双解 :「朴素解法」&「二分 + 优先队列(堆)」| 8月更文挑战
|
C++ 容器
【LeetCode451】根据字符出现频率排序(优先队列)
【LeetCode451】根据字符出现频率排序(优先队列) (1)根据词频排序,很容易想到用哈希表统计每个字符的个数,然后排序。对于“求前k个”或“排序”的题目可以使用堆排序,用优先级队列实现最大堆,进行堆排序,堆顶即当前的最大值。因为我们的pair<char, int>的second才是对应字符(first)的词频,需要的是对second进行排序,所以重写cmp。
148 0
【LeetCode451】根据字符出现频率排序(优先队列)
LeetCode 2070. 每一个查询的最大美丽值(离线查询+排序+优先队列)
LeetCode 2070. 每一个查询的最大美丽值(离线查询+排序+优先队列)
174 0