Skip to content

LeetCode: 2352-Design a Food Rating System 解題紀錄

題目

Design a food rating system that can do the following:

  • Modify the rating of a food item listed in the system.
  • Return the highest-rated food item for a type of cuisine in the system.

Implement the FoodRatings class:

  • FoodRatings(String[] foods, String[] cuisines, int[] ratings) Initializes the system. The food items are described by foods, cuisines and ratings, all of which have a length of n.
    • foods[i] is the name of the ith food,
    • cuisines[i] is the type of cuisine of the ith food, and
    • ratings[i] is the initial rating of the ith food.
  • void changeRating(String food, int newRating) Changes the rating of the food item with the name food.
  • String highestRated(String cuisine) Returns the name of the food item that has the highest rating for the given type of cuisine. If there is a tie, return the item with the lexicographically smaller name.

Note that a string x is lexicographically smaller than string y if x comes before y in dictionary order, that is, either x is a prefix of y, or if i is the first position such that x[i] != y[i], then x[i] comes before y[i] in alphabetic order.

Example 1:

Input
[“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”]]

Output
[null, “kimchi”, “ramen”, null, “sushi”, null, “ramen”]


Constraints:

  • 1 <= n <= 2 * 104
  • n == foods.length == cuisines.length == ratings.length
  • 1 <= foods[i].length, cuisines[i].length <= 10
  • foods[i], cuisines[i] consist of lowercase English letters.
  • 1 <= ratings[i] <= 108
  • All the strings in foods are distinct.
  • food will be the name of a food item in the system across all calls to changeRating.
  • cuisine will be a type of cuisine of at least one food item in the system across all calls to highestRated.
  • At most 2 * 104 calls in total will be made to changeRating and highestRated.

解題思路

這題雖然看起來很單純就是我們建構好依照不同菜系的餐點名稱列表，並依照評分排序，接著在 highestRated() 呼叫時，依照傳入的菜系不同，返回該菜系最高評分的餐點；與此同時，我們需要另外建構一個 changeRating() 的方法，讓程式可以隨時更改餐點的分數。

最後我選擇了使用 set 來解，並且 set 中的元素都是 pair 的元件，pair 的第一個元素為餐點分數，第二個元素為餐點名稱。並且我們需要建構屬於這個題目的排序比較方法，因為評分最高的定義是分數最高者、並且同分的情況選擇字典序較低者 —— 預設的排序無論是分數還是字典序都是由小到大。

所以在 changeRating() 的情況下，我可以在 O(log(n)) 的情況下刪除舊有的 pair（因為 set 是紅黑樹的檢索），並且同樣在 O(log(n)) 的情況下插入新的 pair。

然後在 highestRated() 的情況，則依照餐點菜系，直接返回排序最高者的參點名稱，這一過程就是 O(1) 了。


C++ 範例程式碼

class FoodRatings {
private:
    struct Compare {
        bool operator()(const std::pair<int, std::string>& a, const std::pair<int, std::string>& b) const {
            if (a.first != b.first) {
                return a.first > b.first;
            }
            
            return a.second < b.second;
        }
    };

    std::unordered_map<std::string, int> food2rating;
    std::unordered_map<std::string, std::string> food2cuisine;
    std::unordered_map<std::string, std::set<std::pair<int, std::string>, Compare>> cuisine2foods;

public:
    FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {
        for (int i=0; i<foods.size(); ++i) {
            food2rating[foods[i]] = ratings[i];
            food2cuisine[foods[i]] = cuisines[i];
            cuisine2foods[cuisines[i]].insert({ratings[i], foods[i]});
        }
    }
    
    void changeRating(string food, int newRating) {
        // Update highest food by cuisines
        const std::string& cuisine = food2cuisine[food];
        cuisine2foods[cuisine].erase({food2rating[food], food});
        cuisine2foods[cuisine].insert({newRating, food});

        // Update rating
        food2rating[food] = newRating;
    }
    
    std::string highestRated(string cuisine) {
        return cuisine2foods[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);
 */



References

Read More

Tags:

Leave a Reply