LeetCode 1357：电商折扣系统的设计与实现

1. 问题背景与需求分析

1357. Apply Discount Every n Orders 是 LeetCode 平台上的一道中等难度题目，属于设计类问题。这类问题在实际电商系统开发中非常常见，特别是在会员体系、促销活动等场景下。

题目要求我们设计一个 Cashier 类，需要实现以下核心功能：

• 记录顾客消费的订单数量
• 每当第 n 个顾客到来时，对其账单应用特定折扣
• 能够正确处理商品价格查询和账单计算

这类问题的难点不在于算法复杂度，而在于：

1. 状态维护的准确性（订单计数）
2. 边界条件的处理（计数重置）
3. 计算过程的效率（避免重复计算）

2. 类设计与接口规划

2.1 数据结构选择

我们需要维护几个关键数据：

• 商品价格映射表：使用 unordered_map 存储，保证 O(1) 的查询效率
• 订单计数器：整数类型，记录当前顾客序号
• 折扣周期 n 和折扣率 discount：在构造函数中初始化

class Cashier { private: unordered_map<int, int> priceMap; int customerCount; int discountInterval; double discountRate; public: Cashier(int n, int discount, vector<int>& products, vector<int>& prices) { // 初始化代码 } double getBill(vector<int> product, vector<int> amount) { // 计算账单代码 } };

2.2 接口设计要点

构造函数需要处理：

1. 折扣参数初始化
2. 商品价格表的建立
3. 计数器归零

getBill 方法需要：

1. 正确处理商品和数量的对应关系
2. 准确计算总价
3. 在适当时机应用折扣
4. 更新顾客计数

3. 核心算法实现

3.1 账单计算流程

账单计算的核心步骤如下：

1. 遍历 product 和 amount 数组
2. 查询每个商品的价格
3. 计算商品总价 = 单价 × 数量
4. 累加所有商品总价得到原始账单
5. 检查是否满足折扣条件
6. 应用折扣（如果需要）

double getBill(vector<int> product, vector<int> amount) { double total = 0.0; for(int i = 0; i < product.size(); ++i) { total += priceMap[product[i]] * amount[i]; } customerCount++; if(customerCount % discountInterval == 0) { total *= (1 - discountRate / 100.0); customerCount = 0; // 重置计数器 } return total; }

3.2 性能优化考虑

虽然题目数据规模不大，但实际工程中我们可以优化：

1. 使用 const reference 传递参数避免拷贝
2. 预先计算折扣系数（1 - discount/100）避免重复计算
3. 使用位运算代替模运算（当n是2的幂时）

4. 边界条件与测试用例

4.1 关键边界情况

需要特别注意以下场景：

1. 第一个顾客就是第n个顾客（n=1）
2. 商品列表为空的情况
3. 折扣率为0的情况
4. n=0 的非法输入处理（题目保证n>0）

4.2 测试用例设计

建议自测用例：

// 用例1：基本功能测试 products = [1,2,3,4,5,6,7], prices = [100,200,300,400,300,200,100] cashier = Cashier(3, 50, products, prices) assert(cashier.getBill([1,2],[1,2]) == 500) // 无折扣 assert(cashier.getBill([3,7],[10,10]) == 4000) // 无折扣 assert(cashier.getBill([1,2,3,4,5,6,7],[1,1,1,1,1,1,1]) == 800) // 应用50%折扣 // 用例2：边界条件测试 cashier = Cashier(1, 100, products, prices) // 每个顾客都打折 assert(cashier.getBill([1],[1]) == 0) // 100%折扣

5. 实际工程应用扩展

5.1 电商系统中的折扣策略

在实际电商系统中，折扣策略通常更复杂：

1. 多级折扣（不同商品不同折扣）
2. 组合优惠（满减、赠品等）
3. 会员专属折扣
4. 限时折扣

5.2 并发环境下的处理

如果系统需要支持高并发：

1. 使用原子操作维护计数器
2. 考虑分布式计数器（Redis等）
3. 添加适当的锁机制

5.3 折扣策略模式

可以采用策略模式实现多种折扣方式：

class DiscountStrategy { public: virtual double applyDiscount(double original) = 0; }; class PercentageDiscount : public DiscountStrategy { double rate; public: PercentageDiscount(double r) : rate(r) {} double applyDiscount(double original) override { return original * (1 - rate); } }; // 在Cashier类中使用策略接口

6. 常见错误与调试技巧

6.1 典型错误模式

1. 计数器未正确重置：

// 错误示例 if(customerCount % n == 0) { applyDiscount(); // 忘记重置customerCount }

2. 折扣计算错误：

// 错误示例 total *= discountRate; // 应该是 (1 - discountRate)

3. 商品价格查询越界：

// 不安全访问 total += prices[product[i]] * amount[i]; // 应该用map查询

6.2 调试建议

1. 打印中间变量：

cout << "Customer: " << customerCount << ", Total: " << total << endl;

2. 单元测试覆盖所有边界条件

3. 使用调试器逐步执行验证计数器变化

7. 算法复杂度分析

7.1 时间复杂度

• 构造函数：O(m)，m是商品数量（构建价格表）
• getBill：O(k)，k是账单中商品种类数

7.2 空间复杂度

• O(m) 存储商品价格表
• O(1) 额外空间用于计数器等变量

8. 不同语言实现差异

8.1 Java实现要点

class Cashier { private Map<Integer, Integer> priceMap; private int count; private int n; private double discount; public Cashier(int n, int discount, int[] products, int[] prices) { this.priceMap = new HashMap<>(); for(int i = 0; i < products.length; i++) { priceMap.put(products[i], prices[i]); } this.n = n; this.discount = discount; } public double getBill(int[] product, int[] amount) { double total = 0; for(int i = 0; i < product.length; i++) { total += priceMap.get(product[i]) * amount[i]; } if(++count % n == 0) { total *= (100 - discount) / 100; count = 0; } return total; } }

8.2 Python实现特点

class Cashier: def __init__(self, n: int, discount: int, products: List[int], prices: List[int]): self.price_dict = {p: prices[i] for i, p in enumerate(products)} self.n = n self.discount = discount self.count = 0 def getBill(self, product: List[int], amount: List[int]) -> float: total = sum(self.price_dict[p] * a for p, a in zip(product, amount)) self.count += 1 if self.count % self.n == 0: total *= (100 - self.discount) / 100 self.count = 0 return total

9. 实际业务场景思考

9.1 超市收银系统

在真实超市系统中：

1. 折扣可能基于累计消费金额而非订单数
2. 需要考虑税费计算
3. 可能需要处理退货场景

9.2 线上电商平台

电商平台额外考虑：

1. 优惠券叠加规则
2. 运费计算
3. 积分抵扣

9.3 会员体系集成

高级实现可能包含：

1. 会员等级折扣
2. 生日特权
3. 消费积分

10. 代码优化与重构

10.1 可读性优化

1. 提取折扣应用为独立方法：

private: double applyDiscount(double total) { return total * (1 - discountRate / 100.0); }

2. 使用有意义的变量名：

int currentCustomerCount; // 比 customerCount 更明确

10.2 性能优化

1. 预先计算折扣系数：

double discountFactor; // 在构造函数中计算

2. 使用reserve优化map：

priceMap.reserve(products.size());

10.3 异常处理

添加基本错误检查：

if(product.size() != amount.size()) { throw invalid_argument("product and amount size mismatch"); }

11. 单元测试实践

11.1 测试框架选择

根据语言选择测试框架：

• C++: Google Test
• Java: JUnit
• Python: unittest/pytest

11.2 测试用例设计原则

1. 正常流程测试
2. 边界条件测试
3. 异常输入测试
4. 性能测试（大数据量）

11.3 测试示例(Google Test)

TEST(CashierTest, BasicDiscount) { vector<int> products = {1,2,3}; vector<int> prices = {100,200,300}; Cashier cashier(2, 50, products, prices); EXPECT_DOUBLE_EQ(100, cashier.getBill({1},{1})); EXPECT_DOUBLE_EQ(100, cashier.getBill({1},{1})); // 50% discount EXPECT_DOUBLE_EQ(200, cashier.getBill({2},{1})); }

12. 相关算法题目推荐

1. 设计停车系统（LeetCode 1603）
2. 设计浏览器历史记录（LeetCode 1472）
3. 设计哈希集合（LeetCode 705）
4. 设计推特（LeetCode 355）

这些题目都考察面向对象设计和状态维护能力，是很好的补充练习。

13. 面试考察要点

面试中遇到此类问题，面试官通常会考察：

1. 面向对象设计能力
2. 边界条件处理
3. 代码整洁度
4. 测试用例设计
5. 扩展性思考

建议在实现基本功能后，主动讨论：

• 如何支持更多折扣类型
• 并发环境下的处理
• 大数据量下的优化

14. 个人实现心得

在实际实现过程中，有几个关键点值得注意：

1. 计数器更新时机：应该在计算总价后更新，而不是之前，避免逻辑错误

2. 浮点数精度：商业计算中要考虑使用定点数或高精度库，避免浮点误差累积

3. 线程安全：虽然题目不要求，但实际工程中要考虑多线程访问问题

4. 折扣应用顺序：在复杂系统中，折扣应用顺序可能影响最终价格，需要明确规则

5. 日志记录：重要的价格变动应该记录日志，便于后续对账和审计