华为OD机考C卷“完美走位”题解：滑动窗口与计数条件的Java实现

华为OD机考C卷里有一道让不少人栽跟头的滑动窗口题叫完美走位。题目说的是机器人按 W、A、S、D 四个指令在二维平面上移动允许改掉一段连续的同长指令让机器人最终回到原点要求输出最短改写长度。第一次在双机位监考环境下碰到它时很多人的第一反应是不就是枚举子串吗结果写出来不是超时就是边界错。这篇文章会把题目还原、背后的数学条件推导、Java 的 ACM 模式完整实现、以及考场上怎么自测、怎么分配时间全部讲清楚。不管你是正在刷华为OD机试题、准备华为OD机试 C卷还是单纯想练滑动窗口这份攻略都能直接照着用。1. 题目还原回到原点等价于四种指令数量相等1.1 原题到底说了什么先完整还原一遍原题。机器人从坐标原点 (0,0) 出发输入一行字符串长度记为 n字符串只包含四个大写字母W向上走一步纵坐标 1S向下走一步纵坐标 -1A向左走一步横坐标 -1D向右走一步横坐标 1你只能修改其中一段连续的子串修改后的长度必须和原来一样子串里的每个字符都可以任意改成 W/A/S/D。要求修改之后机器人按照新的完整指令从头走一遍能回到原点求需要修改的子串的最短长度。这道题在华为 OD 机考 C 卷里一般出现在第二题的位置难度中等偏下考察的是字符串计数和滑动窗口两个基础能力。但因为是在 ACM 模式下手写完整 Java 代码加上双机位监考的紧张氛围实际通过率并不像题目本身看起来那么高。面经里经常有人吐槽思路对但代码跑不对问题基本都出在窗口边界和特判上。1.2 把移动问题翻译成计数问题回到原点这件事用坐标来想非常直接。设最终 W 出现了 countW 次、A 出现了 countA 次、S 出现了 countS 次、D 出现了 countD 次。机器人走完所有指令后横坐标 countD - countA所以横坐标回到 0 等价于 countD countA纵坐标 countW - countS所以纵坐标回到 0 等价于 countW countS两个条件加起来就是四个字符的最终出现次数全部相等。设每种字符出现 k 次那么 n 4kk n/4。这个 k 是整道题的锚点后面所有判断都以它为基准。如果 n 不能被 4 整除那不管怎么改都不可能让四种字符数量相等直接输出 -1 即可部分题目会保证 n 是 4 的倍数但代码里写上取模判断没有任何坏处。还有一个特判如果原始字符串本身已经满足四种字符数量相等答案就是 0。不要傻傻地进入滑动窗口逻辑之后才发现怎么窗口都能满足条件先把这个情况拦在前面代码会清爽很多。1.3 修改段与保留段的分工我们把被修改的连续子串记作窗口 [l, r]窗口外面的字符完全保留窗口里的字符可以随便改写。于是整个问题变成两个角色窗口外不可变的存量它决定了下限窗口内可自由调配的变量它负责补齐差额因为窗口内想填什么就填什么窗口内本身原来是什么样根本不重要。真正决定一个窗口是否可行的只有窗口外每种字符的数量。这个观察是整道题的分水岭很多人卡住就是因为一直在纠结窗口里的字符该怎么变其实只要算清楚窗口外窗口内一定填得满。2. 一条不等式判生死窗口外计数都不能超过 n/42.1 必要条件超过目标值的字符无法被消化假设窗口 [l, r] 的长度是 len窗口外 W/A/S/D 的数量分别是 c_W、c_A、c_S、c_D。由于窗口外的字符原封不动最终结果里 W 的总数至少是 c_W。如果 c_W 已经大于 n/4那么最终 W 的数量必然大于 n/4而其他三个字符的数量加起来最多是 n - c_W不够凑齐每个 n/4。所以窗口外任何字符数量超过 n/4这个窗口就是铁定非法的。2.2 充分条件只要没超过差额刚好被窗口补齐反过来想。如果窗口外的四种字符数量都不超过 n/4要让最终四种字符各 n/4 个还缺多少缺的数量是(n/4 - c_W) (n/4 - c_A) (n/4 - c_S) (n/4 - c_D) n - (c_W c_A c_S c_D)窗口外一共保留 n - len 个字符所以 c_W c_A c_S c_D n - len上面的算式结果正好就是 len。缺多少个字符窗口里恰好就有多少个位置可以补不多不少。这说明窗口外每种字符不超过 n/4 是一个充分条件。必要加充分就得到了窗口合法的充要条件窗口外四种字符数量的最大值小于等于 n/4。这一步可以说是整道题的题眼。一旦把它写出来问题就从如何修改字符彻底变成了找一个最短窗口挖掉之后剩余字符串里没有任何一种字符超过 n/4。2.3 代码里就是一行 max 判断代码层面我们用一个长度为 4 的 int 数组维护窗口外四种字符的数量每次判断 max(cnt[0], cnt[1], cnt[2], cnt[3]) target 即可。数组长度固定为 4这个判断是常数时间不会成为性能瓶颈。千万别用 HashMap 再遍历 keySet 去判断最大值属于能省则省机考时间很宝贵。3. 双指针怎么收敛右指针负责扩左指针负责缩3.1 暴力枚举为什么必挂最直白的做法是枚举所有窗口 [l, r]对每个窗口重新统计窗口外计数并判断条件复杂度 O(n²)。机考数据 n 动辄 10^5O(n²) 就是 10^10 级别必挂。所以必须利用条件随窗口大小单调变化这个性质。3.2 单调性滑动窗口成立的根观察窗口变大时会发生什么窗口外剩下的字符变少四种字符的最大值只会变小或不变也就是说合法条件只会从不成立变成成立。反过来窗口变小时窗口外字符变多条件只会从成立变成不成立。这种单向变化的单调性正是双指针滑动窗口可以放心使用的根本原因。3.3 右扩左缩的标准节奏具体节奏是右指针每次向右移动一格把新字符从窗外划入窗内对应的窗外计数减一。然后检查合法性如果窗口外所有字符数量都不超过 target说明当前窗口合法记录窗口长度并尝试把左指针向右移动把窗口左端的字符从窗内放回窗外窗外计数加一。只要移动后依然合法就继续移动并更新答案直到条件刚好被破坏。3.4 最容易翻车的三个细节细节一记录答案的时机必须是在 left 移动之前。每次 while 循环里先记录当前合法窗口的长度再执行 left这样才不会把合法窗口漏掉。如果先移动再判断记录下来的可能是已经不合法的长度答案就会偏小。细节二while 循环退出的原因一定是条件刚好被破坏。退出之后 left 停住右指针继续前进下一轮新的字符进入窗口后条件可能重新成立这个重新检查的过程由循环顶部的判断自动完成。细节三写循环前把特判做干净。如果初始字符串已经平衡直接输出 0如果 n 不是 4 的倍数直接输出 -1。否则滑动窗口逻辑里会混进各种缺省值的边界问题debug 起来非常难受。4. 完整 Java 解法ACM 模式代码与逐段拆解4.1 考前先背熟的 ACM 壳子华为 OD 机考是 ACM 模式提交的是完整 Java 类类名固定 Main入口是 main 方法数据从 System.in 读取结果写到 System.out。平时用 IDEA 习惯自动生成类的人考场上手写壳子最容易卡壳。建议把下面这个壳子背到肌肉记忆import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); String s sc.nextLine(); // 在这里写业务逻辑 System.out.println(ans); } }4.2 核心代码import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); String s sc.nextLine().trim(); int n s.length(); // 特判长度不是 4 的倍数时不可能平衡 if (n % 4 ! 0) { System.out.println(-1); return; } int target n / 4; // 0-W 1-A 2-S 3-D int[] cnt new int[4]; for (char c : s.toCharArray()) { cnt[toIdx(c)]; } // 本来就平衡不需要修改任何字符 if (max(cnt) target) { System.out.println(0); return; } int ans n; int left 0; for (int right 0; right n; right) { // s[right] 进入窗口窗外计数减一 cnt[toIdx(s.charAt(right))]--; // 窗外所有计数都不超过 target 时窗口合法 while (max(cnt) target) { ans Math.min(ans, right - left 1); // s[left] 从窗口放回窗外窗外计数加一 cnt[toIdx(s.charAt(left))]; left; } } System.out.println(ans); sc.close(); } private static int toIdx(char c) { switch (c) { case W: return 0; case A: return 1; case S: return 2; default: return 3; // D } } private static int max(int[] arr) { int m arr[0]; for (int v : arr) { m Math.max(m, v); } return m; } }4.3 逐段解释cnt 数组初始存的是整个字符串四种字符的数量也就是窗口为空时窗口外的计数。随着 right 右移s[right] 进入窗口所以 cnt 里对应的字符数量减一表示它不再属于窗外。当 max(cnt) target 时当前窗口是合法的。先记录 right - left 1再把 s[left] 从窗口放回窗外cnt 加一left 右移。这一收一缩之间所有以 right 结尾的合法窗口都会被遍历到。toIdx 方法负责把字符映射成数组下标default 分支兜住 D避免漏写。max 方法单独抽出来是因为主循环里要反复求最大值写成一个方法可读性好也不容易在循环里写错。4.4 自测用例表输入输出说明WASDWASD0四种字符各两次本来就平衡WWWW3把前三个字符改成 A、S、D得到 ASDWAAAW2把前两个字符改成 S、D得到 SDAWWWWWAAAA4至少要覆盖两个 W 和两个 AW-1长度不是 4 的倍数无法平衡拿 WWWWAAAA 单独验证一下。n8target2初始 W 和 A 各有 4 个。必须让窗口外剩下的 W 和 A 都不超过 2 个也就是窗口至少要吃掉 2 个 W 和 2 个 A最短窗口长度是 4。实际替换后窗口外是 WWAA再往窗口里补上 S 和 D 各两个整体就能平衡。4.5 常见报错与解法输入空行sc.nextLine() 可能拿到空串记得 trim 或者判空否则 s.length() 直接是 0后面逻辑全乱。数组越界如果输入里混入小写字母toIdx 的 default 分支会把它当成 D。原题保证大写不用过度防御但心里要有数。输出多余内容ACM 判题只认标准输出里合法的结果调试信息千万别打在最终输出里否则样例直接判错。5. 双机位机考现场设备、节奏与自测策略5.1 双机位监考的环境清单华为 OD 机考采用双机位监考电脑前置摄像头拍你本人第二机位通常是手机从侧后方拍摄桌面、键盘和双手。开考前的环境检测环节建议提前准备好这些房间光线均匀摄像头画面里不要出现大面积逆光或暗角。桌面上只留考试允许的物品草稿纸和笔一般可以放但不要有纸质资料和手机。第二机位的手机提前充电、充满调成勿扰模式最好接上电源。网络优先用有线网络或者确认 Wi-Fi 信号稳定避免中途断线重新登录浪费时间。有些人不注意这些细节开考后才发现摄像头权限没开、手机角度不对调试设备就耗掉十几分钟非常影响心态。5.2 C卷的时间分配建议C卷通常是三题两道 100 分题加一道 200 分题。完美走位这种题大概率落在 100 分档属于保分题。我的策略是拿到题先把三题都扫一遍按熟悉度和难度拍个序先做最有把握的再做难题最后回头补检查。对于完美走位理想的用时是 15 到 20 分钟5 分钟推条件和特判10 分钟写代码最后留 5 分钟跑测试用例。样例通过只代表最基本的情况没问题机考判题数据里一定有边界比如全相同字符、长度恰好 4、已经平衡、长度上限。在本地把这几类用例先跑一遍再提交比写完直接交要稳得多。5.3 考场写 Java 的实操习惯第一平时练习就别依赖 IDE 自动补全Scanner 的 nextLine、字符串转字符数组、数组遍历求最大值这些基本写法要能默写。第二像完美走位这种明确需要计数的题直接用一个 int[4] 就够了别上 HashMap 给自己增加复杂度。第三提交前检查 System.out.println 的输出格式多打一个空格或者多打一行调试信息都可能被判错。第四草稿纸上先把 W/A/S/D 四个方向和坐标的关系写出来理清回原点等于四计数相等再做能避免一半的慌乱。5.4 万一卡住了怎么自救如果现场突然想不起滑动窗口模板先退回到暴力枚举把样例过了拿到基础分再说然后再针对大数据的用例优化。机考按用例给分暴力解法通常能覆盖一部分用例总比交一个编译都过不了的代码强。我在练习时也用过这种先暴力拿到分数、再优化的策略实测下来非常管用。6. 从完美走位延伸出去滑动窗口题型的通用打法6.1 三个常见变形变形一修改后要求机器人到达指定坐标。假设终点是 (x, y)那平衡条件就变成 countD - countA x、countW - countS y。窗口外的计数依然决定可行性但判断式从一个最大值限制变成了差值等于目标的约束难度立刻上一个台阶适合作为进阶练习。变形二允许修改任意位置的字符求最少修改数。没有了连续子串的限制这道题直接统计原字符串四种字符的数量算算有多少字符超出 n/4、需要改成别的字符补齐缺口是个纯计数题两三行就写完。变形三替换后最长的连续相同子串。把一段子串里的字符替换成同一种字符求替换后最长连续相同长度。这是 LeetCode 424 的经典题同样用计数数组加双指针合法性判断变成窗口长度减去窗口内最多字符数不超过允许替换次数。和完美走位的思路同源练完这道再刷 424会有融会贯通的感觉。6.2 通用四步法把题目约束翻译成计数条件写成明确的数学表达式。验证合法性是否随窗口增大单调变化不单调就不能用双指针。右指针扩展条件满足时左指针收缩收缩前记录最优值。补特判已经满足、不可能满足、空输入、长度上界等。6.3 准备华为OD机试的一点个人体会我在准备华为 OD 机试那段时间把滑动窗口类题目集中刷了二十多道最大的体会是这类题不怕难怕想当然。完美走位第一次做的时候我先枚举左边界再找右边界写了个 O(n²) 版本数据一大就超时。后来把窗口外计数小于等于 n/4这个条件在纸上完整推了一遍才真正理解为什么左指针可以放心收缩。还有一个考场心得机考现场双机位盯着节奏会比平时练习紧张不少。平时练习一定要计时并且养成写完先跑特判用例、再提交的习惯。像完美走位这样的保分题只要条件推对了、特判写全了、滑动窗口边界稳了基本就是稳稳的满分。