「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

「LeetCode每日一题」—— 466. 统计重复个数

466. 统计重复个数

题目

思路

方案代码

相关

相关推荐

`466. 统计重复个数`

`题目`

`思路`