华为OD机试高频题：字符串摘要算法详解与多语言实现 1. 项目概述从一道机试题看字符串摘要算法的实战价值最近在技术社区和求职圈里华为OD的机试题目热度一直不减尤其是那些涉及字符串处理的题目几乎是必考项。我翻看了不少真题回忆录发现“字符串摘要”这类算法题出现的频率相当高。它不像单纯的字符串反转或查找那么简单而是要求你综合运用哈希、排序、滑动窗口等多种技巧去提炼和压缩字符串的核心信息非常考验编程基本功和逻辑思维能力。很多朋友在初次接触时会觉得题目描述有点绕不知道从何下手或者写出来的代码虽然能跑通样例但一遇到边界情况就崩溃效率也不尽如人意。今天我们就来彻底拆解这道经典的“字符串摘要”算法题。我会先带你理解题目到底要我们做什么然后一步步推导出高效的解题思路最后给出C、Java、JavaScript和Python四种主流语言的完整实现代码。更重要的是我会分享我在刷题和面试中总结出来的那些“坑点”和调试技巧比如在C里处理字符计数时map和unordered_map的选择在Java里如何避免字符串拼接的性能陷阱在JavaScript中处理Unicode字符的注意事项以及在Python里如何写出既简洁又高效的代码。无论你是正在备战华为OD还是想巩固字符串算法这篇文章都能给你提供一份可以直接“抄作业”的实战指南。2. 题目深度解析与核心需求拆解2.1 题目描述还原与题意理解首先我们需要统一对题目的理解。根据多个渠道的真题回忆“字符串摘要”算法的典型描述如下给定一个只包含小写字母的字符串有些变体可能包含数字要求生成该字符串的“摘要”。生成规则通常包含以下几步连续字符压缩对于字符串中连续出现的相同字符将其替换为“该字符 出现次数”。例如aaabb压缩后成为a3b2。注意只出现一次的字符不记录次数例如ab压缩后仍是ab。字符排序常见变体在压缩之后可能需要根据字符的原始出现顺序、字符本身或者压缩后的新字符串进行排序。一个常见的变体是忽略压缩后的数字仅根据字符在原始字符串中首次出现的顺序对压缩后的字符连带其数字进行重排。另一种变体是要求按字符ASCII码升序排列。非连续字符处理这是关键也是容易混淆的点。摘要算法不是简单的“游程编码”。游程编码只处理连续的相同字符。而字符串摘要算法要求对于非连续出现的相同字符需要将它们出现的所有位置找到并计算它们之间的“距离”或“索引差”然后将这些信息也编码进去。但更常见的简化描述是最终输出的摘要字符串需要按字符在原始字符串中首次出现的顺序输出并且对于每个字符输出其本身以及它出现的总次数如果大于1。为了聚焦核心算法思想我们采用一个清晰且高频的题目定义输入一个字符串s仅包含小写字母。输出字符串的摘要。规则统计字符串中每个字符出现的总次数。将统计结果按照字符在字符串中首次出现的顺序进行排序。对于每个字符如果出现次数大于1则输出字符次数如果等于1则只输出字符。示例输入aaabbccccd输出a3b2c4d解释字符a首次出现在位置0出现3次输出”a3“b首次出现在位置3出现2次输出”b2“c首次出现在位置5出现4次输出”c4“d首次出现在位置9出现1次输出”d“。按首次出现顺序拼接得到”a3b2c4d“。这个定义避免了“距离”计算的复杂性聚焦于顺序统计和条件格式化这正是华为OD机试中考查的重点对数据结构哈希表、列表的熟练运用以及对遍历顺序的精确控制。2.2 解题思路分析与算法选型理解了题目要求我们来设计算法。核心需求可以分解为两个关键任务统计次数和保持顺序。统计字符出现次数这是一个典型的“词频统计”问题。最自然的选择是使用哈希表Hash Map。键Key是字符值Value是该字符出现的次数。我们只需要遍历一次字符串对每个字符在哈希表中进行计数即可。时间复杂度是O(n)n为字符串长度。按首次出现顺序输出哈希表本身是无序的某些语言如Python 3.7的dict、JavaScript的Map会保持插入顺序但作为通用解法我们不应依赖此特性。为了按首次出现顺序输出我们需要额外记录字符的“首次出现顺序”。方法一使用LinkedHashMapJava或OrderedDictPython collections。这些数据结构在保有哈希表O(1)查询性能的同时维护了键的插入顺序。这几乎是为本题量身定做的。遍历字符串插入字符并计数遍历完成后这个容器的迭代顺序自然就是字符首次出现的顺序。方法二使用“哈希表 顺序列表”。这是更通用的解法适用于所有语言。我们维护一个哈希表countMap用于计数同时维护一个列表orderList。遍历字符串时如果当前字符不在countMap中说明是第一次出现我们将其加入orderList。无论是否第一次出现都在countMap中增加计数。最后我们遍历orderList从countMap中取出对应字符的次数组装成最终字符串。格式化输出遍历按顺序存储的字符检查其在countMap中的次数。如果次数为1只拼接字符如果大于1拼接字符和次数需要将整数转换为字符串。算法流程图逻辑描述开始 输入字符串 s 初始化 哈希表 countMap 初始化 列表 orderList 对于 s 中的每一个字符 c 如果 c 不在 countMap 中 将 c 加入 orderList 末尾 将 countMap[c] 的值加1 初始化结果字符串 result 为空字符串 对于 orderList 中的每一个字符 c 次数 countMap[c] 如果 次数 1 result c 否则 result c 将次数转换为字符串 输出 result 结束这个思路清晰效率高两次遍历O(n)时间复杂度空间复杂度为O(k)k是字符串中不同字符的个数最大26。接下来我们进入具体的代码实现环节我会结合每种语言的特性和常见“坑点”进行详细说明。3. 多语言核心实现与代码精讲我将分别用C、Java、JavaScript和Python实现上述算法。每种实现我都会附上完整代码并重点讲解其中的关键点、语言特性以及如何避免常见错误。3.1 C实现注重效率与容器选择C的实现需要关注容器的选择和字符串操作的效率。#include iostream #include string #include vector #include unordered_map std::string generateStringSummary(const std::string s) { // 使用 unordered_map 进行O(1)复杂度的字符计数 std::unordered_mapchar, int countMap; // 使用 vector 记录字符首次出现的顺序 std::vectorchar orderList; // 第一次遍历统计次数并记录顺序 for (char c : s) { // 如果字符第一次出现加入顺序列表 if (countMap.find(c) countMap.end()) { // 也可以用 countMap.count(c) 0 orderList.push_back(c); } countMap[c]; // 计数加1 } // 构建结果字符串 std::string result; // 预分配内存避免多次扩容优化点 result.reserve(s.length()); // 第二次遍历按顺序生成摘要 for (char c : orderList) { int count countMap[c]; result.push_back(c); // 添加字符 if (count 1) { // 将数字转换为字符串并追加 // 使用 to_string 是最简单直接的方法 result.append(std::to_string(count)); } } return result; } int main() { std::string testStr aaabbccccd; std::string summary generateStringSummary(testStr); std::cout Input: testStr std::endl; std::cout Output: summary std::endl; // 输出: a3b2c4d return 0; }C实现关键点解析容器选择std::unordered_mapchar, int用于字符计数。选择unordered_map而非map是因为前者基于哈希表平均O(1)的查找和插入效率更高而map基于红黑树是O(log n)。对于字符键范围很小哈希表优势明显。std::vectorchar用于记录字符首次出现顺序。vector在尾部插入push_back效率高且能保持插入顺序。查找与插入if (countMap.find(c) countMap.end())是检查键是否存在的标准方式。在C17及以上可以使用if (countMap.try_emplace(c, 0).second)它更高效且能避免不必要的默认构造。字符串拼接优化result.reserve(s.length())这是一个重要的性能优化。由于我们知道结果字符串的长度最多和原字符串一样长当所有字符只出现一次时预分配足够空间可以避免result在动态增长过程中多次重新分配内存和拷贝数据对于长字符串能显著提升性能。使用result.push_back(c)和result.append(std::to_string(count))进行拼接。数字转字符串使用std::to_string(count)将整数转换为字符串这是C11之后的标准方法简单可靠。注意std::unordered_map的迭代顺序是不确定的所以绝对不能直接遍历它来输出结果必须依赖orderList。3.2 Java实现利用LinkedHashMap简化逻辑Java的LinkedHashMap完美契合本题需求它既保留了HashMap的快速存取特性又通过一个双向链表维护了元素的插入顺序。import java.util.LinkedHashMap; import java.util.Map; public class StringSummary { public static String generateStringSummary(String s) { // 使用LinkedHashMap键为字符值为出现次数 // 它默认按插入顺序迭代这正是我们需要的 MapCharacter, Integer linkedMap new LinkedHashMap(); // 单次遍历即可完成统计和顺序记录 for (char c : s.toCharArray()) { // getOrDefault 是简洁的写法如果不存在则返回0然后加1 linkedMap.put(c, linkedMap.getOrDefault(c, 0) 1); } // 使用StringBuilder构建结果字符串性能远优于String拼接 StringBuilder result new StringBuilder(); // 遍历LinkedHashMap其entrySet的顺序就是插入顺序字符首次出现顺序 for (Map.EntryCharacter, Integer entry : linkedMap.entrySet()) { char key entry.getKey(); int value entry.getValue(); result.append(key); if (value 1) { result.append(value); } } return result.toString(); } public static void main(String[] args) { String testStr aaabbccccd; String summary generateStringSummary(testStr); System.out.println(Input: testStr); System.out.println(Output: summary); // 输出: a3b2c4d } }Java实现关键点解析LinkedHashMap的妙用这是本解法的核心。LinkedHashMap在HashMap的基础上增加了一个维护插入顺序的双向链表。我们只需要一次遍历将字符和计数放入LinkedHashMap遍历完成后它的迭代顺序自然就是字符首次出现的顺序。这省去了维护单独顺序列表的步骤代码更简洁。getOrDefault方法linkedMap.getOrDefault(c, 0)是Java 8引入的非常实用的方法。如果键c存在返回其值如果不存在则返回默认值0。然后我们加1再put回去。这比传统的if-else判断containsKey再get/put的写法简洁得多。使用StringBuilder在循环中拼接字符串必须使用StringBuilder。如果使用String的操作符在循环体内会创建大量临时的String对象导致性能低下和内存浪费。StringBuilder在内部维护一个可变的字符数组效率高得多。遍历Map使用for (Map.EntryCharacter, Integer entry : linkedMap.entrySet())来同时获取键和值比先取keySet()再get(key)更高效。实操心得在Java面试或机试中如果题目要求保持插入顺序LinkedHashMap是你的首选。同时但凡涉及循环内字符串拼接一定要条件反射般地想到StringBuilder或StringBuffer线程安全场景。3.3 JavaScript实现处理Unicode与Map对象现代JavaScriptES6提供了Map对象它同样能保持键的插入顺序非常适合本题。function generateStringSummary(s) { // 使用Map对象它会记住键的原始插入顺序 const charMap new Map(); // 遍历字符串统计字符次数 for (const char of s) { // 如果Map中已有该字符获取当前值并加1否则设置初始值为1 charMap.set(char, (charMap.get(char) || 0) 1); } // 使用数组的join方法构建字符串性能较好 const resultParts []; // 遍历Map其顺序就是插入顺序 for (const [char, count] of charMap) { resultParts.push(char); if (count 1) { resultParts.push(count.toString()); } } // 将数组所有元素连接成一个字符串 return resultParts.join(); } // 测试 const testStr aaabbccccd; const summary generateStringSummary(testStr); console.log(Input: ${testStr}); console.log(Output: ${summary}); // 输出: a3b2c4dJavaScript实现关键点解析Map对象ES6的Map不仅键值对的形式更直观键可以是任何值而不仅仅是字符串而且它维护键值对的插入顺序。这是它与普通Object的一个关键区别。我们直接使用Map就能在遍历时得到字符首次出现的顺序。遍历字符串使用for...of循环来遍历字符串它会迭代字符串中的每个字符包括一些复杂的Unicode字符如表情符号但对于本题的小写字母完全够用。也可以使用for循环或Array.from(s)。简洁的计数逻辑charMap.set(char, (charMap.get(char) || 0) 1)这行代码非常精炼。charMap.get(char)尝试获取当前字符的计数如果不存在则返回undefined。(charMap.get(char) || 0)利用了逻辑或||的短路特性。如果get返回的是undefined假值则表达式结果为0否则为获取到的计数值。然后加1并通过set方法写回Map。字符串构建优化在循环中反复使用拼接字符串在JavaScript中同样有性能问题尽管现代引擎有优化。更推荐的做法是先将各部分推入一个数组resultParts最后使用Array.join()方法一次性连接。这种方法通常比循环拼接更快代码也更清晰。遍历Mapfor (const [char, count] of charMap)使用了Map的迭代器和解构赋值能直接拿到键值对非常方便。注意事项如果输入的字符串可能包含**代理对Surrogate Pairs**表示的Unicode字符如一些表情符号‘’for...of循环可以正确处理它会将代理对作为一个整体字符迭代。而传统的for循环或.split()会将其拆分成两个码元code unit导致错误计数。虽然本题限定小写字母但了解这一点对处理更广泛的字符串问题很重要。3.4 Python实现简洁与高效的平衡Python以其简洁的语法和强大的内置数据结构能让这道题的实现变得非常优雅。def generate_string_summary(s: str) - str: # 使用字典进行计数 # 使用列表推导式记录首次出现顺序保持顺序 order_list [] count_dict {} # 一次遍历完成统计和顺序记录 for ch in s: if ch not in count_dict: # 如果是第一次出现 order_list.append(ch) count_dict[ch] 0 # 初始化计数器 count_dict[ch] 1 # 计数加1 # 使用列表推导式构建结果字符列表最后用join连接 # 这是Python中高效的字符串构建方式 result_list [] for ch in order_list: result_list.append(ch) cnt count_dict[ch] if cnt 1: result_list.append(str(cnt)) return .join(result_list) # 测试 if __name__ __main__: test_str aaabbccccd summary generate_string_summary(test_str) print(fInput: {test_str}) print(fOutput: {summary}) # 输出: a3b2c4dPython实现关键点解析字典与列表的组合这是最通用的方法。count_dict普通字典用于O(1)时间复杂度的计数order_list用于记录字符首次出现的顺序。从Python 3.7开始普通字典dict已经正式成为有序字典会保持插入顺序。但是在算法题或面试中为了代码的清晰性和与老版本Python的兼容性显式使用order_list来记录顺序仍然是更推荐、更稳妥的做法它能明确体现你的算法逻辑。成员检查使用if ch not in count_dict:来检查字符是否第一次出现。在字典中检查键是否存在平均时间复杂度是O(1)非常高效。字符串构建与JavaScript类似避免在循环中使用result ch str(cnt)这样的字符串拼接。因为字符串在Python中是不可变对象每次拼接都会产生一个新的字符串对象。推荐的做法是先将所有部分放入一个列表result_list循环结束后使用.join(result_list)一次性连接。join方法在底层做了高度优化对于大量字符串拼接其性能优势是数量级的差距。类型注解def generate_string_summary(s: str) - str:使用了类型注解虽然不是强制要求但能让代码意图更清晰是现代Python的好习惯。更Pythonic的写法使用collections.OrderedDict如果你明确想使用有序字典并且环境是Python 3.7也可以这样写from collections import OrderedDict # 在Python 3.7中普通dict已有序但使用OrderedDict意图更明确 def generate_string_summary_v2(s: str) - str: od OrderedDict() for ch in s: od[ch] od.get(ch, 0) 1 # 使用get方法提供默认值 return .join([k (str(v) if v 1 else ) for k, v in od.items()])这种写法极其简洁一行核心逻辑。od.get(ch, 0)与Java的getOrDefault异曲同工。列表推导式[k (str(v) if v 1 else ) for k, v in od.items()]生成了最终的字符列表。但请注意在面试中写出这种高度浓缩的代码时最好能对每一步进行解释以展示你对语言特性的理解而不是炫技。4. 算法扩展、边界案例与性能考量4.1 处理更复杂的输入与规则变体我们之前讨论的是基础版本。实际机试中题目可能会有变体我们需要让算法具备更强的适应性。变体1包含大写字母和数字如果输入字符串可能包含大写字母‘A’-‘Z’和数字‘0’-‘9’我们的算法依然有效因为哈希表的键可以存储这些字符。但需要注意大小写敏感‘a’和‘A’会被视为不同的键。输出顺序题目可能要求不区分大小写或者按ASCII码整体排序。如果是前者我们在插入哈希表前需要先将字符统一转换为小写或大写ch ch.lower()。如果是后者我们可能需要在最后对orderList或字典的键进行排序而不是保持插入顺序。变体2需要输出字符的首次出现索引有些题目可能要求输出格式为“字符:首次出现索引,次数”例如“a:0,3 b:3,2 ...”。这只需要我们在第一次遇到字符时除了将其加入orderList还要在一个额外的哈希表如firstIndexMap中记录其索引。最后遍历时从firstIndexMap中取出索引即可。变体3真正的“游程编码”如果题目明确是游程编码Run-Length Encoding, RLE即只压缩连续字符那么算法完全不同。例如”aaabbcaa“的RLE结果是”a3b2c1a2“。这需要我们用双指针或一次遍历来统计连续段def run_length_encode(s: str) - str: if not s: return result [] count 1 for i in range(1, len(s)): if s[i] s[i-1]: count 1 else: result.append(s[i-1] (str(count) if count 1 else )) count 1 # 处理最后一个字符段 result.append(s[-1] (str(count) if count 1 else )) return .join(result)务必仔细审题区分是“统计总次数并按首次出现顺序输出”还是“游程编码”。4.2 边界条件与异常处理健壮的代码必须考虑边界条件空字符串输入如果输入字符串s为空或长度为0我们的算法应该返回什么通常返回空字符串“”是合理的。在代码中我们可以在开头进行检查。if not s: return 超长字符串虽然本题字符集有限但字符串长度可能很大例如上百万。我们的算法时间复杂度是O(n)空间复杂度是O(k)k≤26完全可以应对。但要注意在一些语言中如Python使用拼接字符串会导致性能灾难必须使用列表join的方式。非法字符输入题目明确说只包含小写字母但实际编程中可以加入断言或简单检查。if not s.islower(): # 简单检查非必须 # 可以根据题目要求决定是报错、忽略还是转换 pass4.3 性能分析与优化对比让我们对比一下四种实现的性能特点语言核心数据结构时间复杂度空间复杂度关键性能点Cunordered_mapvectorO(n)O(k)预分配字符串内存(reserve)能极大提升拼接效率。JavaLinkedHashMapO(n)O(k)使用StringBuilder是字符串拼接的性能关键。LinkedHashMap比HashMap略慢但在此题数据量下可忽略。JavaScriptMapO(n)O(k)使用数组push再join的方式构建字符串优于循环。Map的插入顺序特性简化了逻辑。Pythondictlist或OrderedDictO(n)O(k)使用列表append再.join()是性能最佳实践。普通dict(Py3.7)已有序但显式用list记录顺序更清晰通用。通用优化建议减少遍历次数理想情况是一次遍历完成统计和顺序记录。Java的LinkedHashMap和Python的OrderedDict/dict3.7解法天然就是一次遍历。C和通用解法需要两次遍历一次统计一次组装但依然是O(n)。选择高效的数据结构对于字符键哈希表(unordered_map,HashMap,dict,Map)是绝对首选。注意字符串构建在任何语言中在循环内进行不可变字符串的拼接都是性能瓶颈。务必使用对应的可变构建器StringBuilder, 列表, 数组。5. 实战调试技巧与常见“坑点”复盘即使思路正确在实现和调试时也可能遇到各种问题。这里我总结了一些在实现“字符串摘要”算法时容易踩的坑以及调试方法。5.1 各语言实现中的典型错误C常见坑直接遍历unordered_map输出这是最致命的错误。unordered_map的内部顺序是不确定的输出结果每次运行都可能不同。// 错误示例 for (auto pair : countMap) { // 顺序不确定 result pair.first ... }忘记预分配字符串空间对于长字符串频繁的操作会导致多次内存重分配严重拖慢程序。务必使用result.reserve(...)。使用map而非unordered_map对于字符键unordered_map的O(1)平均复杂度优于map的O(log n)。Java常见坑使用String进行循环拼接在for循环里写result key value;这会在堆上产生大量临时String对象极大影响性能和内存。必须用StringBuilder。误用HashMap如果使用普通的HashMap然后尝试直接遍历它来输出顺序会是随机的导致错误。必须用LinkedHashMap或额外维护顺序列表。JavaScript常见坑使用for...in遍历字符串或Mapfor...in是用来遍历对象可枚举属性的不适用于数组、字符串或Map的常规遍历。遍历字符串应用for...of或for循环遍历Map应用for...of或Map.forEach()。// 错误示例 for (let i in str) { ... } // i是字符串索引且可能遍历到原型链属性 for (let key in myMap) { ... } // 不会按你期望的方式工作在循环中使用拼接长字符串和Java、Python一样这有性能问题。应该用数组收集最后join。Python常见坑依赖dict的顺序在Python 3.6及以前在Python 3.6及更早版本中普通字典dict是无序的。如果你在那些环境或不确定环境版本时写了依赖字典顺序的代码就会出错。最安全的做法是始终显式使用order_list。使用拼接字符串在循环中result char str(count)性能极差。永远使用列表append然后join。混淆dict.get()的用法count_dict[ch] count_dict.get(ch, 0) 1是正确的。但注意get方法返回的是值的副本修改它不会影响字典中的值所以必须重新赋值。5.2 调试与测试用例设计写出代码后需要用全面的测试用例来验证。以下是一些必备的测试用例# 测试函数 def test(): test_cases [ (, ), # 空字符串 (a, a), # 单字符 (aa, a2), # 单一重复字符 (ab, ab), # 无重复字符 (aaabbccccd, a3b2c4d), # 标准用例 (abcabc, a2b2c2), # 字符交错出现 (zzzzzz, z6), # 全相同字符 (aabbaa, a4b2), # 字符重复出现但不连续 ] for input_str, expected in test_cases: result generate_string_summary(input_str) if result expected: print(f✓ PASS: {input_str} - {result}) else: print(f✗ FAIL: {input_str} - expected {expected}, got {result}) if __name__ __main__: test()设计测试用例的原则边界用例空字符串、单字符字符串。简单用例纯重复(”aaa“)、无重复(”abc“)。标准用例题目给的例子。复杂用例字符交错出现(”abcabc“)验证“首次出现顺序”和“总次数统计”是否正确。全相同字符极限情况如长串的同一个字符。在调试时如果结果不对可以在循环中打印countMap和orderList的内容检查统计和顺序是否正确。检查数字转换是否正确整数转字符串。检查条件判断count 1的逻辑。5.3 机试环境下的实战建议在华为OD或其他在线机试平台上除了算法正确还要注意以下几点处理输入输出仔细阅读题目说明的输入输出格式。是函数接口像我们上面实现的还是需要自己写完整的main函数处理标准输入输出例如在C中可能需要用cin s;在Java中用Scanner在Python中用input()。时间与空间限制我们的算法是O(n)时间O(k)空间对于字符串题通常足够。但要避免在循环内进行低效操作如Python的。代码风格与注释写清晰的代码适当添加注释尤其是复杂逻辑处。良好的命名如countMap,orderList本身就是最好的注释。先写思路注释如果时间允许可以在代码开头用注释简要写下你的算法步骤这有助于理清思路也方便考官理解。本地测试如果平台允许先用题目给的样例在本地或提供的测试环境跑通。