2353-设计食物评分系统

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

设计一个支持下述操作的食物评分系统：

  • 修改 系统中列出的某种食物的评分。
  • 返回系统中某一类烹饪方式下评分最高的食物。

实现 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 次

本题 视频讲解 已出炉，额外讲解了应对设计题的一些技巧。欢迎点赞三连，在评论区分享你对这场周赛的看法~

方法一：平衡树（有序集合）

我们可以用一个哈希表 fs 记录每个食物名称对应的食物评分和烹饪方式，另一个哈希表套平衡树 cs 记录每个烹饪方式对应的食物评分和食物名字集合。

对于 changeRating 操作，先从 cs}[\textit{fs}[\textit{food}].\textit{cuisine}] 中删掉旧数据，然后将 newRating 和 food 记录到 cs 和 fs 中。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from sortedcontainers import SortedSet

class FoodRatings:
    def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
        self.fs = {}
        self.cs = defaultdict(SortedSet)
        for f, c, r in zip(foods, cuisines, ratings):
            self.fs[f] = [r, c]
            self.cs[c].add((-r, f))

    def changeRating(self, food: str, newRating: int) -> None:
        r, c = self.fs[food]
        s = self.cs[c]
        s.remove((-r, food))  # 移除旧数据
        s.add((-newRating, food))  # 添加新数据
        self.fs[food][0] = newRating

    def highestRated(self, cuisine: str) -> str:
        return self.cs[cuisine][0][1]
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class FoodRatings {
    Map<String, Pair<Integer, String>> fs = new HashMap<>();
    Map<String, TreeSet<Pair<Integer, String>>> cs = new HashMap<>();

    public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
        for (var i = 0; i < foods.length; i++) {
            String f = foods[i], c = cuisines[i];
            var r = ratings[i];
            fs.put(f, new Pair<>(r, c));
            cs.computeIfAbsent(c, k -> new TreeSet<>((a, b) -> !Objects.equals(a.getKey(), b.getKey()) ? b.getKey() - a.getKey() : a.getValue().compareTo(b.getValue()))).add(new Pair<>(r, f));
        }
    }

    public void changeRating(String food, int newRating) {
        var e = fs.get(food);
        var s = cs.get(e.getValue());
        s.remove(new Pair<>(e.getKey(), food)); // 移除旧数据
        s.add(new Pair<>(newRating, food)); // 添加新数据
        fs.put(food, new Pair<>(newRating, e.getValue()));
    }

    public String highestRated(String cuisine) {
        return cs.get(cuisine).first().getValue();
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class FoodRatings {
    unordered_map<string, pair<int, string>> fs;
    unordered_map<string, set<pair<int, string>>> cs;
public:
    FoodRatings(vector<string> &foods, vector<string> &cuisines, vector<int> &ratings) {
        for (int i = 0; i < foods.size(); ++i) {
            auto &f = foods[i], &c = cuisines[i];
            int r = ratings[i];
            fs[f] = {r, c};
            cs[c].emplace(-r, f);
        }
    }

    void changeRating(string food, int newRating) {
        auto &[r, c] = fs[food];
        auto &s = cs[c];
        s.erase({-r, food}); // 移除旧数据
        s.emplace(-newRating, food); // 添加新数据
        r = newRating;
    }

    string highestRated(string cuisine) {
        return cs[cuisine].begin()->second;
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
type pair struct {
	r int
	s string
}

type FoodRatings struct {
	fs map[string]pair
	cs map[string]*redblacktree.Tree
}

func Constructor(foods, cuisines []string, ratings []int) FoodRatings {
	fs := map[string]pair{}
	cs := map[string]*redblacktree.Tree{}
	for i, f := range foods {
		r, c := ratings[i], cuisines[i]
		fs[f] = pair{r, c}
		if cs[c] == nil {
			cs[c] = redblacktree.NewWith(func(x, y interface{}) int {
				a, b := x.(pair), y.(pair)
				if a.r != b.r {
					return utils.IntComparator(b.r, a.r)
				}
				return utils.StringComparator(a.s, b.s)
			})
		}
		cs[c].Put(pair{r, f}, nil)
	}
	return FoodRatings{fs, cs}
}

func (r FoodRatings) ChangeRating(food string, newRating int) {
	p := r.fs[food]
	t := r.cs[p.s]
	t.Remove(pair{p.r, food}) // 移除旧数据
	t.Put(pair{newRating, food}, nil) // 添加新数据
	p.r = newRating
	r.fs[food] = p
}

func (r FoodRatings) HighestRated(cuisine string) string {
	return r.cs[cuisine].Left().Key.(pair).s
}

方法二：懒删除堆

另一种做法是用堆：

  • 对于 changeRating 操作，直接往 cs 中记录，不做任何删除操作；
  • 对于 highestRated 操作，查看堆顶的食物评分是否等于其实际值，若不相同则意味着对应的元素已被替换成了其他值，堆顶存的是个垃圾数据，直接弹出堆顶；否则堆顶就是答案。
[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class FoodRatings:
    def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
        self.fs = {}
        self.cs = defaultdict(list)
        for f, c, r in zip(foods, cuisines, ratings):
            self.fs[f] = [r, c]
            heappush(self.cs[c], (-r, f))

    def changeRating(self, food: str, newRating: int) -> None:
        f = self.fs[food]
        heappush(self.cs[f[1]], (-newRating, food))  # 直接添加新数据，后面 highestRated 再删除旧的
        f[0] = newRating

    def highestRated(self, cuisine: str) -> str:
        h = self.cs[cuisine]
        while -h[0][0] != self.fs[h[0][1]][0]:  # 堆顶的食物评分不等于其实际值
            heappop(h)
        return h[0][1]
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class FoodRatings {
    Map<String, Pair<Integer, String>> fs = new HashMap<>();
    Map<String, Queue<Pair<Integer, String>>> cs = new HashMap<>();

    public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {
        for (var i = 0; i < foods.length; i++) {
            String f = foods[i], c = cuisines[i];
            var r = ratings[i];
            fs.put(f, new Pair<>(r, c));
            cs.computeIfAbsent(c, k -> new PriorityQueue<>((a, b) -> !Objects.equals(a.getKey(), b.getKey()) ? b.getKey() - a.getKey() : a.getValue().compareTo(b.getValue()))).add(new Pair<>(r, f));
        }
    }

    public void changeRating(String food, int newRating) {
        var c = fs.get(food).getValue();
        cs.get(c).offer(new Pair<>(newRating, food)); // 直接添加新数据，后面 highestRated 再删除旧的
        fs.put(food, new Pair<>(newRating, c));
    }

    public String highestRated(String cuisine) {
        var q = cs.get(cuisine);
        while (!Objects.equals(q.peek().getKey(), fs.get(q.peek().getValue()).getKey())) // 堆顶的食物评分不等于其实际值
            q.poll();
        return q.peek().getValue();
    }
}
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class FoodRatings {
    unordered_map<string, pair<int, string>> fs;
    unordered_map<string, priority_queue<pair<int, string>, vector<pair<int, string>>, greater<>>> cs;
public:
    FoodRatings(vector<string> &foods, vector<string> &cuisines, vector<int> &ratings) {
        for (int i = 0; i < foods.size(); ++i) {
            auto &f = foods[i], &c = cuisines[i];
            int r = ratings[i];
            fs[f] = {r, c};
            cs[c].emplace(-r, f);
        }
    }

    void changeRating(string food, int newRating) {
        auto &[r, c] = fs[food];
        cs[c].emplace(-newRating, food); // 直接添加新数据，后面 highestRated 再删除旧的
        r = newRating;
    }

    string highestRated(string cuisine) {
        auto &q = cs[cuisine];
        while (-q.top().first != fs[q.top().second].first) // 堆顶的食物评分不等于其实际值
            q.pop();
        return q.top().second;
    }
};
[sol2-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
type pair struct {
	r int
	s string
}

type FoodRatings struct {
	fs map[string]pair
	cs map[string]*hp
}

func Constructor(foods, cuisines []string, ratings []int) FoodRatings {
	fs := map[string]pair{}
	cs := map[string]*hp{}
	for i, f := range foods {
		r, c := ratings[i], cuisines[i]
		fs[f] = pair{r, c}
		if cs[c] == nil {
			cs[c] = &hp{}
		}
		heap.Push(cs[c], pair{r, f})
	}
	return FoodRatings{fs, cs}
}

func (r FoodRatings) ChangeRating(food string, newRating int) {
	p := r.fs[food]
	heap.Push(r.cs[p.s], pair{newRating, food}) // 直接添加新数据，后面 highestRated 再删除旧的
	p.r = newRating
	r.fs[food] = p
}

func (r FoodRatings) HighestRated(cuisine string) string {
	h := *r.cs[cuisine]
	for h.Len() > 0 && h[0].r != r.fs[h[0].s].r { // 堆顶的食物评分不等于其实际值
		heap.Pop(&h)
	}
	return h[0].s
}

type hp []pair
func (h hp) Len() int            { return len(h) }
func (h hp) Less(i, j int) bool  { a, b := h[i], h[j]; return a.r > b.r || a.r == b.r && a.s < b.s }
func (h hp) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
 Comments
On this page
2353-设计食物评分系统
  1. 方法一：平衡树（有序集合）
  • 方法二：懒删除堆