【蓝桥杯】历届真题 重复字符串

来源：郑州童程童美少儿编程培训机构时间：2023/12/11 14:50:03

　　如果一个字符串 S 恰好可以由某个字符串重复 K 次得到，我们就称 S 是K 次重复字符串。例如 “abcabcabc” 可以看作是 “abc” 重复 3 次得到，所以“abcabcabc” 是 3 次重复字符串。同理 “aaaaaa” 既是 2 次重复字符串、又是 3 次重复字符串和 6 次重复字符串。

　　现在给定一个字符串 S ，请你计算较少要修改其中几个字符，可以使 S 变为一个 K 次字符串?

　　【输入格式】

　　输入行包含一个整数 K。

　　第二行包含一个只含小写字母的字符串 S 。

　　【输出格式】

　　输出一个整数代表答案。如果 S 无法修改成 K 次重复字符串，输出 − 1。

　　【样例输入】

　　2

　　aabbaa

　　【样例输出】

　　2

　　【评测用例规模与约定】

　　对于所有评测用例，1 ≤ K ≤ 100000, 1 ≤ | S | ≤ 100000。其中 | S | 表示 S 的

　　长度。

　　【前言】

　　这道题在解的过程中发现了点问题，可能是测试用例的问题。

　　因题中所说的是：如果s无法修改成k次重复字符串，输出-1，所以在较开始判断一下。

　　if(len%k != 0){

　　System.out.println(-1);

　　return;

　　}

　　但加上上述代码后，只有90，较后一个测试用例拿不到分。

　　因此数据错误，不完整的循环节也输出了答案，例如 abcde 当 k 取 3 的时候，可以修改为 abc，这是不符合题意的。

　　如果非要过OJ，修改代码 -1 输出的条件为 length < k，且将字符串长度截断为abc即可。

　　【思路及分析】

　　若字母序列为aab，要让它们一样，只需要将b改为a即可，即变化成aaa。

　　由此可知，只需要找到这一列中哪个字母数较多的，那么剩下的字母都改为该字母是操作较少的。

　　因此，我们只需要统计每一个字母序列中出现次数较多的字母出现的次数即可，记为max，那么用该列的长度k减去max，即为该列需要更改的次数。

　　【代码】

　　import java.util.*;

　　public class Main{

　　public static void main(String[] args){

　　Scanner sc = new Scanner(System.in);

　　int k = sc.nextInt();

　　String str = sc.next();

　　char[] c = str.toCharArray();

　　int len = str.length();

　　if(len%k != 0){

　　System.out.println(-1);

　　return;

　　}

　　int sum = 0;

　　int max = 0;

　　int temp = 0;

　　int[] arr = new int[26];

　　for(int i=0; i

　　arr[i] = 0;

　　}

　　for(int i=0; i

　　for(int j=i; j

　　temp = (int)(c[j]-'a');

　　arr[temp]++;

　　}

　　for(int m=0; m

　　if(arr[m]>max){

　　max = arr[m];

　　}

　　}

　　sum += (k-max);

　　max = 0;

　　for(int n = 0; n

　　arr[n]=0;

　　}

　　}

　　System.out.println(sum);

　　}

　　}

尊重原创文章，转载请注明出处与链接：http://www.peixun360.com/2474/news/689541/违者必究！ 以上就是郑州童程童美少儿编程培训机构 小编为您整理 【蓝桥杯】历届真题 重复字符串的全部内容。