Medium

题目描述

有一个超市，经常有许多顾客光顾。超市销售的产品用两个平行的整数数组 products 和 prices 表示，其中第 i 个产品的 ID 为 products[i]，价格为 prices[i]。

当顾客付款时，他们的账单用两个平行的整数数组 product 和 amount 表示，其中第 j 个产品的 ID 为 product[j]，购买数量为 amount[j]。小计按每个 amount[j] * (第 j 个产品的价格) 的总和计算。

超市决定进行促销活动。每第 n 个付款的顾客将获得百分比折扣。折扣金额由 discount 给出，他们将获得小计的 discount 百分比折扣。更正式地说，如果他们的小计是 bill，那么他们实际支付 bill * ((100 - discount) / 100)。

实现 Cashier 类：

  • Cashier(int n, int discount, int[] products, int[] prices) 用 n、折扣和产品及其价格初始化对象。
  • 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]

约束条件：

  • 1 <= n <= 10^4
  • 0 <= discount <= 100
  • 1 <= products.length <= 200
  • prices.length == products.length
  • 1 <= products[i] <= 200
  • 1 <= prices[i] <= 1000
  • products 中的元素是唯一的
  • 1 <= product.length <= products.length
  • amount.length == product.length
  • product[j] 存在于 products 中
  • 1 <= amount[j] <= 1000
  • product 的元素是唯一的
  • 最多调用 getBill 1000 次
  • 与实际值相差 10^-5 以内的答案将被接受

解题思路

这是一个设计类问题，需要实现一个收银台系统。

核心思路：

  1. 初始化阶段：使用哈希表存储商品ID到价格的映射关系，便于快速查找商品价格。同时记录折扣间隔n、折扣百分比discount，以及当前顾客计数。

  2. 计算账单：每次调用getBill时，先计算原始账单总额，然后判断当前顾客是否应该享受折扣。关键是维护顾客计数器，每次计算完账单后递增。

  3. 折扣逻辑：如果当前顾客编号能被n整除，则应用折扣公式：原价 * (100 - discount) / 100。

实现细节：

  • 使用HashMap/unordered_map存储商品价格映射
  • 维护一个计数器跟踪顾客数量
  • 每次getBill调用都要先递增计数器再判断是否折扣
  • 注意折扣计算的精度要求

这种设计的时间复杂度主要取决于每次账单中商品的数量，空间复杂度为O(商品总数)。

代码实现

class Cashier {
private:
    int n, discount, customerCount;
    unordered_map<int, int> priceMap;
    
public:
    Cashier(int n, int discount, vector<int>& products, vector<int>& prices) {
        this->n = n;
        this->discount = discount;
        this->customerCount = 0;
        
        for (int i = 0; i < products.size(); i++) {
            priceMap[products[i]] = prices[i];
        }
    }
    
    double getBill(vector<int> product, vector<int> amount) {
        customerCount++;
        
        double total = 0.0;
        for (int i = 0; i < product.size(); i++) {
            total += amount[i] * priceMap[product[i]];
        }
        
        if (customerCount % n == 0) {
            total = total * (100 - discount) / 100.0;
        }
        
        return total;
    }
};

class Cashier:
    def __init__(self, n: int, discount: int, products: List[int], prices: List[int]):
        self.n = n
        self.discount = discount
        self.customer_count = 0
        self.price_map = {}
        
        for i in range(len(products)):
            self.price_map[products[i]] = prices[i]
    
    def getBill(self, product: List[int], amount: List[int]) -> float:
        self.customer_count += 1
        
        total = 0.0
        for i in range(len(product)):
            total += amount[i] * self.price_map[product[i]]
        
        if self.customer_count % self.n == 0:
            total = total * (100 - self.discount) / 100
        
        return total

public class Cashier {
    private int n, discount, customerCount;
    private Dictionary<int, int> priceMap;
    
    public Cashier(int n, int discount, int[] products, int[] prices) {
        this.n = n;
        this.discount = discount;
        this.customerCount = 0;
        this.priceMap = new Dictionary<int, int>();
        
        for (int i = 0; i < products.Length; i++) {
            priceMap[products[i]] = prices[i];
        }
    }
    
    public double GetBill(int[] product, int[] amount) {
        customerCount++;
        
        double total = 0.0;
        for (int i = 0; i < product.Length; i++) {
            total += amount[i] * priceMap[product[i]];
        }
        
        if (customerCount % n == 0) {
            total = total * (100 - discount) / 100.0;
        }
        
        return total;
    }
}

var Cashier = function(n, discount, products, prices) {
    this.n = n;
    this.discount = discount;
    this.priceMap = new Map();
    this.customerCount = 0;
    
    for (let i = 0; i < products.length; i++) {
        this.priceMap.set(products[i], prices[i]);
    }
};

Cashier.prototype.getBill = function(product, amount) {
    this.customerCount++;
    
    let bill = 0;
    for (let i = 0; i < product.length; i++) {
        bill += amount[i] * this.priceMap.get(product[i]);
    }
    
    if (this.customerCount % this.n === 0) {
        bill = bill * ((100 - this.discount) / 100);
    }
    
    return bill;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
初始化O(m)O(m)
getBillO(k)O(1)

其中：

  • m 为商品种类数量
  • k 为单次购买的商品种类数量

说明：

  • 初始化时需要遍历所有商品建立价格映射，时间复杂度O(m)，空间复杂度O(m)
  • getBill操作需要遍历当前购买的商品计算总价，时间复杂度O(k)，额外空间复杂度O(1)

相关题目