1：字符串匹配
题目链接：LCR 137. 模糊搜索验证 - 力扣（LeetCode）
可以使用递归的方法来检查 input 是否可以匹配 article。目的是正确处理两种通配符：‘.’ 和 ‘*’的匹配规则。
def is_match(article: str, input: str) -> bool:
if not input:
return not article
first_match = bool(article) and (input[0] == article[0] or input[0] == '.')
if len(input) >= 2 and input[1] == '*':
return (is_match(article, input[2:]) or
(first_match and is_match(article[1:], input)))
else:
return first_match and is_match(article[1:], input[1:])
以下是对该代码的详细解释：
def is_match(article: str, input: str) -> bool:
- 定义一个函数
is_match，它接受两个字符串参数：article和input。这个函数的目标是确定input是否可以匹配article。函数返回一个布尔值。
if not input:
return not article
- 检查
input是否为空。如果input为空，那么只有当article也为空时，才能匹配成功。因此，返回not article。如果article也为空，返回True，表示匹配成功；否则返回False。
first_match = bool(article) and (input[0] == article[0] or input[0] == '.')
- 初始化一个布尔变量
first_match。它表示input的第一个字符是否与article的第一个字符匹配。匹配的条件是input的第一个字符等于article的第一个字符，或者input的第一个字符是通配符 ‘.’（可以匹配任意单个字符）。
if len(input) >= 2 and input[1] == '*':
- 检查
input的长度是否至少为2，并且input的第二个字符是否是通配符。如果这两个条件都满足，那么我们可以选择忽略 '’ 和它前面的字符，或者尝试将 ‘*’ 前面的字符与article中的字符进行匹配。
return (is_match(article, input[2:]) or
(first_match and is_match(article[1:], input)))
如果
input的第二个字符是 ‘*’，我们有两种选择：
- 忽略 ‘*’ 和它前面的字符，并递归地检查
input[2:]（即input中去掉前两个字符）是否可以匹配article。- 如果
first_match为True（即input的第一个字符与article的第一个字符匹配），我们可以尝试将 ‘*’ 前面的字符与article中的字符进行匹配，并递归地检查input是否可以匹配article[1:]（即去掉article第一个字符的字符串）。这两种选择中只要有一种是
True，就返回True。
else:
return first_match and is_match(article[1:], input[1:])
- 如果
input的第二个字符不是 ‘*’，那么我们只需要检查input的第一个字符是否与article的第一个字符匹配（即first_match是否为True），并且递归地检查input[1:]是否可以匹配article[1:]。如果这两个条件都满足，返回True；否则返回False。
2：最长连续序列
题目链接：128. 最长连续序列 - 力扣（LeetCode）
这个题目的目的是找到输入数组中数字连续的最长序列的长度。可以通过将数组转换为集合，能够以 O(1) 的时间复杂度来检查一个数字是否存在，从而使得整个算法的时间复杂度为 O(n)。
def longest_consecutive(nums):
if not nums:
return 0
num_set = set(nums)
max_length = 0
for num in num_set:
# 检查当前数字 num 是否是一个序列的开始。这是通过检查 num - 1 是否在集合中来确定的。如果 num - 1 不在集合中，那么 num 就是一个序列的开始。
if num - 1 not in num_set:
length = 1
# 使用一个 while 循环来检查从 num 开始的连续数字是否在集合中。如果 num + length 在集合中，则将 length 增加 1，并继续检查下一个连续数字。
while num + length in num_set:
length += 1
# 更新 max_length 为 max_length 和 length 中的较大值。这确保了 max_length 总是记录着找到的最长连续序列的长度。
max_length = max(max_length, length)
return max_length3：有效的数独
首先初始化三个集合列表：rows、cols 和 boxes，分别用于存储每一行、每一列和每一个 3x3 宫内的数字。然后，遍历整个数独板，检查每个数字是否已经在相应的行、列或宫中出现过。如果出现过，则返回 False；否则，将数字添加到相应的集合中。如果整个数独板都检查完毕且没有发现冲突，则返回 True。
def is_valid_sudoku(board):
# 初始化9个集合，分别代表9行、9列和9个3x3宫，用于存储出现的数字
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
# 遍历数独板的每一个位置
for i in range(9):
for j in range(9):
# 获取当前位置的数字
num = board[i][j]
# 如果当前位置不是空白格（即不是'.')
if num != '.':
# 计算当前数字属于哪一个3x3宫
box_index = (i // 3) * 3 + j // 3
# 检查当前数字是否已经在当前行、当前列或当前宫出现过
if num in rows[i] or num in cols[j] or num in boxes[box_index]:
# 如果出现过，则数独无效，返回False
return False
# 将当前数字添加到当前行、当前列和当前宫的集合中
rows[i].add(num)
cols[j].add(num)
boxes[box_index].add(num)
# 如果所有位置都检查完毕且没有冲突，则数独有效，返回True
return True