LeetCode刷题实战466：统计重复个数
算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 统计重复个数，我们先来看题面：
https://leetcode-cn.com/problems/count-the-repetitions/
We define str = [s, n] as the string str which consists of the string s concatenated n times.
For example, str == ["abc", 3] =="abcabcabc".
We define that string s1 can be obtained from string s2 if we can remove some characters from s2 such that it becomes s1.
For example, s1 = "abc" can be obtained from s2 = "abdbec" based on our definition by removing the bolded underlined characters.
You are given two strings s1 and s2 and two integers n1 and n2. You have the two strings str1 = [s1, n1] and str2 = [s2, n2].
Return the maximum integer m such that str = [str2, m] can be obtained from str1.
定义 str = [s, n] 表示 str 由 n 个字符串 s 连接构成。
例如，str == ["abc", 3] =="abcabcabc" 。
如果可以从 s2 中删除某些字符使其变为 s1，则称字符串 s1 可以从字符串 s2 获得。
例如，根据定义，s1 = "abc" 可以从 s2 = "abdbec" 获得，仅需要删除加粗且用斜体标识的字符。
现在给你两个字符串 s1 和 s2 和两个整数 n1 和 n2 。由此构造得到两个字符串，其中 str1 = [s1, n1]、str2 = [s2, n2] 。
请你找出一个最大整数 m ，以满足 str = [str2, m] 可以从 str1 获得。
示例
示例 1：
输入：s1 = "acb", n1 = 4, s2 = "ab", n2 = 2
输出：2
示例 2：
输入：s1 = "acb", n1 = 1, s2 = "acb", n2 = 1
输出：1解题
http://www.manongjc.com/detail/16-brgjkiiatjfsbja.html
思路1：可能超时。分析题目可知，字符串S1是由n1个s1连接而成，字符串S2是由n2个s2连接而成，求满足使[S2,M]从S1获得的最大整数M，有点绕口，通俗说，即求S1中包含S2的个数M。最容易想到的方法是初始化M=0，然后遍历S1寻找S2，找到S2后M++，依次继续，直到S1遍历结束。当然，需要注意遍历的条件，即保证S2的长度应该小于等于S1的长度。不过可惜的是，这种思路导致超时问题。
class Solution {
public:
int getMaxRepetitions(string s1, int n1, string s2, int n2) {
string S1 = "", S2 = "";
int M = 0;
for(int i = 0; i < n1; i++) S1 += s1;
for(int j = 0; j < n2; j++) S2 += s2;
int k = 0;
for(int i = 0; i < S1.size(); i++)
{
if(S1[i] == S2[k]) k++;
if(k == S2.size())
{
M++;
k = 0;
}
}
return M;
}
};思路2：如果s2在S1中出现了N次，那么S2肯定在S1中出现了N/n2次，这里的大写表示字符串加上重复次数组成的大字符串，即字符串拼接结果。所以，我们只要算出s2出现的次数count_s2，然后除以n2，就可以得出S2在S1中出现的次数了，即可求得M。
class Solution {
public:
int getMaxRepetitions(string s1, int n1, string s2, int n2) {
int s2_next_index = 0, count_s1 = 0, count_s2 = 0;
unordered_map<int, pair<int, int>> mp;
while(count_s1 < n1)
{
for(int i = 0; i < s1.size(); i++)
{
if(s1[i] == s2[s2_next_index]) s2_next_index++;
if(s2_next_index == s2.size())
{
s2_next_index = 0; //下一轮循环
count_s2++;
}
}
count_s1++;
if(mp.count(s2_next_index) == 0) mp[s2_next_index] = make_pair(count_s1, count_s2);
else
{
int last_count_s1 = mp[s2_next_index].first;
int last_count_s2 = mp[s2_next_index].second;
int interval_s1 = count_s1 - last_count_s1;
int interval_s2 = count_s2 - last_count_s2;
int num = (n1 - count_s1) / interval_s1;
count_s2 += num * interval_s2;
count_s1 += num * interval_s1;
}
}
return count_s2 / n2;
}
};好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
上期推文：
腾讯云开发者
