• 【LeetCode题目详解】银联-02. 优惠活动系统（c++和python3）

    目录

    题目：

    c++解法：

    题意

    思路

    代码

    代码详解：

    python3解法：

    算法描述：

    代码：

    代码详解：

    题目：

    「云闪付」作为各方联手打造的全新移动端统一入口，致力成为消费者省钱省心的移动支付管家。
    请你设计一个「云闪付」优惠活动管理系统 DiscountSystem，具体功能如下：

    • AddActivity(int actId, int priceLimit, int discount, int number, int userLimit) -- 表示创建编号为 actId 的优惠减免活动：

      • 单笔消费的原价不小于 priceLimit 时，可享受 discount 的减免
      • 每个用户最多参与该优惠活动 userLimit 次
      • 该优惠活动共有 number 数量的参加名额

    • RemoveActivity(actId) -- 表示结束编号为 actId 的优惠活动

    • Consume(int userId, int cost) -- 表示用户 userId 产生了一笔原价为 cost 的消费。请返回用户的实际支付金额。

      • 单次消费最多可参加一份优惠活动
      • 若可享受优惠减免，则 「支付金额 = 原价 - 优惠减免」
      • 若同时满足多个优惠活动时，则优先参加优惠减免最大的活动

      注：若有多个优惠减免最大的活动，优先参加 actId 最小的活动

    注意：

    • actId 全局唯一

    示例 1：

    输入：
    ["DiscountSystem","addActivity","consume","removeActivity","consume"]
    [[],[1,15,5,7,2],[101,16],[1],[102,19]]

    输出：[null,null,11,null,19]

    解释：
    DiscountSystem obj = DiscountSystem(); // 初始化系统
    obj.addActicity(1,15,5,7,2); //创建编号 1 的优惠活动，单笔消费原价不小于 15 时，
    可享受 5 的减免，优惠活动共有 7 个名额，每个用户最多参与该活动 2 次
    obj.consume(101,16); //用户 101 消费了 16，满足优惠活动 1 条件，返回实际支付 16 - 5 = 11
    obj.removeActivity(1); // 结束编号为 1 的优惠活动
    obj.consume(102,19); //用户 101 消费了 19，目前不存在任何优惠活动，需按原价支付，返回 19

    示例 2：

    输入：
    ["DiscountSystem","addActivity","addActivity","consume","removeActivity","consume","consume","consume","consume"]
    [[],[1,10,6,3,2],[2,15,8,8,2],[101,13],[2],[101,17],[101,11],[102,16],[102,21]]

    输出：[null,null,null,7,null,11,11,10,21]

    解释：
    DiscountSystem obj = DiscountSystem(); // 初始化系统
    obj.addActivity(1,10,6,3,2); // 创建编号 1 的优惠活动，单笔消费原价不小于 10 时，
    可享受 6 的减免，优惠活动共有 3 个名额，每个用户最多参与该活动 2 次
    obj.addActivity(2,15,8,8,2); // 创建编号 2 的优惠活动，单笔消费原价不小于 15 时，
    可享受 8 的减免，优惠活动共有 8 个名额，每个用户最多参与该活动 2 次
    obj.consume(101,13); // 用户 101 消费了 13，仅满足优惠活动 1 条件，返回实际支付 13 - 6 = 7
    用户 101 参加 1 次活动 1，活动 1 剩余 2 个名额
    obj.consume(101,8); // 用户 101 消费了 8，不满足任何活动，返回支付原价 8
    obj.removeActivity(2); // 结束编号为 2 的活动
    obj.consume(101,17); // 用户 101 消费了 17，满足优惠活动 1 条件，返回实际支付 17 - 6 = 11
    用户 101 参加 2 次活动 1，活动 1 剩余 1 个名额
    obj.consume(101,11); // 用户 101 消费了 11，满足优惠活动 1 条件，但已达到参加次数限制，返回支付原价 11
    obj.consume(102,16); // 用户 102 消费了 16，满足优惠活动 1 条件，返回实际支付 16 - 6 = 10
    用户 102 参加 1 次活动 1，活动 1 无剩余名额
    obj.consume(102,21); // 用户 102 消费了 21，满足优惠活动 1 条件，但活动 1 已无剩余名额，返回支付原价 21

    提示：

    • 1 <= addActicity, removeActivity, consume 累计操作数 <= 10^3
    • 0 <= actId, userId <= 1000
    • 1 <= discount < priceLimit <= 10^5
    • 1 <= cost <= 10^5
    • 1 <= number <= 1000
    • 1 <= userLimit <= 10

    c++解法：

    题意

    哈希表

    思路

    1. 题目本身只是考察设计与数据结构，实际的解法肯定许多种。我们设计一个数据结构来存储每个Activity的信息，分别存储：
    • priceLimit: 允许折扣的价格
    • int discount: 折扣的金额
    • number: 当前还剩余多少个名额
    • userLimit: 每个用户的优惠限制次数
    • record: 记录每个用户已经使用的优惠的次数。
    1. 分别对每个API进行操作：
    • addActivity: 生成一个新的Activity即可。
    • removeActivity：从列表中将去删除即可。
    • consume：这部稍微复杂点，首先找到最大可能的优惠，满足的前提是当前priceLimit >= cost,number > 0, record[userid] < userLimit，满足以上三个条件就记录下该Activity的id以及优惠。 找到最大的优惠后，对应Activity信息更新，主要涉及到number与record的更新即可。
    1. 复杂度分析：
    • 时间复杂度：

    , addActivity与removeActivity均为 , consume为,其中

    • 为Activity的数量。
    • 空间复杂度：
    • ,
      • 为Activity的数量。

      代码

      1. struct Activity {
      2.     int priceLimit;
      3.     int discount;
      4.     int number;
      5.     int userLimit;
      6.     unordered_map<int, int> record;
      7.     Activity(int priceLimit, int discount, int number, int userLimit){
      8.         this->priceLimit = priceLimit;
      9.         this->discount = discount;
      10.         this->number = number;
      11.         this->userLimit = userLimit;
      12.     }
      13. };
      14.  
      15. class DiscountSystem {
      16. private:
      17.     map<int, Activity *> cnt;
      18. public:
      19.     DiscountSystem() {
      20.         
      21.     }
      22.     
      23.     void addActivity(int actId, int priceLimit, int discount, int number, int userLimit) {
      24.         cnt[actId] = new Activity(priceLimit, discount, number, userLimit);
      25.     }
      26.     
      27.     void removeActivity(int actId) {
      28.         cnt.erase(actId);
      29.     }
      30.     
      31.     int consume(int userId, int cost) {
      32.         int maxdiscount = 0;
      33.         int id = -1;
      34.         for(auto &[actId, pAct]: cnt) {
      35.             if(cost >= pAct->priceLimit) {
      36.                 if(pAct->discount > maxdiscount && pAct->number > 0) {
      37.                     if(pAct->record.count(userId)){
      38.                         if(pAct->record[userId] < pAct->userLimit){
      39.                             maxdiscount = pAct->discount;
      40.                             id = actId;
      41.                         }
      42.                     }else{
      43.                         maxdiscount = pAct->discount;
      44.                         id = actId;
      45.                     }
      46.                 }
      47.             }
      48.         }
      49.         if(id >= 0){
      50.             cnt[id]->record[userId]++;
      51.             cnt[id]->number--;
      52.         }
      53.         return cost - maxdiscount;
      54.     }
      55. };

    代码详解：

    这段C++代码定义了两类，Activity 和 DiscountSystem，并提供了与折扣活动和消费相关的功能。让我逐个部分详细解释：

    1. struct Activity {
    2.     int priceLimit;
    3.     int discount;
    4.     int number;
    5.     int userLimit;
    6.     unordered_map<int, int> record;
    7.  
    8.     Activity(int priceLimit, int discount, int number, int userLimit) {
    9.         this->priceLimit = priceLimit;
    10.         this->discount = discount;
    11.         this->number = number;
    12.         this->userLimit = userLimit;
    13.     }
    14. };

    1. Activity 结构体：这个结构体表示一个折扣活动。它包括了以下成员变量：

      • priceLimit：价格限制，用户的消费金额必须达到或超过此限制才能参与活动。
      • discount：折扣金额，表示用户在参与活动时可以获得的折扣金额。
      • number：剩余活动数量，表示这个活动还剩下多少个名额。
      • userLimit：用户参与次数限制，表示一个用户最多可以参与活动的次数。
      • record：使用无序映射（unordered_map）记录每个用户参与活动的次数。

    2. Activity 结构体的构造函数：构造函数用于初始化 Activity 对象的各个成员变量。在对象创建时，将传入的参数值分配给相应的成员变量。

    1. class DiscountSystem {
    2. private:
    3.     map<int, Activity *> cnt;
    4.  
    5. public:
    6.     DiscountSystem() {
    7.     }
    8.  
    9.     void addActivity(int actId, int priceLimit, int discount, int number, int userLimit) {
    10.         cnt[actId] = new Activity(priceLimit, discount, number, userLimit);
    11.     }
    12.  
    13.     void removeActivity(int actId) {
    14.         cnt.erase(actId);
    15.     }
    16.  
    17.     int consume(int userId, int cost) {
    18.         int maxdiscount = 0;
    19.         int id = -1;
    20.         for (auto &[actId, pAct] : cnt) {
    21.             if (cost >= pAct->priceLimit) {
    22.                 if (pAct->discount > maxdiscount && pAct->number > 0) {
    23.                     if (pAct->record.count(userId)) {
    24.                         if (pAct->record[userId] < pAct->userLimit) {
    25.                             maxdiscount = pAct->discount;
    26.                             id = actId;
    27.                         }
    28.                     } else {
    29.                         maxdiscount = pAct->discount;
    30.                         id = actId;
    31.                     }
    32.                 }
    33.             }
    34.         }
    35.         if (id >= 0) {
    36.             pAct->record[userId]++;
    37.             pAct->number--;
    38.         }
    39.         return cost - maxdiscount;
    40.     }
    41. };

    1. DiscountSystem 类：这个类用于管理折扣活动和消费的主要功能。它包括以下成员变量和方法：

      • cnt：使用 map 存储不同折扣活动的信息，每个活动由一个唯一的 actId 标识，并关联到相应的 Activity 对象指针。

    2. DiscountSystem 类的构造函数：构造函数为空，表示在创建 DiscountSystem 对象时不需要额外的初始化操作。

    3. addActivity 方法：这个方法用于添加新的折扣活动。它接受 actId 以及与该活动相关的 priceLimit、discount、number 和 userLimit。在内部，它创建一个新的 Activity 对象，并将其与 actId 关联，然后将该关联添加到 cnt 中。

    4. removeActivity 方法：这个方法用于移除指定的折扣活动。它接受一个 actId 参数，然后在 cnt 中查找并删除与该 actId 相关的 Activity 对象。

    5. consume 方法：这是核心的消费方法。它接受 userId 和 cost 作为参数，用于模拟用户的消费操作并计算折扣。以下是详细解释：

      • 初始化 maxdiscount 和 id，分别用于跟踪用户能够获得的最大折扣金额和适用的活动标识。
      • 使用 for 循环遍历 cnt 中的活动，其中 auto &[actId, pAct] 允许同时迭代活动的标识和对应的 Activity 对象指针。
      • 在迭代过程中，检查用户的消费是否达到当前活动的价格限制。
      • 如果达到价格限制，进一步检查当前活动的折扣是否大于已记录的最大折扣，以及该活动的剩余数量是否大于0。
      • 如果满足这些条件，再检查用户是否已经参加了该活动，以及是否已达到参与次数的限制。
      • 如果找到适用的活动，更新 maxdiscount 和 id。
      • 如果找到了适用的活动（id >= 0），则更新相应的 Activity 对象的记录和剩余数量，并返回用户实际支付的金额（原始消费减去最大折扣）

    python3解法：

    算法描述：

    代码建立了两个类：Activity和DiscountSystem，用于管理优惠活动和消费记录。

    Activity 类:

    这个类代表了一个优惠活动。它的构造函数 __init__ 接受四个参数：priceLimit（价格限制）、discount（折扣）、number（活动数量）、和 userLimit（用户限制）。

    这些参数分别表示：活动的价格限制（只有当消费满足该限制时才能参加活动）、折扣金额、活动的剩余数量、和每个用户可参加活动的次数。

    record 字典用于跟踪每个用户参加活动的次数。

    DiscountSystem 类:

    这个类用于管理多个不同的优惠活动。它的构造函数 __init__ 初始化一个空的 activities 字典，用于存储活动的信息。

    addActivity 方法:

    这个方法用于向 DiscountSystem 中添加新的优惠活动。

    它接受 actId（活动的唯一标识符）以及与该活动相关的 priceLimit、discount、number 和 userLimit。

    通过调用 Activity 的构造函数创建一个新的活动对象，并将其存储在 activities 字典中。

    removeActivity 方法:

    这个方法用于从 DiscountSystem 中删除特定的优惠活动，通过提供 actId 来指定要删除的活动。

    consume 方法:

    这个方法用于用户消费时查找适用于用户的最大折扣。

    它接受 userId（用户标识符）和 cost（消费金额）作为参数。

    方法遍历 activities 字典，查找用户满足价格限制的活动，然后比较这些活动的折扣和用户的历史参加次数，以确定用户可以享受的最大折扣。

    如果找到适用的活动，它会更新 Activity 对象的 record 和 number 字段，并返回最终消费金额减去折扣金额。

    总之，这个代码演示了一个优惠活动管理系统，用户可以通过 DiscountSystem 添加和删除不同的活动，然后在消费时根据条件享受相应的折扣。活动的参与次数和剩余数量也得到了跟踪。

    时间复杂度分析：

    这个系统的时间复杂度主要受到两个因素的影响：

    添加活动 (addActivity)：这是一个O(1)的操作，因为它只涉及将新活动添加到字典中。

    用户消费 (consume)：在最坏情况下，需要遍历所有活动，所以它的时间复杂度是O(n)，其中n是活动的数量。

    代码：

    1. class Activity:
    2.     def __init__(self, priceLimit, discount, number, userLimit):
    3.         self.priceLimit = priceLimit
    4.         self.discount = discount
    5.         self.number = number
    6.         self.userLimit = userLimit
    7.         self.record = {}
    8.  
    9. class DiscountSystem:
    10.     def __init__(self):
    11.         self.activities = {}
    12.  
    13.     def addActivity(self, actId, priceLimit, discount, number, userLimit):
    14.         self.activities[actId] = Activity(priceLimit, discount, number, userLimit)
    15.  
    16.     def removeActivity(self, actId):
    17.         del self.activities[actId]
    18.  
    19.     def consume(self, userId, cost):
    20.         maxdiscount = 0
    21.         id = -1
    22.         for actId, pAct in self.activities.items():
    23.             if cost >= pAct.priceLimit:
    24.                 if pAct.discount > maxdiscount and pAct.number > 0:
    25.                     if userId in pAct.record:
    26.                         if pAct.record[userId] < pAct.userLimit:
    27.                             maxdiscount = pAct.discount
    28.                             id = actId
    29.                     else:
    30.                         maxdiscount = pAct.discount
    31.                         id = actId
    32.         if id >= 0:
    33.             self.activities[id].record[userId] = self.activities[id].record.get(userId, 0) + 1
    34.             self.activities[id].number -= 1
    35.         return cost - maxdiscount

    代码详解：

    1. class Activity:
    2.     def __init__(self, priceLimit, discount, number, userLimit):
    3.         self.priceLimit = priceLimit
    4.         self.discount = discount
    5.         self.number = number
    6.         self.userLimit = userLimit
    7.         self.record = {}

    这部分定义了 Activity 类。这个类有一个构造函数 __init__，它接受四个参数：priceLimit、discount、number 和 userLimit。这些参数代表了活动的价格限制、折扣、剩余数量和用户限制。同时，创建了一个空字典 record 用于跟踪用户参与活动的次数。

    1. class DiscountSystem:
    2.     def __init__(self):
    3.         self.activities = {}

    在这里，定义了 DiscountSystem 类，它包含一个构造函数 __init__，该构造函数初始化一个空的字典 activities，用于存储不同活动的信息。

    1.     def addActivity(self, actId, priceLimit, discount, number, userLimit):
    2.         self.activities[actId] = Activity(priceLimit, discount, number, userLimit)

    这是 DiscountSystem 类的一个方法，addActivity。它接受 actId（活动的唯一标识符）以及与该活动相关的 priceLimit、discount、number 和 userLimit。方法的作用是将一个新的 Activity 对象添加到 activities 字典中，使用 actId 作为键。

    1.     def removeActivity(self, actId):
    2.         del self.activities[actId]

    这是 DiscountSystem 类的另一个方法，removeActivity。它接受 actId 作为参数，用于从 activities 字典中删除指定的活动。

    1.     def consume(self, userId, cost):
    2.         maxdiscount = 0
    3.         id = -1
    4.         for actId, pAct in self.activities.items():
    5.             if cost >= pAct.priceLimit:
    6.                 if pAct.discount > maxdiscount and pAct.number > 0:
    7.                     if userId in pAct.record:
    8.                         if pAct.record[userId] < pAct.userLimit:
    9.                             maxdiscount = pAct.discount
    10.                             id = actId
    11.                     else:
    12.                         maxdiscount = pAct.discount
    13.                         id = actId
    14.         if id >= 0:
    15.             self.activities[id].record[userId] = self.activities[id].record.get(userId, 0) + 1
    16.             self.activities[id].number -= 1
    17.         return cost - maxdiscount

    1. maxdiscount 和 id 的初始化：

      • maxdiscount 用于跟踪用户可以享受的最大折扣金额。初始值设为0。
      • id 用于记录适用于用户的活动的标识符。初始值设为-1，表示未找到适用的活动。

    2. 迭代活动：

      • for actId, pAct in self.activities.items(): 这一行开始迭代 activities 字典中的每个活动。
      • actId 是活动的唯一标识符，pAct 是与该标识符相关联的 Activity 对象。

    3. 检查价格限制：

      • if cost >= pAct.priceLimit: 这一行检查用户的消费金额是否达到了当前活动的价格限制。只有当消费满足价格限制时，才会考虑这个活动。

    4. 检查折扣和剩余数量：

      • if pAct.discount > maxdiscount and pAct.number > 0: 这一行检查当前活动的折扣是否大于已经记录的最大折扣（maxdiscount），并且该活动的剩余数量（number）是否大于0。
      • 如果这个活动满足条件，将进一步检查用户是否符合参加活动的条件。

    5. 检查用户记录：

      • if userId in pAct.record: 这一行检查用户是否在当前活动的记录中。如果用户之前参加过该活动，就需要检查用户是否达到了参加活动的次数限制。
      • if pAct.record[userId] < pAct.userLimit: 如果用户的参与次数未达到限制，将更新 maxdiscount 为该活动的折扣金额，并将 id 设置为当前活动的标识符。

    6. 用户未在记录中的情况：

      • 如果用户不在当前活动的记录中，也会将 maxdiscount 设置为该活动的折扣金额，并将 id 设置为当前活动的标识符。

    7. 应用折扣和更新记录：

      • 如果 id 大于等于0，表示找到了适用的活动，将会执行以下步骤：
        • 更新 Activity 对象的 record 字典，将用户标识符 userId 对应的值加1，表示用户参加了该活动。
        • 减少活动的剩余数量 number，表示一个用户参加了该活动，活动的可用数量减少了一个。
      • 最后，方法返回用户的消费金额减去最大折扣金额，即用户实际支付的金额。

    这个方法的主要目的是在用户消费时，查找适用于用户的最大折扣活动，然后更新活动记录和剩余数量，最后计算用户实际支付的金额。这使得系统能够管理不同的优惠活动，确保用户获得适用的折扣。

  • 相关阅读:
    Linux安装mysql5.7
    WGAN（1）——为什么不能直接拟合原始分布Pr
    博客系统（升级（Spring））(二)获取当前用户信息、对密码进行加密、设置统一数据格式、设置未登录拦截、线程池
    redis-设置从节点
    机器学习强基计划4-4：详解半朴素贝叶斯分类AODE原理(附Python实现)
    瓦尔纳宝典读后感
    電子郵件IMAP、POP、SMTP 、 應該使用什麼端口
    【博客494】K8s TLS Bootstrap机制
    活动推广的作用有哪些呢？
    mybatis 10: 动态sql --- part2
  • 原文地址：https://blog.csdn.net/weixin_67972246/article/details/133876382