华为OD机考C卷的字符串摘要这道题很多准备机考的同学应该都刷到过。题目描述看着不算长压缩规则也就几行字但我辅导过的不少朋友第一次做的时候都在边界情况和规则理解上栽了跟头——要么忘了处理最后一组连续字符要么没搞懂压缩后长度不小于原长度就返回原串到底什么意思。今天就把这道题的完整解法、Java实现和机考现场的经验一次性说清楚正在刷OD机试真题的同学可以直接参考。1. 华为OD机考C卷字符串摘要题目规则与考察意图1.1 机考背景双机位C卷是什么样的考试华为OD机考目前是社招和校招进入OD项目组的重要筛选环节考试采用在线编程的形式双机位监考意味着你需要在考试前架好两个摄像设备一个对着正面一个对着侧后方全程录屏和录像整个编码过程都会被记录。C卷是近几个批次轮换使用的题目集合和A卷、B卷相比C卷的题目更偏向字符串处理、哈希表、双指针这类基础算法整体难度适中但出题角度偶尔会有一些看似简单、实则暗藏规则细节的题字符串摘要就是典型代表。机考环境一般支持Java、Python、C等主流语言每道题有单独的提交和判题逻辑考试时间总体比较紧凑一道题从读题到提交基本要控制在30到40分钟内。所以刷题的时候不光要会做还要养成快速分析规则、快速编码、快速自测的习惯。1.2 字符串摘要题目的完整规则这道题的规则可以这样理解给定一个只包含大小写字母的字符串对其中连续出现的相同字符进行压缩连续出现的字符用连续出现次数该字符表示不连续出现的字符也就是单独出现的字符保持不变。压缩完成后如果压缩后的字符串长度不小于原字符串长度则返回原字符串否则返回压缩后的字符串。这里有几个容易混淆的点。第一连续出现指的是字符在字符串中相邻且相同比如aaabb中的aaa和bb而不是整个字符串中某个字符出现的总次数。第二压缩时数字加在字符的左边也就是3a而不是a3。第三单个字符即使在整个字符串中出现了多次只要每一次都不是连续出现它就不参与压缩比如abab中的两个a和两个b都是单独出现的压缩后依然保持abab。举个具体例子输入aaabbc连续段aaa压缩成3a连续段bb压缩成2bc单独出现保持不变压缩结果是3a2bc长度为5原串长度为6压缩后变短了所以返回3a2bc。再看输入aabb压缩后是2a2b长度也是4没有变短此时必须返回原串aabb。1.3 这道题到底在考察什么从面试官的角度看这道题想考察的核心能力有三个一是题面信息拆解能力你能不能从一段自然语言描述中提取出准确的规则边界二是单次线性遍历的处理能力字符串压缩这类问题几乎都可以通过一次遍历配合计数完成考察你对循环边界和状态重置的把握三是对结果的全局判断能力也就是最后长度比较这个环节很多人写代码的时候只想着怎么拼接压缩结果完全忘了还有长度没变短就返回原串这个兜底逻辑。换句话说这道题代码量不大但每一个环节都在考察你有没有把规则吃透。很多人在机考中写出的代码基本逻辑是对的但在最后一组连续字符处理、长度比较条件、空字符串等地方翻车最终导致部分测试用例无法通过。这篇文章后面的内容就是围绕这些细节展开的。2. 从规则到算法连续段统计的核心思路2.1 压缩规则的执行顺序与几个关键判断拿到这道题第一步不是急着写代码而是把压缩规则的执行顺序梳理清楚。压缩过程实际上是分段处理从左到右扫描字符串将连续的相同字符划为一个段然后对每个段单独决定是原样输出还是数字字符输出。单独出现的字符可以看作长度为1的段这种段直接输出字符本身长度大于1的段输出段长度字符。这里有一个关键判断长度为1的段也就是单独字符到底要不要输出数字1答案是不要。题目明确说了不连续出现的字符保持不变所以abc压缩后依然还是abc而不是1a1b1c。这一点直接决定了代码中拼接逻辑的写法计数等于1时不拼数字。还有一个容易忽略的判断是连续段长度的计数方式。如果当前字符和前一个字符相同计数加1如果不同说明一个段结束了需要先把之前的段处理完毕再重置计数开始新的段。整个扫描过程可以用一个count变量和一个prev变量来维护状态。2.2 单次遍历统计连续段的原理统计连续段只需要一次从左到右的遍历。我们用一个指针或者说一个循环变量遍历字符串同时维护两个状态当前段的字符prev和当前段的累计长度count。流程是这样的初始化count为1prev为字符串第一个字符。从第二个字符开始遍历如果当前字符等于prevcount加1。如果当前字符不等于prev说明prev所在的段已经结束先对prev这个段进行压缩输出然后更新prev为当前字符count重置为1。遍历结束后最后一组连续段还没有被输出需要在循环外再补一次段处理逻辑。这种做法的本质是把字符串看成一系列段的拼接每次遇到字符变化时就意味着上一个段结束、下一个段开始。用生活化的例子来说就像整理一摞扑克牌把相同数字的连续牌叠成一叠数字一变就换一叠每叠牌记录张数和牌面。初次写这道题的朋友最容易漏掉的就是循环结束后的最后一次段处理。比如字符串aaabbb循环从第2个字符开始到最后一个字符b时由于后面没有字符了循环内的字符不等分支不会触发最后一组bbb就没有被处理。所以循环外再写一次段处理逻辑是必须的这个细节一定要死在代码里。2.3 为什么压缩后长度比较这一步很容易被忽略题目要求压缩后字符串长度不小于原字符串长度时返回原字符串这个规则很多人读完就略过了直到写完代码发现某些用例返回了2a2b这种长度相等的字符串才意识到自己漏了个判断。为什么会有这个规则其实从信息论的角度看压缩的目的是缩短表达。如果一个压缩方案并没有让字符串变短那就没有意义。比如aabb压成2a2b长度都是4这种压缩除了增加两个数字之外并没有起到缩短作用自然就不应该被采用直接返回原串更合理。从算法实现的角度这个判断很简单用StringBuilder或者列表拼接出压缩结果然后比较压缩结果的长度与原串长度只有压缩结果长度严格小于原串长度时才返回压缩结果否则返回原串。这里要注意是严格小于等于的情况必须返回原串。我在实际改代码的过程中发现很多同学会把长度比较的条件写反写成如果压缩结果长度小于等于原串长度就返回压缩结果这是一个非常容易犯的错误。正确逻辑是等于时不采用压缩结果只有小于时才采用。2.4 复杂度的数学直觉这个算法的时间复杂度是O(n)n为原字符串长度因为只需要一次遍历空间复杂度方面如果使用StringBuilder拼接压缩结果最坏情况下压缩结果的长度不超过原串长度所以空间复杂度也是O(n)。这里有一个值得说的数学直觉对于只包含字母的字符串连续段长度为1时保持原样长度为2时压缩成2a数字1位加字母1位恰好也是2个字符长度大于2时压缩一定变短。所以压缩结果长度永远不会超过原串长度等于的情况是完全可能发生的这正好解释了为什么需要最后那一步长度比较。扩展一下如果数字达到10以上比如连续出现10个a压缩成10a长度为3原段长度是10节省更多如果连续段长度为1但很分散压缩这些段时不会添加数字所以不会导致长度膨胀。这也是为什么这道题可以直接使用StringBuilder拼接而不需要中途判断是否会变长最后统一比较即可。3. Java实现完整题解代码与逐行解析3.1 标准单指针遍历写法直接给出可以提交的Java实现import java.util.Scanner; public class Main { public static String compressString(String s) { if (s null || s.length() 1) { return s; } StringBuilder sb new StringBuilder(s.length()); int count 1; char prev s.charAt(0); for (int i 1; i s.length(); i) { char cur s.charAt(i); if (cur prev) { count; } else { if (count 1) { sb.append(count); } sb.append(prev); prev cur; count 1; } } if (count 1) { sb.append(count); } sb.append(prev); if (sb.length() s.length()) { return s; } return sb.toString(); } public static void main(String[] args) { Scanner sc new Scanner(System.in); String input sc.nextLine(); System.out.println(compressString(input)); } }这段代码的核心逻辑完全按照前面分析的流程来写。先处理空串和长度为1的串这两种情况下压缩结果只能等于原串直接返回即可。然后进入循环逐个处理字符循环结束后补上最后一组连续段的输出最后比较长度决定返回值。3.2 StringBuilder容量设置与字符串比较的细节代码里有一个细节创建StringBuilder的时候设置了初始容量为s.length()。这是因为压缩结果的长度不可能超过原串长度按原串长度初始化可以避免后续拼接过程中的扩容操作减少数组复制带来的性能损耗。虽然机考对性能要求不高但这是一个好习惯也是面试中可能被追问的优化点。关于最后的长度比较有一点要特别注意sb.length()统计的是StringBuilder当前内容的字符数不是容量。数字部分比如10a中的10是两个字符StringBuilder会按实际字符数计算这个不需要担心。比较条件写的是满足不小于原字符串长度时返回原字符串的规则等于的情况也包含在内。3.3 几个值得讨论的编码选择第一个选择是为什么不使用String直接拼接如果写String result count prev 每次拼接都会创建新的String对象循环执行多次时会有大量中间对象产生虽然字符串长度不大但代码风格上不如StringBuilder干净。机考中当然不算错但实际工程中肯定优先选择StringBuilder。第二个选择是可不可以把循环外的那段处理最后一组的逻辑合并到循环内可以但需要在循环结束前增加一个特殊分支或者使用双指针配合while循环来处理。从可读性角度我更推荐循环外加一段处理逻辑的方式因为思路清晰不容易在循环内部搞乱状态。第三个选择是如果输入字符串全是字母但大小写混在一起比如aAaa这时a和A是不同字符而aa是同一字符所以压缩结果是aA2a长度为5比原串4长返回原串aAaa。可以看到大小写敏感是天然满足的不需要额外处理。4. 本地自测用例从AC到不翻车的验证清单4.1 按照规则类别设计用例机考提交前最怕的不是不会做而是自以为做对了结果自测用例没覆盖到关键场景。字符串摘要这道题我建议大家在本地按规则类别设计测试用例每一个规则分支对应一组用例。第一类基础压缩场景。输入aaabbc预期输出3a2bc。这个用例覆盖了连续段长度大于1的压缩、长度等于2的连续段压缩、单个字符的保持不变以及压缩后变短会返回压缩串的情况。第二类压缩后等长的场景。输入aabb预期输出aabb。这里aa压缩成2a、bb压缩成2b压缩结果2a2b长度为4与原串长度相等按照规则必须返回原串。这类用例专门用来检验长度比较条件是否正确。第三类全部单字符场景。输入abc压缩结果abc长度等于原串返回原串abc。4.2 边界场景测试边界场景是机考最容易丢分的地方。字符串长度为1时比如输入z压缩结果还是z长度等于1返回原串代码中在开头就已经处理了这个情况。字符串长度为0时输入空字符串代码会在length() 1分支直接返回不会崩溃。还有一种边界场景需要反复确认连续段出现在字符串末尾。比如输入abccc压缩过程是a单独出现、b单独出现、ccc压成3c结果为ab3c长度为5原串为6返回ab3c。这个用例专门考验循环外那段处理逻辑如果漏掉末尾的ccc就不会被压缩输出就会变成abccc直接判错。再举一个更隐蔽的边界场景整个字符串就是一个连续段比如aaaaa压缩成5a长度为2原串长度为5返回5a。这种情况下循环内永远不会进入字符不等分支所有处理都依赖循环外的最后一段逻辑能很好地检验代码的完整性。4.3 容易误判的几种输入我在辅导过程中见过一些典型的误判输入这里列出来供大家避坑。输入aabbaa压缩结果是2a2b2a长度为6原串长度为6等长返回原串aabbaa。注意虽然有两段aa但它们分别出现在开头和结尾中间隔着bb压缩后两段都处理成2a这是正确的。有的同学会想当然地认为同一种字符要合并计数那就错了这里只压缩连续段不统计全局次数。输入bbbbbb压缩结果是6b长度2远小于原串6返回6b。这里验证了连续段长度很大时数字只有一位的情况。如果输入bbbbbbbbbb10个b压缩结果是10b长度3数字占了两位StringBuilder仍然能正确拼接。输入AbC三个字符都是单独出现压缩结果AbC长度相同返回原串。这里要确认大小写不同字符不会合并或压缩A、b、C三个字符完全不同互相独立。上面的用例全部通过这道题基本就稳了。5. 机考现场经验这类题目如何分配时间与排查Bug5.1 读题与规则确认阶段机考一道题的时间通常在30到40分钟字符串摘要这种题读题阶段建议控制在3到5分钟。读题时不要只扫一眼就开始写重点是把规则里的细节圈出来压缩条件是什么、单个字符是否保持不变、数字放在字符左边还是右边、最后要不要比较长度并返回原串。这些细节就是测试用例的切入点。我自己的习惯是读完题目先不看代码而是用一两分钟把题目的输入输出规则在草稿纸上写几个例子比如aaabbc应该输出什么、aabb应该输出什么然后用这些例子来驱动编码。这个过程能显著降低写代码时对规则理解的偏差。如果机考环境支持本地调试建议把上面列出的用例直接跑一遍。如果不支持也要在IDE里先跑通再提交因为在线判题往往只显示部分通过情况提交后发现错误再调会比较浪费时间。5.2 编码与自测阶段编码阶段字符串摘要这类题不建议一上来就考虑各种优化写法先把最朴素的单指针遍历版本写出来确保逻辑正确然后自测用例全部通过后再考虑是否优化。机考环境下正确通过远比代码优雅重要。自测时有一个小技巧把预期输出写在一个注释里然后逐个用例运行比对。比如你可以一次性写一个test方法把多个用例塞进去统一打印输入、实际输出、预期输出和是否通过。这样比手动一次一次输入要高效也能避免自己肉眼比对时看错。如果提交后发现有测试用例没过按我的经验优先检查三个位置循环外最后一组连续段是否处理、长度比较是否用了严格小于、长度为1或空字符串时是否提前返回。字符串摘要这道题的Bug基本都藏在这三个位置逐个排查通常几分钟就能定位。5.3 OD机考中字符串题的整体备考思路字符串摘要只是OD机考字符串大类里的一道题。备考时建议把它和相邻的知识点放在一起练习比如字符串去重、字符计数、滑动窗口、双指针等。你会发现很多题目都是同一个套路一次遍历维护几个状态变量在特定条件下更新结果。掌握这种模式化思维后遇到新题也能快速拆解。另外OD机考的题目包装经常变化但核心算法不变。比如字符串摘要可能换一种说法实际还是连续段压缩与长度判断。备考时不要死记题解而是要把规则拆解能力练出来读题时抓住连续单独返回原串这类关键词自然就能映射到对应的算法结构。还有一点建议机考前一周每天固定刷两三道C卷真题每一道都按读题拆规则、写代码、列用例自测的完整流程来做时间控制在40分钟内。这样上了考场时间分配的节奏感和对题型的熟悉度都会有明显提升。字符串摘要这种题目刷过和没刷过考场上的心态是完全不一样的。