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

2024-01-02 19:03:14

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中出现的平均次数
    }

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

偷cyk的图

文章来源:https://blog.csdn.net/m0_64003319/article/details/135346926
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。