007.创意标题匹配问题
难度：易
问题描述
在广告平台中，为了给广告主一定的自由性和效率，允许广告主在创造标题的时候以通配符的方式进行创意提交。线上服务的时候，会根据用户的搜索词触发的 bidword 对创意中的通配符（通配符是用成对 {} 括起来的字符串，可以包含 0 个或者多个字符）进行替换，用来提升广告投放体验。例如：“{末日血战} 上线送 SSR 英雄，三天集齐无敌阵容！”，会被替换成“帝国时代游戏下载上线送 SSR 英雄，三天集齐无敌阵容！”。给定一个含有通配符的创意和n个标题，判断这句标题是否从该创意替换生成的。
测试样例
样例1：
输入：
n = 4, template = "ad{xyz}cdc{y}f{x}e", titles = ["adcdcefdfeffe", "adcdcefdfeff", "dcdcefdfeffe", "adcdcfe"]
输出："True,False,False,True"
样例2：
输入：
n = 3, template = "a{bdc}efg", titles = ["abcdefg", "abefg", "efg"]
输出："True,True,False"
样例3：
输入：
n = 5, template = "{abc}xyz{def}", titles = ["xyzdef", "abcdef", "abxyzdef", "xyz", "abxyz"]
输出："True,False,True,True,True"
解题思路
- 解析模板：首先，我们需要解析模板字符串，找出所有的通配符及其位置。
- 匹配标题：对于每个标题，我们需要检查它是否可以通过替换模板中的通配符生成。
- 动态匹配：使用双指针技术，一个指针遍历模板，另一个指针遍历标题，尝试匹配模板中的固定部分和通配符部分。
复杂度分析
-
时间复杂度：
- 提取模板的前缀和后缀的时间复杂度为 O(n)，其中 n 是模板的长度。
- 使用正则表达式提取非通配符部分的时间复杂度为 O(n)。
- 对于每个标题，检查其是否符合模板的时间复杂度为 O(m)，其中 m 是标题的长度。
- 因此，总的时间复杂度为 O(n+m⋅k)，其中 k 是标题的数量。
-
空间复杂度：
- 存储模板的前缀、后缀和非通配符部分的空间复杂度为 O(n)。
- 因此，总的空间复杂度为 O(n)。
知识点扩展
-
正则表达式：
- 正则表达式是一种强大的字符串匹配工具，可以用来提取、替换和验证字符串中的模式。在本题中，我们使用正则表达式提取模板中的非通配符部分。
-
字符串处理：
- 字符串处理是算法题中常见的操作，包括字符串的拼接、分割、查找和替换等。在本题中，我们需要处理模板和标题的字符串，提取前缀、后缀和非通配符部分，并进行匹配。
-
双指针技巧：
- 双指针技巧常用于字符串和数组的处理，可以有效地减少时间复杂度。在本题中，我们使用双指针技巧来提取模板的前缀和后缀。
代码提示
def solution(n, template_, titles):
# 解析模板，找出所有的通配符及其位置
import re
pattern = re.compile(r'\{.*?\}')
matches = list(pattern.finditer(template_))
# 定义一个函数来检查某个标题是否匹配模板
def is_match(title):
# 使用双指针技术进行匹配
t_index = 0 # 模板指针
ti_index = 0 # 标题指针
for match in matches:
# 匹配模板中的固定部分
fixed_part = template_[t_index:match.start()]
if title[ti_index:ti_index + len(fixed_part)] != fixed_part:
return False
ti_index += len(fixed_part)
t_index = match.end()
# 匹配通配符部分
wildcard_start = match.start()
wildcard_end = match.end()
wildcard_content = template_[wildcard_start + 1:wildcard_end - 1]
# 找到标题中对应通配符的部分
if wildcard_content:
# 如果通配符内容不为空，尝试匹配
wildcard_match = re.search(wildcard_content, title[ti_index:])
if not wildcard_match:
return False
ti_index += wildcard_match.end()
else:
# 如果通配符内容为空，直接跳过
pass
# 匹配模板剩余部分
if title[ti_index:] != template_[t_index:]:
return False
return True
# 对每个标题进行匹配检查
results = []
for title in titles:
results.append(is_match(title))
# 将结果转换为字符串
return ','.join(map(str, results))
if __name__ == "__main__":
# 你可以添加更多测试用例
testTitles1 = ["adcdcefdfeffe", "adcdcefdfeff", "dcdcefdfeffe", "adcdcfe"]
testTitles2 = ["CLSomGhcQNvFuzENTAMLCqxBdj", "CLSomNvFuXTASzENTAMLCqxBdj", "CLSomFuXTASzExBdj", "CLSoQNvFuMLCqxBdj", "SovFuXTASzENTAMLCq", "mGhcQNvFuXTASzENTAMLCqx"]
testTitles3 = ["abcdefg", "abefg", "efg"]
print(solution(4, "ad{xyz}cdc{y}f{x}e", testTitles1) == "True,False,False,True" )
print(solution(6, "{xxx}h{cQ}N{vF}u{XTA}S{NTA}MLCq{yyy}", testTitles2) == "False,False,False,False,False,True" )
print(solution(3, "a{bdc}efg", testTitles3) == "True,True,False" )008.找出整型数组中占比超过一半的数
难度：易
问题描述
小R从班级中抽取了一些同学，每位同学都会给出一个数字。已知在这些数字中，某个数字的出现次数超过了数字总数的一半。现在需要你帮助小R找到这个数字。
测试样例
样例1：
输入：
array = [1, 3, 8, 2, 3, 1, 3, 3, 3]
输出：3
样例2：
输入：
array = [5, 5, 5, 1, 2, 5, 5]
输出：5
样例3：
输入：
array = [9, 9, 9, 9, 8, 9, 8, 8]
输出：9
解题思路
-
理解问题：
- 题目要求找到数组中出现次数超过一半的数字。
- 这意味着这个数字的出现次数比其他所有数字的出现次数之和还要多。
-
数据结构选择：
- 我们可以使用一个计数器来记录当前候选数字的出现次数。
- 使用一个变量来存储当前的候选数字。
-
算法步骤：
- 初始化一个候选数字
candidate和计数器count。 - 遍历数组中的每一个数字：
- 如果
count为 0，将当前数字设为candidate，并将count设为 1。 - 如果当前数字与
candidate相同，则count加 1。 - 如果当前数字与
candidate不同，则count减 1。
- 如果
- 最终，
candidate就是我们要找的数字。
- 初始化一个候选数字
def solution(array):
# 创建一个字典来记录每个数字的出现次数
count_dict = {}
# 遍历数组
for num in array:
# 更新字典中的计数
if num in count_dict:
count_dict[num] += 1
else:
count_dict[num] = 1
# 检查当前数字的出现次数是否超过数组长度的一半
if count_dict[num] > len(array) // 2:
return num
# 如果没有找到符合条件的数字，返回0（虽然题目保证一定存在这样的数字）
return 0
if __name__ == "__main__":
# 添加你的测试用例
print(solution([1, 3, 8, 2, 3, 1, 3, 3, 3]) == 3)
print(solution([5, 5, 5, 1, 2, 5, 5]) == 5)
print(solution([9, 9, 9, 9, 8, 9, 8, 8]) == 9)来源：https://www.marscode.cn/practice
