#C53. 华为OD机试统一考试D卷C卷 - 连续字母长度

华为OD机试统一考试D卷C卷 - 连续字母长度

题目链接

华为OD机试统一考试D卷C卷 - 连续字母长度(C++ Java JavaScript Python)

https://blog.csdn.net/banxia_frontend/article/details/134841278

题目描述

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

输入描述

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

第二行为 k的值

输出描述

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

用例1

输入

AAAAHHHBBCDHHHH
3

输出

2

说明

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

用例2

输入

AABAAA
2

输出

1

说明

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

用例3

输入

ABC
4

输出

-1

说明 只含有3个包含同一字母的子串,小于k,输出-1

用例4

输入

ABC
2

输出

1

说明 三个子串长度均为1,所以此时k = 1,k=2,k=3这三种情况均输出1。特此说明,避免歧义。

C++

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <regex>
using namespace std;


int main() {
  string str;
  int k = 0;
  cin >> str;
  cin >> k;
  unordered_set<char> charSet;  
  for (char c : str) {
    charSet.insert(c);
  }
  unordered_map<char, int> charMap;  
  for (char c : charSet) { 
    const regex reg(string(1, c) + "+"); 
    sregex_iterator it(str.begin(), str.end(), reg);
    while (it != sregex_iterator()) {
      int repeatTimes = it->str().length();
      charMap[c] = charMap.count(c) ? max(charMap[c], repeatTimes) : repeatTimes;
      ++it;
    }
  }
  vector<int> values;
  for (auto it : charMap) {
    values.push_back(it.second);
  }
  sort(values.begin(), values.end(), greater<int>());
  int rt = k > values.size() ? -1 : values[k - 1];
  cout << rt << endl;
  return 0;
}

java

import java.util.Scanner;
import java.util.HashSet;
import java.util.HashMap;
import java.util.regex.Pattern;
import java.util.regex.Matcher;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String str = input.next();
        int k = input.nextInt();
        HashSet<Character> charSet = new HashSet<>();
        for (char c : str.toCharArray()) {
            charSet.add(c);
        }
        HashMap<Character, Integer> charMap = new HashMap<>();
        for (char c : charSet) {
            Pattern pattern = Pattern.compile(String.valueOf(c) + "+");
            Matcher matcher = pattern.matcher(str);
            while (matcher.find()) {
                int repeatTimes = matcher.group().length();
                if (charMap.containsKey(c)) {
                    charMap.put(c, Math.max(charMap.get(c), repeatTimes));
                } else {
                    charMap.put(c, repeatTimes);
                }
            }
        }
        ArrayList<Integer> values = new ArrayList<>(charMap.values());
        Collections.sort(values, Collections.reverseOrder());
        int rt = k > values.size() ? -1 : values.get(k - 1);
        System.out.println(rt);
    }
}

javaScript

 
const { listeners } = require("process");
const readline = require("readline");
const { isNumber } = require("util");
 
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
 
rl.on("line", (str) => {
 rl.on("line", (k) => {

 let set = new Set(str);
  let obj = {};
  for (let letter of set) {
    const reg = new RegExp(`${letter}+`, "g");
 
    while (true) {
      let res = reg.exec(str);
      if (res === null) {
        break;
      } else {
        let repeatTimes = res[0].length;
        obj[letter] = obj[letter]
          ? Math.max(obj[letter], repeatTimes)
          : repeatTimes;
      }
    }
  }
let res=Object.values(obj).sort((a, b) => b - a)[k - 1] ?? -1;
    console.log( res )

});


});
 

python

import re

str = input()
k = int(input())
charSet = set(str)
charMap = {}
for c in charSet:
    reg = re.compile(c + "+")
    it = re.finditer(reg, str)
    for match in it:
        repeatTimes = len(match.group())
        if c in charMap:
            charMap[c] = max(charMap[c], repeatTimes)
        else:
            charMap[c] = repeatTimes
values = list(charMap.values())
values.sort(reverse=True)
rt = -1 if k > len(values) else values[k-1]
print(rt)

C语言

#include <stdio.h>
#include <string.h>

int main() {
    char str[101]; // 存储输入的字符串,最大长度100
    int k, charMaxCount[26] = {0}, count = 0, maxCount = 0;
    scanf("%s", str); // 读取字符串
    scanf("%d", &k); // 读取k的值

    // 计算每个字符的最大连续出现次数
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        if (i == 0 || str[i] != str[i - 1]) {
            count = 1; // 如果当前字符和前一个字符不同,重置计数器
        } else {
            count++; // 如果当前字符和前一个字符相同,增加计数器
        }

        int index = str[i] - 'A'; // 将字符转换为索引(0-25)
        if (count > charMaxCount[index]) {
            charMaxCount[index] = count; // 更新字符的最大连续出现次数
        }
    }

    // 将连续出现次数存储在数组中,并排序
    int counts[26], j = 0;
    for (int i = 0; i < 26; i++) {
        if (charMaxCount[i] > 0) {
            counts[j++] = charMaxCount[i];
        }
    }

    // 冒泡排序
    for (int i = 0; i < j - 1; i++) {
        for (int p = 0; p < j - i - 1; p++) {
            if (counts[p] < counts[p + 1]) {
                int temp = counts[p];
                counts[p] = counts[p + 1];
                counts[p + 1] = temp;
            }
        }
    }

    // 输出结果
    if (k > j) {
        printf("-1\n"); // 如果k大于数组长度,输出-1
    } else {
        printf("%d\n", counts[k - 1]); // 输出第k多的字符的次数
    }

    return 0;
}

完整用例

用例1

AAAAHHHBBCDHHHH
3

用例2

ABCDDEFG
1

用例3

ABC
4

用例4

HHHHHHHHH
5

用例5

AAABBBCCC
2

用例6

ABBBCCCCCDDDDEEEEEE
4

用例7

AABBCCDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ
10

用例8

AAABBBCCCDDDEEEFFFGGGHHHIIIIJJJKKKLLLMMMNNNNOOO
3

用例9

AAAABBBBCCCCDDDDDEEEEEFFFFFGGGGGHHHHHIIIIIJJJJJ
2

用例10

ABCDEFGHHHHHHIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
1

@[TOC]

fengmian