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 。 <ul>
<li><code>foods</code> 是第 <code>i</code> 种食物的名字。</li>
<li><code>cuisines</code> 是第 <code>i</code> 种食物的烹饪方式。</li>
<li><code>ratings</code> 是第 <code>i</code> 种食物的最初评分。</li>
</ul>
</li>
<li><code>void changeRating(String food, int newRating)</code> 修改名字为 <code>food</code> 的食物的评分。</li>
<li><code>String highestRated(String cuisine)</code> 返回指定烹饪方式 <code>cuisine</code> 下评分最高的食物的名字。如果存在并列，返回 <strong>字典序较小</strong> 的名字。</li>
注意，字符串 x 的字典序比字符串 y 更小的前提是：x 在字典中出现的位置在 y 之前，也就是说，要么 x 是 y 的前缀，或者在满足 x != y 的第一个位置 i 处，x 在字母表中出现的位置在 y 之前。
示例：
<strong>输入</strong>
["FoodRatings", "highestRated", "highestRated", "changeRating", "highestRated", "changeRating", "highestRated"]
[[["kimchi", "miso", "sushi", "moussaka", "ramen", "bulgogi"], ["korean", "japanese", "japanese", "greek", "japanese", "korean"], ], ["korean"], ["japanese"], ["sushi", 16], ["japanese"], ["ramen", 16], ["japanese"]]
<strong>输出</strong>
<strong>解释</strong>
FoodRatings foodRatings = new FoodRatings(["kimchi", "miso", "sushi", "moussaka", "ramen", "bulgogi"], ["korean", "japanese", "japanese", "greek", "japanese", "korean"], );
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 * 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++
/*
* @Author: LetMeFly
* @Date: 2025-02-28 11:12:40
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-02-28 11:29:56
*/
class FoodRatings {
private:
unordered_map<string, pair<string, int>> food2cuisineScore; // food->(cuisine, score)
unordered_map<string, set<pair<int, string>>> cuisine2rscoreFood;// cuisine->[(-score, food), ...]
public:
FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {
for (int i = 0; i < foods.size(); i++) {
food2cuisineScore] = {cuisines, ratings};
cuisine2rscoreFood].insert({-ratings, foods});
}
}
void changeRating(string food, int newRating) {
auto = food2cuisineScore;
food2cuisineScore = {cuisine, newRating};
cuisine2rscoreFood.erase({-score, food});
cuisine2rscoreFood.insert({-newRating, food});
}
string highestRated(string cuisine) {
return (*cuisine2rscoreFood.begin()).second;
}
};
/**
* Your FoodRatings object will be instantiated and called as such:
* FoodRatings* obj = new FoodRatings(foods, cuisines, ratings);
* obj->changeRating(food,newRating);
* string param_2 = obj->highestRated(cuisine);
*/
Python
'''
Author: LetMeFly
Date: 2025-02-28 11:30:57
LastEditors: LetMeFly.xyz
LastEditTime: 2025-02-28 12:28:00
'''
from typing import List
from sortedcontainers import SortedList
from collections import defaultdict
class FoodRatings:
def __init__(self, foods: List, cuisines: List, ratings: List):
self.f2cs = dict()
self.c2rf = defaultdict(SortedList)
for i in range(len(foods)):
self.f2cs] = (cuisines, ratings)
self.c2rf].add((-ratings, foods))
def changeRating(self, food: str, newRating: int) -> None:
cuisine, rating = self.f2cs
self.f2cs = (cuisine, newRating)
self.c2rf.discard((-rating, food))
self.c2rf.add((-newRating, food))
def highestRated(self, cuisine: str) -> str:
return self.c2rf
# Your FoodRatings object will be instantiated and called as such:
# obj = FoodRatings(foods, cuisines, ratings)
# obj.changeRating(food,newRating)
# param_2 = obj.highestRated(cuisine)
Java
/*
* @Author: LetMeFly
* @Date: 2025-02-28 12:31:05
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-02-28 12:58:08
* @Say: Java是真复杂
*/
import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;
final class Pair<K extends Comparable<K>, V extends Comparable<V>> implements Comparable<Pair<K, V>> {
private final K key;
private final V value;
public Pair(K key, V value) {
this.key = key;
this.value = value;
}
public K first() {
return key;
}
public V second() {
return value;
}
@Override
public int compareTo(Pair<K, V> other) {
int keyCompare = this.key.compareTo(other.key);
if (keyCompare != 0) {
return keyCompare;
}
return this.value.compareTo(other.value);
}
@Override
public String toString() {
return "Pair{" + "key=" + key + ", value=" + value + '}';
}
}
class FoodRatings {
private Map<String, Pair<String, Integer>> f2cr = new HashMap<>();
private Map<String, TreeSet<Pair<Integer, String>>> c2rf = new HashMap<>();
public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
for (int i = 0; i < foods.length; i++) {
f2cr.put(foods, new Pair<>(cuisines, ratings));
c2rf.computeIfAbsent(cuisines, k -> new TreeSet<>());
c2rf.get(cuisines).add(new Pair<>(-ratings, foods));
}
}
public void changeRating(String food, int newRating) {
Pair<String, Integer> temp = f2cr.get(food);
String cuisine = temp.first();
int rating = temp.second();
f2cr.put(food, new Pair<>(cuisine, newRating));
TreeSet<Pair<Integer, String>> list = c2rf.get(cuisine);
list.remove(new Pair<>(-rating, food));
list.add(new Pair<>(-newRating, food));
}
public String highestRated(String cuisine) {
return c2rf.get(cuisine).first().second();
}
}
/**
* Your FoodRatings object will be instantiated and called as such:
* FoodRatings obj = new FoodRatings(foods, cuisines, ratings);
* obj.changeRating(food,newRating);
* String param_2 = obj.highestRated(cuisine);
*/
同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
千篇源码题解已开源
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]