2353. Design a Food Rating System

Leetcode link

题目简介

题目要求我们实现一个食物评分系统，其中包含三个方法

• FoodRatings：构造函数，包含 foods, cuisines, ratings 三个参数分别代表食物、菜系、评分，其中食物是唯一的
• changeRating：更改评分，接受 food, newRating 两个参数
• highestRated：返回当前菜系最高评分的食物，接受 cuisine 一个参数

解题思路

这道题的核心难点在于，要如何在调用 highestRated 时使用最少的时间复杂度

解决方案是使用大顶堆 MaxHeap

首先我们需要几个 Map 来帮助我们保存食物、菜系、评分之间的关系：

• foodToCuisine：保存食物到菜系之间的映射关系
• foodToRating：保存食物到评分间的映射关系
• cuisineToHeap：保存菜系到大顶堆之间的映射关系

大顶堆中保存着由评分与食物组成的数组

当调用 FoodRatings 时，我们需要根据参数初始化好三个 Map 的数据

当调用 changeRating 时，我们需要更新 foodToRating 与 cuisineToHeap之中的 heap，但是 heap 中的数据不好删除，所以我们在这一步就先只插入新数据就好

最后当调用 highestRated 时，我们需要将 heap 取得的最大 rating 与当前的 foodToRating 中记录的 rating 做对比，如果不符合我们需要抛弃当前的数据（把 changeRating 时没有删除的数据在这里删除了）直到我们找到符合 foodToRating 记录的 rating

leetcode 在 js 环境有提供了 PriorityQueue 的实现，所以也可以不用自己实现一个 MaxHeap

Javascript（自己实现 maxHeap）

/**
 * @param {string[]} foods
 * @param {string[]} cuisines
 * @param {number[]} ratings
 */
var FoodRatings = function (foods, cuisines, ratings) {
    this.foodTocuisine = new Map()
    this.foodToRating = new Map()
    this.cuisineToHeap = new Map()

    for (let i = 0; i < foods.length; i++) {
        this.foodTocuisine.set(foods[i], cuisines[i])
        this.foodToRating.set(foods[i], ratings[i])

        const cuisine = cuisines[i]
        if(!this.cuisineToHeap.has(cuisine)) {
            this.cuisineToHeap.set(cuisine, new MyMaxHeap())
        }
        this.cuisineToHeap.get(cuisine).push([ratings[i], foods[i]])
    }
};

/** 
 * @param {string} food 
 * @param {number} newRating
 * @return {void}
 */
FoodRatings.prototype.changeRating = function (food, newRating) {
    this.foodToRating.set(food, newRating)
    const cuisine = this.foodTocuisine.get(food)
    this.cuisineToHeap.get(cuisine).push([newRating, food])
};

/** 
 * @param {string} cuisine
 * @return {string}
 */
FoodRatings.prototype.highestRated = function (cuisine) {
    const heap = this.cuisineToHeap.get(cuisine)

    while(!heap.isEmpty()){
        const [rating, food] = heap.peek()
        if(rating === this.foodToRating.get(food)) {
            return food
        }
        heap.pop()
    }
    return ''
};

class MyMaxHeap {
    constructor() {
        this.heap = []
    }

    push(item) {
        this.heap.push(item)
        this.heapifyUp(this.heap.length - 1)
    }

    isEmpty() {
        return this.heap.length === 0
    }

    pop() {
        if (this.heap.length <= 1) {
            return this.heap.pop()
        }
        const res = this.heap[0]
        this.heap[0] = this.heap.pop()
        this.heapifyDown(0)
        return res
    }

    peek() {
        return this.heap[0]
    }

    heapifyUp(index) {
        const parent = Math.floor((index - 1) / 2)
        //  if index's rating > parent's rating
        if (parent >= 0 && this.compare(this.heap[index], this.heap[parent]) > 0) {
            // swap them
            [this.heap[index], this.heap[parent]] = [this.heap[parent], this.heap[index]]
            this.heapifyUp(parent)
        }
    }

    heapifyDown(index) {
        const left = index * 2 + 1
        const right = index * 2 + 2
        let largest = index

        // if left > largest
        if (left < this.heap.length && this.compare(this.heap[left], this.heap[largest]) > 0) {
            largest = left
        }
        // if right > largest
        if (right < this.heap.length && this.compare(this.heap[right], this.heap[largest]) > 0) {
            largest = right
        }

        if (largest !== index) {
            [this.heap[index], this.heap[largest]] = [this.heap[largest], this.heap[index]]
            this.heapifyDown(largest)
        }
    }

    compare([ratingA, foodA], [ratingB, foodB]) {
        if (ratingA !== ratingB) {
            return ratingA - ratingB
        }
        return foodB.localeCompare(foodA)
    }
}

Javascript（使用 leetcode 提供的 PriorityQueue）

/**
 * @param {string[]} foods
 * @param {string[]} cuisines
 * @param {number[]} ratings
 */
var FoodRatings = function (foods, cuisines, ratings) {
    this.foodTocuisine = new Map()
    this.foodToRating = new Map()
    this.cuisineToQueue = new Map()

    for (let i = 0; i < foods.length; i++) {
        this.foodTocuisine.set(foods[i], cuisines[i])
        this.foodToRating.set(foods[i], ratings[i])

        const cuisine = cuisines[i]
        if(!this.cuisineToQueue.has(cuisine)) {
            this.cuisineToQueue.set(cuisine, new PriorityQueue((a, b) => {
                if (a[0] !== b[0]) return b[0] - a[0];
                return a[1].localeCompare(b[1]);
            }))
        }
        this.cuisineToQueue.get(cuisine).enqueue([ratings[i], foods[i]])
    }
};

/** 
 * @param {string} food 
 * @param {number} newRating
 * @return {void}
 */
FoodRatings.prototype.changeRating = function (food, newRating) {
    this.foodToRating.set(food, newRating)
    const cuisine = this.foodTocuisine.get(food)
    this.cuisineToQueue.get(cuisine).enqueue([newRating, food])
};

/** 
 * @param {string} cuisine
 * @return {string}
 */
FoodRatings.prototype.highestRated = function (cuisine) {
    const queue = this.cuisineToQueue.get(cuisine)

    while(!queue.isEmpty()){
        const [rating, food] = queue.front()
        if(rating === this.foodToRating.get(food)) {
            return food
        }
        queue.dequeue()
    }
    return ''
};