华为OD机试C++题解：滑动窗口与哈希集合破解字符串解密

1. 项目概述从一道机试题看华为OD的选拔逻辑最近在技术社区和求职圈里华为ODOutsourcing Dispatch的机试成了一个绕不开的话题。很多朋友尤其是刚接触C不久或者准备转行做开发的一听到“机试”两个字就有点发怵特别是遇到“字符串解密”这类听起来就涉及复杂逻辑处理的题目。我当年准备的时候也走过不少弯路后来带过几届新人发现大家卡壳的地方都差不多。所以今天我就以这道经典的“字符串解密”问题为引子不光是给出一份C题解更想拆解一下这类题目背后的考察意图、解题的通用思路以及如何写出让考官眼前一亮的代码。这道题本质上是在考察你对字符串的熟练操作、对哈希集合这类数据结构的灵活运用以及最关键的——将模糊的自然语言描述转化为清晰、严谨算法步骤的能力。无论你是正在备战华为OD还是想提升自己的C算法功底相信这篇从实战中总结出来的经验都能给你带来一些直接的帮助。2. 问题深度解析与建模思路2.1 题目场景还原与需求拆解首先我们需要把常见的“字符串解密”类题目的描述进行具象化。题目通常不会直接说“请你实现一个解密函数”而是会包裹在一个业务场景里。一个典型的描述可能是这样的给定两个字符串encryptedStr已加密字符串和keyStr密钥字符串。 要求从encryptedStr中找出所有同时满足以下两个条件的连续子串该子串中的所有字符都必须出现在keyStr中。该子串必须是所有满足条件1的子串中包含不同字符种类最多的那个。如果有多个子串包含的不同字符种类数相同则取最长的那个。如果仍有多个则取最先出现的那个。 最后输出这个满足条件的子串。看到这里你可能有点晕。别急我们一步步拆。核心需求其实就三点筛选、比较、选择。筛选遍历encryptedStr找出所有“完全由keyStr中字符构成”的连续子串。这类子串我们称之为“有效子串”。比较在所有“有效子串”里比较它们的“唯一字符数”即去重后的字符种类数量。选择根据比较规则先比种类数再比长度最后比位置选出最终胜出的那个子串。这立刻引出了两个关键问题第一如何高效地判断一个子串是否“完全由keyStr中字符构成”第二如何高效地统计一个子串中的“唯一字符数”2.2 核心算法思路选型与论证针对第一个问题最直观的做法是遍历子串的每个字符去keyStr里查找。如果keyStr长度是m子串长度是n那么一次判断就是O(n*m)在字符串较长时效率极低。更优的方案是使用一个哈希集合在C中就是std::unordered_setchar。我们预处理keyStr将其所有字符插入到一个哈希集合keySet中。这样判断一个字符c是否在keyStr中就变成了keySet.find(c) ! keySet.end()这是一个平均O(1)时间的操作。整个判断过程就降到了O(n)。注意这里选择unordered_set而不是set是因为我们只关心存在性查询不要求有序unordered_set的平均时间复杂度更低。但要注意unordered_set的哈希冲突在最坏情况下可能导致O(n)的查找时间不过对于字符集通常0-255这种小范围数据几乎不会发生可以放心使用。第二个问题统计子串的唯一字符数。同样我们可以在遍历子串的过程中将字符插入另一个哈希集合charSet中遍历结束后charSet.size()就是唯一字符数。但这里有一个更高效的技巧滑动窗口。我们不需要为每一个子串都重新构建一个集合。当窗口向右滑动一位时只是左边移出一个字符右边移入一个字符。我们可以维护一个窗口内字符的频次数组freq[128]假设是ASCII字符和一个计数器uniqueCount。当移入字符使其频次从0变1时uniqueCount加1当移出字符使其频次从1变0时uniqueCount减1。这样我们就能在O(1)时间内动态得知当前窗口的唯一字符数将统计复杂度从O(n)降到了O(1)。结合以上两点我们的算法骨架就出来了使用滑动窗口来遍历encryptedStr并用哈希集合keySet来快速校验字符合法性。窗口滑动过程中动态维护窗口内字符的频次和唯一字符数。但滑动窗口通常用于寻找“满足某个条件的最短/最长子串”而本题是寻找“所有合法子串中评价最高的一个”。因此我们需要一个变体当窗口内出现非法字符时窗口需要重置因为包含非法字符的子串整体无效。我们需要记录下每一个“纯有效”的窗口即从开始到遇到非法字符前的这段连续有效子串并对它们进行评估比较。2.3 数据结构设计与预备知识在动手写代码前最后明确一下我们要用的“武器”std::unordered_setchar用于存储keyStr的字符集实现O(1)的成员查询。std::vectorint或int[128]用于作为频次数组记录当前滑动窗口内各ASCII字符的出现次数。使用数组访问速度更快内存占用也小。std::string存储输入字符串和最终结果。注意C中string的可变性方便我们截取子串。滑动窗口指针通常用两个整数索引left和right来表示窗口的左右边界左闭右开区间。此外我们需要几个变量来记录“当前找到的最佳子串”的信息bestStart最佳子串的起始索引。bestLen最佳子串的长度。bestUnique最佳子串的唯一字符数。3. C代码实现与逐行精讲有了清晰的思路现在我们把算法翻译成C代码。我会将代码分成几个逻辑块并逐块讲解。3.1 辅助函数与核心逻辑实现首先我们实现核心的解题函数。为了代码清晰我们可以将“更新最佳结果”的逻辑抽成一个内联函数或直接写在主循环里。#include iostream #include string #include unordered_set #include vector #include climits // 用于INT_MIN std::string decryptString(const std::string encryptedStr, const std::string keyStr) { // 1. 构建密钥字符的快速查询集合 std::unordered_setchar keySet(keyStr.begin(), keyStr.end()); // 2. 初始化变量 int n encryptedStr.size(); int bestStart 0; // 最佳子串起始位置 int bestLen 0; // 最佳子串长度 int bestUnique -1; // 最佳子串的唯一字符数初始化为-1便于比较 // 频次数组记录当前窗口内字符出现次数ASCII范围0-127足矣 std::vectorint freq(128, 0); int currentUnique 0; // 当前窗口内的唯一字符数 int left 0; // 滑动窗口左边界 int right 0; // 滑动窗口右边界指向下一个待处理字符 // 3. 主循环遍历字符串 while (right n) { char c encryptedStr[right]; // 情况A当前字符是有效字符在keySet中 if (keySet.count(c)) { // 将字符纳入当前窗口 if (freq[c] 0) { currentUnique; // 新字符加入窗口 } freq[c]; right; // 右边界向右扩展 // **关键点**此时窗口[left, right)是一个有效的连续子串 // 我们需要将其与当前最佳结果进行比较 if (currentUnique bestUnique || (currentUnique bestUnique (right - left) bestLen)) { // 找到了更优解唯一字符数更多或字符数相同但更长 bestUnique currentUnique; bestStart left; bestLen right - left; } } else { // 情况B当前字符是无效字符 // 无效字符打断了连续的有效序列 // 我们需要重置窗口从无效字符的下一个位置重新开始 while (left right) { // 清理当前窗口内的字符频次 char charToRemove encryptedStr[left]; freq[charToRemove]--; if (freq[charToRemove] 0) { currentUnique--; } left; } // 跳过这个无效字符本身 left right; // 此时窗口为空currentUnique应为0freq数组被清理 } } // 4. 返回结果 if (bestLen 0) { return ; // 没有找到任何有效子串 } return encryptedStr.substr(bestStart, bestLen); }3.2 代码逻辑逐段解析第一部分预处理std::unordered_setchar keySet(keyStr.begin(), keyStr.end());这行代码是效率的关键。它一次性将keyStr的所有字符装入哈希表后续的keySet.count(c)操作平均时间复杂度为O(1)。第二部分变量初始化注意bestUnique初始化为-1。这是因为唯一字符数最小为0空窗口初始化为-1可以确保第一个有效窗口其currentUnique至少为1一定能更新最佳记录。freq数组大小为128涵盖了标准ASCII字符使用vectorint方便初始化为0。第三部分主循环逻辑这是算法的核心我们采用一个while循环用right指针探索字符串。当c是有效字符时我们将其纳入窗口更新freq和currentUnique然后right。紧接着立即将当前窗口[left, right)作为一个候选子串进行评估。为什么在这里评估因为此时窗口刚刚向右扩展了一位并且窗口内的所有字符都是有效的我们只在遇到有效字符时才扩展right。评估条件严格按照题目要求先比unique再比length。注意我们不需要比较“最先出现”因为我们是顺序遍历的只有当找到严格更优字符数更多或字符数相同但更长的解时才会更新bestStart和bestLen。如果后来的子串和当前最佳解在字符数和长度上都完全一样它不会覆盖之前的这就保证了“最先出现”的优先级。当c是无效字符时这意味着从left到right不包括right本身的子串是有效的但加上c就无效了。所以[left, right)这个窗口已经是我们需要考察的最后一个连续有效子串我们在上一步已经评估过了。现在这个无效字符c像一堵墙它之后的有效子串必须从它后面重新开始。因此我们需要完全清空当前窗口。内层的while (left right)循环就是为了将left指针移动到right的位置并在此过程中将窗口内所有字符从freq中移除同时更新currentUnique。最后left和right都跳过这个无效字符left right从下一个位置开始全新的探索。第四部分返回结果循环结束后bestStart和bestLen就记录了最优解的位置。使用substr方法截取并返回。如果bestLen为0说明从未找到过有效子串返回空串。3.3 测试用例与验证写完代码必须用多种情况测试。一个好的测试集应该包含基础功能encryptedStr abcde, keyStr ace。有效子串有a,c,e,ac,ce,ace。其中ace包含3个不同字符是最优解。包含无效字符encryptedStr ab#cde!fg, keyStr abcdefg。字符串被#和!分割成三段ab,cde,fg。需要算法能正确重置窗口。并列最优解encryptedStr aabbcc, keyStr abc。所有字符都有效。子串aabb(字符{a,b})bbcc(字符{b,c})都包含2种字符长度都是4。根据“最先出现”应返回aabb。空结果encryptedStr xyz, keyStr abc。应返回空串。密钥重复字符keyStr aabbbc哈希集合会自动去重不影响逻辑。长字符串压力测试可以构造一个长字符串验证算法效率。在本地编写一个简单的main函数来运行这些测试确保输出符合预期。int main() { // 测试用例 std::cout decryptString(abcde, ace) std::endl; // 期望输出 ace std::cout decryptString(ab#cde!fg, abcdefg) std::endl; // 期望输出 cde (最长且字符数最多) std::cout decryptString(aabbcc, abc) std::endl; // 期望输出 aabb std::cout decryptString(xyz, abc) std::endl; // 期望输出 // 更复杂的例子 std::cout decryptString(bcabcab, abc) std::endl; // 期望输出 abcab (字符数3长度5) return 0; }4. 性能分析与优化空间探讨4.1 时间与空间复杂度分析时间复杂度O(n)其中n是encryptedStr的长度。整个算法只遍历了一次字符串right指针每个字符最多被left和right指针各访问一次进入窗口和离开窗口。所有哈希集合的插入、查询数组的更新都是O(1)操作。空间复杂度O(1)或O(m)这里容易有误解。我们开辟的额外空间包括keySet其大小最多为字符集大小ASCII是128但实际取决于keyStrfreq数组固定128个int几个整型变量。如果字符集是固定大小的如ASCII那么空间复杂度是O(1)即常数空间。如果字符集是Unicode等超大集合并且我们使用unordered_set来模拟freq那么空间复杂度取决于窗口内不同字符的数量最坏是O(m)但题目通常限定在较小字符集。这个性能对于机试场景是完全足够的甚至可以说是最优解之一。4.2 潜在优化与变体思考虽然上述解法已经很好但我们可以思考一些边界情况和优化点空字符串和单字符处理我们的代码已经能正确处理。当encryptedStr为空时循环不会进入返回空串。单字符情况也能正常纳入窗口并参与比较。大字符集处理如果题目明确字符范围很大如整个Unicode使用int[128]的数组就不行了。我们可以将freq数组替换为std::unordered_mapchar, int但这样freq[c]和freq[c]--的操作就从O(1)变成了平均O(1)但常数时间更大。在机试中除非特别说明否则按ASCII处理是安全且高效的。代码简洁性优化可以将“更新最佳结果”的逻辑封装成一个函数updateBest让主循环更清晰。但对于机试代码紧凑、一目了然有时更重要。滑动窗口的另一种写法有些同学喜欢用for (right 0; right n; right)的循环然后在循环内部根据encryptedStr[right]的值来更新left。对于本题由于无效字符需要清空整个窗口用while循环控制right的递增可能更直观。两种方式本质等价。实操心得在机试中正确性永远优先于微优化。先写出一个清晰、正确、复杂度可接受的解法。如果时间充裕再考虑代码的简洁性或微小的常数优化。像本题使用vectorint(128,0)就比unordered_mapchar,int在性能上有明显优势而且代码更简单。5. 华为OD机试的通用备战策略与避坑指南通过这道题我们可以提炼出应对华为OD乃至大多数公司算法机试的通用方法。5.1 审题与建模的黄金法则提取核心约束像本题中的“字符必须在keyStr中出现”、“连续子串”、“不同字符数最多”、“最长”、“最先出现”每一个都是硬性约束。最好用笔标记出来。自己构造样例题目给的样例往往很简单。必须自己构造边界案例和复杂案例。例如空串、全无效串、密钥串有重复字符、最长子串在开头/中间/末尾、有多个并列最优解等。先想暴力再优化不要一开始就追求最优解。先思考一个最直观的解法比如本题暴力枚举所有子串再逐一校验。哪怕它的复杂度是O(n^3)这也帮你理清了所有判断逻辑。然后再思考如何用哈希表、滑动窗口、双指针、动态规划等技巧来优化每一步。5.2 C编码实战中的细节陷阱字符串下标与长度std::string的length()或size()方法返回的是size_t无符号整数。在循环条件i str.size()中如果i是int比较无符号和有符号虽然能工作但一些编译器会告警。安全的做法是循环变量也用size_t或者用int n str.size()先转换。子串截取substr(start, length)注意第二个参数是长度不是结束位置。常见的错误是写成substr(start, end)。哈希集合的使用unordered_set的count方法返回0或1表示是否存在。find方法返回迭代器。在只需要判断存在性的场景用count代码更简洁。全局变量与函数机试平台通常要求你将代码写在指定的函数内比如string decryptString(string encryptedStr, string keyStr)。切勿使用全局变量因为多个测试用例会连续调用你的函数全局变量会保留上一次调用的状态导致错误。5.3 调试与提交前的最后检查内存与越界确保你的数组或容器访问不会越界。例如我们的freq数组索引是c这要求c的ASCII码在0-127之间。如果题目说只有小写字母可以减a来映射到0-25更安全。初始化所有变量特别是用于累加、比较的变量如bestUnique,currentUnique必须赋予正确的初始值。多用例测试在本地IDE中模拟OJ平台的调用方式用多个测试用例连续调用你的函数检查输出。复杂度自评在代码注释里简单写一下时间和空间复杂度这不仅能帮助阅卷人理解你的思路也能提醒自己。回到这道“字符串解密”题它很好地考察了候选人的基础编码能力、对数据结构的理解以及逻辑思维的严密性。它不像动态规划那样需要复杂的状态推导也不像图论那样需要深厚的算法储备但它要求你将一个看似复杂的问题分解成几个清晰的步骤并用高效的代码实现出来——这恰恰是软件开发中最核心的能力之一。