蓝桥杯 java 重复字符串

发布时间:2024年01月17日
题目描述
* 如果一个字符串S恰好可以由某个字符串重复K次得到,我们就称S是K次重复字符串。
* 例如 abcabcabc 可以看作是 abc重复3次得到,所以 abcabcabc 是3次重复字符串。
* 同理 aaaaaa 既是2次重复字符串、又是3次重复字符串和6次重复字符串。
* 现在给定一个字符串S,请你计算最少要修改其中几个字符可以使S变为一个K次字符串?
* 无法修改成重复字符串就输出 -1
* 思路:
* 1:如果出现了无法修改就输出-1这种题 我们就先思考怎样会无解
* -- 那什么情况下会无解?
* --如果字符串s是k次字符串 那么s的长度就肯定是k的倍数
* --如果不是倍数 那就无解

* 2:怎样才能是操作最少次?
* --寻找出现次数最多的字符 然后把其他字符全部变为出现次数最多的字符
* --比如有字符串:abcdabcdabcd  是三次字符串
* --那么第一个字符肯定就和第四个字符相同
* --那么第二个字符肯定就和第六个字符相同
* --类推
* --第一个字符串 和 1+k个字符 和1+2k个字符都要一样
* --第二个字符串 和 2+k个字符 和2+2k个字符都要一样
* --类推

* 列题:比如:a b c a b c c c a 我怎么变?
* --找到出现次数最多的字符然后把其他的都变为出现最多的字符
* --这里如果变c 就只操作五次 变其他的 操作的次数就更多
package LqJava._课程代练.第三章.test6;

import java.util.Arrays;
import java.util.Scanner;

public class 重复字符串 {
    static int[] cnt = new int[26];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 是k次字符串
        int k = sc.nextInt();
        // 字符
        char[] s = sc.next().toCharArray();
        // 字符长度
        int n = s.length;

        // 无解的情况
        if (n % k != 0) {
            System.out.println(-1);
            return;
        }

        // 以第一个字符串 和 1+k个字符 和1+2k个字符都要一样
        // 我们会分为几组?是不是就是k组
        // 第一组就是下标0开始 第二组1 类推到最后一组就是k-1


        // 每一组内有t个元素
        int t = n / k;
        int ans = 0;
        // 1:枚举开头
        for (int i = 0; i < k; i++) {
            // cnt是全局变量 每一组要把它清空
            Arrays.fill(cnt,0);
            // 枚举组内所有的元素
            //  2:存元素记录大小第一个元素从第一组开始 j=i j<字符串长度 j+=k 第一个元素为j 下一个元素就是j+k 所以是j+=k
            for (int j = i; j < n; j += k) {
                cnt[s[j] - 'a']++;
            }
            // 3:最多的字符出现的次数
            int max = 0;
            for (int j = 0; j < 26; j++) {
                max = Math.max(max, cnt[j]);
            }
            //
            ans += t - max;
        }
        System.out.println(ans);
    }
}

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