先说明一下这道题我在几年前整理面试题库时仔细推演过也拿它当过模拟题去练手。它表面上是“找出字符串里的最长数字串”但背后真正考查的是一个研发工程师对字符串处理、边界条件和状态机思想的掌握程度。今天把完整的解题思路、代码实现、边界坑点和面试官的考察逻辑一次讲透希望能帮到正在准备笔试或日常写代码需要处理字符串的同学。1. 这道题考的是什么从题目看研发岗位的基本功1.1 题目背景与来龙去脉爱奇艺2016年研发工程师笔试题里有一道出现频率很高的字符串算法题题干通常描述为输入一个字符串输出该字符串中最长的数字子串。如果存在多个长度相同的最长数字子串则输出最后一个也有版本要求输出第一个不同题目描述略有差异。这个题目在当年属于典型的“看似简单、实则埋坑”的题目。2016年移动视频行业正处于高速扩张期爱奇艺作为头部视频平台研发岗位每天的日常业务里充斥着大量与字符串处理相关的逻辑比如用户搜索词的解析、视频标签的提取、URL参数的切割、日志中数字字段的过滤等。笔试出这道题本质上不是要难倒候选人而是想看候选人能不能用最简洁、最健壮的代码完成一件“生产环境里随时要用到”的小事。题目本身的难度不大但区分度很高。我的直观感受是这道题的通过率并不低但能一次写对、把所有边界情况都考虑全的人比例并不高。很多人能写出核心逻辑但往往在处理“数字串在字符串最末尾”“全字符串都是数字”“没有数字”这些特殊情况时翻车。1.2 考点拆解字符串处理背后的三道坎拆开看这道题主要考察三个层面的能力第一层是基础语法能力。候选人对字符串的遍历、字符判断、数组或指针操作是否熟练这决定了他能不能写出能跑起来的代码。这一层大约刷过一些题的人都能过关。第二层是逻辑设计能力。如何用一个高效的方案完成最长子串的查找这里涉及状态记录、临时变量与结果变量之间的协作。很多人会本能地想到“遍历所有子串逐个判断”这种解法在数据量小的时候没有问题但时间复杂度和空间复杂度都不理想暴露出对算法效率缺乏意识。第三层是工程思维和边界处理能力。这是最拉分的一层。字符串为空怎么处理没有数字怎么处理多个最长子串长度相同取哪个数字子串紧贴着字符串开头和结尾怎么处理这些细节在校招笔试里直接决定一个候选人是否具备“生产级代码”的意识。实际业务里的输入数据永远比你预想的更脏能够把边界想全的程序员线上出bug的概率会小很多。2. 完整题面与题意拆解动手之前先把规则定清楚2.1 原题表述与输入输出约定结合网络上流传的2016年爱奇艺研发工程师笔试题版本这道题比较完整的描述如下题目描述 在给定的字符串中找出最长的数字子串。数字子串指连续的数字字符组成的子串。 若存在多个长度相同的最长数字子串输出最后一个。 字符串长度不超过1000。 输入 一个字符串可以包含数字、字母、空格、标点符号等任意可见字符。 输出 最长的数字子串。若不存在数字子串输出空字符串。这里有一个细节需要特别留意题目说的是“数字子串”在C/C语境里通常指0到9这10个字符的连续序列不包括正负号、小数点。也就是说-123应该被拆成“空串 123”来看待3.14应该被拆成“3”和“14”两个数字子串。这个细节在笔试现场很容易被忽略因为人眼看到“-123”会本能地觉得它是一个整体但在程序里负号和小数点都不是数字字符所以不能算入数字子串。另外“输出最后一个”还是“输出第一个”这个细节特别重要。我见过有人在这里吃亏题目明明要求输出最后一个结果写了个遇到更长才更新的逻辑遇到等长直接跳过输出的是第一个。也有版本要求输出第一个又有人写了的更新条件导致输出最后一个。这个细节没有难度纯粹是审题问题但面试官就是故意放在那里看你会不会认真读题。2.2 边界条件先想清楚再动手写代码之前建议先花两分钟把边界条件列出来这比直接写代码效率更高。就这道题而言边界条件至少包括以下几类输入字符串为空字符串长度是0此时没有数字子串应该输出空串。输入字符串里一个数字都没有比如”abcdef”输出空串。输入字符串全部是数字比如”12345678”此时整个字符串就是最长数字子串需要能被正确识别并输出。数字串位于字符串最开头比如”123abc”扫描时需要把从索引0开始的数字串纳入统计。数字串位于字符串最末尾比如”abc123”这是最容易出错的地方。很多解法是在字符从数字变成非数字的“下降沿”做结算但数字串一直持续到字符串结束的话就没有“下降沿”了。这个边界如果没有额外处理最后一个数字串永远统计不到。连续多个长度相同的数字子串比如”abc12def34gh”题目要求输出最后一个也就是”34”不能输出”12”。数字串之间只隔一个非数字字符比如”a1b22c333d”要保证分隔逻辑正确不会把两段数字串错误地拼在一起。把以上条件列出来之后你会发现这个题目的核心逻辑并不复杂难点全在“结算时机”上。所谓的结算时机就是什么时候把当前正在统计的数字串判定为“结束”并和当前已知的最长数字串做比较。把这个想清楚了代码怎么写都是对的只是风格不同。3. 核心解题思路从直觉到状态机3.1 最直白的双层循环为什么能跑但不好先聊聊大家最容易想到的暴力解法枚举所有起点i然后从i开始往后找只要字符是数字就继续扩展直到遇到非数字字符为止记录这一段长度不断更新最大值。这种解法的代码如下C语言风格伪代码char* longestDigits(char* s) { int len strlen(s); int maxLen 0; int maxStart -1; for (int i 0; i len; i) { if (s[i] 0 s[i] 9) { int j i; while (j len s[j] 0 s[j] 9) { j; } int curLen j - i; if (curLen maxLen) { maxLen curLen; maxStart i; } i j - 1; // 跳过已经统计过的数字串避免重复扫描 } } // 根据maxStart和maxLen提取子串并返回 }这里用是因为题目要求多个等长时取最后一个。注意我写了i j - 1来跳过已经扫过的数字区域这样整体复杂度在最坏情况下依然是O(n)因为每个字符最多被访问两次。如果没有这一行外层循环每遇到一个数字开头的字符就在内层重复扫描最坏情况下是O(n^2)比如字符串是”1111111111”这种全数字串第一轮从i0扫到末尾第二轮从i1又扫到末尾白白浪费了很多时间。但这种方法有一个问题代码逻辑里有跳出循环、回拨索引这些操作一旦字符串变长、条件变多很容易在指针操作上犯错。同时它依赖“内层扫描到非数字字符后外层把i拨回j-1”这个技巧这个技巧能用但不够优雅面试官看了会觉得你是在“绕过问题”而不是“正面解决问题”。从算法设计的角度我更推荐用状态机思想来一次遍历解决问题。这个思路可以迁移到很多字符串处理场景中比如解析HTTP请求头、拆分日志字段、识别词法单元等比暴力解法有更广的适用性。3.2 状态机思想一次扫描解决战斗状态机思想的核心是在遍历字符串的过程中我们只维护一个“当前状态”这个状态表示“我正在一个数字串内部”还是“我在非数字区域”。每次读入一个字符时根据当前状态和字符类型决定下一步如何更新。具体到这道题需要维护的变量有以下几个curStart当前正在统计的数字串的起始索引只有处于数字串状态时才有意义。curLen当前正在统计的数字串的长度。maxStart已知最长数字串的起始索引。maxLen已知最长数字串的长度。遍历规则如果当前状态是“不在数字串中”且读到的是数字字符说明一个新的数字串开始了此时设置curStart为当前索引curLen为1状态切换为“在数字串中”。如果当前状态是“在数字串中”且读到的还是数字字符curLen加1说明当前数字串还在持续增长。如果当前状态是“在数字串中”且读到的是非数字字符说明当前的数字串结束了此时拿curLen和maxLen做一次比较决定是否更新maxStart和maxLen然后把状态切回“不在数字串中”。如果当前状态是“不在数字串中”且读到的不是数字字符直接忽略继续往后走。这套逻辑有一个关键的额外处理当遍历完整个字符串时如果最后的状态仍然处于“在数字串中”说明字符串是以数字结尾的此时必须再做一次结算。这个操作就是前面提到的“数字串在末尾”边界条件的解决方案。这种状态机写法的好处是逻辑清晰、不会遗漏结算时机、每个字符只被访问一次时间复杂度严格O(n)空间复杂度O(1)。而且它很容易扩展到其他模式匹配场景比如找最长的连续字母串、找符合特定规则的子串只需要修改“状态切换条件”和“结算条件”即可。3.3 复杂度与正确性分析复杂度方面遍历整个字符串一次每个字符进行常数次比较和赋值因此时间复杂度为O(n)n为字符串长度。只使用了固定数量的整型变量没有额外分配与输入规模相关的存储空间因此空间复杂度为O(1)。正确性方面关键在于两点第一是数字串的“开始”“延续”“结束”三个事件都被正确处理第二是末尾结算没有遗漏。只要这两点做到就不存在漏掉某个数字串的问题。每个数字串从第一个数字字符开始被识别在遇到非数字字符时完成结算或在字符串结束时完成结算二者必居其一。因此所有数字串都会被统计最长子串一定能被找到。如果题目要求输出第一个而不是最后一个只需把更新逻辑中的改成因为只有在“严格更长”时才更新等长时不更新自然就保留了第一个最长子串。4. 多语言实现与代码精讲4.1 C/C版本贴近2016年的笔试战场2016年前后校招笔试的主流语言是C/C很多在线评测系统对C的支持也最成熟。下面给出一个C实现逻辑完全按照上面的状态机思路#include iostream #include string using namespace std; string longestDigits(const string s) { int maxStart -1, maxLen 0; int curStart -1, curLen 0; bool inDigits false; for (int i 0; i s.length(); i) { bool isDigit (s[i] 0 s[i] 9); if (!inDigits isDigit) { inDigits true; curStart i; curLen 1; } else if (inDigits isDigit) { curLen; } else if (inDigits !isDigit) { if (curLen maxLen) { maxStart curStart; maxLen curLen; } inDigits false; curStart -1; curLen 0; } } // 末尾结算 if (inDigits) { if (curLen maxLen) { maxStart curStart; maxLen curLen; } } if (maxLen 0) { return ; } return s.substr(maxStart, maxLen); } int main() { string s ab12cd345ef6; cout longestDigits(s) endl; // 输出 345 return 0; }注意main函数里的测试用例输入ab12cd345ef6预计输出345。这个用例覆盖了数字串在中间、前后都有非数字字符的常规情况。如果想测试数字串在末尾的情况可以改成ab12cd345此时最后一个数字串345在遍历结束时才结算正好验证末尾结算逻辑。这段代码里的inDigits变量就是状态标志位。如果你愿意也可以用curStart 0来充当状态标志不过显式声明一个布尔变量会让逻辑更直观。写笔试代码时清晰比炫技重要阅卷人看你的代码不是为了欣赏而是为了快速判断你的思路是否正确。4.2 Python版本三行核心逻辑如果是Python环境代码可以写得更紧凑。Python的字符串切片特性让“提取子串”这件事变得极其方便但我们还是要维护状态因为循环内部的逻辑是跟语言无关的def longest_digits(s: str) - str: max_start, max_len -1, 0 cur_start, cur_len -1, 0 in_digits False for i, ch in enumerate(s): if ch.isdigit(): if not in_digits: in_digits True cur_start i cur_len 1 else: cur_len 1 else: if in_digits: if cur_len max_len: max_start, max_len cur_start, cur_len in_digits False cur_start, cur_len -1, 0 if in_digits: if cur_len max_len: max_start, max_len cur_start, cur_len return if max_len 0 else s[max_start:max_start max_len]关于str.isdigit()有一个小坑要提醒Python的isdigit()对Unicode数字字符会返回True比如阿拉伯语数字、上标数字等。这道题的输入一般是ASCII字符用isdigit()问题不大但在处理真实业务数据时要小心最好用0 ch 9来严格限定ASCII数字避免非预期字符混入。在C/C里isdigit也有类似的locale问题用c 0 c 9最稳妥。4.3 Java版本与工程化细节Java版本的思路完全一样只是字符串和循环的语法不同。可以直接用String的charAt方法和substring方法public class LongestDigits { public static String longestDigits(String s) { int maxStart -1, maxLen 0; int curStart -1, curLen 0; boolean inDigits false; for (int i 0; i s.length(); i) { char c s.charAt(i); boolean isDigit (c 0 c 9); if (!inDigits isDigit) { inDigits true; curStart i; curLen 1; } else if (inDigits isDigit) { curLen; } else if (inDigits !isDigit) { if (curLen maxLen) { maxStart curStart; maxLen curLen; } inDigits false; curStart -1; curLen 0; } } if (inDigits curLen maxLen) { maxStart curStart; maxLen curLen; } return maxLen 0 ? : s.substring(maxStart, maxStart maxLen); } public static void main(String[] args) { System.out.println(longestDigits(ab12cd345ef6)); } }Java版本的工程化细节主要体现在字符串提取上substring(beginIndex, endIndex)的第二个参数是结束索引不包含在内所以要用maxStart maxLen而不是maxStart maxLen - 1。这个细节特别容易在写的时候疏忽导致输出的字符串少一个字符或多一个字符。除了以上三种语言用Go、JavaScript、Rust等语言实现这道题也都很合适。核心逻辑就那几行状态判断换语言只是换语法外壳。我建议准备笔试的同学至少用两种语言各写一遍一种用于在线笔试C或Java一种用于日常练习Python这样既能快速验证思路又能训练代码手感。5. 容易踩的坑边界条件和面试追问5.1 五个典型陷阱逐个拆解陷阱一数字串在字符串末尾没结算。这是最经典的坑。很多人的代码在“遇到非数字字符”时才做长度比较如果数字串一直延伸到字符串结束循环结束了还没比较过于是最后一段数字串就被漏掉了。解决办法就是在循环结束后增加一次状态检查如果仍然处于“在数字串中”的状态就补一次结算。陷阱二多个等长数字串的输出选择。题目要求输出最后一个时更新条件用要求输出第一个时更新条件用。我见过有人在同一个代码里两个地方一个用一个用导致逻辑不一致。用状态机写法的好处是结算逻辑集中在一处不容易出现这种不一致但还是要在提交前确认一遍。陷阱三从数字串中间开始扫描导致起始索引错误。这个坑主要出现在暴力解法中如果你在外层循环里没有跳过已经处理过的数字区域就可能从某个数字串的中间位置重新开始统计导致输出的子串只是原数字串的一部分。比如输入”123abc456”如果外层循环从i1开始又统计出了一个”23”或”234”结果就错了。状态机写法天然规避这个问题因为curStart只会在进入数字状态时设置一次。陷阱四没有考虑空输出。当字符串不包含任何数字时正确输出应该是空串。有些候选人在没有找到任何数字时返回了NULL或抛异常这在笔试环境里可能直接导致运行时错误。统一约定返回空字符串最稳妥。陷阱五字符判断条件写反。0 c c 9和c 0 c 9在逻辑上是等价的但有些同学把条件写成c 0 || c 9这个在逻辑上永远为真程序就会把所有字符都当成数字处理。这种错误在笔试现场很容易发生因为大脑里想的是“与”键盘上敲出来却是“或”。写完之后用一组混合字符的测试用例跑一遍就能发现。我建议把下面这些测试用例在本地一次性跑通再提交代码输入期望输出考察点空字符串abc无数字1234512345全数字123abc123数字在开头abc123abc123中的123数字在末尾验证末尾结算a12b345c67345多个数字串取最长a12b34c5656等长取最后一个a1b22c333d333递增长度abc123 456456带空格分隔a-12b3434负号/加号不是数字需要拆分个人经验是笔试时时间再紧张也要把“空输入”“全数字”“无数字”“数字在末尾”“等长取末”这五类用例手动跑一遍。这几个用例一旦通过这道题的正确率就有九成以上。5.2 面试官在这里等你升级问题这道题放在笔试环节是编程题但如果进入面试环节面试官很可能基于这道题做二次追问考察候选人对问题理解的深度。最常见的追问是“如果我想提取字符串中最长的连续字母子串怎么改”答案很简单把字符判断条件从”是数字”改成”是字母”即可。如果面试官让你提取最长连续递增数字串比如123是递增的132不是那难度就上来了需要额外维护一个“前一个数字”的状态在结算时判断整段数字串是否满足递增关系。这个变体能很好地考察候选人对状态机模型的迁移能力。还有一种追问是“如果有多个最长数字串不输出最后一个而是输出长度和数量怎么改”这就涉及到在结算时同时维护“到目前为止看到的最长长度”和“达到这个长度的子串个数”。核心逻辑不复杂但需要额外一个计数器在更新maxLen时重置在等长时累加。这类变形题的训练价值很大因为它强迫你理解“状态更新”和“结果维护”之间的关系而不是死记某一道题的答案。另外面试官还可能让你用正则表达式实现一遍。在Python里一行代码就能搞定import re def longest_digits_regex(s: str) - str: matches re.findall(r\d, s) if not matches: return return max(matches, keylen)用正则实现代码很短但在笔试环境下不一定被允许因为有些在线评测系统不允许引入正则库而且正则表达式的行为比如是否包含Unicode数字在不同语言里也有差异。不过这个解法用来和手写的状态机版本做对照测试非常方便我经常用正则版来验证自己手写代码结果的正确性。6. 从一道题到一类题扩展与对比6.1 同类题型的横向对比这道”最长数字子串“问题本质上属于“最长连续满足某条件子串”这类问题的简化版。类似的题目还有最长连续递增子序列要求子序列中元素严格递增数字串场景下就是判断相邻字符的数值大小。最长无重复字符子串经典滑动窗口题目需要维护一个窗口和一个字符出现位置的映射。最长回文子串中心扩展法或动态规划比赛很多。最长有效括号子串需要栈或计数器平衡判断。这些题目和“最长数字子串”有一个共同点都是在线性遍历中维护一组状态在合适时机结算并更新全局最优解。掌握了这个通用的方法论刷这些题时就会有一种“套路感”——不是死记硬背而是知道每种题对应什么状态、什么结算时机。“最长数字子串”和其他题目相比最大特点是状态只有两个数字/非数字这是一个非常简单的两状态自动机。正因为它简单特别适合用来向面试官展示你对“状态机思想”的理解。你可以在讲解时先画出状态转移的思维过程然后指出代码中每一个if分支对应哪一条状态转移边这样即使代码很短你也能展示出高于“会写这道题”的水平。从另一个角度看2016年前后的视频平台研发岗日常处理的数据大都是日志、搜索词、弹幕文本、用户反馈等字符串密集型数据”找出最长的数字串“这类需求看着像算法题实际上在日志分析、A/B测试数据提取、用户ID解析等场景中都会遇到类似的“从污浊文本里提取结构化信息”的需求。6.2 刷题之外这道题暴露的工程习惯我见过很多人把这道题写完后觉得”这么简单的题有什么好讲的“然后草率提交。但恰恰是这道题最能看出一个候选人平时写代码的习惯。比如字符串为空时该怎么处理有人直接返回空串有人返回NULL有人抛异常。在笔试里可能都能过但在工程里这个选择决定了调用方要不要判空。再比如函数命名是longestDigits还是fun还是f虽然不影响正确性但一个清晰的名字能让面试官在潜意识里给你加分。还有你写的循环里有没有多余的变量有没有在循环内部做不必要的字符串拼接这些细节在线上代码里都直接影响性能和可维护性。我个人在实际项目里遇到过类似的场景解析一批用户导入的Excel数据时有一列是“手机号/微信号/QQ号混填”需要提取其中最长的一段连续数字作为可能的手机号。当时我第一反应就是拿这道题的状态机逻辑来改很快就写出了一个健壮的提取函数后面又根据手机号必须11位这个业务约束加了过滤条件。这就是笔试题目和真实工程之间最有价值的连接——你不可能在笔试时背下所有业务需求但你可以通过做这些基础题建立一套“如何分析字符串、如何管理状态、如何考虑边界”的思维框架框架一旦建立遇到具体业务就能快速套用。最后再分享一个我在实际写代码时才意识到的小技巧这类“边遍历边维护最优解”的题目在循环内部尽量少做字符串切片或拷贝只记录索引和长度。等循环结束、确定边界之后再执行一次切片操作提取结果。这样做有两个好处一是循环内部性能更好不会因为反复创建子串导致不必要的内存和CPU开销二是逻辑更清晰切片操作集中在最后不容易因为切片边界算错导致bug。这个习惯在处理超长字符串时尤其有价值比如日志文件里一行就有几十KB如果每个数字串都截取一遍内存瞬间就会被大量临时对象占满。如果你正准备研发岗的笔试建议把这道题熟练到闭着眼都能写出来的程度再花点时间试着给它做变形强迫自己在不同约束下重新思考。当你能把一个题目从多个角度讲清楚时这道题才真正成为你的东西。