LeetCode 题解工作台
优惠券校验器
给你三个长度为 n 的数组，分别描述 n 个优惠券的属性： code 、 businessLine 和 isActive 。其中，第 i 个优惠券具有以下属性： code[i] ：一个 字符串 ，表示优惠券的标识符。 businessLine[i] ：一个 字符串 ，表示优惠券所属的业务类别。 is…
4
题型
6
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
我们可以直接模拟题目中的条件来筛选出有效的优惠券。具体步骤如下： 1. 检查标识符：对于每个优惠券的标识符，检查它是否非空，并且只包含字母、数字和下划线。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你三个长度为 n 的数组，分别描述 n 个优惠券的属性：code、businessLine 和 isActive。其中，第 i 个优惠券具有以下属性：
code[i]：一个 字符串，表示优惠券的标识符。businessLine[i]：一个 字符串，表示优惠券所属的业务类别。isActive[i]：一个 布尔值，表示优惠券是否当前有效。
当以下所有条件都满足时，优惠券被认为是 有效的 ：
code[i]不能为空，并且仅由字母数字字符（a-z、A-Z、0-9）和下划线（_）组成。businessLine[i]必须是以下四个类别之一："electronics"、"grocery"、"pharmacy"、"restaurant"。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.length1 <= n <= 1000 <= code[i].length, businessLine[i].length <= 100code[i]和businessLine[i]由可打印的 ASCII 字符组成。isActive[i]的值为true或false。
解题思路
方法一：模拟
我们可以直接模拟题目中的条件来筛选出有效的优惠券。具体步骤如下：
- 检查标识符：对于每个优惠券的标识符，检查它是否非空，并且只包含字母、数字和下划线。
- 检查业务类别：检查每个优惠券的业务类别是否属于给定的四个有效类别之一。
- 检查激活状态：检查每个优惠券是否处于激活状态。
- 收集有效优惠券：将所有满足上述条件的优惠券的 id 收集起来。
- 排序：根据业务类别和标识符对有效优惠券进行排序。
- 返回结果：返回排序后的有效优惠券的标识符列表。
时间复杂度 ，空间复杂度 ，其中 是优惠券的数量。
class Solution:
def validateCoupons(
self, code: List[str], businessLine: List[str], isActive: List[bool]
) -> List[str]:
def check(s: str) -> bool:
if not s:
return False
for c in s:
if not (c.isalpha() or c.isdigit() or c == "_"):
return False
return True
idx = []
bs = {"electronics", "grocery", "pharmacy", "restaurant"}
for i, (c, b, a) in enumerate(zip(code, businessLine, isActive)):
if a and b in bs and check(c):
idx.append(i)
idx.sort(key=lambda i: (businessLine[i], code[i]))
return [code[i] for i in idx]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidates should demonstrate an understanding of array scanning techniques to efficiently filter out invalid coupons.
- question_mark
Interviewers should look for efficient sorting algorithms, especially when handling multiple categories.
- question_mark
Look for the use of hash tables or similar structures to manage business line categorization.
常见陷阱
外企场景- error
Failing to handle invalid business lines or misinterpreting the valid categories.
- error
Not properly filtering out non-alphanumeric characters in coupon codes or failing to check if code[i] is empty.
- error
Incorrect sorting logic, such as not sorting coupons correctly within each business line or misordering business lines.
进阶变体
外企场景- arrow_right_alt
Handling a larger number of coupons (n > 100) with the same filtering and sorting approach.
- arrow_right_alt
Returning coupons in reverse lexicographical order for each business line.
- arrow_right_alt
Allowing different valid business lines and adjusting the sorting order accordingly.