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

华为OD机试 - 连续字母长度 - 字符串（Java 2023 B卷 100分）

news 2025/7/21 17:12:43

在这里插入图片描述

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

给定一个字符串，只包含大写字母，求在包含同一字母的子串中，长度第 k 长的子串的长度，相同字母只取最长的那个子串。

二、输入描述

第一行有一个子串(1<长度<=100)，只包含大写字母。

第二行为 k的值

三、输出描述

输出连续出现次数第k多的字母的次数。

例如：

1、输入

AAAAHHHBBCDHHHH
3

2、输出

3、说明

同一字母连续出现的最多的是A和H，四次；
第二多的是H，3次，但是H已经存在4个连续的，故不考虑；
下个最长子串是BB，所以最终答案应该输出2

4、再输入

AABAAA
2

5、输出

6、说明

同一字母连续出现的最多的是A，三次；
第二多的还是A，两次，但A已经存在最大连续次数三次，故不考虑；
下个最长子串是B，所以输出1。

四、解题思路

本题的关键是理解“相同字母只取最长的那个子串”。

遍历输入字符串，获取每个字母最长的字符串；
再将其按照字符串长度降序排序；
获取连续出现次数第k多的字母的个数；

五、Java算法源码

package com.guor.od;import java.util.*;public class OdTest02 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String input = sc.nextLine();int index = Integer.valueOf(sc.nextLine());// 首字母连续字符串String firstSameStr = getSameChar(input);// 记录某字符的最大长度Map<Character, Integer> map = new HashMap<Character, Integer>();map.put(firstSameStr.charAt(0), firstSameStr.length());while (input.substring(firstSameStr.length()).length() > 0) {input = input.substring(firstSameStr.length());firstSameStr = getSameChar(input);// 如果map中没有此字符if (!map.containsKey(firstSameStr.charAt(0))) {map.put(firstSameStr.charAt(0), firstSameStr.length());continue;}// 获取某字符的最大长度if (map.get(firstSameStr.charAt(0)) < firstSameStr.length()) {map.put(firstSameStr.charAt(0), firstSameStr.length());}}// 存储相同字母最常的那个字符串List<String> list = new ArrayList<String>();for(Map.Entry<Character, Integer> entry : map.entrySet()){Character key = entry.getKey();Integer value = entry.getValue();StringBuilder builder = new StringBuilder();for (int i = 0; i < value; i++) {builder.append(key);}list.add(builder.toString());}// 按相同字符长度降序排列list.sort(new Comparator<String>() {@Overridepublic int compare(String o1, String o2) {if (o1.length() > o2.length()) {return -1;}else if (o1.length() < o2.length()) {return 1;}else {return 0;}}});System.out.println(list);// 输出连续出现次数第k多的字母的次数System.out.println(list.get(index - 1).length());}// 获取首字母连续字符串public static String getSameChar(String str) {StringBuilder builder = new StringBuilder();char first = str.charAt(0);builder.append(first);for (int i = 1; i < str.length(); i++) {if(first != str.charAt(i)){break;}builder.append(str.charAt(i));}return builder.toString();}
}