每隔 n 个顾客打折

标签: 设计 数组 哈希表

难度: Medium

超市里正在举行打折活动，每隔 n 个顾客会得到 discount 的折扣。

超市里有一些商品，第 i 种商品为 products[i] 且每件单品的价格为 prices[i] 。

结账系统会统计顾客的数目，每隔 n 个顾客结账时，该顾客的账单都会打折，折扣为 discount （也就是如果原本账单为 x ，那么实际金额会变成 x - (discount * x) / 100 ），然后系统会重新开始计数。

顾客会购买一些商品， product[i] 是顾客购买的第 i 种商品， amount[i] 是对应的购买该种商品的数目。

请你实现 Cashier 类：

  • Cashier(int n, int discount, int[] products, int[] prices) 初始化实例对象，参数分别为打折频率 n ，折扣大小 discount ，超市里的商品列表 products 和它们的价格 prices 。
  • double getBill(int[] product, int[] amount) 返回账单的实际金额（如果有打折，请返回打折后的结果）。返回结果与标准答案误差在 10^-5 以内都视为正确结果。

示例 1：

输入
["Cashier","getBill","getBill","getBill","getBill","getBill","getBill","getBill"]
[[3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]],[[1,2],[1,2]],[[3,7],[10,10]],[[1,2,3,4,5,6,7],[1,1,1,1,1,1,1]],[[4],[10]],[[7,3],[10,10]],[[7,5,3,1,6,4,2],[10,10,10,9,9,9,7]],[[2,3,5],[5,3,2]]]
输出
[null,500.0,4000.0,800.0,4000.0,4000.0,7350.0,2500.0]
解释
Cashier cashier = new Cashier(3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]);
cashier.getBill([1,2],[1,2]);                        // 返回 500.0, 账单金额为 = 1 * 100 + 2 * 200 = 500.
cashier.getBill([3,7],[10,10]);                      // 返回 4000.0
cashier.getBill([1,2,3,4,5,6,7],[1,1,1,1,1,1,1]);    // 返回 800.0 ，账单原本为 1600.0 ，但由于该顾客是第三位顾客，他将得到 50% 的折扣，所以实际金额为 1600 - 1600 * (50 / 100) = 800 。
cashier.getBill([4],[10]);                           // 返回 4000.0
cashier.getBill([7,3],[10,10]);                      // 返回 4000.0
cashier.getBill([7,5,3,1,6,4,2],[10,10,10,9,9,9,7]); // 返回 7350.0 ，账单原本为 14700.0 ，但由于系统计数再次达到三，该顾客将得到 50% 的折扣，实际金额为 7350.0 。
cashier.getBill([2,3,5],[5,3,2]);                    // 返回 2500.0

提示：

  • 1 <= n <= 10^4
  • 0 <= discount <= 100
  • 1 <= products.length <= 200
  • 1 <= products[i] <= 200
  • products 列表中 不会 有重复的元素。
  • prices.length == products.length
  • 1 <= prices[i] <= 1000
  • 1 <= product.length <= products.length
  • product[i] 在 products 出现过。
  • amount.length == product.length
  • 1 <= amount[i] <= 1000
  • 最多有 1000 次对 getBill 函数的调用。
  • 返回结果与标准答案误差在 10^-5 以内都视为正确结果。

Submission

运行时间: 92 ms

内存: 28.6 MB

class Cashier:
    def __init__(self, n: int, discount: int, products: List[int], prices: List[int]):
        self.n = n
        self.discount = discount
        self.products = products
        self.prices = prices
        self.customer_count = 0
        self.price_map = {product: price for product, price in zip(products, prices)}

    def getBill(self, product: List[int], amount: List[int]) -> float:
        total_bill = 0
        for prod, amt in zip(product, amount):
            total_bill += self.price_map[prod] * amt

        self.customer_count += 1
        if self.customer_count == self.n:
            total_bill -= (self.discount * total_bill) / 100
            self.customer_count = 0

        return total_bill

Explain

这个题解的思路是首先在构造函数中创建一个字典 price_map 将产品 ID 和其价格对应起来，以便快速查找每个产品的价格。然后，在 getBill 函数中，遍历顾客购买的每种产品和数量，计算总账单金额。如果顾客是每 n 个顾客之一，则给予折扣。折扣是通过将总账单金额减去其与折扣比例的乘积来计算的。最后，如果给予了折扣，则重置顾客计数器；否则，增加顾客计数器。

时间复杂度: O(m)

空间复杂度: O(p)

class Cashier:
    def __init__(self, n: int, discount: int, products: List[int], prices: List[int]):
        self.n = n  # 打折频率
        self.discount = discount  # 折扣大小
        self.products = products  # 商品列表
        self.prices = prices  # 商品价格列表
        self.customer_count = 0  # 顾客计数器
        self.price_map = {product: price for product, price in zip(products, prices)}  # 商品 ID 到价格的映射

    def getBill(self, product: List[int], amount: List[int]) -> float:
        total_bill = 0
        for prod, amt in zip(product, amount):  # 遍历顾客购买的每种产品和数量
            total_bill += self.price_map[prod] * amt  # 累加总账单金额

        self.customer_count += 1  # 增加顾客计数器
        if self.customer_count == self.n:  # 如果顾客是每 n 个顾客之一
            total_bill -= (self.discount * total_bill) / 100  # 给予折扣
            self.customer_count = 0  # 重置顾客计数器

        return total_bill  # 返回总账单金额

Explore

字典在Python中是基于哈希表实现的，可以提供平均时间复杂度为O(1)的快速查找功能。这对于getBill方法中需要频繁根据产品ID查询价格的操作是非常高效的。相比之下，如果使用列表或数组，我们需要遍历整个数据结构来查找价格，其时间复杂度为O(n)，效率较低。因此，字典是处理这种键值对映射关系的理想选择。

如果在getBill方法中遇到product数组中存在但不在price_map中的商品ID，这通常表示输入错误或商品数据不完整。一种处理方式是在尝试获取价格之前检查该商品ID是否存在于price_map中。如果不存在，可以选择抛出一个异常或返回一个错误信息，通知调用者该商品ID无效，或者忽略该商品ID并继续处理其他商品。具体的处理策略应根据实际业务需求和错误处理策略来确定。

顾客计数器的更新放在计算折扣之后是为了确保在计算当前顾客的账单时能正确判断其是否应该享受折扣。如果计数器在折扣计算前就更新，那么每到第n个顾客时，计数器已经被重置，这将导致第一个顾客（实际上是第n+1个顾客）被错误地视为应该打折的顾客。因此，先进行账单计算和折扣处理，然后再更新计数器，可以保证顾客和折扣的正确匹配。

是的，使用浮点数进行金钱计算可能会引入精度问题，因为浮点数在表示一些分数时可能不精确。为了避免这种问题，可以采用整数来表示所有的金额（例如以最小货币单位如分来计算），或者使用Python的decimal模块，它提供了更精确的十进制浮点运算。使用decimal可以有效防止因浮点数精度问题导致的计算误差，特别是在金钱交易处理中非常有用。