leetcode
leetcode 2001 ~ 2050
设计食物评分系统

设计食物评分系统

难度:

标签:

题目描述

代码结果

运行时间: 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)

代码细节讲解

🦆
为什么在实现最大堆时选择用最小堆存储负数,而不是直接使用最大堆库?
在许多编程语言的标准库中,包括Python,通常只提供了最小堆的实现(例如Python的heapq库)。为了实现最大堆的功能,一种常见的技巧是将元素的符号取反,即存储元素的负值,这样原本较大的数在负值后会变得较小,因此在最小堆的顶部就能得到原始数值中的最大值。这种方法简单且利用了现有的库,避免了从零开始实现最大堆的复杂性和可能的错误。
🦆
在`changeRating`方法中,添加新评分到堆而不移除旧评分的设计有何优缺点?
这种设计的主要优点是简化了评分更新操作。当食物评分改变时,新的评分可以快速地被添加到堆中,而不需要先遍历堆来移除旧的评分,从而提高了操作的效率。然而,主要缺点是堆可能会积累很多过时的评分数据,这不仅增加了空间复杂度,还可能在执行查询最高评分的操作时增加时间复杂度,因为需要在返回结果前清理这些无效的评分。
🦆
如何确保在`highestRated`方法中能正确地清除所有过时的评分,而不会错误地移除当前有效的评分?
在`highestRated`方法中,通过检查堆顶元素的评分是否与哈希表中记录的当前评分一致来确保只移除过时的评分。如果堆顶的评分(需要考虑到存储时取了负数)不等于哈希表中的评分,说明这是一个过时的评分,应该被移除。这个操作会持续进行,直到堆顶的评分是有效的为止。这种方法确保了只有过时的评分被移除,而当前有效的评分保持在堆顶。
🦆
如果`highestRated`方法中堆的所有元素都是无效的,如何处理这种极端情况?
如果在`highestRated`方法执行过程中发现堆中的所有元素都是无效的(即堆被完全清空),这表明存在逻辑错误或数据维护问题。在实际应用中,应该确保在食物评分被移除或更新时堆能正确地维持至少一个有效的评分。如果真的发生了堆完全清空的情况,则可能需要抛出异常或返回一个错误信息,提示系统存在数据一致性问题。在设计系统时,应该尽量避免这种情况的发生。

相关问题