本页目录

65.有效数字

题目

LeetCode 困难

有效数字（按顺序）可以分成以下几个部分：

一个小数或者整数

（可选）一个 ‘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 。

题解

确定有限状态自动机

精选解法

O(n) O(1)

// 生成数字关系图 只有状态为 3 5 6 的时候才为一个数字
const graph = {
  0: { blank: 0, sign: 1, '.': 2, digit: 6 },
  1: { digit: 6, '.': 2 },
  2: { digit: 3 },
  3: { digit: 3, e: 4 },
  4: { digit: 5, sign: 7 },
  5: { digit: 5 },
  6: { digit: 6, '.': 3, e: 4 },
  7: { digit: 5 },
}

function isNumber(s) {
  // 记录状态
  let state = 0
  // 遍历字符串
  for (let c of s.trim()) {
    console.log(c)
    // 把字符进行转换
    if (c >= '0' && c <= '9') {
      c = 'digit'
    } else if (c === ' ') {
      c = 'blank'
    } else if (c === '+' || c === '-') {
      c = 'sign'
    } else if (c === 'E' || c === 'e') {
      c = 'e'
    }
    // 开始寻找图
    state = graph[state][c]

    console.log(c, state)
    console.log('------')

    // 找不到直接返回
    if (state === undefined) return false
  }

  console.log('🔚 state', state)

  // 判断最后的结果是不是合法的数字
  if (state === 3 || state === 5 || state === 6) return true
  return false
}

console.log('🌰 -123.456e789', isNumber('-123.456e789'))
console.log('🌰 -.9', isNumber('-.9'))
console.log('🌰 3e+7', isNumber('3e+7'))
console.log('🌰 abc', isNumber('abc'))

执行结果

-
sign 1
------
1
digit 6
------
2
digit 6
------
3
digit 6
------
.
. 3
------
4
digit 3
------
5
digit 3
------
6
digit 3
------
e
e 4
------
7
digit 5
------
8
digit 5
------
9
digit 5
------
🔚 state 5
🌰 -123.456e789 true
-
sign 1
------
.
. 2
------
9
digit 3
------
🔚 state 3
🌰 -.9 true
3
digit 6
------
e
e 4
------
+
sign 7
------
7
digit 5
------
🔚 state 5
🌰 3e+7 true
a
a undefined
------
🌰 abc false

本页目录

65.有效数字

题目 #

题解 #

题目

题解