华为OD机考双机位C卷 - 字符串计数匹配（Java Python JS C/C++ GO ）-开发者社区

题目描述

给你一个字符串str和整数k，返回满足以下条件的所有子字符串个数：

恰好包含k个字母。
数字0-9各出现至少一次。

输入描述

第一行字符串str(1≤ length ≤ 100000),仅包含数字和小写字母
第二行为整数k(0 ≤ k ≤100000 )

输出描述

输出一个整数，表示满足所有条件的子字符串的个数。

子字符串是字符串中连续的非空字符序列

示例1

输入

a0123456789aa 1

输出

说明

解题思路

Java

importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);// 读取第一行输入，获取字符串strStringstr=scanner.nextLine();// 读取第二行输入，获取整数kintk=Integer.parseInt(scanner.nextLine());// 初始化计数器，用于统计满足条件的子字符串个数intcount=0;// 获取字符串的长度intn=str.length();// 特殊情况处理：当k=0时，即要求子字符串中不包含任何字母if(k==0){// 使用双指针方法，right指针逐步向右移动for(intleft=0,right=0;right<n;right++){// 创建数组用于记录每个数字(0-9)的出现次数int[]digits=newint[10];// 记录当前子字符串中字母的数量intletters=0;// 遍历从left到right的所有字符for(inti=left;i<=right;i++){charc=str.charAt(i);// 如果是字母，字母计数器加1if(c>='a'&&c<='z'){letters++;}// 如果是数字，对应数字的计数器加1elseif(c>='0'&&c<='9'){digits[c-'0']++;}}// 判断当前子字符串是否满足条件：不含字母且包含所有数字(0-9)if(letters==0&&allDigitsPresent(digits)){count++;}}}else{// 一般情况：当k>0时，需要恰好有k个字母的子字符串// 枚举所有可能的子字符串起始位置for(intleft=0;left<n;left++){// 创建数组用于记录每个数字(0-9)的出现次数int[]digits=newint[10];// 记录当前子字符串中字母的数量intletters=0;// 枚举所有可能的子字符串结束位置for(intright=left;right<n;right++){charc=str.charAt(right);// 如果是字母，字母计数器加1if(c>='a'&&c<='z'){letters++;// 优化：如果字母数量超过k，就不再继续扩展当前子字符串if(letters>k)break;}// 如果是数字，对应数字的计数器加1elseif(c>='0'&&c<='9'){digits[c-'0']++;}// 判断当前子字符串是否满足条件：恰好有k个字母且包含所有数字(0-9)if(letters==k&&allDigitsPresent(digits)){count++;}}}}// 输出结果System.out.println(count);}/** * 检查是否所有数字(0-9)都至少出现一次 * @param digits 记录数字出现次数的数组 * @return 如果所有数字都至少出现一次，返回true；否则返回false */privatestaticbooleanallDigitsPresent(int[]digits){// 检查每个数字是否都出现至少一次for(intdigit:digits){// 如果有任何一个数字的出现次数为0，返回falseif(digit==0)returnfalse;}// 所有数字都至少出现一次，返回truereturntrue;}}

Python

defall_digits_present(digits):""" 检查是否所有数字(0-9)都至少出现一次 Args: digits: 记录数字出现次数的列表 Returns: 如果所有数字都至少出现一次，返回True；否则返回False """fordigitindigits:ifdigit==0:returnFalsereturnTrue# 读取输入str_input=input()k=int(input())# 初始化计数器，用于统计满足条件的子字符串个数count=0n=len(str_input)# 特殊情况处理：当k=0时，即要求子字符串中不包含任何字母ifk==0:left=0# 使用双指针方法，right指针逐步向右移动forrightinrange(n):# 创建列表用于记录每个数字(0-9)的出现次数digits=[0]*10# 记录当前子字符串中字母的数量letters=0# 遍历从left到right的所有字符foriinrange(left,right+1):c=str_input[i]# 如果是字母，字母计数器加1if'a'<=c<='z':letters+=1# 如果是数字，对应数字的计数器加1elif'0'<=c<='9':digits[int(c)]+=1# 判断当前子字符串是否满足条件：不含字母且包含所有数字(0-9)ifletters==0andall_digits_present(digits):count+=1else:# 一般情况：当k>0时，需要恰好有k个字母的子字符串# 枚举所有可能的子字符串起始位置forleftinrange(n):# 创建列表用于记录每个数字(0-9)的出现次数digits=[0]*10# 记录当前子字符串中字母的数量letters=0# 枚举所有可能的子字符串结束位置forrightinrange(left,n):c=str_input[right]# 如果是字母，字母计数器加1if'a'<=c<='z':letters+=1# 优化：如果字母数量超过k，就不再继续扩展当前子字符串ifletters>k:break# 如果是数字，对应数字的计数器加1elif'0'<=c<='9':digits[int(c)]+=1# 判断当前子字符串是否满足条件：恰好有k个字母且包含所有数字(0-9)ifletters==kandall_digits_present(digits):count+=1# 输出结果print(count)

JavaScript

// 引入readline模块用于读取输入constreadline=require('readline');constrl=readline.createInterface({input:process.stdin,output:process.stdout});letinputLines=[];letlineCount=0;// 检查是否所有数字(0-9)都至少出现一次functionallDigitsPresent(digits){for(letdigitofdigits){if(digit===0)returnfalse;}returntrue;}// 读取输入rl.on('line',(line)=>{inputLines.push(line);lineCount++;if(lineCount===2){conststr=inputLines[0];constk=parseInt(inputLines[1]);letcount=0;constn=str.length;// 特殊情况处理：当k=0时，即要求子字符串中不包含任何字母if(k===0){// 使用双指针方法，right指针逐步向右移动for(letleft=0,right=0;right<n;right++){// 创建数组用于记录每个数字(0-9)的出现次数constdigits=newArray(10).fill(0);// 记录当前子字符串中字母的数量letletters=0;// 遍历从left到right的所有字符for(leti=left;i<=right;i++){constc=str.charAt(i);// 如果是字母，字母计数器加1if(c>='a'&&c<='z'){letters++;}// 如果是数字，对应数字的计数器加1elseif(c>='0'&&c<='9'){digits[parseInt(c)]++;}}// 判断当前子字符串是否满足条件：不含字母且包含所有数字(0-9)if(letters===0&&allDigitsPresent(digits)){count++;}}}else{// 一般情况：当k>0时，需要恰好有k个字母的子字符串// 枚举所有可能的子字符串起始位置for(letleft=0;left<n;left++){// 创建数组用于记录每个数字(0-9)的出现次数constdigits=newArray(10).fill(0);// 记录当前子字符串中字母的数量letletters=0;// 枚举所有可能的子字符串结束位置for(letright=left;right<n;right++){constc=str.charAt(right);// 如果是字母，字母计数器加1if(c>='a'&&c<='z'){letters++;// 优化：如果字母数量超过k，就不再继续扩展当前子字符串if(letters>k)break;}// 如果是数字，对应数字的计数器加1elseif(c>='0'&&c<='9'){digits[parseInt(c)]++;}// 判断当前子字符串是否满足条件：恰好有k个字母且包含所有数字(0-9)if(letters===k&&allDigitsPresent(digits)){count++;}}}}// 输出结果console.log(count);rl.close();}});

C++

#include<iostream>#include<string>#include<vector>using namespace std;// 检查是否所有数字(0-9)都至少出现一次boolallDigitsPresent(constvector<int>&digits){for(intdigit:digits){if(digit==0)returnfalse;}returntrue;}intmain(){// 读取输入string str;intk;getline(cin,str);cin>>k;// 初始化计数器，用于统计满足条件的子字符串个数intcount=0;intn=str.length();// 特殊情况处理：当k=0时，即要求子字符串中不包含任何字母if(k==0){// 使用双指针方法，right指针逐步向右移动for(intleft=0,right=0;right<n;right++){// 创建向量用于记录每个数字(0-9)的出现次数vector<int>digits(10,0);// 记录当前子字符串中字母的数量intletters=0;// 遍历从left到right的所有字符for(inti=left;i<=right;i++){charc=str[i];// 如果是字母，字母计数器加1if(c>='a'&&c<='z'){letters++;}// 如果是数字，对应数字的计数器加1elseif(c>='0'&&c<='9'){digits[c-'0']++;}}// 判断当前子字符串是否满足条件：不含字母且包含所有数字(0-9)if(letters==0&&allDigitsPresent(digits)){count++;}}}else{// 一般情况：当k>0时，需要恰好有k个字母的子字符串// 枚举所有可能的子字符串起始位置for(intleft=0;left<n;left++){// 创建向量用于记录每个数字(0-9)的出现次数vector<int>digits(10,0);// 记录当前子字符串中字母的数量intletters=0;// 枚举所有可能的子字符串结束位置for(intright=left;right<n;right++){charc=str[right];// 如果是字母，字母计数器加1if(c>='a'&&c<='z'){letters++;// 优化：如果字母数量超过k，就不再继续扩展当前子字符串if(letters>k)break;}// 如果是数字，对应数字的计数器加1elseif(c>='0'&&c<='9'){digits[c-'0']++;}// 判断当前子字符串是否满足条件：恰好有k个字母且包含所有数字(0-9)if(letters==k&&allDigitsPresent(digits)){count++;}}}}// 输出结果cout<<count<<endl;return0;}

C语言

#include<stdio.h>#include<stdlib.h>#include<string.h>#include<stdbool.h>/** * 检查是否所有数字(0-9)都至少出现一次 * @param digits 记录数字出现次数的数组 * @return 如果所有数字都至少出现一次，返回true；否则返回false */boolallDigitsPresent(intdigits[10]){for(inti=0;i<10;i++){if(digits[i]==0)returnfalse;}returntrue;}intmain(){// 定义变量charstr[100001];// 字符串最大长度为100000intk;// 读取输入fgets(str,sizeof(str),stdin);// 移除换行符str[strcspn(str,"\n")]=0;scanf("%d",&k);// 初始化计数器，用于统计满足条件的子字符串个数intcount=0;intn=strlen(str);// 特殊情况处理：当k=0时，即要求子字符串中不包含任何字母if(k==0){// 使用双指针方法，right指针逐步向右移动for(intleft=0,right=0;right<n;right++){// 创建数组用于记录每个数字(0-9)的出现次数intdigits[10]={0};// 记录当前子字符串中字母的数量intletters=0;// 遍历从left到right的所有字符for(inti=left;i<=right;i++){charc=str[i];// 如果是字母，字母计数器加1if(c>='a'&&c<='z'){letters++;}// 如果是数字，对应数字的计数器加1elseif(c>='0'&&c<='9'){digits[c-'0']++;}}// 判断当前子字符串是否满足条件：不含字母且包含所有数字(0-9)if(letters==0&&allDigitsPresent(digits)){count++;}}}else{// 一般情况：当k>0时，需要恰好有k个字母的子字符串// 枚举所有可能的子字符串起始位置for(intleft=0;left<n;left++){// 创建数组用于记录每个数字(0-9)的出现次数intdigits[10]={0};// 记录当前子字符串中字母的数量intletters=0;// 枚举所有可能的子字符串结束位置for(intright=left;right<n;right++){charc=str[right];// 如果是字母，字母计数器加1if(c>='a'&&c<='z'){letters++;// 优化：如果字母数量超过k，就不再继续扩展当前子字符串if(letters>k)break;}// 如果是数字，对应数字的计数器加1elseif(c>='0'&&c<='9'){digits[c-'0']++;}// 判断当前子字符串是否满足条件：恰好有k个字母且包含所有数字(0-9)if(letters==k&&allDigitsPresent(digits)){count++;}}}}// 输出结果printf("%d\n",count);return0;}