算法题记录 17

2353.设计食物评分系统（1782）

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

修改 系统中列出的某种食物的评分。
返回系统中某一类烹饪方式下评分最高的食物。
实现 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] 之前。

涉及知识点

哈希表

解决思路

比较简单的构造题，熟悉哈希表的创建和排序SortedList即可。

class FoodRatings:

    def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
        self.food_map={}
        self.cuisine_map=defaultdict(SortedList)
        for food,cuisine,rating in zip(foods,cuisines,ratings):
            self.food_map[food]=[rating,cuisine]
            self.cuisine_map[cuisine].add((-rating,food))

    def changeRating(self, food: str, newRating: int) -> None:
        rating,cuisine=self.food_map[food]
        sl=self.cuisine_map[cuisine]
        sl.discard((-rating,food))
        sl.add((-newRating,food))
        self.food_map[food][0]=newRating

    def highestRated(self, cuisine: str) -> str:
        return self.cuisine_map[cuisine][0][1]

2412.完成所有交易的初始最少钱数（2092）

给你一个下标从 0 开始的二维整数数组 transactions，其中transactions[i] = [costi, cashbacki] 。

数组描述了若干笔交易。其中每笔交易必须以 某种顺序 恰好完成一次。在任意一个时刻，你有一定数目的钱 money ，为了完成交易 i ，money >= costi 这个条件必须为真。执行交易后，你的钱数 money 变成 money - costi + cashbacki 。

请你返回 任意一种 交易顺序下，你都能完成所有交易的最少钱数 money 是多少。

涉及知识点

贪心

解决思路

注意题目所求：任意一种交易顺序下都能完成交易。这意味着贪心是可能的，找到最坏情况即可。最坏情况为：先亏，把所有会亏的交易都做了，然后再去找cost需求最大的盈利的交易。如果此时仍能进行交易，那么所有情况都能交易了。用数学列个不等式即可找到最小值money

class Solution:
    def minimumMoney(self, transactions: List[List[int]]) -> int:
        total_lose = mx = 0
        for cost, cashback in transactions:
            total_lose += max(cost - cashback, 0)
            mx = max(mx, min(cost, cashback))
        return total_lose + mx

2931.购买物品的最大开销（1822）

给你一个下标从 0 开始大小为 m * n 的整数矩阵 values ，表示 m 个不同商店里 m * n 件不同的物品。每个商店有 n 件物品，第 i 个商店的第 j 件物品的价值为 values[i][j] 。除此以外，第 i 个商店的物品已经按照价值非递增排好序了，也就是说对于所有 0 <= j < n - 1 都有 values[i][j] >= values[i][j + 1] 。

每一天，你可以在一个商店里购买一件物品。具体来说，在第 d 天，你可以：

选择商店 i 。
购买数组中最右边的物品 j ，开销为 values[i][j] * d 。换句话说，选择该商店中还没购买过的物品中最大的下标 j ，并且花费 values[i][j] * d 去购买。
注意，所有物品都视为不同的物品。比方说如果你已经从商店 1 购买了物品 0 ，你还可以在别的商店里购买其他商店的物品 0 。

请你返回购买所有 m * n 件物品需要的 最大开销 。

涉及知识点

贪心

解决思路

最小的都在每行的最后一列，我们从小到大取数就可以了，所以可以直接把二维数组展平成一维的，从小到大排列累计加和即可。

class Solution:
    def maxSpending(self, values: List[List[int]]) -> int:
        a = sorted(x for row in values for x in row)
        return sum(x * i for i, x in enumerate(a, 1))

声明

题目均来源于leetcode公开题库，部分方法解析来源于高赞题解，如有不妥请联系。