LeetCode 3606.优惠券校验器：分类 + 排序

【LetMeFly】3606.优惠券校验器：分类 + 排序

力扣题目链接：https://leetcode.cn/problems/coupon-code-validator/

给你三个长度为n的数组，分别描述n个优惠券的属性：code、businessLine和isActive。其中，第i个优惠券具有以下属性：

• code[i]：一个字符串，表示优惠券的标识符。
• businessLine[i]：一个字符串，表示优惠券所属的业务类别。
• isActive[i]：一个布尔值，表示优惠券是否当前有效。

当以下所有条件都满足时，优惠券被认为是有效的：

1. code[i]不能为空，并且仅由字母数字字符（a-z、A-Z、0-9）和下划线（_）组成。
2. businessLine[i]必须是以下四个类别之一："electronics"、"grocery"、"pharmacy"、"restaurant"。
3. isActive[i]为true。

返回所有有效优惠券的标识符组成的数组，按照以下规则排序：

• 先按照其businessLine的顺序排序："electronics"、"grocery"、"pharmacy"、"restaurant"。
• 在每个类别内，再按照标识符的字典序（升序）排序。

示例 1：

输入：code = ["SAVE20","","PHARMA5","SAVE@20"], businessLine = ["restaurant","grocery","pharmacy","restaurant"], isActive = [true,true,true,true]

输出：["PHARMA5","SAVE20"]

解释：

• 第一个优惠券有效。
• 第二个优惠券的标识符为空（无效）。
• 第三个优惠券有效。
• 第四个优惠券的标识符包含特殊字符@（无效）。

示例 2：

输入：code = ["GROCERY15","ELECTRONICS_50","DISCOUNT10"], businessLine = ["grocery","electronics","invalid"], isActive = [false,true,true]

输出：["ELECTRONICS_50"]

解释：

• 第一个优惠券无效，因为它未激活。
• 第二个优惠券有效。
• 第三个优惠券无效，因为其业务类别无效。

提示：

• n == code.length == businessLine.length == isActive.length
• 1 <= n <= 100
• 0 <= code[i].length, businessLine[i].length <= 100
• code[i]和businessLine[i]由可打印的 ASCII 字符组成。
• isActive[i]的值为true或false。

解题方法：分组 + 排序

分组/分类似乎差不多，暂不深究。

使用4个数组，分别存放合法的4类优惠券。最后对4个数组分别按字符串字典序排序，合并为一个数组并返回。

如何判断一个优惠券是否合法？

1. active为true
2. businessLine属于4类之一
3. code不为空且只由数组字母下划线组成

注意，C++中合并vector时若被合并vector后续无需再使用，则可以使用make_move_iterator在内存上移动。

• 时间复杂度O ( L log ⁡ n ) O(L\log n)O(Llogn)，其中L LL是合法code总字符数
• 空间复杂度：C++O ( L ) O(L)O(L)

AC代码

C++

/* * @LastEditTime: 2025-12-13 22:42:29 */classSolution{private:inlineboolis_ok(string&s){for(charc:s){if(c!='_'&&!isalnum(c)){returnfalse;}}return!s.empty();}public:vector<string>validateCoupons(vector<string>&code,vector<string>&businessLine,vector<bool>&isActive){vector<string>electronics,grocery,pharmacy,restaurant;for(inti=0;i<code.size();i++){if(!isActive[i]){continue;}if(!is_ok(code[i])){continue;}if(businessLine[i]=="electronics"){electronics.push_back(code[i]);}elseif(businessLine[i]=="grocery"){grocery.push_back(code[i]);}elseif(businessLine[i]=="pharmacy"){pharmacy.push_back(code[i]);}elseif(businessLine[i]=="restaurant"){restaurant.push_back(code[i]);}}sort(electronics.begin(),electronics.end());sort(grocery.begin(),grocery.end());sort(pharmacy.begin(),pharmacy.end());sort(restaurant.begin(),restaurant.end());vector<string>ans;ans.reserve(electronics.size()+grocery.size()+pharmacy.size()+restaurant.size());ans.insert(ans.end(),make_move_iterator(electronics.begin()),make_move_iterator(electronics.end()));ans.insert(ans.end(),make_move_iterator(grocery.begin()),make_move_iterator(grocery.end()));ans.insert(ans.end(),make_move_iterator(pharmacy.begin()),make_move_iterator(pharmacy.end()));ans.insert(ans.end(),make_move_iterator(restaurant.begin()),make_move_iterator(restaurant.end()));returnans;}};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源