【LeetCode每日一题】466. 统计重复个数

2024-1-2

466. 统计重复个数

思路：

1. ? s1表示要重复的序列。n1表示要重复s1的次数。
   ? s2表示要判断的子序列。n2表示子序列s2在整个序列中重复的次数。返回值表示子序列s2在重复序列s1中出现的次数。
2. 定义一个二维数组d，其中有n行，每行只有一个元素
3. 遍历子序列s2的每个字符
4. 遍历重复序列s1的每个字符，统计子序列s2在重复序列s1中出现的次数
5. 如果重复序列s1的第k个字符等于子序列s2的第j个字符
6. j自增后等于n，说明已经遍历完子序列s2的所有字符，需要从头开始再次匹配，j清空
7. 将统计的次数和当前j的值存入二维数组d的第i行。
8. 循环直到s1的次数走完为止，将二维数组d中第j行的统计次数累加到ans中，更新j的值为二维数组d中第j行的下一个字符的位置
9. 求子序列s2在重复序列s1中出现的平均次数

    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
        //s1表示要重复的序列。n1表示要重复s1的次数。
        //s2表示要判断的子序列。n2表示子序列s2在整个序列中重复的次数。
      // 返回值表示子序列s2在重复序列s1中出现的次数。
        int m = s1.length(), n = s2.length();
        //m和n，分别表示序列s1和s2的长度。
        int[][] d = new int[n][0];
       // 定义一个二维数组d，其中有n行，每行只有一个元素
        for (int i = 0; i < n; ++i) {
            //遍历子序列s2的每个字符
            int j = i;//j 表示在字符串s2中出现的位置
            int cnt = 0;
           // 统计子序列s2在重复序列s1中出现的次数
            for (int k = 0; k < m; ++k) {
                //遍历重复序列s1的每个字符
                if (s1.charAt(k) == s2.charAt(j)) {
                    //如果重复序列s1的第k个字符等于子序列s2的第j个字符
                    if (++j == n) {
                        //如果j自增后等于n，说明已经遍历完子序列s2的所有字符，需要从头开始再次匹配
                        j = 0;
                        //将j重置为0，重新从子序列s2的开头开始匹配
                        ++cnt;
                        //子序列s2在重复序列s1中出现的次数加1
                    }
                }
            }
            d[i] = new int[] {cnt, j};
            //将统计的次数和当前j的值存入二维数组d的第i行。
        }
        int ans = 0;
        //用于保存子序列s2在重复序列s1中出现的总次数
        for (int j = 0; n1 > 0; --n1) {
            ///每次循环将n1减1，直到n1为0,s1的次数走完为止
            ans += d[j][0];
            //将二维数组d中第j行的统计次数累加到ans中。
            j = d[j][1];
            //更新j的值为二维数组d中第j行的下一个字符的位置
        }
        return ans / n2;
        //子序列s2在重复序列s1中出现的平均次数
    }

点击移步博客主页，欢迎光临~