字符移动这道题我在不同的机试场合见过很多次贵州大学把它作为机试题华为OD机试里有类似版本华中科技大学软件学院复试也出现过。说白了就是给你一个字符串让你把某类字符统一搬到另一个位置同时保持其余字符的相对顺序不变。题目看起来很简单但真正在机试环境里手写代码时挂掉的人不在少数。今天我就以最常见的“把指定字符移动到字符串末尾”为例子把这道题的解法思路、代码实现、复杂度计算和机试避坑经验一次性讲透。不管你是准备考研复试、参加校招机考还是纯粹想巩固字符串处理的基本功这篇文章都可以直接拿来当复习材料。1. 字符移动到底在考什么1.1 常见题目设定与样例题目本身并不复杂但因为“字符移动”四个字写得太笼统网上流传的版本特别多。我按最常见的几种设定列个表方便你对号入座变体输入输出核心要求把*移动到末尾A*B*C*ABC***非*字符保持原顺序把*移动到开头a*b*c**abc非*字符保持原顺序把数字移动到末尾a1b2c3abc123字母保持原顺序把空格移动到末尾hello worldhelloworld非空格字符保持原顺序贵州大学那道题我刷到的版本大多是把*或指定字符移到末尾其他字符顺序不能乱。华为OD那边则喜欢出“把*移到开头”的变体本质上是一模一样的东西只是方向反了。华科软件学院复试也考过类似思路不过会稍微包装一下比如让你区分字母和数字然后把数字整体搬到后面。不管外层怎么变核心都能归结成一个问题给定一个判别条件把满足条件的字符挪到一端同时让其他字符的相对顺序保持不变。这就是所谓的“稳定分区”理解到这个层面题目就基本拿捏了。1.2 机试考这个题目背后在考察什么表面上是一道字符串题实际考的是三个基本功索引操作是否熟练。字符串本质就是字符数组指针、下标打架最容易出错。是否理解“稳定性”。很多考生写交换法会把顺序搞乱就是因为没意识到分区时要保序。在空间限制下能否写出更优解。暴力解法人人都会但机试经常要求 O(1) 额外空间这就筛掉一批人。机试环境通常没有断点调试也没有太多时间让你反复试错。这种小而精的题目能快速看出一个人有没有真正写过代码而不是只会背模板。所以不要因为它简单就轻视细节里全是分。1.3 为什么贵州大学、华科、华为OD都爱出这道题贵州大学复试机试偏基础字符移动是典型的“一题测基本功”写完马上能看出数据处理能力。华中科技大学软件学院复试时间紧题目量大这种能快速验证思维的题目适合放在中间作为区分度。华为OD机试双指针几乎是必考主题字符移动就是双指针最直白的入口后面还可以接滑动窗口、原地去重等进阶题。不要小看这个简单模型。它既可以用for循环暴力写又可以用双指针写还能扩展成稳定排序题。出题人只需要改一个条件就能从“会不会写”直接跳到“写得够不够好”。2. 解题思路从暴力到双指针的演进2.1 先写暴力版把需求彻底理清楚以“把*移动到末尾”为例最不动脑子的写法是第一次扫描字符串把所有非*字符按顺序放进一个新字符串。第二次扫描字符串把所有*字符按顺序追加到新字符串后面。用 Python 表示就是def move_star_to_end(s: str) - str: letters [] stars 0 for ch in s: if ch *: stars 1 else: letters.append(ch) return .join(letters) * * stars这个版本非常适合用来确认自己对题意的理解非*字符的顺序要保持*的数量要数清楚。但它用了额外空间而且如果题目要求“原地修改字符串”这个方案就直接不满足要求。暴力版真正的价值是作为“基准答案”。在机试时间特别紧张的时候先把暴力版跑通保住基础分再考虑优化。我见过不少考生一上来就想写双指针结果卡在边界条件上连暴力分都没拿到这是很亏的。2.2 双指针原地移动核心思想与为什么不会覆盖数据要写出 O(1) 额外空间的版本就不能再开一个新字符串必须在原字符数组上操作。这里只需要两个指针read负责遍历整个字符串它永远往前跑。write负责标记“下一个非目标字符应该放到哪里”。以*移动到末尾为例过程如下read从头到尾扫描如果s[read]不是*就把它写到s[write]然后write如果s[read]是*用一个计数器starCnt记下来不往前写扫描结束后原来的非*字符已经被搬到了字符串头部从write位置开始连续填starCnt个*。很多人会担心直接覆盖s[write]会不会把后面还没读到的数据弄丢答案是“不会”。因为write永远小于等于read每次覆盖的位置都是read已经走过的地方。读指针往前读新字符写指针只回头覆盖旧区域二者不会撞车。为了更直观拿A*B*C走一遍初始read0, write0read0字符A不是*放到s[0]write1read1字符*starCnt1read2字符B放到s[1]write2read3字符*starCnt2read4字符C放到s[2]write3扫描结束前三格已被写成ABC从write3开始填两个*结果就是ABC**整个过程中字符串内容虽然是原地变的但读指针始终保持在未读区域之前所以不会漏数据。2.3 如果要求“移到开头”就反向双指针上面说的是移到最后。如果题目改成“把*移动到最前面字母顺序保持不变”只需要把方向反过来从字符串尾部开始往前扫描维护一个write指向“从后往前下一个非目标字符应该放的位置”遇到非目标字符就放在后面遇到目标字符就计数扫描结束后在字符串头部填充目标字符。这样写的好处是所有非目标字符的原始顺序天然保持。反向扫描时我们是按从后往前的顺序把非目标字符放到后面的最后整体看前面到后面的顺序其实仍然维持了从左到右的相对位置。如果对这一点不太理解可以联想一下“倒序搬箱子”你从仓库最里面往外搬不想要的箱子剩下的箱子不要打乱它们在原队列里的前后关系从尾部开始搬运是唯一不会弄乱顺序的做法。2.4 更进阶的视角稳定分区问题字符移动其实就是算法里经典的 “stable partition” 问题。很多同学可能没意识到C 标准库里甚至有现成函数std::stable_partition它能把满足条件的元素分成两组同时保证两组的相对顺序都不变。不过机试不建议直接调库。一来有的环境禁止或者不方便用二来题目本身需要的逻辑特别简单手写双指针最多十行比调库更可控。但理解这个概念有个好处以后遇到“把奇数移到偶数前”“把负数移到正数后”这类题你会立刻想到同一个套路举一反三的能力就是这么练出来的。3. 完整实现三种语言代码与关键细节3.1 C 版本覆盖移动与尾部填充C 里string是可变类型可以在原串上操作。建议写一个接收引用参数的函数直接修改原字符串不需要返回值。#include string void moveStarToEnd(std::string s) { int write 0; int starCnt 0; for (int read 0; read (int)s.size(); read) { if (s[read] ! *) { s[write] s[read]; } else { starCnt; } } while (starCnt--) { s[write] *; } } void moveStarToFront(std::string s) { int write (int)s.size() - 1; int starCnt 0; for (int read (int)s.size() - 1; read 0; --read) { if (s[read] ! *) { s[write--] s[read]; } else { starCnt; } } for (int i 0; i starCnt; i) { s[i] *; } }这里有几个细节需要注意一是循环里read (int)s.size()这个类型转换。s.size()返回的是无符号数如果直接和int比较在极端情况下可能触发类型转换问题。机试时为了省事不写转换一般也没事但养成好习惯更安全。二是moveStarToFront中read 0的判断。read类型是int如果写成size_tread--到-1时会变成很大的正数直接死循环。我就在这个坑上栽过一次。三是函数结束后原字符串长度没有变。我们在填充阶段确实把后续位置都写成了*所以s的长度还是原来的长度但内容已经变成我们想要的结果。3.2 Python 版本不可变字符串的规避方法Python 字符串不可变没法像 C 那样直接改。最接近原地思路的做法是转成列表操作完再拼回来。def move_star_to_end(s: str) - str: arr list(s) write 0 star_cnt 0 for ch in s: # 遍历原字符串不要遍历 arr避免原地修改带来的混淆 if ch ! *: arr[write] ch write 1 else: star_cnt 1 # 从 write 位置开始填 *填完后 write 正好等于 len(s) while star_cnt: arr[write] * write 1 star_cnt - 1 return .join(arr)这段代码里有两点值得说第一for ch in s用的是原来字符串不是arr。虽然遍历arr也不会出大问题因为你只回头修改已走过的位置不会改变后面未读字符但初学者很容易懵。直接用原字符串最清晰。第二最后的join把整个列表拼回来。由于我们在填充*时已经填到列表末尾arr最后的结构就是“非星号 星号”长度没有变化不需要截断。Python 的双指针写法本身不复杂但要注意如果你在函数里把参数直接list(s)返回时要重新join这个过程会有 O(n) 的额外空间。严格来说不算真正意义上的“原地”但机试一般不会在这种题上卡 Python 的空间最多提示一下别用 O(n^2) 算法就好。3.3 Java 版本字符数组与字符串构造Java 的String也是不可变的同样要转成char[]操作。public class MoveChar { public static String moveStarToEnd(String s) { char[] arr s.toCharArray(); int write 0; int starCnt 0; for (char ch : arr) { if (ch ! *) { arr[write] ch; } else { starCnt; } } while (starCnt-- 0) { arr[write] *; } return new String(arr); } public static void main(String[] args) { String s A*B*C; System.out.println(moveStarToEnd(s)); // ABC** } }Java 版本需要注意for (char ch : arr)这个增强型 for 循环遍历的是原数组内容但我们在循环里修改arr[write]不会影响当前迭代变量ch的取值所以安全。如果先用String s遍历再修改arr效果也一样。new String(arr)会把整个字符数组变成字符串。因为数组长度始终等于原串长度且后面已经填满了*所以直接构造没问题。3.4 读入输出机试最容易翻车的地方机试时字符串读入是个坑点尤其当测试用例里可能包含空格时。如果字符串不含空格cin s或input().strip()都行。如果字符串可能含空格比如移动空格那道题C 就必须用getline(cin, s)Java 用BufferedReader.readLine()Python 用sys.stdin.readline().rstrip(\n)。一次输入多组数据时注意不要多读换行。C 的getline会残留上一次cin的换行符需要及时getchar()或换用getline统一处理。我曾经在联调时吃过一次亏题目明明说“字符串可能包含空格”我贪省事用cin s结果第二个测试点青一块紫一块最后才发现空格被截断了。从那以后看见“字符移动”“字符串处理”这类题我第一反应就是先确认读入方式。4. 实战校验样例推导与复杂度分析4.1 手动推演完整过程还是用A*B*C作为样例把每一轮的状态变化写出来。初始s A*B*C,read0,write0,starCnt0第1轮读A不是*执行s[0] s[0]write1第2轮读*starCnt1第3轮读B不是*执行s[1] B原来的*被覆盖write2第4轮读*starCnt2第5轮读C不是*执行s[2] Cwrite3循环结束s前三个字符依次为A,B,C即ABC*C中某些位置还没被覆盖但结果不重要。填充s[3] *,s[4] *最终结果是ABC**。注意在第5轮执行s[2] C时原来的s[2]是B已经读过了覆盖它没有任何问题。这就是write read带来的安全性。4.2 复杂度分析与对比解法时间复杂度额外空间稳定性适用场景暴力拼接O(n)O(n)稳定快速验证思路双指针原地O(n)O(1)非目标字符稳定机试首选反向双指针O(n)O(1)非目标字符稳定移到开头稳定分区库函数O(n)O(n)全部稳定工程中使用这里说的“稳定性”重点是在移动目标字符的过程中其他字符的相对顺序是否被破坏。双指针方案中非目标字符遇到一个写一个顺序天然保持。目标字符如果都是同一个字符比如*那它们之间无所谓稳定不稳定如果目标是不同的数字那就要额外处理后面我会专门讲。4.3 边界条件测试清单机试评分是按测试点来的边界条件一个都不能漏。我建议至少准备下面这些用例空字符串直接返回空不能崩溃。全是****输出不变。没有*abc输出不变。*在开头*abc移动到末尾后变成abc*。*在结尾abc*输出abc*或不变。多个*连续a**b*c输出abc***。所有字符都是目标字符以外abcdef输出不变。字符串长度很长10^6 或更大验证 O(n) 算法不会超时。把这些用例在自己本地跑一遍基本能确定代码是稳的。机试时不需要全跑但心里要有数。5. 常见问题与避坑实录5.1 机试现场最容易踩的坑这些年我看过太多人在字符移动上丢分总结下来无非这几类第一类是边遍历边删字符。有些人一看到移动第一反应是循环里erase或者delete然后插入到末尾。这个思路在 C 的vector或string上会触发元素搬移一次删除就是 O(n)整体复杂度能到 O(n^2)。数据量一大必超时。第二类是忘了处理目标字符计数。双指针代码里如果只做覆盖不数目标字符个数最后填充阶段就不知道要填多少个输出长度就不对。第三类是不熟悉语言特性直接修改不可变字符串。Java 和 Python 里String/str不可变有人直接s[i] ...编译都不通过。第四类是漏看题意把“移到末尾”看成“移到开头”白白浪费十分钟。机试紧张的时候人很容易被惯性思维带偏拿到题先圈一下“end”还是“front”。5.2 如果目标是数字字符还要保持相对顺序怎么办很多网上版本其实是“把数字移动到末尾”而不是移动*。数字和*最大的区别是数字字符不是同一个字符移动后需要保留原来的顺序。比如a1b2c3应该变成abc123而不是abc000或任意顺序。这时候双指针覆盖法就不好使了因为你在覆盖过程中可能把前面数字覆盖掉。最简单的保序办法是第一遍扫描把非数字字符按顺序放进一个字符串letters。第二遍扫描把数字字符按顺序放进另一个字符串digits。最后返回letters digits。Python 代码def move_digits_to_end(s: str) - str: letters [] digits [] for ch in s: if ch.isdigit(): digits.append(ch) else: letters.append(ch) return .join(letters) .join(digits)这个方案时间 O(n)额外空间 O(n)。机试的时候除非题目明确要求“原地修改”且数字顺序必须保留否则直接这样写完全没问题。如果真遇到更苛刻的要求那就得用稳定分区算法或者用额外的偏移数组辅助交换复杂度也会上去。一个小细节Python 的ch.isdigit()不仅能判断0-9还可能识别一些特殊数字字符比如上标数字。如果你想严格只判断0-9用0 ch 9更稳妥。5.3 快速写出无 bug 代码的私人习惯最后分享一个我自己的习惯。拿到这类题我不会马上写代码而是先在注释里写三行输入是什么字符串还是字符数组输出要求是什么原地修改还是返回新字符串移动哪个字符移到开头还是末尾其他字符顺序是否必须保持这三个问题明确后再动手。很多小问题其实都源于需求没看清比如移动*还是移动空格是移到开头还是移到末尾。机试时先花一分钟确认题意比写错后重新调试省太多时间。另外我习惯在写完双指针代码后马上用长度很短的样例手动跑一遍比如a*b确认read、write最终位置都符合预期。这种自测成本极低却能拦住一大半逻辑错误。字符移动看起来是个小题目但它串联了字符串、数组、双指针、稳定性和边界处理这些基本功。把这一题吃透再碰到“移动零到数组末尾”“奇数移到偶数前”这些同类题目你会觉得它们都长一个样。机试没有捷径但一层一层拆透之后你会发现所谓的难题其实都是这些基本功的组合。