文章目录相关推荐阅读题目描述与示例题目描述输入描述输出描述示例输入输出解题思路滑窗三问滑窗三答代码PythonJavaCCNode JavaScriptGo时空复杂度华为OD算法/大厂面试高频题算法练习冲刺训练相关推荐阅读【华为OD机考正在更新】2025年双机位A卷真题【完全原创题解 | 详细考点分类 | 不断更新题目 | 六种主流语言PyJavaCppCJsGo】【华为OD机考】2025C2025B2024ED卷真题【完全原创题解 | 详细考点分类 | 不断更新题目】【华为OD笔试】双机位A2025C2025B2024ED卷真题机考套题汇总【真实反馈不断更新限时免费】【华为OD笔试】2024ED卷命题规律解读【分析500场OD笔试考点总结】【华为OD流程】性格测试选项注意事项】题目练习网址【固定滑窗】双机位A-字符串计数匹配题目描述与示例题目描述给你一个字符串str和整数k返回满足以下条件的所有子字符串个数恰好包含k个字母。数字0-9各出现至少一次。输入描述第一行字符串str (1 ≤ length ≤ 100000)仅包含数字和小写字母第二行为整数k (0 ≤ k ≤100000 )输出描述输出一个整数表示满足所有条件的子字符串的个数。示例输入a0123456789aa 1输出2解题思路由于符合要求的子串必然包含10个数字0-9恰好各自出现一次和k个字母且原字符串s仅包含数字和小写字母不包含其他特殊字符因此符合要求的子串的长度必然为k10。因此我们可以构建一个长度为win_len k10的窗口通过固定滑窗过程来解决该问题。为了判断子串中数字是否都恰好出现一次我们可以构建一个长度为10的列表cnt_num_win来储存窗口中出现的数字个数。其中cnt_num_win[i]就表示数字i在窗口中出现的次数。考虑滑动窗口三问三答滑窗三问Q1对于每一个右指针right所指的元素ch做什么操作Q2什么时候要令左指针left右移对于left所指的元素left_ch要做什么操作Q3什么时候进行ans的更新如何更新滑窗三答A1如果ch是数字则更新cnt_num_win[ch] 1表示ch在窗口中出现的次数增加1。A2移除窗口的left right - win_len。如果ch_left是数字则更新cnt_num_win[ch_left] - 1表示ch_left在窗口中出现的次数减少1。A3如果cnt_num_win中的所有元素均为1则说明0-9这10个数字在窗口中出现的次数恰好均为1更新答案。当ch或ch_left为字母时无需做任何操作。代码Python# 题目【固定滑窗】双机位A-字符串计数匹配# 分值100# 作者闭着眼睛学数理化# 算法固定滑窗# 代码看不懂的地方请直接在群上提问# 用于检查长度为10的列表cnt中所有元素是否为1的函数# 如果cnt中所有元素都为1则返回1否则返回0defcheck(cnt):returnint(all(num1fornumincnt))# 输入原字符串sinput()# 输入k值kint(input())# 固定滑窗的窗口长度为k10win_lenk10# 构建长度为10的列表用来记录窗口中的数字个数# cnt[i]就表示数字i的出现次数cnt[0]*10# 初始化第一个窗口的情况forchins[:win_len]:# 如果ch是数字ifch.isdigit():# 则令ch在cnt中的计数1cnt[int(ch)]1# 初始化答案变量# 如果第一个窗口中0-9这些数字出现次数均为1则初始化ans为1# 否则初始化为0anscheck(cnt)# 固定滑窗过程forright,chinenumerate(s[win_len:],win_len):# A1ifch.isdigit():cnt[int(ch)]1# A2leftright-win_len ch_lefts[left]ifch_left.isdigit():cnt[int(ch_left)]-1# A3anscheck(cnt)print(ans)Javaimportjava.util.*;publicclassMain{// 用于检查长度为10的数组 cnt 中所有元素是否为1的函数// 如果 cnt 中所有元素都为1则返回1否则返回0publicstaticintcheck(int[]cnt){for(intnum:cnt){if(num!1)return0;}return1;}publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);// 输入原字符串Stringssc.nextLine();// 输入 k 值intksc.nextInt();// 固定滑窗的窗口长度为 k10intwinLenk10;// 构建长度为10的数组用来记录窗口中的数字个数// cnt[i] 就表示数字 i 的出现次数int[]cntnewint[10];// 初始化第一个窗口的情况for(inti0;iMath.min(winLen,s.length());i){charchs.charAt(i);// 如果 ch 是数字if(Character.isDigit(ch)){cnt[ch-0];}}// 初始化答案变量// 如果第一个窗口中0-9这些数字出现次数均为1则初始化ans为1否则初始化为0intanscheck(cnt);// 固定滑窗过程for(intrightwinLen;rights.length();right){charchs.charAt(right);// A1if(Character.isDigit(ch)){cnt[ch-0];}// A2intleftright-winLen;charchLefts.charAt(left);if(Character.isDigit(chLeft)){cnt[chLeft-0]--;}// A3anscheck(cnt);}System.out.println(ans);}}C#includeiostream#includestring#includevectorusingnamespacestd;// 用于检查长度为10的数组 cnt 中所有元素是否为1的函数// 如果 cnt 中所有元素都为1则返回1否则返回0intcheck(constvectorintcnt){for(intnum:cnt){if(num!1)return0;}return1;}intmain(){string s;getline(cin,s);// 输入原字符串intk;cink;// 输入 k 值// 固定滑窗的窗口长度为 k10intwin_lenk10;// 构建长度为10的数组用来记录窗口中的数字个数vectorintcnt(10,0);// 初始化第一个窗口的情况for(inti0;imin(win_len,(int)s.size());i){charchs[i];// 如果 ch 是数字if(isdigit(ch)){cnt[ch-0];}}// 初始化答案变量// 如果第一个窗口中0-9这些数字出现次数均为1则初始化ans为1否则初始化为0intanscheck(cnt);// 固定滑窗过程for(intrightwin_len;right(int)s.size();right){charchs[right];// A1if(isdigit(ch)){cnt[ch-0];}// A2intleftright-win_len;charch_lefts[left];if(isdigit(ch_left)){cnt[ch_left-0]--;}// A3anscheck(cnt);}coutansendl;return0;}C#includestdio.h#includestring.h#includectype.h// 用于检查长度为10的数组 cnt 中所有元素是否为1的函数// 如果 cnt 中所有元素都为1则返回1否则返回0intcheck(intcnt[10]){for(inti0;i10;i){if(cnt[i]!1)return0;}return1;}intmain(){chars[100005];// 输入原字符串fgets(s,sizeof(s),stdin);s[strcspn(s,\n)]\0;// 去除换行符intk;// 输入 k 值scanf(%d,k);// 固定滑窗的窗口长度为 k10intwin_lenk10;// 构建长度为10的数组用来记录窗口中的数字个数intcnt[10]{0};intnstrlen(s);// 初始化第一个窗口的情况for(inti0;iwin_lenin;i){charchs[i];// 如果 ch 是数字if(isdigit(ch)){cnt[ch-0];}}// 初始化答案变量// 如果第一个窗口中0-9这些数字出现次数均为1则初始化ans为1否则初始化为0intanscheck(cnt);// 固定滑窗过程for(intrightwin_len;rightn;right){charchs[right];// A1if(isdigit(ch)){cnt[ch-0];}// A2intleftright-win_len;charch_lefts[left];if(isdigit(ch_left)){cnt[ch_left-0]--;}// A3anscheck(cnt);}printf(%d\n,ans);return0;}Node JavaScript// Node.js 固定滑窗实现 - 字符串计数匹配constreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});letinputLines[];rl.on(line,lineinputLines.push(line.trim())).on(close,(){constsinputLines[0];// 输入原字符串constkparseInt(inputLines[1]);// 输入 k 值console.log(solve(s,k));});// 检查长度为10的数组 cnt 中所有元素是否为1的函数functioncheck(cnt){for(letnumofcnt){if(num!1)return0;}return1;}functionsolve(s,k){// 固定滑窗的窗口长度为 k10constwinLenk10;// 构建长度为10的数组用来记录窗口中的数字个数constcntArray(10).fill(0);// 初始化第一个窗口的情况for(leti0;iMath.min(winLen,s.length);i){constchs[i];// 如果 ch 是数字if(/\d/.test(ch)){cnt[parseInt(ch)];}}// 初始化答案变量// 如果第一个窗口中0-9这些数字出现次数均为1则初始化ans为1否则初始化为0letanscheck(cnt);// 固定滑窗过程for(letrightwinLen;rights.length;right){constchs[right];// A1if(/\d/.test(ch)){cnt[parseInt(ch)];}// A2constleftright-winLen;constchLefts[left];if(/\d/.test(chLeft)){cnt[parseInt(chLeft)]--;}// A3anscheck(cnt);}returnans;}Gopackagemainimport(bufiofmtosstrconvstrings)// 用于检查长度为10的数组 cnt 中所有元素是否为1的函数// 如果 cnt 中所有元素都为1则返回1否则返回0funccheck(cnt[10]int)int{for_,num:rangecnt{ifnum!1{return0}}return1}funcmain(){in:bufio.NewScanner(os.Stdin)in.Buffer(make([]byte,0,1024),120)// 放大缓冲防止长行被截断// 输入原字符串if!in.Scan(){return}s:strings.TrimSpace(in.Text())// 输入 k 值if!in.Scan(){return}kStr:strings.TrimSpace(in.Text())k,_:strconv.Atoi(kStr)// 固定滑窗的窗口长度为 k10winLen:k10// 构建长度为10的数组用来记录窗口中的数字个数varcnt[10]intn:len(s)// 初始化第一个窗口的情况limit:winLeniflimitn{limitn}fori:0;ilimit;i{ch:s[i]// 如果 ch 是数字ifch0ch9{cnt[ch-0]}}// 初始化答案变量// 如果第一个窗口中0-9这些数字出现次数均为1则初始化ans为1否则初始化为0ans:check(cnt)// 固定滑窗过程forright:winLen;rightn;right{// A1ch:s[right]ifch0ch9{cnt[ch-0]}// A2left:right-winLen chLeft:s[left]ifchLeft0chLeft9{cnt[chLeft-0]--}// A3anscheck(cnt)}fmt.Println(ans)}时空复杂度时间复杂度O(n)。仅需一次遍历原字符串空间复杂度O(1)。仅需长度为10的列表cnt来维护固定滑窗过程可视为常数空间复杂度。华为OD算法/大厂面试高频题算法练习冲刺训练华子OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名目前已服务1000同学成功上岸课程讲师为全网200w粉丝编程博主吴师兄学算法以及小红书头部编程博主闭着眼睛学数理化90天陪伴式学习100直播课时300动画图解视频500LeetCode经典题500华为OD真题/大厂真题还有简历修改、模拟面试、陪伴小群、资深HR对接将为你解锁
