计算无限字符串中字母的出现次数

Question

我有以下称为s="abcac"无限次重复的字符串。这意味着s它将看起来像：s="abcacabcacabcacabcacabcac...."并n代表s.

例如，如果s="monday"和n="10"，我们考虑的子字符串将是finalString="mondaymond"，因为无限字符串将是"mondaymondaymondaymonday..."并且 的前 10 个字符s是"mondaymond"

我正在尝试计算 .csv 中字母“a”的出现次数finalString。此代码运行正常，但是当 n>1000000 时程序将无法运行。

此外，如果我n从intto更改为long，则在这种情况下 for 循环将不起作用。

这个问题的解决方案是什么？

public static void main(String[] args){

            String s="abcac";

            int aCount=0;

            int n=1000;

            int j=0;

            char[] sCharArray=s.toCharArray();

            char[] finalString = new char[n];

            for(int i=0;i<n;i++){

                if(j==s.length())

                    j=0;

                finalString[i]=sCharArray[j];

                j++;

            }

            for(int i=0; i<n;i++){

                if(finalString[i]=='a')

                    aCount++;

            }

    System.out.println(aCount);

            }

Answer 1

我建议找出基本字符串重复的次数，并使用此信息计算字母的出现次数，以及最后出现的额外子字符串的次数。例如：String s = "monday";int n = 10;String chr = "a";int baseNum = s.length() - s.replace(chr, "").length();int baseCnt = (n / s.length()) * baseNum;int index = n % s.length();String left = s.substring(0, index);int finalCnt = left.length() - left.replace(chr, "").length();int totalCnt = baseCnt + finalCnt;System.out.println("There were " + totalCnt + " letter " + chr + ".");这里的基本思想是效率。我们实际上不需要创建和使用任意长度的字符串，因为我们知道它只是重复相同的子字符串。相反，我们可以只计算子字符串中的出现次数，并通过该子字符串重复的次数来预测总数。

Answer 2

正如其他答案中已经指出的那样，您不需要构建最终字符串。这是我的解决方案：public static void main(String[] args){&nbsp; &nbsp; String s = "abcacas";&nbsp; &nbsp; long n = 1000000;&nbsp; &nbsp; long count = getCount(s, n, 'a');&nbsp; &nbsp; System.out.println(count);}private long getCount(String str, long n, char c) {&nbsp; &nbsp; int length = str.length();&nbsp; &nbsp; long repeats = n / length;&nbsp; &nbsp; long reminder = n % length;&nbsp; &nbsp; long count = 0;&nbsp; &nbsp; for (int i = 0; i < length; i++) {&nbsp; &nbsp; &nbsp; &nbsp; if (str.charAt(i) == c) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count += repeats;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (i < reminder) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return count;}

Answer 3

您不需要构建最终字符串。您只需要计算s字符串中 'a'（或任何您想要的）的出现次数，并计算它s重复了多少次。毕竟，计算提醒中“a”的出现次数。long countInS = // count all occurances of 'a'long repeats = n / s.length;long reminder = n % s.length;String sReminder = s.substring(reminder);long countInReminder = // count all occurances of 'a' in sReminder&nbsp;long count = repeats * countInS + countInReminder;无需浪费您的 RAM