LeetCode No.65 | StriveZs的博客

LeetCode No.65

LeetCode第六十五题

自己代码的开源仓库:click here 欢迎Star和Fork :)

题目描述

有效数字(按顺序)可以分成以下几个部分:

一个 小数 或者 整数
(可选)一个 ‘e’ 或 ‘E’ ,后面跟着一个 整数
小数(按顺序)可以分成以下几个部分:

(可选)一个符号字符(’+’ 或 ‘-‘)
下述格式之一:
至少一位数字,后面跟着一个点 ‘.’
至少一位数字,后面跟着一个点 ‘.’ ,后面再跟着至少一位数字
一个点 ‘.’ ,后面跟着至少一位数字
整数(按顺序)可以分成以下几个部分:

(可选)一个符号字符(’+’ 或 ‘-‘)
至少一位数字

部分有效数字列举如下:
[“2”, “0089”, “-0.1”, “+3.14”, “4.”, “-.9”, “2e10”, “-90E3”, “3e+7”, “+6e-1”, “53.5e93”, “-123.456e789”]

部分无效数字列举如下:
[“abc”, “1a”, “1e”, “e3”, “99e2.5”, “—6”, “-+3”, “95a54e53”]

给你一个字符串 s ,如果 s 是一个 有效数字 ,请返回 true 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

示例 1

输入:s = "0"
输出:true
示例 2

输入:s = "e"
输出:false
示例 3

输入:s = "."
输出:false
示例 4

输入:s = ".1"
输出:true
 

提示:

1 <= s.length <= 20
s 仅含英文字母(大写和小写),数字(0-9),加号 '+' ,减号 '-' ,或者点 '.'

解法

遍历原理已经忘记多时了。这里参考了一下大佬的题解,写成的。

首先看到题目是可以想到使用自动机的,因此需要画出状态转移图,然后再根据状态转移图来写出状态转移表,最后通过一个个字符串对应的状态进行查表来得到最终状态。

所有的状态为:
所有状态:

0. 初始状态
1.符号位
2.整数部分
3.左侧有整数的小数点
4.左侧无整数的小数点(根据前面的第二条额外规则,需要对左侧有无整数的两种小数点做区分)
5.小数部分
6.字符 e/E
7.指数部分的符号位
8.指数部分的整数部分

其中2、3、5、8为终止状态(可以接受),还定义一个-1作为不可接收状态,直接结束。

状态转移图:

figure.1

状态转移表:

sate blank +/- 0-9 . e other
0 0 1 6 2 -1 -1
1 -1 -1 6 2 -1 -1
2 -1 -1 3 -1 -1 -1
3 8 -1 3 -1 4 -1
4 -1 7 5 -1 -1 -1
5 8 -1 5 -1 -1 -1
6 8 -1 6 3 4 -1
7 -1 -1 5 -1 -1 -1
8 8 -1 -1 -1 -1 -1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution(object):
# 确定下一个状态
def make(self,c):
if c == ' ':
return 0
elif c == '+':
return 1
elif c == '-':
return 1
elif c == '.':
return 3
elif c == 'e' or c == 'E':
return 4
else:
# 数字情况
if c >= '0' and c <= '9':
return 2
# 其他情况
else:
return 5
def isNumber(self, s):
"""
:type s: str
:rtype: bool

核心思想:
使用DFA求解
分析题意、画出状态转移图(可以不是最简的)
根据状态转移图写出状态转移表
状态共8个状态,下标为0、1、2、3、4、5、6、7、8
"""
state = 0 # 状态
finals = [0,0,0,1,0,1,1,0,1] # 最终可接受的状态 1表示可以介绍 0表示不可以接收
# 状态转移表
transfer = [[ 0, 1, 6, 2,-1,-1],
[-1,-1, 6, 2,-1,-1],
[-1,-1, 3,-1,-1,-1],
[ 8,-1, 3,-1, 4,-1],
[-1, 7, 5,-1,-1,-1],
[ 8,-1, 5,-1,-1,-1],
[ 8,-1, 6, 3, 4,-1],
[-1,-1, 5,-1,-1,-1],
[ 8,-1,-1,-1,-1,-1]]

for i in range(len(s)):
state = transfer[state][self.make(s[i])] # 访问状态转移表转移到下一个状态
if state < 0: # 状态达到不可接受状态
return False

return bool(finals[state])

if __name__ == '__main__':
s = Solution()
print(s.isNumber('95a54e53'))
StriveZs wechat
Hobby lead  creation, technology change world.