蓝桥杯|历届真题:重复字符串

jupiter
2022-03-19 / 0 评论 / 616 阅读 / 正在检测是否收录...
温馨提示:
本文最后更新于2022年03月19日,已超过819天没有更新,若内容或图片失效,请留言反馈。

1.题目

【问题描述】
如果一个字符串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 \leq K \leq 100000,1 \leq |S| \leq 100000$。其中$|S|$表示$S$的长度。

2. 题解

2.1 思路分析

先判断字符串长度是否是K的整数倍,不是则输出-1
若是,则将字符串分为K组,对每组的第i位统计得到各字符出现次数的最大值maxAppear
    则要想将该字符串变为重复字符串在第i位上需要修改的最少的次数为K-maxAppear
对每一位需要做的最小修改进行求和即可得到最终的结果

2.2 代码实现

import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);
    
    public static void main(String[] args) {
        int K = scanner.nextInt();
        String str = scanner.next();

        int len = str.length();
        char[] strChars = str.toCharArray();

        if(len%K!=0){
            System.out.println(-1);
        }else {
            int minChange = 0;

            int groupLen = len/K;

            for (int i = 0; i < groupLen; i++) {//将字符串分成K组
                // 统计每组字符串第j位的哪个字符出现的次数最多得到次数
                int maxAppear = 0;
                int[] charCounter = new int[26];
                for (int j = 0; j < 26; j++) {
                    charCounter[j]=0;
                }
                for (int j = 0; j < K; j++) {
                    int tmpIndex = (int)(strChars[j*groupLen+i]-'a');
                    charCounter[tmpIndex] += 1;
                }

                for (int j = 0; j < 26; j++) {
                    maxAppear = Math.max(maxAppear,charCounter[j]);
                }
                minChange += (K-maxAppear);
            }
            System.out.println(minChange);
        }

    }
}

2.3 提交结果

1正确10.0062ms22.22MB输入 输出
2正确10.0093ms22.30MBVIP特权
3正确10.00109ms22.30MBVIP特权
4正确10.0093ms22.26MBVIP特权
5正确10.00109ms22.23MBVIP特权
6正确10.0078ms22.29MBVIP特权
7正确10.00140ms22.99MBVIP特权
8正确10.00171ms25.62MBVIP特权
9正确10.00125ms25.64MBVIP特权
10错误0.00125ms24.57MBVIP特权
暂未看出错在哪了

参考资料

  1. http://lx.lanqiao.cn/problem.page?gpid=T2890
0

评论 (0)

打卡
取消