当前位置:网站首页>LeetCode 2353. 设计食物评分系统 维护哈希表+set
LeetCode 2353. 设计食物评分系统 维护哈希表+set
2022-08-02 14:11:00 【超级码力奥】
设计一个支持下述操作的食物评分系统:
修改 系统中列出的某种食物的评分。
返回系统中某一类烹饪方式下评分最高的食物。
实现 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 * 104
n == foods.length == cuisines.length == ratings.length
1 <= foods[i].length, cuisines[i].length <= 10
foods[i]、cuisines[i] 由小写英文字母组成
1 <= ratings[i] <= 108
foods 中的所有字符串 互不相同
在对 changeRating 的所有调用中,food 是系统中食物的名字。
在对 highestRated 的所有调用中,cuisine 是系统中 至少一种 食物的烹饪方式。
最多调用 changeRating 和 highestRated 总计 2 * 104 次
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/design-a-food-rating-system
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class FoodRatings {
public:
/* 一种食物对应一种烹饪方式和一个评分 食物不重复,烹饪方式只有几种 要求支持修改食物的评分 支持取得指定烹饪方式下的评分最高的食物名称 那么对于每种烹饪方式,维护一个对应他的集合set, set是平衡树,查询时间是O(n)级别 set中存评分和食物名称 set会自动按照所存元素的小于号来比较,而pair是自带一个小于号的 修改食物评分,这个会影响每种烹饪方式对应的最高评分 一种食物 -> 一个评分 一种食物 -> 一种烹饪方式 所以总共维护三个: 一种烹饪方式 -> 一个食物和评分的集合(这个集合支持查找最高评分对应的食物) */
// 烹饪方式 -> 选用此烹饪方式的集合,集合中的元素是一个
// pair<int, string> 评分和食物名称,因为题中要求返回评分最高的食物名字
// 如果存在并列,则返回字典序较小的名字,pair排序先看第一位,默认从小到大
// 排序,所以第一位是评分,第二位是食物名称。
unordered_map<string, set<pair<int, string>>> hash;
// 一种食物 -> 一种烹饪方式
unordered_map<string, string> c;
// 一种食物 -> 一个评分
unordered_map<string, int> r;
FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {
for(int i = 0; i < foods.size(); i ++){
c[foods[i]] = cuisines[i];
r[foods[i]] = ratings[i];
// 因为hash[cuisines[i]]是一个set,所以要用insert
// 因为pair排序默认从小到大,而我们维护的是最大的
// 所以取个负号
hash[cuisines[i]].insert({
-ratings[i], foods[i]});
}
}
void changeRating(string food, int newRating) {
auto cuisine = c[food]; // 先取出food对应的食谱
// 把原来食谱中对应的rating删掉
hash[cuisine].erase({
-r[food], food});
r[food] = newRating;
// 加入新的rating
hash[cuisine].insert({
-newRating, food});
}
string highestRated(string cuisine) {
// set的头部的第二个元素
return hash[cuisine].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); */
边栏推荐
猜你喜欢
3. User upload avatar
Detailed introduction to drawing complex surfaces using the plot_surface command
Do Windows 10 computers need antivirus software installed?
What are IPV4 and IPV6?
Win10系统设置application identity自动提示拒绝访问怎么办
Introduction to in-order traversal (non-recursive, recursive) after binary tree traversal
利用plot_surface命令绘制复杂曲面入门详解
Introduction to MATLAB drawing functions ezplot explanation
What should I do if I install a solid-state drive in Win10 and still have obvious lags?
Summarize computer network super comprehensive test questions
随机推荐
Software Testing Basics (Back)
为vscode配置clangd
Do Windows 10 computers need antivirus software installed?
编译error D8021 :无效的数值参数“/Wextra” cl command line error d8021 invalid numeric argument ‘/wextra‘
开心一下,9/28名场面合集
win10系统更新错误代码0x80244022怎么办
一篇文章彻底理解Redis的持久化:RDB、AOF
1.开发社区首页,注册
DP1332E刷卡芯片支持NFC内置mcu智能楼宇/终端poss机/智能门锁
将SSE指令转换为ARM NEON指令
How to set the win10 taskbar does not merge icons
[STM32 Learning 1] Basic knowledge and concepts are clear
CMAKE
IPV4和IPV6是什么?
A clean start Windows 7?How to load only the basic service start Windows 7 system
Win10系统设置application identity自动提示拒绝访问怎么办
【STM32学习1】基础知识与概念明晰
专硕与学硕
General syntax and usage instructions of SQL (picture and text)
背包问题-动态规划-理论篇