华为OD高频机试：状态机解析字符串最长数字串（含正负号）
1. 项目概述一道经典的字符串处理机试题最近在整理一些大厂技术岗的机试真题发现“在字符串中找出连续最长的数字串含-号”这道题出现的频率相当高尤其是在华为OD的机试环节。这不仅仅是一道简单的字符串遍历题它巧妙地融合了状态机思想、边界条件处理和多语言实现的考察非常能检验一个程序员的基本功是否扎实。题目看似简单——给你一个字符串找出其中连续最长的数字子串并且这个数字串可以以正负号或-开头。但实际动手写起来你会发现不少细节坑比如正负号只能出现在数字串的开头、如何处理多个相同长度的最长串、空字符串或无边数字的情况怎么处理等。这道题的价值在于它剥离了复杂的业务外壳直指编程核心如何准确、高效地处理输入并设计出鲁棒性强的算法。无论你是用C追求极致性能用Java构建健壮工程还是用Python、JS快速实现原型都能在这道题上找到发挥空间。接下来我就结合自己多次模拟面试和评审代码的经验从问题本质、解题思路、多语言代码实现到避坑指南为你完整拆解这道题并提供可以直接“抄作业”的代码解析。2. 核心需求与问题边界解析在开始编码之前我们必须把题目要求“翻译”成精确的、无歧义的技术规格。这是避免后期反复修改和边界错误的关键一步。2.1 功能需求定义题目描述可以提炼为以下几个核心功能点输入接收一个字符串s长度n未知理论上可达很大需考虑性能。处理从s中找出所有“合法的数字子串”。合法数字子串定义由数字字符‘0’-‘9’组成并且可选地在第一个数字字符前拥有一个正号‘’或负号‘-’。关键约束正负号如果存在必须且只能出现在该数字子串的第一个字符位置。像“123-456”会被拆分成“123”和“456”两个独立的数字串“-123”则不是合法数字串。输出找出所有合法数字子串中长度最长的那个或那些。如果只有一个最长串则输出该子串。如果存在多个长度相同的最长数字串则需将它们全部输出并按它们在原字符串中的出现顺序以逗号拼接。最后需要输出最长数字串的长度。输出格式通常为数字子串1,数字子串2,...逗号分隔加上一个换行再输出长度。例如对于输入“a123bc-123defg12345hif”输出应为12345和5。2.2 边界条件与难点分析这里才是体现编程功力的地方很多同学栽在以下场景空字符串或无边数字输入“abc”或“”。此时没有任何合法数字串输出应该是什么通常约定输出空字符串“”和长度0。必须在代码开始就处理这种情况。正负号在非开头位置“12-34”。这里的‘-’是减号不是数字串的符号。算法必须能正确识别将字符串分割为“12”和“34”。连续的正负号“123”或“--456”。根据规则只有紧邻数字的第一个符号有效所以这些都不是合法数字串的开头。符号后紧跟非数字“abc”或“- ”。单独的符号不是数字串。多个等长最长串“ab123cd4567ef8910”。这里“4567”和“8910”长度都是4需要输出“4567,8910”和4。如何高效地记录和比较这些候选串是设计重点。性能考虑字符串长度可能很大比如上百万字符。我们的算法时间复杂度最好是O(n)即一次遍历完成所有工作避免使用嵌套循环或复杂的字符串截取操作在某些语言中频繁截取子串可能产生大量临时对象影响性能。理清了这些我们就可以开始设计核心的解题算法了。3. 核心算法设计与思路拆解解决这类“在序列中寻找符合某种模式的最长子序列”问题滑动窗口和线性扫描状态记录是两种最直观的思路。对于本题由于模式相对简单数字序列开头可选符号线性扫描是更清晰、更高效的选择。3.1 算法思路一次遍历与状态机我们可以把遍历字符串的过程看作一个简单的状态机在运行。这个状态机有三种状态状态0未在数字串中。这是初始状态表示当前字符不在一个正在构建的数字串里。状态1正在构建数字串且已遇到开头的正负号。这个状态表示我们刚刚读入了一个‘’或‘-’正在期待后面紧跟数字。状态2正在构建数字串且正在读取数字。算法的核心流程如下初始化设置当前找到的max_len 0用一个列表candidates来保存当前找到的所有最长数字串。设置一个start_index记录当前正在考察的数字串的起始位置一个current_len记录当前数字串的长度。状态初始为0。遍历字符串对每个字符ch和其索引i如果ch是数字‘0’-‘9’如果当前状态是0未在数字串中说明这是一个新数字串的开始无符号。将状态置为2start_index icurrent_len 1。如果当前状态是1刚遇到符号说明符号后紧跟了数字是合法的。将状态置为2current_len注意这里长度从符号开始算所以是加1但start_index在状态1时已记录。如果当前状态是2已在数字串中直接current_len。如果ch是 ‘’ 或 ‘-’关键判断只有当当前状态是0并且下一个字符s[i1]存在且是数字时这个符号才可能是一个合法数字串的开头。此时将状态置为1start_index icurrent_len 1。其他情况如状态1或状态2下遇到符号说明当前数字串结束或者这是一个无效的单独符号。需要触发“结束当前数字串”的处理逻辑。如果ch是其他字符字母、空格等无论当前处于什么状态都意味着当前数字串如果存在结束了。需要触发“结束当前数字串”的处理逻辑。“结束当前数字串”的处理逻辑首先只有当前状态是2即正在读取数字时我们才真正捕获到了一个完整的合法数字串。状态1只有符号是无效的直接丢弃。如果current_len max_len说明我们找到了更长的串。清空candidates列表将当前子串s[start_index: start_indexcurrent_len]加入并更新max_len current_len。如果current_len max_len说明找到了一个和当前最长串等长的串将其加入candidates列表。最后重置状态将状态置为0current_len和start_index可以置为任意值因为状态0下会被重新赋值。遍历结束后的处理循环结束后不要忘记再执行一次“结束当前数字串”的逻辑以处理以数字串结尾的字符串例如“abc123”。这个算法的时间复杂度是 O(n)n为字符串长度我们只遍历了一次。空间复杂度也是 O(n)在最坏情况下整个字符串是一个数字串candidates列表可能保存整个字符串但通常情况远小于此。3.2 方案选型为什么不用正则表达式看到字符串匹配很多熟悉Python或JS的同学第一反应可能是用正则表达式。确实用正则r[-]?\d可以非常简洁地找出所有匹配项然后再找出最长的。这在小规模输入和快速原型中是可行的。但是在机试或性能敏感的场景下我不推荐首选正则表达式原因有三可控性差正则表达式是一个“黑盒”其内部实现回溯机制在极端复杂的模式或字符串下可能导致性能急剧下降灾难性回溯。对于确定性的、简单的线性扫描任务手写循环的性能是稳定且可预测的。不利于展示算法思维机试的目的之一是考察你的基础算法能力和编码功底。直接调用re.findall可能让面试官觉得你在取巧错过了展示你状态机设计和边界处理能力的机会。多语言一致性虽然主流语言都有正则库但语法和性能略有差异。手写的线性扫描算法在C、Java、Python、JS中逻辑几乎完全一致便于理解和移植更能体现你的编程素养。当然在时间紧迫或确认输入规模不大的情况下用正则快速实现也是一个备选方案。但在我们深入探讨的这篇解析里我们将聚焦于更本质、更通用的线性扫描算法实现。4. 多语言代码实现与解析下面我将分别用C、Java、Python和JavaScript实现上述算法并附上详细的代码解析和注意事项。你可以清晰地看到核心逻辑是相通的只是语法和标准库的调用方式不同。4.1 C 实现追求效率与控制#include iostream #include string #include vector using namespace std; int main() { string s; getline(cin, s); // 读取一行包含可能有的空格 int n s.length(); int max_len 0; vectorstring candidates; int state 0; // 0: 非数字串, 1: 刚遇到符号, 2: 在数字串中 int start 0; int current_len 0; for (int i 0; i n; i) { // 注意循环到 n为了处理结尾 char ch (i n) ? s[i] : \0; // 末尾添加哨兵字符 if (isdigit(ch)) { if (state 0) { // 状态0遇到数字新数字串开始无符号 state 2; start i; current_len 1; } else if (state 1) { // 状态1遇到数字符号后紧跟数字合法转入状态2 state 2; current_len; } else if (state 2) { // 状态2遇到数字继续延长当前数字串 current_len; } } else if (ch || ch -) { if (state 0 i 1 n isdigit(s[i 1])) { // 关键只有当前不在数字串中且符号后紧跟数字才认为符号是数字串开头 state 1; start i; current_len 1; } else { // 其他情况当前数字串如果存在结束 if (state 2) { if (current_len max_len) { max_len current_len; candidates.clear(); candidates.push_back(s.substr(start, current_len)); } else if (current_len max_len) { candidates.push_back(s.substr(start, current_len)); } } state 0; // 重置状态 current_len 0; } } else { // 遇到其他字符当前数字串如果存在结束 if (state 2) { if (current_len max_len) { max_len current_len; candidates.clear(); candidates.push_back(s.substr(start, current_len)); } else if (current_len max_len) { candidates.push_back(s.substr(start, current_len)); } } state 0; current_len 0; } } // 输出结果 if (candidates.empty()) { cout endl 0 endl; } else { for (size_t i 0; i candidates.size(); i) { if (i 0) cout ,; cout candidates[i]; } cout endl max_len endl; } return 0; }C实现要点解析输入处理使用getline(cin, s)而非cin s因为输入字符串可能包含空格。哨兵技巧循环条件为i n并在循环内通过char ch (i n) ? s[i] : \0模拟一个结尾的空字符。这巧妙地统一了“在循环内遇到终止符”和“遍历结束后处理最后一个数字串”的逻辑避免了在循环外再写一遍重复的结束处理代码。这是C/C中处理这类问题的常用技巧。状态判断严格遵循状态机。对符号‘’、‘-’的判断是核心必须检查i1是否越界以及是否为数字。子串提取使用s.substr(start, current_len)注意参数是起始位置和长度。性能考虑使用vectorstring存储候选串clear()和push_back操作都是高效的。整个算法没有冗余的字符串拷贝。4.2 Java 实现严谨与健壮import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); String s scanner.nextLine(); int n s.length(); int maxLen 0; ListString candidates new ArrayList(); int state 0; // 0: 非数字串, 1: 刚遇到符号, 2: 在数字串中 int start 0; int currentLen 0; for (int i 0; i n; i) { char ch (i n) ? s.charAt(i) : \0; if (Character.isDigit(ch)) { if (state 0) { state 2; start i; currentLen 1; } else if (state 1) { state 2; currentLen; } else if (state 2) { currentLen; } } else if (ch || ch -) { if (state 0 i 1 n Character.isDigit(s.charAt(i 1))) { state 1; start i; currentLen 1; } else { // 结束当前可能存在的数字串 if (state 2) { if (currentLen maxLen) { maxLen currentLen; candidates.clear(); candidates.add(s.substring(start, start currentLen)); } else if (currentLen maxLen) { candidates.add(s.substring(start, start currentLen)); } } state 0; currentLen 0; } } else { // 遇到其他字符 if (state 2) { if (currentLen maxLen) { maxLen currentLen; candidates.clear(); candidates.add(s.substring(start, start currentLen)); } else if (currentLen maxLen) { candidates.add(s.substring(start, start currentLen)); } } state 0; currentLen 0; } } // 输出结果 if (candidates.isEmpty()) { System.out.println(); System.out.println(0); } else { System.out.println(String.join(,, candidates)); System.out.println(maxLen); } scanner.close(); } }Java实现要点解析字符判断使用Character.isDigit(ch)判断数字比ch 0 ch 9更清晰且国际化友好。子串提取使用s.substring(start, start currentLen)注意Java的substring(beginIndex, endIndex)是前闭后开区间。优雅输出使用String.join(,, candidates)来拼接结果列表这是Java 8之后非常方便的API。资源管理记得在最后scanner.close()虽然对于标准输入不是必须但养成好习惯。健壮性Java的字符串索引访问会进行边界检查如果手误写错索引会抛出StringIndexOutOfBoundsException这有助于调试。4.3 Python 实现简洁与高效def find_longest_digit_str(s: str) - tuple: 找出字符串中最长的数字串可含开头正负号 返回: (拼接后的最长数字串, 最大长度) n len(s) max_len 0 candidates [] state 0 # 0: 非数字串, 1: 刚遇到符号, 2: 在数字串中 start 0 current_len 0 # 添加哨兵简化边界处理 s s \0 for i, ch in enumerate(s): if ch.isdigit(): if state 0: state 2 start i current_len 1 elif state 1: state 2 current_len 1 elif state 2: current_len 1 elif ch or ch -: if state 0 and i 1 len(s) and s[i 1].isdigit(): state 1 start i current_len 1 else: if state 2: if current_len max_len: max_len current_len candidates [s[start:start current_len]] elif current_len max_len: candidates.append(s[start:start current_len]) state 0 current_len 0 else: if state 2: if current_len max_len: max_len current_len candidates [s[start:start current_len]] elif current_len max_len: candidates.append(s[start:start current_len]) state 0 current_len 0 # 移除哨兵字符对结果的影响哨兵是\0不会出现在原串中切片不受影响 result_str ,.join(candidates) # 注意由于加了哨兵candidates里的字符串末尾可能包含\0不会因为遇到\0会触发else分支在加入candidates之前就结束了。 # 更稳妥的做法是遍历原字符串s[:-1]这里为了逻辑清晰采用加哨兵方式。 # 实际处理时应使用原字符串长度n进行切片。以下是修正版核心循环 def find_longest_digit_str_correct(s: str) - tuple: n len(s) max_len 0 candidates [] state 0 start 0 current_len 0 for i in range(n 1): # 多遍历一位处理以数字结尾的情况 ch s[i] if i n else # 使用空字符串作为哨兵 if ch and ch.isdigit(): if state 0: state 2 start i current_len 1 elif state 1: state 2 current_len 1 elif state 2: current_len 1 elif ch in -: if state 0 and i 1 n and s[i 1].isdigit(): state 1 start i current_len 1 else: if state 2: if current_len max_len: max_len current_len candidates [s[start:start current_len]] elif current_len max_len: candidates.append(s[start:start current_len]) state 0 current_len 0 else: if state 2: if current_len max_len: max_len current_len candidates [s[start:start current_len]] elif current_len max_len: candidates.append(s[start:start current_len]) state 0 current_len 0 result_str ,.join(candidates) if candidates else return result_str, max_len if __name__ __main__: import sys for line in sys.stdin: line line.rstrip(\n) result_str, max_len find_longest_digit_str_correct(line) print(result_str) print(max_len)Python实现要点与避坑指南哨兵处理Python中字符串不可变直接s s \0会创建新字符串。上面的第一种写法在逻辑演示上清晰但第二种find_longest_digit_str_correct使用循环索引和空字符串哨兵更为通用和准确避免了修改原输入字符串。字符串切片s[start:start current_len]非常高效它返回一个新的子串视图在CPython中短字符串会拷贝长字符串可能优化。对于本题规模完全足够。str.isdigit()方法这是判断数字字符最Pythonic的方式。列表的清空与重建当找到更长的串时代码使用candidates [s[start:...]]直接重建列表这比candidates.clear()后append在Python中通常更简洁。candidates.append(...)用于添加等长串。输入循环使用for line in sys.stdin:可以处理多行输入如果题目需要line.rstrip(\n)去掉换行符。一个易错点在判断符号后的字符是否为数字时一定要先检查i1是否越界 (i 1 n)否则s[i1]会引发IndexError。4.4 JavaScript (Node.js) 实现灵活与动态function findLongestDigitStr(s) { const n s.length; let maxLen 0; let candidates []; let state 0; // 0: 非数字串, 1: 刚遇到符号, 2: 在数字串中 let start 0; let currentLen 0; for (let i 0; i n; i) { const ch i n ? s[i] : ; // 使用空字符串作为哨兵 if (ch 0 ch 9) { if (state 0) { state 2; start i; currentLen 1; } else if (state 1) { state 2; currentLen; } else if (state 2) { currentLen; } } else if (ch || ch -) { if (state 0 i 1 n s[i 1] 0 s[i 1] 9) { state 1; start i; currentLen 1; } else { if (state 2) { if (currentLen maxLen) { maxLen currentLen; candidates [s.substring(start, start currentLen)]; } else if (currentLen maxLen) { candidates.push(s.substring(start, start currentLen)); } } state 0; currentLen 0; } } else { if (state 2) { if (currentLen maxLen) { maxLen currentLen; candidates [s.substring(start, start currentLen)]; } else if (currentLen maxLen) { candidates.push(s.substring(start, start currentLen)); } } state 0; currentLen 0; } } const resultStr candidates.length 0 ? candidates.join(,) : ; return { resultStr, maxLen }; } // 处理输入输出 (Node.js环境) const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout }); rl.on(line, (input) { const { resultStr, maxLen } findLongestDigitStr(input); console.log(resultStr); console.log(maxLen); });JavaScript实现要点解析字符判断JS中判断数字字符最直接可靠的方式还是ch 0 ch 9。虽然可以用/\d/.test(ch)但在循环中频繁调用正则测试性能稍差且意图不如直接比较清晰。子串提取使用s.substring(start, start currentLen)。注意substring的参数是起始和结束索引结束索引不包含和Java类似。不要与substr起始索引和长度混淆后者已废弃。数组操作当找到更长串时直接赋值candidates [newStr]来重置数组。使用push添加等长串。输入输出在Node.js环境中使用readline模块逐行读取标准输入。这是处理ACM模式机试的常见方式。返回结果函数返回一个对象{ resultStr, maxLen }结构清晰。在需要时也可以直接返回数组[resultStr, maxLen]。性能注意在V8引擎中字符串的substring方法通常不会创建新的字符串存储而是返回一个指向原字符串的视图直到被修改为止因此效率很高。5. 常见问题与调试技巧实录即使理解了算法实际编写和调试时还是会遇到各种问题。下面是我在练习和教学中总结的几个高频问题和解决技巧。5.1 问题1输出结果莫名包含非数字字符或符号症状对于输入“a-123b”期望输出“-123”但实际输出可能变成了“-123b”或“a-123”。根因状态机重置逻辑有误。当遇到非数字字符如‘b’时代码正确结束了数字串“-123”并将其加入候选列表。但是如果没有正确重置state和current_len下一个字符的判断可能会基于错误的上文状态。更隐蔽的 bug 是子串切片索引计算错误。start索引记录的是数字串的开始对于“-123”就是‘-’的位置current_len是包含符号的长度。必须确保s.substring(start, startcurrent_len)精确地截取到这个范围。排查技巧打印日志在状态变化、开始记录子串、结束子串时打印出i,ch,state,start,current_len等关键变量。这是最直接的调试方法。单步调试在IDE中针对简单用例如“a-123b”进行单步调试观察每个循环步骤变量的变化是否符合预期。边界测试专门测试以数字开头、以数字结尾、符号后无数字、连续符号等边界情况。5.2 问题2对于多个等长串输出顺序错误或漏掉症状输入“ab123cd456ef789”三个数字串长度都是3但输出可能不是“123,456,789”或者漏掉了某个。根因候选列表更新逻辑不完整。在current_len max_len时清空列表并加入新串是正确的。但在current_len max_len时必须将当前串加入列表。这里容易犯的错误是在current_len max_len的判断分支里没有执行candidates.append(...)或candidates.push(...)。另一种可能是在遍历结束后忘记处理最后一个字符正好是数字结尾的情况导致最后一个串没有被评估是否应该加入候选列表。排查技巧构造等长测试用例这是必须的测试步骤。检查循环结束后逻辑确认在循环外或通过哨兵在循环内是否对最后一个数字串进行了处理。审查比较逻辑仔细检查if (current_len max_len)和else if (current_len max_len)这两个分支的代码块确保动作完整。5.3 问题3性能不达标处理超长字符串超时症状当输入字符串长度达到10^5或更高时程序运行时间过长。根因算法复杂度不是O(n)或存在低效操作。嵌套循环如果在每个位置都尝试向后扩展寻找数字串会是O(n^2)。频繁的字符串拼接在循环内使用result substr这种方式拼接最终结果在Java/Python中会创建大量中间字符串对象性能极差。应使用列表List/ArrayList/Array收集最后一次性拼接。不必要的函数调用例如在Python的循环中频繁调用len(s)应提前存到变量n中。优化技巧确保单次遍历我们的状态机算法本身就是O(n)的这是最优解。使用列表/容器收集结果正如所有示例代码所示这是标准做法。避免在循环内进行昂贵的操作如正则匹配、复杂的字符串查找等。对于C注意std::string::substr会生成拷贝但在本题数据量下可以接受。如果追求极致可以只记录start和length最后输出时再一次性拷贝。5.4 一份快速自查清单在写完代码后对照这个清单检查可以避免80%的常见错误[ ]输入读取是否能正确处理带空格的字符串用getline/nextLine/readline[ ]空输入输入空字符串“”或纯字母串时是否输出空结果和0[ ]符号处理“123”输出“123”“-456”输出“-456”“123”不输出“123”。[ ]符号位置“123-456”输出“123,456”两个串而不是“123-456”。[ ]结尾数字“abc123”能正确输出“123”吗[ ]等长串“a12b34c56”输出“12,34,56”和2吗[ ]最大长度更新当找到更长的串时max_len和候选列表是否被正确更新和清空[ ]索引越界在判断s[i1]是否为数字前是否检查了i1 n[ ]遍历完整性循环是否处理了以数字结尾的情况通过循环到n或循环后额外判断6. 举一反三题型变种与扩展思考掌握了这道基础题我们可以看看它的一些常见变种这能帮助你真正吃透这类问题的核心。6.1 变种一找出所有数字串并转换为数值求和这是很自然的扩展。在遍历过程中不仅记录子串还可以在确定一个数字串结束时状态2转为其他状态时将其截取出来用stoi(C)、Integer.parseInt(Java)、int()(Python)、parseInt(JS) 转换为整数累加到一个总和变量中。特别注意转换时要考虑字符串可能以‘’或‘-’开头这些函数通常能直接处理。6.2 变种二找出最长的“合法数字串”包含小数点和科学计数法难度升级。此时“合法数字串”的定义变得更复杂例如允许小数点.但只能出现一次且前后至少有一个数字。允许科学计数法e或E后面可以跟一个可选的正负号和整数。 这需要设计一个更复杂的状态机DFA。状态可能包括开始、符号后、整数部分、小数点后、小数部分、指数符号E、指数符号后、指数部分等。面试中有时会要求实现一个简化的字符串转浮点数 (atof)其核心就是这样的状态机解析。6.3 变种三在流数据中实时查找如果数据不是一次性给出的字符串而是一个字符流例如从网络或文件逐字符读取你无法预知长度也不能随机访问之前的字符。如何实时找出当前已接收数据中最长的数字串 这时状态机算法依然有效你只需要维护state、current_start在流中的相对位置或时间戳、current_len、max_len以及当前最长串的start和len或缓存该子串。每读入一个新字符就根据状态机更新这些变量。当流结束时就能得到结果。这体现了状态机算法在流式处理中的优势。6.4 从解题到工程代码的模块化虽然机试题常写在一个main函数里但在实际工程中我们应该将核心逻辑封装成函数如findLongestDigitStr(s)使其职责单一易于测试和复用。函数应该有清晰的输入输出定义并进行必要的参数校验例如输入是否为字符串。上面的示例代码已经做了这样的示范。这道“最长数字串”题目就像一把尺子能量出你对字符串处理、状态机、边界条件和代码严谨性的掌握程度。它不涉及高深的数据结构但正是这些基本功决定了代码在真实场景下的稳定性和可靠性。多花时间理解状态转移的每一个细节亲手用不同语言实现几遍比你刷十道囫囵吞枣的难题更有价值。下次遇到类似的字符串解析问题你就能下意识地想到“哦这可以用一个状态机来优雅地解决。”
)
