设计食物评分系统
难度:
标签:
题目描述
代码结果
运行时间: 252 ms, 内存: 49.9 MB
/*
* 思路:
* 1. 使用 HashMap 存储食物到评分和食物到烹饪方式的映射。
* 2. 使用 TreeSet 存储每种烹饪方式下的食物,TreeSet 以评分为主要排序,
* 字典序为次要排序。
* 3. changeRating 方法使用 Java Stream 操作,更新评分后重新插入 TreeSet。
* 4. highestRated 方法直接从 TreeSet 获取评分最高的食物。
*/
import java.util.*;
import java.util.stream.*;
class FoodRatings {
private Map<String, String> foodToCuisine;
private Map<String, Integer> foodToRating;
private Map<String, TreeSet<String>> cuisineToFoods;
public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
foodToCuisine = new HashMap<>();
foodToRating = new HashMap<>();
cuisineToFoods = new HashMap<>();
for (int i = 0; i < foods.length; i++) {
foodToCuisine.put(foods[i], cuisines[i]);
foodToRating.put(foods[i], ratings[i]);
cuisineToFoods.computeIfAbsent(cuisines[i], k -> new TreeSet<>((a, b) -> {
int ratingA = foodToRating.get(a);
int ratingB = foodToRating.get(b);
if (ratingA == ratingB) {
return a.compareTo(b);
}
return Integer.compare(ratingB, ratingA);
})).add(foods[i]);
}
}
public void changeRating(String food, int newRating) {
String cuisine = foodToCuisine.get(food);
TreeSet<String> foodSet = cuisineToFoods.get(cuisine);
foodSet.remove(food); // 先移除旧的评分
foodToRating.put(food, newRating); // 更新评分
foodSet.add(food); // 重新加入以保持排序
}
public String highestRated(String cuisine) {
return cuisineToFoods.get(cuisine).first();
}
}
解释
方法:
这个题解采用了哈希表和最小堆的数据结构来有效管理食物的评分和查询。具体来说,使用一个哈希表 `fs` 存储每个食物的评分和所属烹饪方式,使用 `cs` 字典的每个键对应一个最小堆,存储每种烹饪方式下所有食物的评分(存储为负数以模拟最大堆)和食物名。当修改食物评分时,直接在对应烹饪方式的堆中添加新的评分,旧的评分将在执行 `highestRated` 操作时被检查并移除,保证了堆中总是有最新的评分数据。这种做法虽然在更改评分时较快,但可能导致堆中有多余的元素,需要在查询最高评分时进行清理。
时间复杂度:
O(log n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在实现最大堆时选择用最小堆存储负数,而不是直接使用最大堆库?
▷🦆
在`changeRating`方法中,添加新评分到堆而不移除旧评分的设计有何优缺点?
▷🦆
如何确保在`highestRated`方法中能正确地清除所有过时的评分,而不会错误地移除当前有效的评分?
▷🦆
如果`highestRated`方法中堆的所有元素都是无效的,如何处理这种极端情况?
▷