每日一练 2024.5.23 （补：2024.5.24）

题目

定义 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 <= 100
• s1 和 s2 由小写英文字母组成
• 1 <= n1, n2 <= 106

分析

1. 初始计数过程：

   • s1 和 s2 分别重复 n1 和 n2 次组成的字符串。
   • 我们可以通过逐个字符匹配 s2 来达到这个目的。

2. 记录状态与循环检测：

   • 当我们反复扫描 s1 去匹配 s2 时，如果存在循环出现的情况，那么可以加速计算。
   • 通过使用哈希表记录每次遇到的位置状态，来检测是否有循环。

3. 基于循环优化：

   • 如果发现循环，则可以跳过某些步骤利用循环性质直接得到答案。

步骤1：初始化变量

我们需要一些变量来跟踪：

• index1 和 index2 分别用于遍历 s1 和 s2；
• count1 和 count2 分别用于记录 s1 和 s2 循环的总次数；
• memo 用于存储和检测循环状态。

步骤2：逐字符匹配

我们逐字符遍历 s1，尝试匹配 s2。每当匹配到 s2 的一个字符时，就推进 index2。如果 index2 到达 s2 的末尾，表示完整匹配一个 s2，此时重置 index2，并增加 count2。

步骤3：检测并利用循环

当在遍历 s1 的每次循环过程中，如果遇到之前已经遇到相同 index2 的情况，说明已经形成一个循环。我们记录下循环的长度，然后可以直接跳过这些循环，通过数学计算快速得出结果。

步骤4：计算最优解

利用记录的状态，通过跳过循环部分，计算可以完整包含 str2 的最大次数。

代码优化及实现

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
        int l1 = s1.length(), l2 = s2.length();
        Map<Integer, int[]> memo = new HashMap<>();
        int count1 = 0, count2 = 0;
        int i = 0, j = 0;
        
        while (count1 < n1) {
            if (s1.charAt(i) == s2.charAt(j)) {
                j++;
                if (j == l2) {
                    j = 0;
                    count2++;
                }
            }
            i++;
            if (i == l1) {
                i = 0;
                count1++;
                if (memo.containsKey(j)) {
                    int[] last = memo.get(j);
                    int previous_count1 = last[0];
                    int previous_count2 = last[1];
                    int loop1 = count1 - last[0];
                    int loop2 = count2 - last[1];
                    int remaining_count1 = n1 - count1;
                    count1 += (remaining_count1 / loop1) * loop1;
                    count2 += (remaining_count1 / loop1) * loop2;
                } else {
                    memo.put(j, new int[]{count1, count2});
                }
            }
        }

        return count2 / n2;
    }
}

代码讲解

1. 变量初始化：

   • l1 和 l2 分别为 s1 和 s2 的长度；
   • index1 和 index2 分别用于遍历 s1 和 s2；
   • count1 和 count2 分别记录使用了多少个 s1 和匹配了多少个 s2；
   • memo 记录每次循环的状态，用于检测循环。

2. 逐字符匹配：

   • 通过 if 语句逐字符匹配 s1 中的字符和 s2 中的字符。

3. 循环检测：

   • 使用 if 判断 index1 是否达到 s1 末尾，如果是，增加 count1；
   • 如果在 memo 中找到已记录的 index2，说明进入循环，计算剩余部分的循环次数。

4. 结果计算：

   • 计算 count2 整除 n2 的值，作为最终结果。

知识点解析

2025.5.24