算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从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;
}
};
好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。
上期推文: