设计食物评分系统

难度: Medium

设计一个支持下述操作的食物评分系统：

修改系统中列出的某种食物的评分。
返回系统中某一类烹饪方式下评分最高的食物。

实现 FoodRatings 类：

FoodRatings(String[] foods, String[] cuisines, int[] ratings) 初始化系统。食物由 foods、cuisines 和 ratings 描述，长度均为 n 。
- foods[i] 是第 i 种食物的名字。
- cuisines[i] 是第 i 种食物的烹饪方式。
- ratings[i] 是第 i 种食物的最初评分。
void changeRating(String food, int newRating) 修改名字为 food 的食物的评分。
String highestRated(String cuisine) 返回指定烹饪方式 cuisine 下评分最高的食物的名字。如果存在并列，返回 字典序较小 的名字。

注意，字符串 x 的字典序比字符串 y 更小的前提是：x 在字典中出现的位置在 y 之前，也就是说，要么 x 是 y 的前缀，或者在满足 x[i] != y[i] 的第一个位置 i 处，x[i] 在字母表中出现的位置在 y[i] 之前。

示例：

输入
["FoodRatings", "highestRated", "highestRated", "changeRating", "highestRated", "changeRating", "highestRated"]
[[["kimchi", "miso", "sushi", "moussaka", "ramen", "bulgogi"], ["korean", "japanese", "japanese", "greek", "japanese", "korean"], [9, 12, 8, 15, 14, 7]], ["korean"], ["japanese"], ["sushi", 16], ["japanese"], ["ramen", 16], ["japanese"]]
输出
[null, "kimchi", "ramen", null, "sushi", null, "ramen"]

解释
FoodRatings foodRatings = new FoodRatings(["kimchi", "miso", "sushi", "moussaka", "ramen", "bulgogi"], ["korean", "japanese", "japanese", "greek", "japanese", "korean"], [9, 12, 8, 15, 14, 7]);
foodRatings.highestRated("korean"); // 返回 "kimchi"
                                    // "kimchi" 是分数最高的韩式料理，评分为 9 。
foodRatings.highestRated("japanese"); // 返回 "ramen"
                                      // "ramen" 是分数最高的日式料理，评分为 14 。
foodRatings.changeRating("sushi", 16); // "sushi" 现在评分变更为 16 。
foodRatings.highestRated("japanese"); // 返回 "sushi"
                                      // "sushi" 是分数最高的日式料理，评分为 16 。
foodRatings.changeRating("ramen", 16); // "ramen" 现在评分变更为 16 。
foodRatings.highestRated("japanese"); // 返回 "ramen"
                                      // "sushi" 和 "ramen" 的评分都是 16 。
                                      // 但是，"ramen" 的字典序比 "sushi" 更小。

提示：

1 <= n <= 2 * 10⁴
n == foods.length == cuisines.length == ratings.length
1 <= foods[i].length, cuisines[i].length <= 10
foods[i]、cuisines[i] 由小写英文字母组成
1 <= ratings[i] <= 10⁸
foods 中的所有字符串 互不相同
在对 changeRating 的所有调用中，food 是系统中食物的名字。
在对 highestRated 的所有调用中，cuisine 是系统中 至少一种 食物的烹饪方式。
最多调用 changeRating 和 highestRated 总计 2 * 10⁴ 次

Submission

运行时间: 252 ms

内存: 49.9 MB

class FoodRatings:
    def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
        self.fs = {}
        self.cs = defaultdict(list)
        for f, c, r in zip(foods, cuisines, ratings):
            self.fs[f] = [r, c]
            heappush(self.cs[c], (-r, f))

    def changeRating(self, food: str, newRating: int) -> None:
        f = self.fs[food]
        heappush(self.cs[f[1]], (-newRating, food))  # 直接添加新数据，后面 highestRated 再删除旧的
        f[0] = newRating

    def highestRated(self, cuisine: str) -> str:
        h = self.cs[cuisine]
        while -h[0][0] != self.fs[h[0][1]][0]:  # 堆顶的食物评分不等于其实际值
            heappop(h)
        return h[0][1]

Explain

这个题解采用了哈希表和最小堆的数据结构来有效管理食物的评分和查询。具体来说，使用一个哈希表 `fs` 存储每个食物的评分和所属烹饪方式，使用 `cs` 字典的每个键对应一个最小堆，存储每种烹饪方式下所有食物的评分（存储为负数以模拟最大堆）和食物名。当修改食物评分时，直接在对应烹饪方式的堆中添加新的评分，旧的评分将在执行 `highestRated` 操作时被检查并移除，保证了堆中总是有最新的评分数据。这种做法虽然在更改评分时较快，但可能导致堆中有多余的元素，需要在查询最高评分时进行清理。

时间复杂度: O(log n)

空间复杂度: O(n)

class FoodRatings:
    def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
        self.fs = {}  # 存储食物及其评分和烹饪方式
        self.cs = defaultdict(list)  # 存储每种烹饪方式的食物评分堆
        for f, c, r in zip(foods, cuisines, ratings):
            self.fs[f] = [r, c]
            heappush(self.cs[c], (-r, f))  # 使用负值模拟最大堆

    def changeRating(self, food: str, newRating: int) -> None:
        f = self.fs[food]
        heappush(self.cs[f[1]], (-newRating, food))  # 将新评分添加到堆中
        f[0] = newRating  # 更新哈希表中的评分

    def highestRated(self, cuisine: str) -> str:
        h = self.cs[cuisine]
        while -h[0][0] != self.fs[h[0][1]][0]:  # 清理堆顶的无效评分
            heappop(h)
        return h[0][1]  # 返回当前最高评分的食物名

Explore

在许多编程语言的标准库中，包括Python，通常只提供了最小堆的实现（例如Python的heapq库）。为了实现最大堆的功能，一种常见的技巧是将元素的符号取反，即存储元素的负值，这样原本较大的数在负值后会变得较小，因此在最小堆的顶部就能得到原始数值中的最大值。这种方法简单且利用了现有的库，避免了从零开始实现最大堆的复杂性和可能的错误。

这种设计的主要优点是简化了评分更新操作。当食物评分改变时，新的评分可以快速地被添加到堆中，而不需要先遍历堆来移除旧的评分，从而提高了操作的效率。然而，主要缺点是堆可能会积累很多过时的评分数据，这不仅增加了空间复杂度，还可能在执行查询最高评分的操作时增加时间复杂度，因为需要在返回结果前清理这些无效的评分。

在`highestRated`方法中，通过检查堆顶元素的评分是否与哈希表中记录的当前评分一致来确保只移除过时的评分。如果堆顶的评分（需要考虑到存储时取了负数）不等于哈希表中的评分，说明这是一个过时的评分，应该被移除。这个操作会持续进行，直到堆顶的评分是有效的为止。这种方法确保了只有过时的评分被移除，而当前有效的评分保持在堆顶。

如果在`highestRated`方法执行过程中发现堆中的所有元素都是无效的（即堆被完全清空），这表明存在逻辑错误或数据维护问题。在实际应用中，应该确保在食物评分被移除或更新时堆能正确地维持至少一个有效的评分。如果真的发生了堆完全清空的情况，则可能需要抛出异常或返回一个错误信息，提示系统存在数据一致性问题。在设计系统时，应该尽量避免这种情况的发生。