class Solution {
public:
int getMaxRepetitions(string s1, int n1, string s2, int n2) {
}
};
466. 统计重复个数
定义 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
提示：
1 <= s1.length, s2.length <= 100s1 和 s2 由小写英文字母组成1 <= n1, n2 <= 106原站题解
java 解法, 执行用时: 4 ms, 内存消耗: 40.3 MB, 提交时间: 2024-01-02 07:41:01
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 个字符开始匹配
Map<Integer, int[]> recall = new HashMap<Integer, int[]>();
int[] preLoop = new int[2];
int[] inLoop = new int[2];
while (true) {
// 我们多遍历一个 s1，看看能不能找到循环节
++s1cnt;
for (int i = 0; i < s1.length(); ++i) {
char ch = s1.charAt(i);
if (ch == s2.charAt(index)) {
index += 1;
if (index == s2.length()) {
++s2cnt;
index = 0;
}
}
}
// 还没有找到循环节，所有的 s1 就用完了
if (s1cnt == n1) {
return s2cnt / n2;
}
// 出现了之前的 index，表示找到了循环节
if (recall.containsKey(index)) {
int[] value = recall.get(index);
int s1cntPrime = value[0];
int s2cntPrime = value[1];
// 前 s1cnt' 个 s1 包含了 s2cnt' 个 s2
preLoop = new int[]{s1cntPrime, s2cntPrime};
// 以后的每 (s1cnt - s1cnt') 个 s1 包含了 (s2cnt - s2cnt') 个 s2
inLoop = new int[]{s1cnt - s1cntPrime, s2cnt - s2cntPrime};
break;
} else {
recall.put(index, new int[]{s1cnt, s2cnt});
}
}
// ans 存储的是 S1 包含的 s2 的数量，考虑的之前的 preLoop 和 inLoop
int ans = preLoop[1] + (n1 - preLoop[0]) / inLoop[0] * inLoop[1];
// S1 的末尾还剩下一些 s1，我们暴力进行匹配
int rest = (n1 - preLoop[0]) % inLoop[0];
for (int i = 0; i < rest; ++i) {
for (int j = 0; j < s1.length(); ++j) {
char ch = s1.charAt(j);
if (ch == s2.charAt(index)) {
++index;
if (index == s2.length()) {
++ans;
index = 0;
}
}
}
}
// S1 包含 ans 个 s2，那么就包含 ans / n2 个 S2
return ans / n2;
}
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 6.6 MB, 提交时间: 2024-01-02 07:40:40
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;
}
};
golang 解法, 执行用时: 4 ms, 内存消耗: 1.9 MB, 提交时间: 2023-09-07 14:46:36
func getMaxRepetitions(s1 string, n1 int, s2 string, n2 int) int {
len1, len2 := len(s1), len(s2)
index1, index2 := 0, 0 // 注意此处直接使用 Ra Rb 的下标，不取模
if len1 == 0 || len2 == 0 || len1*n1 < len2*n2 {
return 0
}
map1, map2 := make(map[int]int), make(map[int]int)
ans := 0 // 注意，此处存储的是 Ra 中 Sb 的个数，而非 Ra 中 Rb 的个数
for index1/len1 < n1 { // 遍历整个 Ra
if index1%len1 == len1-1 { //在 Sa 末尾
if val, ok := map1[index2%len2]; ok { // 出现了循环，进行快进
cycleLen := index1/len1 - val/len1 // 每个循环占多少个 Sa
cycleNum := (n1 - 1 - index1/len1) / cycleLen // 还有多少个循环
cycleS2Num := index2/len2 - map2[index2%len2]/len2 // 每个循环含有多少个 Sb
index1 += cycleNum * cycleLen * len1 // 将 Ra 快进到相应的位置
ans += cycleNum * cycleS2Num // 把快进部分的答案数量加上
} else { // 第一次，注意存储的是未取模的
map1[index2%len2] = index1
map2[index2%len2] = index2
}
}
if s1[index1%len1] == s2[index2%len2] {
if index2%len2 == len2-1 {
ans += 1
}
index2 += 1
}
index1 += 1
}
return ans / n2
}
python3 解法, 执行用时: 52 ms, 内存消耗: 16 MB, 提交时间: 2023-09-07 14:44:10
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