每日一题-设计食物评分系统，哈希表的有效使用

本题出自LeetCode2353.设计食物评分系统，连着一星期都是设计类的题目哈

---

题目 

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

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

实现 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. 数据结构选择：
   • 使用一个哈希表（如 HashMap）来记录每个食物对应的当前评分和烹饪方式（foodInfo map）。
   • 另一个哈希表（cuisineMap）来记录每个烹饪方式对应的有序集合（如 TreeSet），集合中的元素按评分从高到低排序，评分相同时按食物名称的字典序升序排列。
2. 初始化方法：
   • 遍历输入数组，将每个食物的信息存入 foodInfo。
   • 同时，将每个食物按其烹饪方式加入到对应的 TreeSet 中。
3. 修改评分方法 changeRating：
   • 从 foodInfo 中获取该食物的旧评分和烹饪方式。
   • 在对应的烹饪方式的 TreeSet 中移除旧的（评分，食物）记录。
   • 更新 foodInfo 中的评分。
   • 将新的（评分，食物）记录插入到 TreeSet 中。
4. 查询最高评分方法 highestRated：
   • 从 cuisineMap 中获取对应烹饪方式的 TreeSet。
   • 返回 TreeSet 的第一个元素的食物名称，因为 TreeSet 是按自定义排序规则排列的，第一个元素就是最高评分且字典序最小的。

---

题解 

class FoodRatings {private static class FoodData {int rating;String cuisine;FoodData(int rating, String cuisine) {this.rating = rating;this.cuisine = cuisine;}}private final Map<String, FoodData> foodMap = new HashMap<>();private final Map<String, TreeSet<Pair<Integer, String>>> cuisineMap = new HashMap<>();public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {for (int i = 0; i < foods.length; i++) {String food = foods[i];String cuisine = cuisines[i];int rating = ratings[i];FoodData data = new FoodData(rating, cuisine);foodMap.put(food, data);cuisineMap.computeIfAbsent(cuisine, k -> new TreeSet<>(Comparator.comparingInt((Pair<Integer, String> p) -> -p.getKey()).thenComparing(Pair::getValue))).add(new Pair<>(rating, food));}}public void changeRating(String food, int newRating) {FoodData data = foodMap.get(food);TreeSet<Pair<Integer, String>> set = cuisineMap.get(data.cuisine);set.remove(new Pair<>(data.rating, food));set.add(new Pair<>(newRating, food));data.rating = newRating;}public String highestRated(String cuisine) {return cuisineMap.get(cuisine).first().getValue();}
}

解题思路的核心在于通过合理的数据结构实现高效的评分更新和最高评分查询操作。系统需维护两种关键数据：各食物的当前属性（烹饪方式、评分）和各烹饪方式下的食物排序。

 

数据结构设计：

 

1. 食物信息映射：使用哈希表存储食物名称到其当前评分及烹饪方式的映射，确保 O (1) 时间获取属性。
2. 烹饪方式的有序集合：为每个烹饪方式维护一个按评分降序、字典序升序排列的有序集合（如 TreeSet），便于快速获取最高评分食物。

 

关键操作实现：

 

1. 初始化：

   • 遍历输入数组，填充食物信息映射。
   • 将每个食物插入对应烹饪方式的排序集合。

2. 修改评分：

   • 通过食物名称获取旧评分和烹饪方式。
   • 从原烹饪方式的集合中移除旧记录。
   • 更新映射中的评分，并将新记录插入集合。

3. 查询最高评分：

   • 直接获取对应烹饪方式集合的首元素（即最高评分且字典序最小的食物）。

 

效率分析：

 

• 修改操作的时间复杂度为 O (logN)，主要消耗在有序集合的删除和插入。
• 查询操作时间复杂度为 O (1)，通过有序集合的首元素直接获取结果。

 

题目属于系统设计类问题，核心在于通过高效的数据结构实现动态评分更新与快速查询最高评分。

---

制作不易，您的关注与点赞是我最大的动力！