题目重点:按ASCII十进制语法解析有效数字,分别验证尾数、符号、小数点和整数指数。
题意与假设
这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。
- 训练无前后空白,ASCII digits,允许±、小数点、e/E和带符号整数指数;不接受NaN/Infinity/hex/下划线。题面若允许trim需外层显式处理。
- 尾数至少一位digit,允许1.和.1;指数存在时至少一位digit,不允许小数指数。返回bool,不实际转float,因此不会受溢出决定合法性。
解题路线
- 先消耗可选符号,再消耗整数digits;可选点后消耗小数digits,两部分总数至少1。只有点/只有符号不能通过。
- 如果遇e/E,再消耗可选指数符号和连续ASCII digits,要求至少1。最后必须正好到字符串末尾,不能忽略尾部垃圾。
- 各阶段最多前进不回退,状态等价于有限状态机。明确grammar比调用float更符合题面:float可能接受空白/特殊值、丢失精度或溢出,却不代表训练语法有效。
- ASCII判断使用0≤char≤9,Python isdigit会接受一些Unicode数字,不符合本合同。大写E与小写e都合法,但指数只能出现一次。
- 测试oracle用独立正则grammar fullmatch,不把另一个同样逐字符parser当对照;加入全角数字、末尾换行和长指数确保不是数值转换。
手动走一遍
+.8、46.e3、-90E-2合法;.、e3、1e、1e2.3、--1、1x非法。1e999999在语法上合法,即使机器float无法保持有限值;“3 ”本合同拒绝,若允许trim需先strip再调用。
Python 参考实现
下面的代码按上文假设实现,适合本地运行并追加自己的测试用例。
代码区可横向滚动;使用键盘时,先聚焦代码区再按方向键查看。
def is_number(text):
"""ASCII decimal grammar, no whitespace/NaN/hex; e/E with integer exponent.
mantissa: [+-]?(digits(.digits*)?|.digits+); exponent: [eE][+-]?digits+
"""
n=len(text);i=0
if i<n and text[i] in '+-':i+=1
digits=0
while i<n and '0'<=text[i]<='9':digits+=1;i+=1
if i<n and text[i]=='.':
i+=1
while i<n and '0'<=text[i]<='9':digits+=1;i+=1
if digits==0:return False
if i<n and text[i] in 'eE':
i+=1
if i<n and text[i] in '+-':i+=1
start=i
while i<n and '0'<=text[i]<='9':i+=1
if i==start:return False
return i==n
复杂度
O(n)时间、O(1)辅助空间,不进行任意精度数值求值。字符串长度是主要规模,正则oracle仅供测试,不是用数值转换偷换语法验证。
易错点与追问
容易失分的边界
- 指数复用小数尾数parser,会错误接受1e2.3。
- 使用isdigit但合同只接受ASCII,会接受不应出现的字符。
继续深挖
- 如果允许分隔符_,它只能出现在数字之间还是任意位置?先扩grammar再改状态。
- 验证成功后还要转数值,溢出/精度应如何返回?这是另一个接口结果。
