LeetCode 2353.计划食品评分体系：哈希表 + 有序集合

【LetMeFly】2353.计划食品评分体系：哈希表 + 有序集合

力扣题目链接：https://leetcode.cn/problems/design-a-food-rating-system/
计划一个支持下述操纵的食品评分体系：

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

实现 FoodRatings 类：

• FoodRatings(String[] foods, String[] cuisines, int[] ratings) 初始化体系。食品由 foods、cuisines 和 ratings 形貌，长度均为 n 。
  1. <ul>
  2.         <li><code>foods[i]</code> 是第 <code>i</code> 种食物的名字。</li>
  3.         <li><code>cuisines[i]</code> 是第 <code>i</code> 种食物的烹饪方式。</li>
  4.         <li><code>ratings[i]</code> 是第 <code>i</code> 种食物的最初评分。</li>
  5. </ul>
  6. </li>
  7. <li><code>void changeRating(String food, int newRating)</code> 修改名字为 <code>food</code> 的食物的评分。</li>
  8. <li><code>String highestRated(String cuisine)</code> 返回指定烹饪方式 <code>cuisine</code> 下评分最高的食物的名字。如果存在并列，返回 <strong>字典序较小</strong> 的名字。</li>

  复制代码

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

1. <strong>输入</strong>
2. ["FoodRatings", "highestRated", "highestRated", "changeRating", "highestRated", "changeRating", "highestRated"]
3. [[["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"]]
4. <strong>输出</strong>
5. [null, "kimchi", "ramen", null, "sushi", null, "ramen"]
7. <strong>解释</strong>
8. FoodRatings foodRatings = new FoodRatings(["kimchi", "miso", "sushi", "moussaka", "ramen", "bulgogi"], ["korean", "japanese", "japanese", "greek", "japanese", "korean"], [9, 12, 8, 15, 14, 7]);
9. foodRatings.highestRated("korean"); // 返回 "kimchi"
10.                                     // "kimchi" 是分数最高的韩式料理，评分为 9 。
11. foodRatings.highestRated("japanese"); // 返回 "ramen"
12.                                       // "ramen" 是分数最高的日式料理，评分为 14 。
13. foodRatings.changeRating("sushi", 16); // "sushi" 现在评分变更为 16 。
14. foodRatings.highestRated("japanese"); // 返回 "sushi"
15.                                       // "sushi" 是分数最高的日式料理，评分为 16 。
16. foodRatings.changeRating("ramen", 16); // "ramen" 现在评分变更为 16 。
17. foodRatings.highestRated("japanese"); // 返回 "ramen"
18.                                       // "sushi" 和 "ramen" 的评分都是 16 。
19.                                       // 但是，"ramen" 的字典序比 "sushi" 更小。

复制代码

 
提示：

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

解题方法：计划

哈希表可以通过一个值快速找到拎一个值，有序集合可以快速插入删除一些值并保持集合中元素的有序性。

• 创建一个哈希表，由food查询cuisine和rating；
  
• 创建一个哈希表，由cuisine查询所有使用这个cuisine的(food, rating)集合，集合的排序方式是rating大优先然后字典序小优先。
  

修改评分时，先由food查询出cuisine和rating，再由cuisine查询出使用这个cuisine的(food, rating)集合，删除旧的(food, rating)对，插入新的(food, rating)对。
查询时，由cuisine查询出使用这个cuisine的(food, rating)集合，因为是有序的，所以集合中的第一个元素对就是我们所求。

• 时间复杂度：初始化                                        O                            (                            n                            log                            ⁡                            n                            )                                  O(n\log n)                     O(nlogn)，单次操纵                                        O                            (                            log                            ⁡                            n                            )                                  O(\log n)                     O(logn)，此中                                        n                                  n                     n是食品数量
  
• 空间复杂度                                        O                            (                            n                            )                                  O(n)                     O(n)
  

AC代码

C++

1. /*
2. * @Author: LetMeFly
3. * @Date: 2025-02-28 11:12:40
4. * @LastEditors: LetMeFly.xyz
5. * @LastEditTime: 2025-02-28 11:29:56
6. */
7. class FoodRatings {
8. private:
9.     unordered_map<string, pair<string, int>> food2cuisineScore;        // food->(cuisine, score)
10.     unordered_map<string, set<pair<int, string>>> cuisine2rscoreFood;  // cuisine->[(-score, food), ...]
11. public:
12.     FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {
13.         for (int i = 0; i < foods.size(); i++) {
14.             food2cuisineScore[foods[i]] = {cuisines[i], ratings[i]};
15.             cuisine2rscoreFood[cuisines[i]].insert({-ratings[i], foods[i]});
16.         }
17.     }
18.    
19.     void changeRating(string food, int newRating) {
20.         auto [cuisine, score] = food2cuisineScore[food];
21.         food2cuisineScore[food] = {cuisine, newRating};
22.         cuisine2rscoreFood[cuisine].erase({-score, food});
23.         cuisine2rscoreFood[cuisine].insert({-newRating, food});
24.     }
25.    
26.     string highestRated(string cuisine) {
27.         return (*cuisine2rscoreFood[cuisine].begin()).second;
28.     }
29. };
31. /**
32. * Your FoodRatings object will be instantiated and called as such:
33. * FoodRatings* obj = new FoodRatings(foods, cuisines, ratings);
34. * obj->changeRating(food,newRating);
35. * string param_2 = obj->highestRated(cuisine);
36. */

复制代码

Python

1. '''
2. Author: LetMeFly
3. Date: 2025-02-28 11:30:57
4. LastEditors: LetMeFly.xyz
5. LastEditTime: 2025-02-28 12:28:00
6. '''
7. from typing import List
8. from sortedcontainers import SortedList
9. from collections import defaultdict
12. class FoodRatings:
13.     def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
14.         self.f2cs = dict()
15.         self.c2rf = defaultdict(SortedList)
16.         for i in range(len(foods)):
17.             self.f2cs[foods[i]] = (cuisines[i], ratings[i])
18.             self.c2rf[cuisines[i]].add((-ratings[i], foods[i]))
20.     def changeRating(self, food: str, newRating: int) -> None:
21.         cuisine, rating = self.f2cs[food]
22.         self.f2cs[food] = (cuisine, newRating)
23.         self.c2rf[cuisine].discard((-rating, food))
24.         self.c2rf[cuisine].add((-newRating, food))
26.     def highestRated(self, cuisine: str) -> str:
27.         return self.c2rf[cuisine][0][1]
30. # Your FoodRatings object will be instantiated and called as such:
31. # obj = FoodRatings(foods, cuisines, ratings)
32. # obj.changeRating(food,newRating)
33. # param_2 = obj.highestRated(cuisine)

复制代码

Java

1. /*
2. * @Author: LetMeFly
3. * @Date: 2025-02-28 12:31:05
4. * @LastEditors: LetMeFly.xyz
5. * @LastEditTime: 2025-02-28 12:58:08
6. * @Say: Java是真复杂
7. */
8. import java.util.HashMap;
9. import java.util.Map;
10. import java.util.TreeSet;
13. final class Pair<K extends Comparable<K>, V extends Comparable<V>> implements Comparable<Pair<K, V>> {
14.     private final K key;
15.     private final V value;
17.     public Pair(K key, V value) {
18.         this.key = key;
19.         this.value = value;
20.     }
22.     public K first() {
23.         return key;
24.     }
26.     public V second() {
27.         return value;
28.     }
30.     @Override
31.     public int compareTo(Pair<K, V> other) {
32.         int keyCompare = this.key.compareTo(other.key);
33.         if (keyCompare != 0) {
34.             return keyCompare;
35.         }
36.         return this.value.compareTo(other.value);
37.     }
39.     @Override
40.     public String toString() {
41.         return "Pair{" + "key=" + key + ", value=" + value + '}';
42.     }
43. }
46. class FoodRatings {
47.     private Map<String, Pair<String, Integer>> f2cr = new HashMap<>();
48.     private Map<String, TreeSet<Pair<Integer, String>>> c2rf = new HashMap<>();
50.     public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
51.         for (int i = 0; i < foods.length; i++) {
52.             f2cr.put(foods[i], new Pair<>(cuisines[i], ratings[i]));
53.             c2rf.computeIfAbsent(cuisines[i], k -> new TreeSet<>());
54.             c2rf.get(cuisines[i]).add(new Pair<>(-ratings[i], foods[i]));
55.         }
56.     }
57.    
58.     public void changeRating(String food, int newRating) {
59.         Pair<String, Integer> temp = f2cr.get(food);
60.         String cuisine = temp.first();
61.         int rating = temp.second();
62.         f2cr.put(food, new Pair<>(cuisine, newRating));
64.         TreeSet<Pair<Integer, String>> list = c2rf.get(cuisine);
65.         list.remove(new Pair<>(-rating, food));
66.         list.add(new Pair<>(-newRating, food));
67.     }
68.    
69.     public String highestRated(String cuisine) {
70.         return c2rf.get(cuisine).first().second();
71.     }
72. }
74. /**
75. * Your FoodRatings object will be instantiated and called as such:
76. * FoodRatings obj = new FoodRatings(foods, cuisines, ratings);
77. * obj.changeRating(food,newRating);
78. * String param_2 = obj.highestRated(cuisine);
79. */

复制代码

  同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
  千篇源码题解已开源

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。