「LeetCode每日一题」—— 466. 统计重复个数
466. 统计重复个数
链接:https://leetcode-cn.com/problems/count-the-repetitions/
难度:困难
题目
思路
这是一道困难题,我们先从例子看起。
输入:
s1 ="acb",n1 = 4
s2 ="ab",n2 = 2
那么根据S = [s,n]的定义
S1="acbacbacbacb"
S2="abab"
如果我们把S1中的”c”去掉,那剩下4个”ab”,那么满足[S2,M]从S1获得的最大整数M可为2,答案就是2。
现在要找出S2在S1中重复的次数,因为n的范围很大,如果暴力先循环得出S1,S2再判断S的个数,这种可能超时。
我们可以判断两个循环体s1,s2的规律,再去算S1,S2循环的次数。
比如上面的例子:
s1 ="acb"
s2 ="ab"
s1去掉c就得到了s2,那么一个s1就可以得到一个s2。S1是4个s1,S2是2个s2,那么M就是4/2,为2。
不过还可能会出现一些情况:
s1 ="acbacb"
s2 ="ab"
s1中就有2个s2
还有后面一种情况:
s1 ="abaacdbac"
s2 ="adcbd"
那么需要


我们以两个s1为一组,可以看到




代码见解决方案
方案代码
解决方案:
class Solution:
def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
if n1 == 0:
return 0
s1cnt, index, s2cnt = 0, 0, 0
# recall 是我们用来找循环节的变量,它是一个哈希映射
# 我们如何找循环节?假设我们遍历了 s1cnt 个 s1,此时匹配到了第 s2cnt 个 s2 中的第 index 个字符
# 如果我们之前遍历了 s1cnt' 个 s1 时,匹配到的是第 s2cnt' 个 s2 中同样的第 index 个字符,那么就有循环节了
# 我们用 (s1cnt', s2cnt', index) 和 (s1cnt, s2cnt, index) 表示两次包含相同 index 的匹配结果
# 那么哈希映射中的键就是 index,值就是 (s1cnt', s2cnt') 这个二元组
# 循环节就是;
# - 前 s1cnt' 个 s1 包含了 s2cnt' 个 s2
# - 以后的每 (s1cnt - s1cnt') 个 s1 包含了 (s2cnt - s2cnt') 个 s2
# 那么还会剩下 (n1 - s1cnt') % (s1cnt - s1cnt') 个 s1, 我们对这些与 s2 进行暴力匹配
# 注意 s2 要从第 index 个字符开始匹配
recall = dict()
while True:
# 我们多遍历一个 s1,看看能不能找到循环节
s1cnt += 1
for ch in s1:
if ch == s2[index]:
index += 1
if index == len(s2):
s2cnt, index = s2cnt + 1, 0
# 还没有找到循环节,所有的 s1 就用完了
if s1cnt == n1:
return s2cnt // n2
# 出现了之前的 index,表示找到了循环节
if index in recall:
s1cnt_prime, s2cnt_prime = recall[index]
# 前 s1cnt' 个 s1 包含了 s2cnt' 个 s2
pre_loop = (s1cnt_prime, s2cnt_prime)
# 以后的每 (s1cnt - s1cnt') 个 s1 包含了 (s2cnt - s2cnt') 个 s2
in_loop = (s1cnt - s1cnt_prime, s2cnt - s2cnt_prime)
break
else:
recall[index] = (s1cnt, s2cnt)
# ans 存储的是 S1 包含的 s2 的数量,考虑的之前的 pre_loop 和 in_loop
ans = pre_loop[1] + (n1 - pre_loop[0]) // in_loop[0] * in_loop[1]
# S1 的末尾还剩下一些 s1,我们暴力进行匹配
rest = (n1 - pre_loop[0]) % in_loop[0]
for i in range(rest):
for ch in s1:
if ch == s2[index]:
index += 1
if index == len(s2):
ans, index = ans + 1, 0
# S1 包含 ans 个 s2,那么就包含 ans / n2 个 S2
return ans // n2
原创文章,作者:flypython,如若转载,请注明出处:http://flypython.com/algorithm/leetcode/338.html
您必须登录才能发表评论。