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

华为OD机试 2023B卷题库疯狂收录中，刷题点这里

专栏导读

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

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

一、题目描述

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

二、输入描述

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

第二行为 k的值

三、输出描述

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

例如：

1、输入

AAAAHHHBBCDHHHH
3

2、输出

2

3、说明

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

4、再输入

AABAAA
2

5、输出

1

6、说明

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

四、解题思路

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

1. 遍历输入字符串，获取每个字母最长的字符串；
2. 再将其按照字符串长度降序排序；
3. 获取连续出现次数第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();}
}

六、效果展示

1、输入

AABBBCCCCCAAAAABB
3

2、输出

3

3、说明

AABBBCCCCCAAAAABB

（1）遍历输入字符串，获取每个字母最长的字符串

AAAAABBBCCCCC

（2）按照其字符串长度排序

AAAAACCCCCBBB

（3）获取第3长的字符的个数

即B的个数3。

🏆下一篇：华为OD机试真题 Java 实现【简易内存池】【2023 B卷 200分 考生抽中题】

🏆本文收录于，华为OD机试（JAVA）真题（A卷+B卷）

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