华为OD机试真题---连续字母长度
针对华为OD机试中的“连续字母长度”这一题目,以下是对题目的详细解析及解答方法:
题目描述
给定一个字符串Q,该字符串只包含大写字母。要求找出在包含同一字母的子串中,长度第k长的子串的长度,相同字母只取最长的子串。若子串中只包含同一字母的子串数小于k,则输出-1。
输入与输出
-
输入:
- 第一行是一个字符串(长度小于100),只包含大写字母。
- 第二行是一个整数,表示k的值。
-
输出:
- 输出连续出现次数第k多的字母的次数。
示例
-
示例1:
- 输入:
AAAAHHHBBCDHHHH
3 - 输出:2
- 说明:A和H出现4次,H(作为第二个最长连续字母子串出现次数,但由于与最长重复,故不计入统计)出现3次(重复),B出现2次,C和D出现1次。第二多的是2次。
- 输入:
-
示例2:
- 输入:
ABCD
5 - 输出:-1
- 说明:k的值超过字符串长度,且不存在5个连续相同字母的子串。
- 输入:
解题思路
- 使用字典(或哈希表)来记录每个字母连续出现的最大长度。
- 遍历字符串,当遇到新的字母或字符串结束时,更新字典中该字母的连续长度。
- 遍历完成后,将字典中的值(即连续长度)存入列表,并按降序排序。
- 根据k的值输出对应的连续长度,若k大于列表长度,则输出-1。
代码实现(java)
package cn.gov.test.gt4.swjggl.leetcode;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class ContinuousLetterLength {
public static int findKthLongestSubstring(String s, int k) {
// 增加输入验证
if (s == null || s.isEmpty() || k <= 0) {
return -1; // 当输入非法时直接返回-1
}
// 使用HashMap来记录每个字母连续出现的最大长度
Map<Character, Integer> maxLengths = new HashMap<>();
int maxLength = 0; // 记录当前遇到的最长连续长度
char currentChar = '\0'; // 当前正在统计的字符
// 遍历字符串,统计每个字符的连续长度
for (char c : s.toCharArray()) {
if (c != currentChar) {
// 如果遇到新字符,更新maxLengths并重置maxLength和currentChar
if (currentChar != '\0') {
maxLengths.put(currentChar, maxLength);
maxLength = 0; // 重置maxLength为0,为下一个字符的统计做准备
}
currentChar = c; // 更新currentChar为新字符
}
maxLength++; // 当前字符的连续长度加1
}
// 不要忘记处理字符串末尾的字符
if (currentChar != '\0') {
maxLengths.put(currentChar, maxLength);
}
// 将maxLengths中的值放入List,并按降序排序
List<Integer> lengths = new ArrayList<>(maxLengths.values());
lengths.sort(Collections.reverseOrder());
// 根据k值返回对应的连续长度或-1
return k <= lengths.size() ? lengths.get(k - 1) : -1;
}
public static void main(String[] args) {
String s1 = "AAAAHHHBBCDHHHH";
int k1 = 3;
System.out.println(findKthLongestSubstring(s1, k1)); // 输出: 2
String s2 = "ABCD";
int k2 = 5;
System.out.println(findKthLongestSubstring(s2, k2)); // 输出: -1
}
}
运行步骤详细解析
1、初始化输入数据:
- String s1 = “AAAAHHHBBCDHHHH”;
- int k1 = 3;
- String s2 = “ABCD”;
- int k2 = 5;
2、调用 findKthLongestSubstring 方法: - 对于 s1 和 k1:
- 输入:“AAAAHHHBBCDHHHH” 和 3
- 输出:2
- 对于 s2 和 k2:
- 输入:“ABCD” 和 5
- 输出:-1
3、具体运行过程:
- 输出:-1
- 对于 s1 = “AAAAHHHBBCDHHHH” 和 k1 = 3:
- 字符串 “AAAAHHHBBCDHHHH” 中连续子串的长度分别为:
- ‘A’:4
- ‘H’:3
- ‘B’:2
- ‘C’:1
- ‘D’:1
- ‘H’:4
- 排序后的连续子串长度为 [4, 4, 3, 2, 1, 1]
- 第 3 长的连续子串长度为 2
- 字符串 “AAAAHHHBBCDHHHH” 中连续子串的长度分别为:
- 对于 s2 = “ABCD” 和 k2 = 5:
- 字符串 “ABCD” 中连续子串的长度分别为:
- ‘A’:1
- ‘B’:1
- ‘C’:1
- ‘D’:1
- 字符串 “ABCD” 中连续子串的长度分别为:
- 排序后的连续子串长度为 [1, 1, 1, 1]
- 由于 k2 = 5 大于实际长度 4,因此返回 -1
原文地址:https://blog.csdn.net/lbp0123456/article/details/142650721
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!