Leetcode Link: 6126. 设计食物评分系统 - 力扣（LeetCode）
题目
设计一个支持下述操作的食物评分系统：
- 修改 系统中列出的某种食物的评分。
- 返回系统中某一类烹饪方式下评分最高的食物。
实现 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] 之前。
解法一
思路： 设计题常常需要根据某一个函数来决定里面的东西怎么写。
先直接看 String highestRated(String cuisine)
-
显然，该函数的查找流程应该是这样的
cuisine -> foods list -> food with higest rated因此，我们需要能够快速的根据 cuisine 找到对应类别下的所有 food。故我们需要一个self.cur2food字典变量，这样能够直接用self.cur2food[cuisine]找到。 -
接下来我们需要在这个 food list 里找到得分最高的 food 不用纠结，这一块一定需要特别设计，不可能让你用一个 for 或者 max 去找，必定会超时，只可能让你用类似大根堆那种直接访问第一个元素就得到结果的数据类型。→ 这也是本题的考点。
对于这种数据结构，python 可以使用”排序容器”，而 Python 标准库没有实现排序容器，在
sortedcontainers库中有了相关实现。下面将会主要介绍其中的SortedList容器1
SortedList 本质上是 list 类型，但是每次添加新的元素后会自动按照创建时的 key 排序
- 创建:
SortedList(data=None, key=None) - 添加元素:
sortedlst.add(data) - 移除元素:
sortedlst.remove(data)
这里不是那种传统的 list 的添加方式
append, 直接按照索引访问会访问第 ind 小的元素 (若 key 不特殊指定的话)
默认情况下，SortedList 会对输入的数据进行升序排列，sortedlst[0] 为最小值，sortedlst[-1] 为最大值
如何使用 key，可以参考 sorted()-method，利用 key 同样可以变成升序。
考虑 void changeRating (String food, int newRating) 函数
- 需要能根据 food 找到对应的 rating:
self.food2rating - 同时需要把上面提到的
self.cui2food进行修改，但是这里没有输入 food 对应的 cui，因此我们创建时需要一个这样的查询变量self.food2cui
初始化函数
根据上面分析的，初始化三个变量 self.food2rating，self.cui2food, self.food2cui
都初始化成字典类型方便查找。
题解：
from sortedcontainers import SortedList
class FoodRatings:
def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
self.food2rating = {}
self.cui2food = {}
self.food2cui = {}
for food, cui, rate in zip(foods, cuisines, ratings):
self.food2cui[food] = cui
self.food2rating[food] = rate
# 先判定存不存在，不存在需要新建
if self.cui2food.get(cui, None) == None:
self.cui2food[cui] = SortedList(key=lambda x: (-x[1], x[0])) # x[0]表字典序升序，初始化时可以不用指定data
self.cui2food[cui].add((food, rate))
def changeRating(self, food: str, newRating: int) -> None:
last_rating = self.food2rating[food]
self.food2rating[food] = newRating
self.cui2food[self.food2cui[food]].remove((food, last_rating)) #注意移除旧的评分
self.cui2food[self.food2cui[food]].add((food, newRating))
def highestRated(self, cuisine: str) -> str:
return self.cui2food[cuisine][0][0] # 注意返回的是food名字