当前位置:网站首页>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); */
边栏推荐
- 【STM32学习1】基础知识与概念明晰
- 3. User upload avatar
- What should I do if the Win10 system sets the application identity to automatically prompt for access denied?
- Mysql connection error solution
- 发布模块到npm应该怎么操作?及错误问题解决方案
- Do Windows 10 computers need antivirus software installed?
- pygame draw arc
- How to add a one-key shutdown option to the right-click menu in Windows 11
- pygame image rotate continuously
- 如何用硬币模拟1/3的概率,以及任意概率?
猜你喜欢
随机推荐
Win11 keeps popping up User Account Control how to fix it
Mysql连接错误解决
Cmd Markdown 公式指导手册
Win7遇到错误无法正常开机进桌面怎么解决?
win10系统更新错误代码0x80244022怎么办
cmake配置libtorch报错Failed to compute shorthash for libnvrtc.so
Lightweight AlphaPose
GMP scheduling model of golang
How to set the win10 taskbar does not merge icons
pygame图像连续旋转
pygame拖动条的实现方法
jest测试,组件测试
日常-笔记
开心一下,9/28名场面合集
Compilation error D8021: Invalid numeric argument '/Wextra' cl command line error d8021 invalid numeric argument '/Wextra'
Win10 Settings screen out from lack of sleep?Win10 set the method that never sleep
二叉树遍历之后序遍历(非递归、递归)入门详解
质数相关问题-小记
Codeforces Round #624 (Div. 3)
What are IPV4 and IPV6?