您的位置:首页 > 健康 > 美食 > 北京网站建设公司分形_互动网页设计是什么_友情链接英文_推广和竞价代运营

北京网站建设公司分形_互动网页设计是什么_友情链接英文_推广和竞价代运营

2025/3/16 2:50:27 来源:https://blog.csdn.net/yl_puyu/article/details/145953947  浏览:    关键词:北京网站建设公司分形_互动网页设计是什么_友情链接英文_推广和竞价代运营
北京网站建设公司分形_互动网页设计是什么_友情链接英文_推广和竞价代运营

文章目录

    • 1. 题目来源
    • 2. 题目解析

1. 题目来源

链接:2353. 设计食物评分系统

题单:

  • 待补充

2. 题目解析

这种 平衡树、优先队列的,暂时拿 go 还写不了,没有合适的板子用。就先拿 C++ 写吧,日后看看啥时候会补齐这个板子。


方法一:set 平衡树写法

  • 涉及到一些 set 的基本操作和技巧操作。
  • set 是一颗平衡树,底层是 红黑树。
  • 从小到大排序。
  • 常用技巧,set 平衡树输入的时候取负值,然后 begin() 位置就是实际的最大值。

方法二:懒删除堆

  • 一个很妙的技巧,之前好像没啥印象,也是记录这个题的目的。
  • chang 的时候,直接往堆中插记录。
  • 查询的时候,直接取堆顶,如果堆顶的评分和哈希表一致的话,那就说明这个就是有效元素,否则这个元素无效,直接 pop 即可。
  • 最终,堆顶即为有效数据。

  • 时间复杂度 O ( n log ⁡ n ) O(n \log n) O(nlogn)
  • 空间复杂度 O ( n ) O(n) O(n)

C++ STL::set 写法:

class FoodRatings {
public:unordered_map<string, pair<string, int>> m1; // 【食物,<烹饪方式, 得分>】unordered_map<string, set<pair<int, string>>> m2; // 【烹饪方式,set<得分,名称>】FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {int n = foods.size();for (int i = 0; i < n; i ++ ) {m1[foods[i]] = {cuisines[i], ratings[i]};// 常用技巧,set 平衡树输入的时候取负值,然后 begin() 位置就是实际的最大值m2[cuisines[i]].insert({-ratings[i], foods[i]}); }}void changeRating(string food, int newRating) {auto f = m1[food];m1[food] = {f.first, newRating};m2[f.first].erase({-f.second, food});m2[f.first].insert({-newRating, food});}string highestRated(string cuisine) {return m2[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);*/

懒删除,小顶堆。写法

class FoodRatings {
public:unordered_map<string, pair<string, int>> m1; // 懒删除堆。注意,这里需要用小顶堆。因为需要按照字典序进行排序输出。unordered_map<string, priority_queue<pair<int, string>, vector<pair<int, string>>, greater<>>> m2;FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {int n = foods.size();for (int i = 0; i < n; i ++ ) {m1[foods[i]] = {cuisines[i], ratings[i]};m2[cuisines[i]].push({-ratings[i], foods[i]}); }}void changeRating(string food, int newRating) {auto &f = m1[food];m1[food] = {f.first, newRating};// 堆中直接插入即可m2[f.first].push({-newRating, food});}string highestRated(string cuisine) {// 这里需要引用...否则 TTLauto &m = m2[cuisine];// 懒删除堆经典操作:查看堆顶元素值是否和实际值一致,不一致则 pop,一致则说明找到了最值while (m.size() && -m1[m.top().second].second != m.top().first) {m.pop();}return m.top().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);*/

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com