1. 项目概述与核心价值最近在技术社区和求职论坛里华为ODOutsourcing Development的机试真题讨论热度一直居高不下。很多朋友无论是应届生还是希望转岗的开发者都在寻找有效的备考资料。今天我想以一个过来人的身份和大家深入聊聊其中一道非常经典的题目——“字符串解密”。这道题之所以经典是因为它完美地融合了字符串处理、逻辑判断、数据结构如集合、映射以及算法思维是检验编程基本功和问题拆解能力的绝佳试金石。我当年备考时这道题也让我卡壳了很久后来通过反复琢磨和与朋友讨论才理清了其中的门道。这篇文章我就把我对这道题的理解、解题思路的完整拆解、不同语言C、C、Java、Python、JavaScript的实现细节以及那些容易踩坑的地方毫无保留地分享出来。无论你是刚开始准备华为OD机试还是单纯想提升自己的编程解题能力相信这篇长文都能给你带来实实在在的帮助。简单来说“字符串解密”题目通常会给你两个字符串比如一个加密字符串和一个密钥字符串要求你根据一系列规则例如过滤掉密钥中出现的字符然后对剩余字符进行某种排序或转换来还原出原始信息或得到目标字符串。它考察的不是多么高深的算法而是你对字符串API的熟练度、对边界条件的把控以及编写清晰、健壮代码的能力。接下来我们就一层层剥开这道题的外壳。2. 题目深度解析与需求拆解在拿到任何机试题时第一步绝不是急着写代码而是彻底读懂题目。很多失分都源于理解偏差。我们假设一道典型的“字符串解密”题目描述如下此为常见变体之一用于阐述思路题目描述: 给定两个字符串str1和str2。从str1中找出所有同时在str1和str2中出现的字符将这些字符从str1中去除。对str1中剩余的字符按照其在原字符串str1中的出现顺序进行去重即保留每个字符第一次出现的位置。如果去重后的字符串为空则输出NULL。输入两个字符串用空格隔开。输出处理后的字符串或NULL。2.1 核心需求与规则翻译我们需要将模糊的自然语言描述翻译成精确的、可执行的计算机逻辑步骤输入解析程序需要能正确读取两个可能包含空格的字符串。这里就有第一个坑如果用简单的cin str1 str2C遇到字符串内部有空格就会出错。必须使用能读取整行的函数如getline(cin, str)。字符筛选去除公共字符核心操作是遍历str1判断每个字符是否存在于str2中。存在的判断需要高效。直接使用str2.find(ch)循环是直观的但时间复杂度是 O(n*m)。更优的做法是先用一个哈希集合HashSet记录str2中的所有字符这样判断存在性的操作可以降到 O(1)。顺序去重在筛选后的新字符串中需要按原始顺序保留不重复的字符。例如”abac“处理后应为”abc“。这同样可以利用一个哈希集合来辅助遍历字符如果该字符不在“已出现集合”中则将其加入结果字符串和集合。空结果处理这是一个关键的边界条件。如果经过上述处理结果字符串长度为0必须输出特定的”NULL“注意全大写而不是空字符串或什么都不输出。2.2 思路设计与算法选择基于以上分析我们可以设计出清晰的算法流程预处理读取字符串str1和str2。构建过滤器将str2中的所有字符放入一个哈希集合filterSet中。这一步的目的是为了 O(1) 时间复杂度的查找。第一次遍历过滤创建一个临时字符串tempStr。遍历str1的每个字符ch如果ch不在filterSet中则将ch追加到tempStr末尾。否则跳过该字符即过滤掉。第二次遍历去重创建一个结果字符串result和一个用于去重的哈希集合seenSet。遍历tempStr的每个字符ch如果ch不在seenSet中则将ch追加到result末尾并加入seenSet。否则跳过。输出检查result是否为空。若为空输出”NULL“否则输出result。复杂度分析假设str1长度为 Nstr2长度为 M。时间复杂度O(N M)。构建filterSet需要 O(M)两次遍历str1或tempStr各需要 O(N)哈希集合的插入和查找均为平均 O(1)。空间复杂度O(N M)。主要用于存储哈希集合和中间字符串。这个思路清晰效率也足够应对机试的一般数据规模。下面我们就用五种主流语言将其实现出来并看看每种语言实现时的特有技巧和注意事项。3. 多语言代码实现与细节剖析不同的编程语言有其独特的语法和标准库特性。实现同一算法时选择合适的工具和方法能让代码更简洁、高效。这里我假设输入格式为第一行是字符串str1第二行是字符串str2。3.1 C语言实现C语言没有内置的哈希集合需要自己实现字符的查找逻辑或者使用一个大小为128或256的数组来模拟哈希表ASCII字符集。#include stdio.h #include string.h #include stdbool.h #define CHAR_SET_SIZE 128 // 足够覆盖标准ASCII字符 int main() { char str1[1000], str2[1000]; char result[1000]; bool filter[CHAR_SET_SIZE] {false}; // 用于过滤的“哈希表” bool seen[CHAR_SET_SIZE] {false}; // 用于去重的“哈希表” // 读取输入注意使用fgets读取整行并去除可能的换行符 fgets(str1, sizeof(str1), stdin); str1[strcspn(str1, \n)] \0; // 去除换行符 fgets(str2, sizeof(str2), stdin); str2[strcspn(str2, \n)] \0; // 步骤1: 构建过滤器 for (int i 0; str2[i] ! \0; i) { // 将str2中的字符对应的ASCII码位置标记为true filter[(unsigned char)str2[i]] true; } // 步骤2: 过滤并顺序去重 int resultIndex 0; for (int i 0; str1[i] ! \0; i) { char ch str1[i]; // 只有当字符不在filter中且未被见过才加入结果 if (!filter[(unsigned char)ch] !seen[(unsigned char)ch]) { result[resultIndex] ch; seen[(unsigned char)ch] true; // 标记为已见 } } result[resultIndex] \0; // C字符串结束符 // 步骤3: 输出 if (resultIndex 0) { printf(NULL\n); } else { printf(%s\n, result); } return 0; }C语言实现要点与避坑指南输入处理scanf(“%s”, str)无法读取带空格的字符串。必须使用fgets。fgets会读取换行符\n并存入字符串所以需要用strcspn或手动遍历将其替换为\0。“哈希表”模拟使用布尔数组filter和seen是C语言中处理固定范围键值如ASCII字符最高效的方式。访问速度是O(1)且代码简单。无符号转换(unsigned char)ch是为了防止字符值为负数时虽然ASCII字符通常为正数组访问越界这是一个良好的防御性编程习惯。二合一操作注意上面的代码将“过滤”和“顺序去重”合并到了一个循环中。这是因为我们的seen数组只在过滤后的字符范围内生效逻辑是通的一个字符要进入结果必须同时满足“不在黑名单(filter)”和“第一次出现(seen)”两个条件。这比先过滤生成中间字符串再遍历去重更高效。空间分配示例中静态分配了大小为1000的数组。在机试中如果题目未明确说明最大长度可以适当开大一些如10000或者使用动态内存分配malloc但静态大数组在机试场景下更简单可靠。3.2 C实现C可以利用STL中的unordered_set来实现哈希集合代码会更贴近高层抽象。#include iostream #include string #include unordered_set using namespace std; int main() { string str1, str2; // 使用getline读取整行包括空格 getline(cin, str1); getline(cin, str2); // 步骤1: 构建过滤器 unordered_setchar filterSet(str2.begin(), str2.end()); // 步骤2: 过滤并顺序去重 string result; unordered_setchar seenSet; for (char ch : str1) { // 如果字符不在过滤集中且是第一次出现 if (filterSet.find(ch) filterSet.end() seenSet.find(ch) seenSet.end()) { result.push_back(ch); seenSet.insert(ch); } } // 步骤3: 输出 if (result.empty()) { cout NULL endl; } else { cout result endl; } return 0; }C实现要点与避坑指南输入处理getline(cin, str)是读取带空格字符串的标准做法。如果之前用过cin someVar会在输入缓冲区留下换行符导致接下来的getline直接读取到一个空行。此时需要在getline前使用cin.ignore()清空缓冲区。在本题只有两个字符串输入时连续使用getline是安全的。STL容器初始化unordered_setchar filterSet(str2.begin(), str2.end())在构造时直接使用迭代器范围初始化比先声明空集合再循环insert更简洁。查找操作unordered_set::find返回一个迭代器。如果没找到则返回end()。这是判断元素是否在集合中的标准写法。性能考量unordered_set在平均情况下有O(1)的查找性能但对于字符这种数量很少的键其开销可能比C语言的布尔数组大。但在机试的数据规模下这点差异完全可以忽略代码的清晰性和可维护性更重要。二合一循环和C语言版本一样这里也合并了过滤和去重步骤逻辑清晰。3.3 Java实现Java的集合框架非常强大使用HashSet可以轻松实现相同逻辑。import java.util.HashSet; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); // 读取两行 String str1 scanner.nextLine(); String str2 scanner.nextLine(); scanner.close(); // 步骤1: 构建过滤器 HashSetCharacter filterSet new HashSet(); for (int i 0; i str2.length(); i) { filterSet.add(str2.charAt(i)); } // 步骤2: 过滤并顺序去重 StringBuilder result new StringBuilder(); HashSetCharacter seenSet new HashSet(); for (int i 0; i str1.length(); i) { char ch str1.charAt(i); if (!filterSet.contains(ch) !seenSet.contains(ch)) { result.append(ch); seenSet.add(ch); } } // 步骤3: 输出 if (result.length() 0) { System.out.println(NULL); } else { System.out.println(result.toString()); } } }Java实现要点与避坑指南输入处理Scanner.nextLine()读取整行。同样要注意如果前面有nextInt()等调用需要用额外的nextLine()消耗掉换行符。HashSetCharacterJava的集合不能存储基本类型所以需要使用包装类Character。好在自动装箱Autoboxing机制让add(ch)和contains(ch)写起来很自然。StringBuilder在循环中拼接字符串务必使用StringBuilder而不是直接用String的操作符。后者在循环中会创建大量临时String对象效率极低是机试中的大忌。关闭Scanner虽然对于标准输入不关闭问题不大但养成用完Scanner后调用close()的习惯是好的。判空使用result.length() 0或result.isEmpty()Java 6来判断。3.4 Python实现Python的代码最为简洁得益于其强大的内置数据类型集合set和列表推导式。def main(): str1 input().strip() str2 input().strip() # 步骤1: 构建过滤器 filter_set set(str2) # 步骤2: 过滤并顺序去重 seen_set set() result_chars [] for ch in str1: if ch not in filter_set and ch not in seen_set: result_chars.append(ch) seen_set.add(ch) # 步骤3: 输出 result .join(result_chars) if not result: print(NULL) else: print(result) if __name__ __main__: main()Python实现要点与避坑指南输入处理input()默认读取一行并包含末尾换行符strip()可以去除首尾的空白字符包括换行符和空格。集合操作set(str2)一行代码就能将字符串转换为字符集合极其方便。in和not in操作符用于判断成员关系可读性很高。列表构建结果在循环中我们将符合条件的字符追加到列表result_chars中最后用.join(result_chars)拼接成字符串。这是Python中构建字符串的高效做法。避免在循环中使用result ch因为字符串是不可变对象每次都会生成新对象。空值判断if not result:可以优雅地判断字符串是否为空。Python中空字符串、空列表等在布尔上下文中为False。3.5 JavaScript (Node.js)实现在华为OD的机试环境中JavaScript通常指Node.js环境。其实现思路与其他语言类似。const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout }); let inputLines []; rl.on(line, (line) { inputLines.push(line.trim()); if (inputLines.length 2) { solve(); rl.close(); } }); function solve() { const str1 inputLines[0]; const str2 inputLines[1]; // 步骤1: 构建过滤器 const filterSet new Set(); for (let ch of str2) { filterSet.add(ch); } // 步骤2: 过滤并顺序去重 const resultChars []; const seenSet new Set(); for (let ch of str1) { if (!filterSet.has(ch) !seenSet.has(ch)) { resultChars.push(ch); seenSet.add(ch); } } // 步骤3: 输出 const result resultChars.join(); if (result.length 0) { console.log(NULL); } else { console.log(result); } }JavaScript实现要点与避坑指南输入处理Node.js没有像其他语言那样的同步控制台读取函数。必须使用readline模块异步读取行。这里采用收集两行输入后触发处理的模式。Set对象ES6引入的Set是完美的哈希集合实现。使用new Set()创建add方法添加元素has方法检查存在性。字符串迭代for...of循环可以直接迭代字符串中的字符Unicode码点比用for循环索引更现代和可靠能正确处理一些特殊Unicode字符。数组拼接字符串和Python一样使用数组resultChars收集字符最后用join()拼接性能优于在循环中进行字符串连接。环境确认务必确认机试环境支持ES6语法现代Node.js版本都支持。Set和for...of都是ES6特性。4. 解题思路的扩展与变体分析“字符串解密”只是一个母题在实际机试或面试中它会有各种各样的变体。掌握核心思路后关键在于灵活调整。下面分析几种常见变体及应对策略。4.1 变体一解密规则变化题目变体不是去除公共字符而是要求只保留str1和str2的公共字符然后进行顺序去重。思路调整这实际上更简单。我们只需要修改过滤条件。在构建了str2的字符集合filterSet后遍历str1时判断条件从if ch not in filterSet改为if ch in filterSet。核心的去重逻辑保持不变。代码示例Pythondef variant1(str1, str2): filter_set set(str2) seen_set set() result_chars [] for ch in str1: if ch in filter_set and ch not in seen_set: # 仅此条件改变 result_chars.append(ch) seen_set.add(ch) result .join(result_chars) return result if result else NULL4.2 变体二处理顺序变化题目变体先对str1进行顺序去重然后再去除与str2的公共字符。思路调整步骤顺序发生了变化。我们需要先创建一个“已见集合”遍历str1生成一个顺序去重后的中间字符串。然后再用str2的集合过滤这个中间字符串。注意这种情况下去重是基于原始str1的顺序。代码示例Javapublic static String variant2(String str1, String str2) { // 第一步对str1顺序去重 StringBuilder deduplicated new StringBuilder(); HashSetCharacter seen new HashSet(); for (char ch : str1.toCharArray()) { if (!seen.contains(ch)) { deduplicated.append(ch); seen.add(ch); } } // 第二步用str2过滤 HashSetCharacter filter new HashSet(); for (char ch : str2.toCharArray()) { filter.add(ch); } StringBuilder result new StringBuilder(); for (char ch : deduplicated.toString().toCharArray()) { if (!filter.contains(ch)) { result.append(ch); } } return result.length() 0 ? NULL : result.toString(); }4.3 变体三输出要求变化题目变体输出结果字符串中每个字符的ASCII码值之和或者输出字典序最小的排列等。思路调整这类变体在完成基本的字符串处理后增加了额外的计算或排序步骤。ASCII码和在得到最终result字符串后遍历每个字符累加其(int)ch值即可。字典序最小如果要求对结果字符串中的字符进行排序那么“顺序去重”的意义可能就变了。需要仔细审题是先去重再排序还是排序后再去重通常在得到字符集合后可以将其放入列表用Collections.sortJava、sortedPython等进行排序然后再拼接。关键点面对变体一定要沉住气把新题目描述翻译成“过滤”、“去重”、“排序”、“计算”等基本操作的组合然后调整我们基础代码模块的执行顺序或参数。5. 机试实战技巧与避坑指南基于这道题和多年的刷题经验我总结了一些在华为OD机试乃至一般编程面试中的通用技巧和常见“坑点”。5.1 输入输出处理重中之重这是机试中错误率最高的部分之一尤其是对于C和Java选手。C/C:scanf(“%s”)遇空格停止。只要字符串可能包含空格就用fgets(C) 或getline(cin, str)(C)。fgets会存储换行符\n记得手动去除str[strcspn(str, “\n”)] 0;。C中混合使用cin 和getline时在getline前使用cin.ignore()清除缓冲区中的换行符。Java:使用Scanner.nextLine()读行。如果前面有nextInt(),nextDouble()等它们不会消耗行尾的换行符导致接下来的nextLine()读到空字符串。解决方案在nextInt()后额外调用一次nextLine()来消耗掉那个换行符。或者更统一的做法全部用nextLine()读取然后用Integer.parseInt()等方式转换数字。Python:input()比较省心但注意它会包含换行符吗实际上input()返回的是用户输入的一行不包含末尾的换行符。但为了安全用strip()处理一下首尾空白是个好习惯。JavaScript(Node.js):异步读取是最大的不同。务必提前练习readline模块的标准写法熟练掌握收集多行输入后统一处理的模式。我的踩坑记录有一次做一道题样例一直过不了调试了半小时才发现是cin n;后直接用getline(cin, str);导致str读取到的是空行。加上cin.ignore();后瞬间通过。这个教训让我之后每次都格外小心输入处理。5.2 数据结构选择与性能边界字符存在性判断优先使用哈希集合unordered_set,HashSet,set,Set。在数据规模不大比如字符总数就几百时用数组模拟C语言或线性查找理论上也可以但用集合是更通用、更不易出错的选择。字符串拼接Java: 循环内必须用StringBuilder/StringBuffer。Python: 循环内用列表append最后join。JavaScript: 循环内用数组push最后join。C: 使用string的或push_back在循环中效率尚可因为string可能有优化但显式使用ostringstream或reserve空间后再追加是更专业的做法。C: 手动维护字符数组索引。复杂度估算机试题通常有时间和内存限制。对于字符串题O(n)或O(n log n)的算法通常足够。如果遇到O(n²)的算法如嵌套循环查找就要考虑优化。本题使用哈希集合将嵌套查找优化为O(n)是典型的优化思路。5.3 边界条件与异常处理空字符串输入题目可能给出空字符串作为输入。你的代码能处理吗getline会读取到空字符串“”你的过滤和去重逻辑在空字符串上运行不应崩溃。结果为空本题明确要求输出”NULL“。其他题目可能要求输出空行或特定字符串。务必仔细阅读输出说明。大小写敏感题目是否说明区分大小写通常默认是区分的‘A‘和‘a‘是不同的字符。如果不区分可以在处理前统一用tolower或toupper转换。空格的处理空格也是一个字符在题目描述中要明确空格是否参与运算。在输入中如果使用getline空格会被包含在字符串内。5.4 调试与测试策略机试环境可能不提供强大的IDE调试功能因此需要掌握基本的调试方法本地充分测试在本地IDE中编写代码后构造多种测试用例常规用例str1“abcdefg”, str2“acf”- 期望输出“bdeg”去掉了a,c,f且顺序去重。包含空格str1“hello world”, str2“ol”- 期望输出“he wrd”。无公共字符str1“abc”, str2“xyz”- 期望输出“abc”。完全重叠str1“aaa”, str2“a”- 期望输出“NULL”过滤后为空。空输入str1“”, str2“abc”- 期望输出“NULL”。特殊字符包含数字、标点等。打印中间变量在代码关键步骤后打印中间结果如过滤后的字符串、去重集合的内容。这在线上环境也是常用的调试手段。理解错误类型编译错误仔细看报错信息通常是语法错误。运行错误数组越界、空指针、除零错误等。检查循环边界、指针/引用是否为空。答案错误最头疼。回头检查算法逻辑、边界条件、输入输出格式。用第1步的测试用例逐一验证。6. 从这道题延伸的编程能力提升一道好的题目就像一把钥匙能打开多扇门。“字符串解密”不仅是为了解题更能锻炼以下几种核心能力问题分解能力将“解密”这个复杂任务分解为“输入”、“过滤”、“去重”、“输出”等原子步骤。这是解决任何复杂工程问题的基本功。API熟悉度你是否能迅速想起每种语言中处理字符串和集合的关键APIfind,substr,Set,HashMap,list comprehension等等。平时多写、多总结形成肌肉记忆。空间换时间思维使用哈希集合额外O(M)空间将查找效率从O(N*M)提升到O(NM)是经典的“空间换时间”策略。在机试和面试中主动提出这种优化能极大提升印象分。边界思维空字符串、全重叠、包含空格、大小写……考虑周全的边界情况是写出健壮Robust代码的关键。这体现了程序员的严谨性。代码整洁度即便在时间紧张的机试中也要尽量保持代码结构清晰、变量命名有意义、关键步骤有注释。清晰的代码有助于你自己在检查时发现错误也方便考官阅读。最后我的个人体会是准备这类机试刷题是必要的但切忌死记硬背答案。更重要的是像今天这样对每一道经典的题目都去深入理解其背后的考点、可能的变体、不同语言的实现差异以及常见的陷阱。把一道题吃透远胜过盲目刷十道题。当你建立起这种分析问题和编码实现的肌肉记忆后遇到新的题目你自然就能快速定位到它属于哪种类型该用什么“武器库”里的工具来解决。希望这篇超详细的拆解能帮助你不仅搞定“字符串解密”这道题更能提升整体的解题能力。
华为OD机试真题解析：字符串解密算法与多语言实现详解
发布时间：2026/7/29 11:45:03
1. 项目概述与核心价值最近在技术社区和求职论坛里华为ODOutsourcing Development的机试真题讨论热度一直居高不下。很多朋友无论是应届生还是希望转岗的开发者都在寻找有效的备考资料。今天我想以一个过来人的身份和大家深入聊聊其中一道非常经典的题目——“字符串解密”。这道题之所以经典是因为它完美地融合了字符串处理、逻辑判断、数据结构如集合、映射以及算法思维是检验编程基本功和问题拆解能力的绝佳试金石。我当年备考时这道题也让我卡壳了很久后来通过反复琢磨和与朋友讨论才理清了其中的门道。这篇文章我就把我对这道题的理解、解题思路的完整拆解、不同语言C、C、Java、Python、JavaScript的实现细节以及那些容易踩坑的地方毫无保留地分享出来。无论你是刚开始准备华为OD机试还是单纯想提升自己的编程解题能力相信这篇长文都能给你带来实实在在的帮助。简单来说“字符串解密”题目通常会给你两个字符串比如一个加密字符串和一个密钥字符串要求你根据一系列规则例如过滤掉密钥中出现的字符然后对剩余字符进行某种排序或转换来还原出原始信息或得到目标字符串。它考察的不是多么高深的算法而是你对字符串API的熟练度、对边界条件的把控以及编写清晰、健壮代码的能力。接下来我们就一层层剥开这道题的外壳。2. 题目深度解析与需求拆解在拿到任何机试题时第一步绝不是急着写代码而是彻底读懂题目。很多失分都源于理解偏差。我们假设一道典型的“字符串解密”题目描述如下此为常见变体之一用于阐述思路题目描述: 给定两个字符串str1和str2。从str1中找出所有同时在str1和str2中出现的字符将这些字符从str1中去除。对str1中剩余的字符按照其在原字符串str1中的出现顺序进行去重即保留每个字符第一次出现的位置。如果去重后的字符串为空则输出NULL。输入两个字符串用空格隔开。输出处理后的字符串或NULL。2.1 核心需求与规则翻译我们需要将模糊的自然语言描述翻译成精确的、可执行的计算机逻辑步骤输入解析程序需要能正确读取两个可能包含空格的字符串。这里就有第一个坑如果用简单的cin str1 str2C遇到字符串内部有空格就会出错。必须使用能读取整行的函数如getline(cin, str)。字符筛选去除公共字符核心操作是遍历str1判断每个字符是否存在于str2中。存在的判断需要高效。直接使用str2.find(ch)循环是直观的但时间复杂度是 O(n*m)。更优的做法是先用一个哈希集合HashSet记录str2中的所有字符这样判断存在性的操作可以降到 O(1)。顺序去重在筛选后的新字符串中需要按原始顺序保留不重复的字符。例如”abac“处理后应为”abc“。这同样可以利用一个哈希集合来辅助遍历字符如果该字符不在“已出现集合”中则将其加入结果字符串和集合。空结果处理这是一个关键的边界条件。如果经过上述处理结果字符串长度为0必须输出特定的”NULL“注意全大写而不是空字符串或什么都不输出。2.2 思路设计与算法选择基于以上分析我们可以设计出清晰的算法流程预处理读取字符串str1和str2。构建过滤器将str2中的所有字符放入一个哈希集合filterSet中。这一步的目的是为了 O(1) 时间复杂度的查找。第一次遍历过滤创建一个临时字符串tempStr。遍历str1的每个字符ch如果ch不在filterSet中则将ch追加到tempStr末尾。否则跳过该字符即过滤掉。第二次遍历去重创建一个结果字符串result和一个用于去重的哈希集合seenSet。遍历tempStr的每个字符ch如果ch不在seenSet中则将ch追加到result末尾并加入seenSet。否则跳过。输出检查result是否为空。若为空输出”NULL“否则输出result。复杂度分析假设str1长度为 Nstr2长度为 M。时间复杂度O(N M)。构建filterSet需要 O(M)两次遍历str1或tempStr各需要 O(N)哈希集合的插入和查找均为平均 O(1)。空间复杂度O(N M)。主要用于存储哈希集合和中间字符串。这个思路清晰效率也足够应对机试的一般数据规模。下面我们就用五种主流语言将其实现出来并看看每种语言实现时的特有技巧和注意事项。3. 多语言代码实现与细节剖析不同的编程语言有其独特的语法和标准库特性。实现同一算法时选择合适的工具和方法能让代码更简洁、高效。这里我假设输入格式为第一行是字符串str1第二行是字符串str2。3.1 C语言实现C语言没有内置的哈希集合需要自己实现字符的查找逻辑或者使用一个大小为128或256的数组来模拟哈希表ASCII字符集。#include stdio.h #include string.h #include stdbool.h #define CHAR_SET_SIZE 128 // 足够覆盖标准ASCII字符 int main() { char str1[1000], str2[1000]; char result[1000]; bool filter[CHAR_SET_SIZE] {false}; // 用于过滤的“哈希表” bool seen[CHAR_SET_SIZE] {false}; // 用于去重的“哈希表” // 读取输入注意使用fgets读取整行并去除可能的换行符 fgets(str1, sizeof(str1), stdin); str1[strcspn(str1, \n)] \0; // 去除换行符 fgets(str2, sizeof(str2), stdin); str2[strcspn(str2, \n)] \0; // 步骤1: 构建过滤器 for (int i 0; str2[i] ! \0; i) { // 将str2中的字符对应的ASCII码位置标记为true filter[(unsigned char)str2[i]] true; } // 步骤2: 过滤并顺序去重 int resultIndex 0; for (int i 0; str1[i] ! \0; i) { char ch str1[i]; // 只有当字符不在filter中且未被见过才加入结果 if (!filter[(unsigned char)ch] !seen[(unsigned char)ch]) { result[resultIndex] ch; seen[(unsigned char)ch] true; // 标记为已见 } } result[resultIndex] \0; // C字符串结束符 // 步骤3: 输出 if (resultIndex 0) { printf(NULL\n); } else { printf(%s\n, result); } return 0; }C语言实现要点与避坑指南输入处理scanf(“%s”, str)无法读取带空格的字符串。必须使用fgets。fgets会读取换行符\n并存入字符串所以需要用strcspn或手动遍历将其替换为\0。“哈希表”模拟使用布尔数组filter和seen是C语言中处理固定范围键值如ASCII字符最高效的方式。访问速度是O(1)且代码简单。无符号转换(unsigned char)ch是为了防止字符值为负数时虽然ASCII字符通常为正数组访问越界这是一个良好的防御性编程习惯。二合一操作注意上面的代码将“过滤”和“顺序去重”合并到了一个循环中。这是因为我们的seen数组只在过滤后的字符范围内生效逻辑是通的一个字符要进入结果必须同时满足“不在黑名单(filter)”和“第一次出现(seen)”两个条件。这比先过滤生成中间字符串再遍历去重更高效。空间分配示例中静态分配了大小为1000的数组。在机试中如果题目未明确说明最大长度可以适当开大一些如10000或者使用动态内存分配malloc但静态大数组在机试场景下更简单可靠。3.2 C实现C可以利用STL中的unordered_set来实现哈希集合代码会更贴近高层抽象。#include iostream #include string #include unordered_set using namespace std; int main() { string str1, str2; // 使用getline读取整行包括空格 getline(cin, str1); getline(cin, str2); // 步骤1: 构建过滤器 unordered_setchar filterSet(str2.begin(), str2.end()); // 步骤2: 过滤并顺序去重 string result; unordered_setchar seenSet; for (char ch : str1) { // 如果字符不在过滤集中且是第一次出现 if (filterSet.find(ch) filterSet.end() seenSet.find(ch) seenSet.end()) { result.push_back(ch); seenSet.insert(ch); } } // 步骤3: 输出 if (result.empty()) { cout NULL endl; } else { cout result endl; } return 0; }C实现要点与避坑指南输入处理getline(cin, str)是读取带空格字符串的标准做法。如果之前用过cin someVar会在输入缓冲区留下换行符导致接下来的getline直接读取到一个空行。此时需要在getline前使用cin.ignore()清空缓冲区。在本题只有两个字符串输入时连续使用getline是安全的。STL容器初始化unordered_setchar filterSet(str2.begin(), str2.end())在构造时直接使用迭代器范围初始化比先声明空集合再循环insert更简洁。查找操作unordered_set::find返回一个迭代器。如果没找到则返回end()。这是判断元素是否在集合中的标准写法。性能考量unordered_set在平均情况下有O(1)的查找性能但对于字符这种数量很少的键其开销可能比C语言的布尔数组大。但在机试的数据规模下这点差异完全可以忽略代码的清晰性和可维护性更重要。二合一循环和C语言版本一样这里也合并了过滤和去重步骤逻辑清晰。3.3 Java实现Java的集合框架非常强大使用HashSet可以轻松实现相同逻辑。import java.util.HashSet; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); // 读取两行 String str1 scanner.nextLine(); String str2 scanner.nextLine(); scanner.close(); // 步骤1: 构建过滤器 HashSetCharacter filterSet new HashSet(); for (int i 0; i str2.length(); i) { filterSet.add(str2.charAt(i)); } // 步骤2: 过滤并顺序去重 StringBuilder result new StringBuilder(); HashSetCharacter seenSet new HashSet(); for (int i 0; i str1.length(); i) { char ch str1.charAt(i); if (!filterSet.contains(ch) !seenSet.contains(ch)) { result.append(ch); seenSet.add(ch); } } // 步骤3: 输出 if (result.length() 0) { System.out.println(NULL); } else { System.out.println(result.toString()); } } }Java实现要点与避坑指南输入处理Scanner.nextLine()读取整行。同样要注意如果前面有nextInt()等调用需要用额外的nextLine()消耗掉换行符。HashSetCharacterJava的集合不能存储基本类型所以需要使用包装类Character。好在自动装箱Autoboxing机制让add(ch)和contains(ch)写起来很自然。StringBuilder在循环中拼接字符串务必使用StringBuilder而不是直接用String的操作符。后者在循环中会创建大量临时String对象效率极低是机试中的大忌。关闭Scanner虽然对于标准输入不关闭问题不大但养成用完Scanner后调用close()的习惯是好的。判空使用result.length() 0或result.isEmpty()Java 6来判断。3.4 Python实现Python的代码最为简洁得益于其强大的内置数据类型集合set和列表推导式。def main(): str1 input().strip() str2 input().strip() # 步骤1: 构建过滤器 filter_set set(str2) # 步骤2: 过滤并顺序去重 seen_set set() result_chars [] for ch in str1: if ch not in filter_set and ch not in seen_set: result_chars.append(ch) seen_set.add(ch) # 步骤3: 输出 result .join(result_chars) if not result: print(NULL) else: print(result) if __name__ __main__: main()Python实现要点与避坑指南输入处理input()默认读取一行并包含末尾换行符strip()可以去除首尾的空白字符包括换行符和空格。集合操作set(str2)一行代码就能将字符串转换为字符集合极其方便。in和not in操作符用于判断成员关系可读性很高。列表构建结果在循环中我们将符合条件的字符追加到列表result_chars中最后用.join(result_chars)拼接成字符串。这是Python中构建字符串的高效做法。避免在循环中使用result ch因为字符串是不可变对象每次都会生成新对象。空值判断if not result:可以优雅地判断字符串是否为空。Python中空字符串、空列表等在布尔上下文中为False。3.5 JavaScript (Node.js)实现在华为OD的机试环境中JavaScript通常指Node.js环境。其实现思路与其他语言类似。const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout }); let inputLines []; rl.on(line, (line) { inputLines.push(line.trim()); if (inputLines.length 2) { solve(); rl.close(); } }); function solve() { const str1 inputLines[0]; const str2 inputLines[1]; // 步骤1: 构建过滤器 const filterSet new Set(); for (let ch of str2) { filterSet.add(ch); } // 步骤2: 过滤并顺序去重 const resultChars []; const seenSet new Set(); for (let ch of str1) { if (!filterSet.has(ch) !seenSet.has(ch)) { resultChars.push(ch); seenSet.add(ch); } } // 步骤3: 输出 const result resultChars.join(); if (result.length 0) { console.log(NULL); } else { console.log(result); } }JavaScript实现要点与避坑指南输入处理Node.js没有像其他语言那样的同步控制台读取函数。必须使用readline模块异步读取行。这里采用收集两行输入后触发处理的模式。Set对象ES6引入的Set是完美的哈希集合实现。使用new Set()创建add方法添加元素has方法检查存在性。字符串迭代for...of循环可以直接迭代字符串中的字符Unicode码点比用for循环索引更现代和可靠能正确处理一些特殊Unicode字符。数组拼接字符串和Python一样使用数组resultChars收集字符最后用join()拼接性能优于在循环中进行字符串连接。环境确认务必确认机试环境支持ES6语法现代Node.js版本都支持。Set和for...of都是ES6特性。4. 解题思路的扩展与变体分析“字符串解密”只是一个母题在实际机试或面试中它会有各种各样的变体。掌握核心思路后关键在于灵活调整。下面分析几种常见变体及应对策略。4.1 变体一解密规则变化题目变体不是去除公共字符而是要求只保留str1和str2的公共字符然后进行顺序去重。思路调整这实际上更简单。我们只需要修改过滤条件。在构建了str2的字符集合filterSet后遍历str1时判断条件从if ch not in filterSet改为if ch in filterSet。核心的去重逻辑保持不变。代码示例Pythondef variant1(str1, str2): filter_set set(str2) seen_set set() result_chars [] for ch in str1: if ch in filter_set and ch not in seen_set: # 仅此条件改变 result_chars.append(ch) seen_set.add(ch) result .join(result_chars) return result if result else NULL4.2 变体二处理顺序变化题目变体先对str1进行顺序去重然后再去除与str2的公共字符。思路调整步骤顺序发生了变化。我们需要先创建一个“已见集合”遍历str1生成一个顺序去重后的中间字符串。然后再用str2的集合过滤这个中间字符串。注意这种情况下去重是基于原始str1的顺序。代码示例Javapublic static String variant2(String str1, String str2) { // 第一步对str1顺序去重 StringBuilder deduplicated new StringBuilder(); HashSetCharacter seen new HashSet(); for (char ch : str1.toCharArray()) { if (!seen.contains(ch)) { deduplicated.append(ch); seen.add(ch); } } // 第二步用str2过滤 HashSetCharacter filter new HashSet(); for (char ch : str2.toCharArray()) { filter.add(ch); } StringBuilder result new StringBuilder(); for (char ch : deduplicated.toString().toCharArray()) { if (!filter.contains(ch)) { result.append(ch); } } return result.length() 0 ? NULL : result.toString(); }4.3 变体三输出要求变化题目变体输出结果字符串中每个字符的ASCII码值之和或者输出字典序最小的排列等。思路调整这类变体在完成基本的字符串处理后增加了额外的计算或排序步骤。ASCII码和在得到最终result字符串后遍历每个字符累加其(int)ch值即可。字典序最小如果要求对结果字符串中的字符进行排序那么“顺序去重”的意义可能就变了。需要仔细审题是先去重再排序还是排序后再去重通常在得到字符集合后可以将其放入列表用Collections.sortJava、sortedPython等进行排序然后再拼接。关键点面对变体一定要沉住气把新题目描述翻译成“过滤”、“去重”、“排序”、“计算”等基本操作的组合然后调整我们基础代码模块的执行顺序或参数。5. 机试实战技巧与避坑指南基于这道题和多年的刷题经验我总结了一些在华为OD机试乃至一般编程面试中的通用技巧和常见“坑点”。5.1 输入输出处理重中之重这是机试中错误率最高的部分之一尤其是对于C和Java选手。C/C:scanf(“%s”)遇空格停止。只要字符串可能包含空格就用fgets(C) 或getline(cin, str)(C)。fgets会存储换行符\n记得手动去除str[strcspn(str, “\n”)] 0;。C中混合使用cin 和getline时在getline前使用cin.ignore()清除缓冲区中的换行符。Java:使用Scanner.nextLine()读行。如果前面有nextInt(),nextDouble()等它们不会消耗行尾的换行符导致接下来的nextLine()读到空字符串。解决方案在nextInt()后额外调用一次nextLine()来消耗掉那个换行符。或者更统一的做法全部用nextLine()读取然后用Integer.parseInt()等方式转换数字。Python:input()比较省心但注意它会包含换行符吗实际上input()返回的是用户输入的一行不包含末尾的换行符。但为了安全用strip()处理一下首尾空白是个好习惯。JavaScript(Node.js):异步读取是最大的不同。务必提前练习readline模块的标准写法熟练掌握收集多行输入后统一处理的模式。我的踩坑记录有一次做一道题样例一直过不了调试了半小时才发现是cin n;后直接用getline(cin, str);导致str读取到的是空行。加上cin.ignore();后瞬间通过。这个教训让我之后每次都格外小心输入处理。5.2 数据结构选择与性能边界字符存在性判断优先使用哈希集合unordered_set,HashSet,set,Set。在数据规模不大比如字符总数就几百时用数组模拟C语言或线性查找理论上也可以但用集合是更通用、更不易出错的选择。字符串拼接Java: 循环内必须用StringBuilder/StringBuffer。Python: 循环内用列表append最后join。JavaScript: 循环内用数组push最后join。C: 使用string的或push_back在循环中效率尚可因为string可能有优化但显式使用ostringstream或reserve空间后再追加是更专业的做法。C: 手动维护字符数组索引。复杂度估算机试题通常有时间和内存限制。对于字符串题O(n)或O(n log n)的算法通常足够。如果遇到O(n²)的算法如嵌套循环查找就要考虑优化。本题使用哈希集合将嵌套查找优化为O(n)是典型的优化思路。5.3 边界条件与异常处理空字符串输入题目可能给出空字符串作为输入。你的代码能处理吗getline会读取到空字符串“”你的过滤和去重逻辑在空字符串上运行不应崩溃。结果为空本题明确要求输出”NULL“。其他题目可能要求输出空行或特定字符串。务必仔细阅读输出说明。大小写敏感题目是否说明区分大小写通常默认是区分的‘A‘和‘a‘是不同的字符。如果不区分可以在处理前统一用tolower或toupper转换。空格的处理空格也是一个字符在题目描述中要明确空格是否参与运算。在输入中如果使用getline空格会被包含在字符串内。5.4 调试与测试策略机试环境可能不提供强大的IDE调试功能因此需要掌握基本的调试方法本地充分测试在本地IDE中编写代码后构造多种测试用例常规用例str1“abcdefg”, str2“acf”- 期望输出“bdeg”去掉了a,c,f且顺序去重。包含空格str1“hello world”, str2“ol”- 期望输出“he wrd”。无公共字符str1“abc”, str2“xyz”- 期望输出“abc”。完全重叠str1“aaa”, str2“a”- 期望输出“NULL”过滤后为空。空输入str1“”, str2“abc”- 期望输出“NULL”。特殊字符包含数字、标点等。打印中间变量在代码关键步骤后打印中间结果如过滤后的字符串、去重集合的内容。这在线上环境也是常用的调试手段。理解错误类型编译错误仔细看报错信息通常是语法错误。运行错误数组越界、空指针、除零错误等。检查循环边界、指针/引用是否为空。答案错误最头疼。回头检查算法逻辑、边界条件、输入输出格式。用第1步的测试用例逐一验证。6. 从这道题延伸的编程能力提升一道好的题目就像一把钥匙能打开多扇门。“字符串解密”不仅是为了解题更能锻炼以下几种核心能力问题分解能力将“解密”这个复杂任务分解为“输入”、“过滤”、“去重”、“输出”等原子步骤。这是解决任何复杂工程问题的基本功。API熟悉度你是否能迅速想起每种语言中处理字符串和集合的关键APIfind,substr,Set,HashMap,list comprehension等等。平时多写、多总结形成肌肉记忆。空间换时间思维使用哈希集合额外O(M)空间将查找效率从O(N*M)提升到O(NM)是经典的“空间换时间”策略。在机试和面试中主动提出这种优化能极大提升印象分。边界思维空字符串、全重叠、包含空格、大小写……考虑周全的边界情况是写出健壮Robust代码的关键。这体现了程序员的严谨性。代码整洁度即便在时间紧张的机试中也要尽量保持代码结构清晰、变量命名有意义、关键步骤有注释。清晰的代码有助于你自己在检查时发现错误也方便考官阅读。最后我的个人体会是准备这类机试刷题是必要的但切忌死记硬背答案。更重要的是像今天这样对每一道经典的题目都去深入理解其背后的考点、可能的变体、不同语言的实现差异以及常见的陷阱。把一道题吃透远胜过盲目刷十道题。当你建立起这种分析问题和编码实现的肌肉记忆后遇到新的题目你自然就能快速定位到它属于哪种类型该用什么“武器库”里的工具来解决。希望这篇超详细的拆解能帮助你不仅搞定“字符串解密”这道题更能提升整体的解题能力。
