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

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){

    String s = "abcacas";

    long n = 1000000;

    long count = getCount(s, n, 'a');

    System.out.println(count);

}

private long getCount(String str, long n, char c) {

    int length = str.length();

    long repeats = n / length;

    long reminder = n % length;

    long count = 0;

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

        if (str.charAt(i) == c) {

            count += repeats;

            if (i < reminder) {

                count++;

            }

        }

    }

    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 

long count = repeats * countInS + countInReminder;

无需浪费您的 RAM