当前位置: 首页 > news >正文

【蓝桥杯】历届真题 重复字符串(省赛)Java

资源限制

内存限制:256.0MB   C/C++时间限制:1.0s   Java时间限制:3.0s   Python时间限制:5.0s

问题描述
        如果一个字符串 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.length; i++){
			arr[i] = 0;
		}
		
		for(int i=0; i<len/k; i++){
			for(int j=i; j<len; j+=(len/k)){
				temp = (int)(c[j]-'a');
				arr[temp]++;
			}
			for(int m=0; m<arr.length; m++){
				if(arr[m]>max){
					max = arr[m];
				}
			}
			sum += (k-max);
			max = 0;
			for(int n = 0; n<arr.length; n++){
				arr[n]=0;
			}
		}
		System.out.println(sum);
	}
}

相关文章:

  • 数据结构初级<排序>
  • Pr 计时器动画
  • 让你彻底明白Java SPI与SpringBoot自动配置,内附实例代码演示
  • 【Uniapp】四、运行环境、终端及组件通信(完结)
  • LeetCode(Array)1365. How Many Numbers Are Smaller Than the Current Number
  • 云原生技能树-docker image 操作-练习篇
  • hids Elastic Security 系列1-Elastic Security介绍
  • 2022 自杀式年度总结(已发老板)
  • [创业之路-46] :动态股权机制 -1- 七步法(流程)
  • Python 实现 JSON 解析器
  • 【数据结构】万字深入浅出讲解顺序表(附原码 | 超详解)
  • Allegro如何设计线圈操作指导
  • c程序gcc编译常见报错及解决方法整理
  • SSH (Secure Shell)
  • 《蓝桥杯》30天拿下Python算法设计与分析【Day 11】
  • PyTorch初学者指南:数据预处理
  • Ribbon策略改变实现步骤(基于Eureka服务注册中心)
  • LeetCode和牛客网二叉树经典例题合集
  • C语言中的数组初始化常见方法
  • DT-6_TTL-WiFi透传模块介绍