题目:
466. 统计重复个数
由 n 个连接的字符串 s 组成字符串 S,记作 S = [s,n]
。例如,["abc",3]
=“abcabcabc”。
如果我们可以从 s2中删除某些字符使其变为 s1,则称字符串 s1可以从字符串 s2 获得。例如,根据定义,”abc” 可以从 “abdbec” 获得,但不能从 “acbbe” 获得。
现在给你两个非空字符串 s1 和 s2(每个最多 100 个字符长)和两个整数 0 ≤ n1 ≤ 10和 1 ≤ n2 ≤ 10。现在考虑字符串 S1 和 S2,其中 S1=[s1,n1]
、S2=[s2,n2]
。
请你找出一个可以满足使[S2,M]
从 S1
获得的最大整数 M 。
示例:
输入:
s1 =”acb”,n1 = 4
s2 =”ab”,n2 = 2
返回:
2
解题思路:
简单的方式是通过遍历解决,但是n1可能会很大,从而造成超时;所以要想办法减少循环;
方式:找循环,记录遍历完一次s1后下一个待找寻的s2节点序号pnext,记录当前完成s2循环的次数psum;如果有当某一次s1遍历完后pnext的值和从前的某一次pnext相同,则说明这之间产生了循环,从而直接结束遍历,只要根据循环计算即可。当无法整除时,最后的几个s2通过psum求得。
解题图解示例:
代码:
class Solution {
public:
int getMaxRepetitions(string s1, int n1, string s2, int n2) {
//清除无用的字符,减短搜索时间
string s3 = "";
for(int i = 0; i < s1.size(); i++){
for(int j = 0; j < s2.size(); j++){
if(s1[i] == s2[j]){
s3 += s1[i];
break;
}
}
}
int i = 0, j = 0; //循环因子
int sum = 0; //s2循环次数
int k = 0; //M=0情况的出循环标志
int y = 0; //s1循环次数
int* pnext = new int [n1 + 1]; //定义记录并初始化开头的值
pnext[0] = 0;
int* psum = new int [n1 + 1];
psum[0] = 0;
bool flagcir = false; //循环节找到标志
int x = 0; //循环节的初始的标志
for(; y < n1; i++){ //y:循环节的结尾标志
if(i >= s2.size()){ //s1循环
i = 0;
sum++;
}
bool flag = false; //已匹配到字符标志
k = 0;
do{
if(j >= s3.size()){ s2循环
j = 0;
y++;
pnext[y] = i;
psum[y] = sum;
for(x = 0; x < y; x++){ //找寻循环节
if(i == pnext[x]){
flag = true;
flagcir = true;
break;
}
}
k++;
if(flagcir){
break;
}
}
if(s3[j] == s2[i]){ //匹配字符
flag = true;
j++;
// cout << "nei:" << j << endl;
break;
}
j++;
}while(k < 2);
// cout << "wai:" << j << endl;
if(!flag){
cout << "error!" << endl;
return 0;
}
if(flagcir){
break;
}
}
if(flagcir){
cout << "cir" << endl;
cout << x << " " << psum[x] << " " << y - 1 << " " << psum[y - 1] << endl;
sum = psum[x] + (psum[y] - psum[x])*((n1 - x) / (y - x))
+ psum[(n1 - x) % (y - x) + x] - psum[x];
/*可化简:sum = (psum[y] - psum[x])*((n1 - x) / (y - x))
+ psum[(n1 - x) % (y - x) + x];
*/
}
return sum/n2;
}
};
思考:
1.这一题做完花费了很长时间,且写题出现了中断,自我反省;
2.错误历史:(1)直接计算一个s1内的s2出现次数,未考虑跨s2的情况;
(2)直接使用遍历的方式,结果超时;
(3)开始考虑s1在s2的循环查找,但是仅仅考虑相邻s1间出现循环的可能;
(4)未考虑为遍历前的pnext[0] = 0,结果也可以对,但是会延迟循环节寻到的时间;
3.考虑2.4错误后,出现错误heap-buffer-overflow,内存非法访问,pnext[n1],psum[n1]在添加未遍历前起点标志后,空间可能不足,所以定义时int *pnext = new int [n1+ 1];
4.在时间上仍然有改进的空间,附上0ms代码,来自leetcode官网:
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
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;
}
};