1. 项目概述什么是“完美走位”最近在帮几个准备华为OD机试的朋友做模拟练习发现“完美走位”这道题出现的频率相当高而且经常被大家吐槽“题意理解有坑”、“边界条件复杂”。我自己也花了不少时间研究发现这其实是一道非常经典的“滑动窗口”应用题考察的核心是对字符串的统计、分析和窗口滑动的优化控制能力。它不像纯算法题那样抽象而是模拟了一个非常具体的游戏场景理解了这个场景解题思路就会清晰很多。简单来说“完美走位”问题可以这样描述假设你控制一个游戏角色在一个一维的指令序列上移动指令只有四种W上、A左、S下、D右。初始状态下你收到了一串由这四种字符组成的指令序列。但是这个序列可能是不平衡的——比如W太多S太少导致角色最终会偏离原点。我们的目标是通过修改序列中一段连续的指令可以改成任意W/A/S/D使得修改后整个序列中W、A、S、D四种指令的数量完全相等。题目要求我们找出需要修改的最短连续子串的长度。举个例子如果初始指令是WASDAASD总长度8。理想状态下每种指令应该有8/42个。我们统计一下W:1,A:3,S:1,D:3。显然A和D多了W和S少了。我们需要找到一个最短的连续区间修改这个区间内的字符使得整体数量达到平衡。这道题的难点在于你修改区间内的字符时可以自由分配这给了我们调整的灵活性但如何高效地找到这个最短区间就需要动点脑筋了。它本质上是在问为了将整个字符串变成四种字符数量均匀的“完美”状态最少需要动多长的一段“坏”代码2. 核心思路与算法选型面对这个问题最直接的暴力方法是枚举所有可能的子串对于每个子串计算如果修改它能否让整体平衡。但字符串长度可能达到10^5O(n^2)的枚举显然会超时。我们必须找到更优的方法。这里的关键洞察在于问题的转化。我们设整个字符串的长度为n那么“完美”状态要求每种字符的数量都是target n / 4。注意题目通常保证n是4的倍数这点很重要。接着我们统计整个字符串中每种字符的初始数量记为count[W],count[A],count[S],count[D]。那么对于每种字符X它超出target的数量就是surplus[X] max(0, count[X] - target)。这个surplus代表了字符串中“多余”的、必须被修改掉的字符X的数量。为什么因为如果某种字符数量不足比如W只有1个但target是2我们不需要在修改区间里特意增加它我们只需要把其他多余的字符改成它就行了。所以我们修改的目标就是找到一个最短的连续子串使得这个子串包含所有“多余”的字符并且包含的数量至少等于它们各自的surplus值。更精确地说设我们需要修改的子串为S[l:r]左闭右开。对于子串外的部分即[0, l)和[r, n)我们必须保持原样。为了让整体平衡子串外部分的每种字符数量不能超过target。因此子串内必须“容纳”所有超出的部分。这意味着对于每种字符X它在子串内至少要包含surplus[X]个。于是问题完美地转化为在一个字符串中找到长度最短的连续子串使得该子串中每种字符X的数量都大于等于surplus[X]。这是一个典型的满足特定条件的最短覆盖子串问题而滑动窗口双指针算法正是解决这类问题的利器。算法选型理由滑动窗口双指针时间复杂度O(n)空间复杂度O(1)只需要常数大小的计数数组。它通过动态维护一个窗口[left, right]并移动right来扩展窗口以满足条件再移动left来收缩窗口以寻找最短长度是解决“最短满足条件子串”问题的最优解。哈希表/数组计数由于字符集只有4种使用一个长度为4的数组来统计窗口内外的字符数量比使用通用哈希表更高效。预处理先计算整体的count和target进而得到surplus数组。如果surplus全为0说明已经是完美状态直接返回0。这个转化是解题的核心也是很多朋友第一次做时容易卡住的地方——不是去想着怎么把子串改成什么样而是思考子串必须包含什么。3. 算法步骤详解与关键变量理解了核心思路后我们来一步步拆解算法的实现步骤。我会用一个具体的例子贯穿说明假设输入字符串s WASDAASD长度n 8。3.1 预处理与边界判断首先进行一些基础计算和快速判断。n len(s) if n % 4 ! 0: # 根据题目实际要求处理有些题目可能保证是4的倍数否则可能无法达成完美。 # 通常机试题会保证n是4的倍数这里我们按此假设。 return 0 # 或者进行其他处理 target n // 4 # 每种指令的目标数量本例中 target 2接下来统计整个字符串的字符频率。我们可以用字典但更高效的是用一个大小为4的数组并建立字符到索引的映射。例如index {W:0, A:1, S:2, D:3}。total_count [0, 0, 0, 0] for ch in s: total_count[char_to_idx(ch)] 1 # 本例结果: total_count [1, 3, 1, 3] (对应 W,A,S,D)然后计算surplus数组。surplus[i] max(0, total_count[i] - target)。surplus [max(0, total_count[i] - target) for i in range(4)] # 本例结果: surplus [0, 1, 0, 1] (A多1个D多1个W和S刚好或不足)关键点如果surplus中所有值都为0说明字符串已经是“完美”的不需要修改任何字符答案就是0。if all(x 0 for x in surplus): return 0在我们的例子中surplus不为零所以需要继续。3.2 滑动窗口的核心逻辑现在问题转化为寻找一个最短的窗口[left, right)使得窗口内字符i的数量win_count[i] surplus[i]对所有i成立。我们使用双指针left和right初始都指向0。用一个数组win_count记录当前窗口[left, right)内的字符统计。滑动过程扩展右边界right每次将s[right]对应的字符加入窗口win_count[idx] 1然后right右移一位。这个操作会增加窗口内该字符的数量。检查条件每次扩展后检查当前窗口是否满足了“覆盖”surplus的条件即是否对于所有i都有win_count[i] surplus[i]。收缩左边界left一旦当前窗口满足了条件我们就尝试收缩左边界来寻找可能更短的、同样满足条件的窗口。将s[left]对应的字符从窗口中移出win_count[idx] - 1然后left右移一位。移出后立刻检查窗口是否依然满足条件。如果依然满足说明我们得到了一个更短的可行窗口更新答案并继续尝试收缩left。如果不满足了就停止收缩回到步骤1继续扩展right。更新答案每当找到一个满足条件的窗口时记录其长度right - left并与历史最小长度比较。这个过程保证了我们能够遍历所有以right结尾的、满足条件的最短窗口从而找到全局最短窗口。以s WASDAASD为例模拟关键步骤初始left0, right0, win_count[0,0,0,0], surplus[0,1,0,1], min_len nright移动到1: 窗口”W”,win_count[1,0,0,0]不满足(A,D数量不足)。right移动到2: 窗口”WA”,win_count[1,1,0,0]不满足。right移动到3: 窗口”WAS”,win_count[1,1,1,0]不满足(D不足)。right移动到4: 窗口”WASD”,win_count[1,1,1,1]。检查win_count[1]1 surplus[1]1(A满足)win_count[3]1 surplus[3]1(D满足)。条件满足开始收缩left:left0移出’W’win_count[0,1,1,1]。检查win_count[0]0 surplus[0]0成立win_count[1]11成立win_count[3]11成立。依然满足更新min_len min(4, 4-1)3。left变为1。left1移出’A’win_count[0,0,1,1]。检查win_count[1]0 surplus[1]1条件不满足。停止收缩。继续扩展right...最终我们会找到最短窗口。手动推导可以发现子串”ASD”(索引1-4) 或”SDAA”(索引2-6) 长度都是3且内部至少包含1个A和1个D。所以答案是3。3.3 为什么滑动窗口是有效的这里有一个必须想明白的点我们修改窗口内的字符时可以任意修改。因此只要窗口包含了足够多的“多余”字符我们就可以把这些多余的字符改成其他种类从而使整体平衡。窗口外的字符我们不动所以它们的数量必须自然就不超过target这由surplus的定义保证了因为surplus计算的就是超过的部分。因此窗口的“覆盖”条件 (win_count[i] surplus[i]) 就是充要条件。滑动窗口的O(n)高效性在于left和right都只向右移动总共移动2n次每次移动只进行常数次操作更新计数和检查条件。4. 多语言代码实现与细节剖析掌握了算法思想代码实现就是水到渠成。但不同语言在细节处理上各有特点也是机试中容易失分的地方。下面我用四种语言分别实现并指出其中的关键细节和易错点。4.1 C 实现C版本注重效率和简洁性。#include iostream #include string #include vector #include algorithm #include climits using namespace std; int charToIndex(char c) { switch(c) { case W: return 0; case A: return 1; case S: return 2; case D: return 3; } return -1; // 理论上不会出现 } int perfectMove(string s) { int n s.length(); if (n % 4 ! 0) return 0; // 根据题目要求调整 int target n / 4; vectorint total(4, 0); for (char c : s) { total[charToIndex(c)]; } vectorint surplus(4, 0); bool alreadyPerfect true; for (int i 0; i 4; i) { surplus[i] max(0, total[i] - target); if (surplus[i] 0) alreadyPerfect false; } if (alreadyPerfect) return 0; vectorint window(4, 0); int left 0, minLen INT_MAX; for (int right 0; right n; right) { // 1. 右指针字符进入窗口 int idx charToIndex(s[right]); window[idx]; // 2. 检查当前窗口是否满足覆盖条件 bool satisfy true; for (int i 0; i 4; i) { if (window[i] surplus[i]) { satisfy false; break; } } // 3. 如果满足尝试收缩左指针 while (satisfy left right) { // 更新最小长度 minLen min(minLen, right - left 1); // 左指针字符移出窗口 int leftIdx charToIndex(s[left]); window[leftIdx]--; left; // 再次检查条件是否仍满足 satisfy true; for (int i 0; i 4; i) { if (window[i] surplus[i]) { satisfy false; break; } } } // 如果不满足继续扩展右指针 } return minLen INT_MAX ? 0 : minLen; } int main() { string s; cin s; cout perfectMove(s) endl; return 0; }C实现要点使用vectorint代替原生数组更安全方便初始化。charToIndex函数用switch语句实现映射清晰且高效。确保输入字符合法。循环条件检查在收缩left的while循环中条件satisfy left right是必须的。left right保证了窗口有效。INT_MAX的使用初始化minLen为一个极大值最后判断是否被更新过。性能窗口条件检查是一个循环4次的for循环是常数操作因此整体复杂度严格O(n)。4.2 Java 实现Java版本要注意字符串处理和容器的使用。import java.util.Scanner; public class Main { private static int charToIndex(char c) { switch (c) { case W: return 0; case A: return 1; case S: return 2; case D: return 3; default: return -1; } } public static int perfectMove(String s) { int n s.length(); if (n % 4 ! 0) { return 0; // 或根据题目要求处理 } int target n / 4; int[] total new int[4]; for (int i 0; i n; i) { total[charToIndex(s.charAt(i))]; } int[] surplus new int[4]; boolean alreadyPerfect true; for (int i 0; i 4; i) { surplus[i] Math.max(0, total[i] - target); if (surplus[i] 0) { alreadyPerfect false; } } if (alreadyPerfect) { return 0; } int[] window new int[4]; int left 0; int minLen Integer.MAX_VALUE; for (int right 0; right n; right) { // 右扩 window[charToIndex(s.charAt(right))]; // 检查条件 boolean satisfy true; for (int i 0; i 4; i) { if (window[i] surplus[i]) { satisfy false; break; } } // 满足则左缩 while (satisfy left right) { minLen Math.min(minLen, right - left 1); // 左移 window[charToIndex(s.charAt(left))]--; left; // 重新检查 satisfy true; for (int i 0; i 4; i) { if (window[i] surplus[i]) { satisfy false; break; } } } } return minLen Integer.MAX_VALUE ? 0 : minLen; } public static void main(String[] args) { Scanner sc new Scanner(System.in); String s sc.next(); System.out.println(perfectMove(s)); sc.close(); } }Java实现要点字符串访问使用s.charAt(i)注意性能在O(n)循环中是可接受的。数组初始化int[]数组元素默认值为0符合我们的需求。Math.max/min使用工具类方法。Integer.MAX_VALUE同C的INT_MAX。Scanner关闭养成好习惯使用后关闭。4.3 JavaScript 实现JavaScript版本在机试环境中如Node.js需要注意输入输出。function charToIndex(c) { switch(c) { case W: return 0; case A: return 1; case S: return 2; case D: return 3; default: return -1; } } function perfectMove(s) { const n s.length; if (n % 4 ! 0) return 0; const target Math.floor(n / 4); const total [0, 0, 0, 0]; for (let i 0; i n; i) { total[charToIndex(s[i])]; } const surplus [0, 0, 0, 0]; let alreadyPerfect true; for (let i 0; i 4; i) { surplus[i] Math.max(0, total[i] - target); if (surplus[i] 0) alreadyPerfect false; } if (alreadyPerfect) return 0; const window [0, 0, 0, 0]; let left 0; let minLen Infinity; for (let right 0; right n; right) { // 右扩 window[charToIndex(s[right])]; // 检查条件 let satisfy true; for (let i 0; i 4; i) { if (window[i] surplus[i]) { satisfy false; break; } } // 满足则左缩 while (satisfy left right) { minLen Math.min(minLen, right - left 1); // 左移 window[charToIndex(s[left])]--; left; // 重新检查 satisfy true; for (let i 0; i 4; i) { if (window[i] surplus[i]) { satisfy false; break; } } } } return minLen Infinity ? 0 : minLen; } // Node.js 环境下的输入输出示例 const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout }); rl.on(line, (input) { console.log(perfectMove(input.trim())); rl.close(); });JavaScript实现要点数组初始化明确使用[0,0,0,0]初始化避免引用问题。Infinity用于初始化最小长度这是一个安全的极大值。严格相等条件判断中使用和!是好习惯。输入输出在华为OD的JS环境中可能需要使用类似readline的模块来处理输入。上面的代码展示了在Node.js环境下的标准写法。函数封装将主要逻辑封装在函数内结构清晰。4.4 Python 实现Python版本以其简洁著称但要注意代码的清晰性和效率。def char_to_index(c: str) - int: 将字符映射到索引W-0, A-1, S-2, D-3 if c W: return 0 elif c A: return 1 elif c S: return 2 elif c D: return 3 else: return -1 # 理论上不会发生 def perfect_move(s: str) - int: n len(s) if n % 4 ! 0: return 0 # 根据题目实际要求调整 target n // 4 # 1. 统计整体词频 total [0, 0, 0, 0] for ch in s: total[char_to_index(ch)] 1 # 2. 计算 surplus 并判断是否已完美 surplus [0, 0, 0, 0] already_perfect True for i in range(4): surplus[i] max(0, total[i] - target) if surplus[i] 0: already_perfect False if already_perfect: return 0 # 3. 滑动窗口 window [0, 0, 0, 0] left 0 min_len float(inf) # 初始化为无穷大 for right in range(n): # 右指针字符进入窗口 window[char_to_index(s[right])] 1 # 检查当前窗口是否满足条件 (覆盖所有 surplus) # 使用 all() 和生成器表达式使代码更 Pythonic while left right and all(window[i] surplus[i] for i in range(4)): # 更新最小长度 min_len min(min_len, right - left 1) # 左指针字符移出窗口 window[char_to_index(s[left])] - 1 left 1 return 0 if min_len float(inf) else min_len if __name__ __main__: s input().strip() print(perfect_move(s))Python实现要点使用all()函数在检查窗口条件时all(window[i] surplus[i] for i in range(4))比显式循环更简洁易懂。但要注意在每次while循环中都会生成一个新的生成器并遍历4次。在性能极致敏感的场景显式循环可能稍快但这样写可读性更高在O(n)算法中影响微乎其微。float(inf)用于初始化最小长度。while循环条件将satisfy的判断直接集成到while的条件中代码更紧凑。注意条件顺序left right and all(...)确保窗口有效。类型提示def perfect_move(s: str) - int:增加了代码的可读性虽然不是必须的。输入处理使用input().strip()读取字符串。5. 常见“坑点”与调试技巧即使理解了算法在实现和调试时还是会遇到一些典型的“坑”。这里我总结了几类常见问题并给出排查思路。5.1 理解错误导致的错误错误理解修改规则题目要求修改一个连续子串而不是任意位置的字符。如果你理解成可以任意修改若干个字符就会得到错误答案。排查重新审题确认“连续”这个关键词。错误理解平衡条件目标是使四种字符数量相等即都等于n/4。不是让它们两两相等或者比例相同。排查用简单例子验证如”WWAA”正确答案应该是修改长度为2的子串如改为”SD”使最终为”SDAA”(W:1,A:2,S:1,D:1)不对这样也不平衡。实际上n4, target1初始W:2,A:2,S:0,D:0surplus[1,1,0,0]。需要找一个包含至少1个W和1个A的最短子串那就是整个字符串”WWAA”本身长度4。但我们可以修改中间两个”WA”为”SD”得到”WSSD”这样W:1,A:1,S:1,D:1平衡。最短窗口是长度为2的”WA”。这个例子值得仔细推敲。5.2 实现细节导致的错误surplus计算错误surplus[i] max(0, total[i] - target)而不是abs(total[i] - target)。不足的字符total[i] target对应的surplus是0因为我们不需要在修改区间内“减少”它反而需要在区间内“增加”它通过把别的字符改成它而“增加”的操作由其他字符的surplus来驱动。排查打印出total,target,surplus的值与手动计算对比。滑动窗口条件判断错误条件是窗口内字符数surplus而不是。因为窗口内可能包含更多的该字符这没关系多出来的部分在修改时一起改掉即可。排查在窗口扩展和收缩时打印window和surplus数组观察条件满足的时机。指针移动与计数更新不同步在收缩left时一定要先更新minLen再移出字符、移动left。顺序错了会导致长度计算错误或计数错误。排查单步调试观察left,right,window在每次循环中的变化。初始化和边界条件minLen初始值应为无穷大或n不能是0。当surplus全为0时应直接返回0。循环中while的条件要包含left right防止窗口左边界超过右边界。排查构造边界用例测试如空字符串通常不会出现、长度非4倍数字符串看题目要求、已经是完美平衡的字符串如”WASD”、全部是一种字符的字符串如”AAAA”。5.3 性能与优化条件检查的优化在while循环内部每次收缩left后都需要检查4个条件是否依然满足。我们可以维护一个变量missing表示当前窗口还有多少种字符的surplus条件未满足。当missing 0时窗口满足条件。这样可以将条件判断的O(4)降到O(1)。不过对于本题只有4种字符优化效果不明显但思路值得学习。提前终止如果发现某个total[i] - target不是整数即n不是4的倍数根据题目描述可能直接返回-1或0要仔细阅读题目输入说明。5.4 调试用例推荐自己构造测试用例是调试的最佳方式。建议准备以下几类用例输入预期输出说明”WASD”0已经完美无需修改。”AAAA”3n4, target1, surplus[0,3,0,0]。需要包含至少3个A的最短子串就是整个字符串但我们可以修改任意连续3个A。例如改前3个为”WSD”得到”WSDA”平衡。”WASDAASD”3本文的例子。”WWWWAAAA”6n8, target2, surplus[2,2,0,0]。需要同时包含至少2个W和2个A的最短子串。”WDSAWDSA”0每个字符恰好2个已平衡。”A”0 (或按题目要求)边界用例长度非4倍数。在IDE或在线判题平台运行你的代码逐一验证这些用例。如果结果不对就针对出错的用例在循环中打印关键变量left,right,window,surplus,minLen进行逐行分析。6. 算法扩展与相关题目“完美走位”问题是一个非常好的滑动窗口教学案例。掌握它之后你可以轻松解决一系列同类型题目。这类问题的核心模式是寻找满足某个条件通常是“包含某些元素达到一定数量”的最短/最长子数组/子串。相关题目举隅最小覆盖子串LeetCode 76给定字符串S和T在S中找到包含T所有字符的最短子串。这是最经典的覆盖子串问题“完美走位”可以看作是它的一个特例T中的字符是“隐含”的由surplus定义。字符串的排列LeetCode 567判断s2是否包含s1的排列即s2的某个子串恰好是s1的字符的一个全排列。这可以转化为在s2中寻找一个长度固定为len(s1)的子串其字符计数与s1完全相同。找到字符串中所有字母异位词LeetCode 438上题的扩展找到所有起始索引。替换后的最长重复字符LeetCode 424给你一个字符串你最多可以替换k个字符找到替换后最长的由相同字符组成的子串。这道题滑动窗口的条件是(窗口长度 - 窗口内最多字符数) k。水果成篮LeetCode 904本质上是在数组中寻找最多包含两种不同数字的最长子数组。解决这类问题的通用思路定义条件明确窗口[left, right)需要满足什么条件。初始化设置指针、计数器、答案变量。移动右指针扩大窗口更新计数器直到窗口满足条件。更新答案在满足条件时根据题目要求最短/最长更新答案。移动左指针收缩窗口更新计数器直到窗口不再满足条件然后回到第3步。或者在满足条件时持续收缩以优化答案如求最短。循环重复3-5步直到右指针到达末尾。对于“完美走位”步骤3和5是交织在一起的在扩展right后用一个while循环不断收缩left以尝试获得更短的可行窗口。这种“右扩一次左缩可能多次”的模式是求“最短满足条件子串”的典型模板。最后在华为OD机试中除了写出正确代码还要注意时间复杂度和空间复杂度的分析通常要在代码注释中简要说明。对于本题明确写出“时间复杂度O(n)空间复杂度O(1)”是一个加分项。多写几种语言的实现并非必须但如果你投递的岗位有语言要求用对应语言熟练实现能展现你的专业能力。在实际练习中建议先用自己最熟悉的语言把逻辑彻底写通、调试通过再尝试用其他语言复现这样对算法本身的理解会更加深刻。