IT源码网

统计重复个数讲解

shasha 2020年10月21日 编程语言 232 0

由 n 个连接的字符串 s 组成字符串 S,记作 S = [s,n]。例如,["abc",3]=“abcabcabc”。

如果我们可以从 s2 中删除某些字符使其变为 s1,则称字符串 s1 可以从字符串 s2 获得。例如,根据定义,"abc" 可以从 “abdbec” 获得,但不能从 “acbbe” 获得。

现在给你两个非空字符串 s1 和 s2(每个最多 100 个字符长)和两个整数 0 ≤ n1 ≤ 106 和 1 ≤ n2 ≤ 106。现在考虑字符串 S1 和 S2,其中 S1=[s1,n1] 、S2=[s2,n2] 。

请你找出一个可以满足使[S2,M] 从 S1 获得的最大整数 M 。

 

示例:

输入:
s1 ="acb",n1 = 4
s2 ="ab",n2 = 2

返回:
2

解:这道题参考别人的答案,难懂的地方在于下面的100为什么减1,想明白了后发现是因为s1第一节所匹配的,未形成循环节,之后的都形成了循环节,所以要把已知的减掉。代码表示的时候,把第一个减掉就行了(可能没描述很清楚。。。)

 

 

 

当我们找出循环节后,我们即可知道一个循环节内包含 s1 的数量,以及在循环节出现前的 s1 的数量,这样就可以在 O(1)O(1) 的时间内,通过简单的运算求出 s2 在 S1 中出现的次数了。当然,由于 S1 中 s1 的数量 n1 是有限的,因此可能会存在循环节最后一个部分没有完全匹配,如上图最后会单独剩一个 s1 出来无法完全匹配完循环节,这部分我们需要单独拿出来遍历处理统计。

有些读者可能会怀疑循环节是否一定存在,这里我们给出的答案是肯定的,根据鸽笼原理,我们最多只要找过 |s2| + 1 个 s1,就一定会出现循环节。

算法

我们设计一个哈希表 recall :哈希表 recall 以 s2 字符串的下标 index 为索引,存储匹配至第 s1cnt 个 s1 的末尾,当前匹配到第 s2cnt 个 s2 中的第 index 个字符时, 已经匹配过的s1 的个数 s1cnt 和 s2 的个数 s2cnt 。

我们在每次遍历至 s1 的末尾时根据当前匹配到的 s2 中的位置 index 查看哈希表中的对应位置,如果哈希表中对应的位置 index 已经存储元素,则说明我们找到了循环节。循环节的长度可以用当前已经匹配的 s1 与 s2 的数量减去上次出现时经过的数量(即哈希表中存储的值)来得到。

class Solution { 
public: 
    int getMaxRepetitions(string s1, int n1, string s2, int n2) { 
        if (n1 == 0) { 
            return 0; 
        } 
        int s1cnt = 0, index = 0, s2cnt = 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 个字符开始匹配 
        unordered_map<int, pair<int, int>> recall; 
        pair<int, int> pre_loop, in_loop;
    //原理在于找到第一个循环节后,就用数学方法推导
while (true) { // 上来先对s1增加 ++s1cnt; for (char ch: s1) { if (ch == s2[index]) { index += 1; if (index == s2.size()) { ++s2cnt; index = 0; } } } // 还没有找到循环节,所有的 s1 就用完了 if (s1cnt == n1) { return s2cnt / n2; } // 出现了之前的 index,表示找到了循环节,这里要对之前的数量进行相减,因为之前的可能不是一个单独的循环节,单独计入就好 if (recall.count(index)) { auto [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 //这里计算的就是按照上图(100-1)/2的方法 来计算有多少s2的 int ans = pre_loop.second + (n1 - pre_loop.first) / in_loop.first * in_loop.second; // S1 的末尾还剩下一些 s1,我们暴力进行匹配 int rest = (n1 - pre_loop.first) % in_loop.first; for (int i = 0; i < rest; ++i) { for (char ch: s1) { if (ch == s2[index]) { ++index; if (index == s2.size()) { ++ans; index = 0; } } } } // S1 包含 ans 个 s2,那么就包含 ans / n2 个 S2 return ans / n2; } };

 

发布评论

分享到:

IT源码网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

nginx限速控制讲解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。