Skip to content

Latest commit

 

History

History
258 lines (164 loc) · 8.61 KB

65.valid-number.md

File metadata and controls

258 lines (164 loc) · 8.61 KB

题目地址(65. 有效数字)

https://leetcode-cn.com/problems/valid-number/

题目描述

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

一个 小数 或者 整数
(可选)一个 '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:

输入:s = "0"
输出:true


示例 2:

输入:s = "e"
输出:false


示例 3:

输入:s = "."
输出:false


示例 4:

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


 

提示:

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

前置知识

  • 暂无

公司

  • 暂无

三个变量一次遍历

思路

我们可以直接进行一次遍历,边遍历边判断是否合法。

如果要边遍历边判断是否合法则需要记录一些关键信息。比如,当我遍历途中遇到了 .,那么我实际上需要知道一些信息,比如前面是否已经出现过 . 了。如果已经出现过了,那么就可以得出结论,该数字非法。

除了前面是否出现 . 这样的信息,我们还需要关注其他信息。具体地,我们需要关注:

  • .
  • e/E
  • 前面是否有数字

以上三个信息。 我们可以用三个变量,分别表示上一次遇到其的位置(索引),用 -1 表示还没有遇到。

实际上,这道题的关键点就是分析出哪些是非法,这样不是非法的,那么就是合法的。 之所以如此是因为合法的实在是太多了,我们没有办法一一判断,而只能从非法的角度入手。而非法的情况比较多,如何分类是个问题,这也是本题是困难难度的原因。

让我们来分析一下非法的情景。

  • 点前面有 e 或者 点,比如 1.1.1 或者 3e5.2
  • e 前面有 e ,比如 e12e。或者 e 前面没有数字,比如 e123
  • + - 前面要么是 e,要么其位于第一位
  • 出现了非法字符。也就是出现了除了 +-eE 数字. 之外的字符

代码上,我们可以使用三个变量:

  1. last_dot 上一次遇到的 . 的位置
  2. last_e 上一次遇到的 e/E 的位置
  3. last_d 上一次遇到的数字的位置

接下来我们需要遍历字符串 s,遍历的同时记得更新三个变量。

  • 如果我们遇到了字符 ".",那么需要前面没有 ".",也不能有 e/E,否则就不合法。
  • 如果遇到了 e/E,那么前面不能有 e/E。除此之前前面还有有数字才行。
  • 如果遇到了 +-,要么它是第一个字符,要么它前面是 e/E,否则不能合法
  • 其他非数字字符均为不合法

关键点

  • 分析非法的情况,用三个变量记录上一次出现的点,指数,数字的位置来复制判断

代码

class Solution:
    def isNumber(self, s: str) -> bool:
        last_dot = last_e = last_d = -1
        for i, c in enumerate(s):
            if c.isdigit():
                last_d = i
            elif c == '.':
                if last_dot != -1 or last_e != -1: return False
                last_dot = i
            elif c.lower() == 'e':
                if last_d == -1 or last_e != -1: return False
                last_e = i
            elif c == '+' or c == '-':
                if i == 0 or s[i-1].lower() == 'e':
                    continue
                else:
                    return False
            else:
                return False

        return s[-1].isdigit() or (s[-1] == '.' and last_d != -1)

复杂度分析

令 n 为数组长度。

  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(1)$

状态机

思路

对于状态机,我们需要解决的就是:

  1. 状态有哪些
  2. 选择有哪些

和动态规划是类似的

对于这道题来说,打底的状态就是各种字符的类型。即:

  • 数字
  • .
  • eE
  • +-

打底就是这四种。

我们没有必要将 eE 或者 +- 进行区分,这是因为在这里二者的逻辑不会有差别。

那么这四种就够了。这是不够的。这是因为题目描述决定的。比如题目说了 e 后面不能是小数。 那么对于 . 来说,

  • 我们就需要分裂 为两种状态: e 前面的 . 和 e 后面的 .。
  • 类似地,+- 号,我们需要区分是第一位还是 e 后面的(紧邻),这是因为第一位后面可以跟 . ,而 e 后面紧邻的不可以。
  • 数字也是一样。 由于 e 后面不能有点,也需要进行类似的分裂

最后一个比较容易漏掉,我们需要一种数字状态,这个数字状态后面只能跟数字,不能跟其他。比如 +2e+3 ,这个时候的 3 后面就只能是数字了,其他都是非法的。

对于这道题来说:

  • 图中黄色的四个部分就是选择。由于 +-,以及 [1-9] 对我们的算法没有影响,因此没有单独抽离出来,而是将其归为一类。
  • 图中虚线部分就是状态。

不难看出,"." 前后的状态选择是不同的。因此除了:"+-", "[1-9]", "e/E", "." 这几种基本状态,还要分别对 [1-9], e/E 进行区分是 “.”前还是后。从左到右我将其进行编号,靠左的是 1,靠右的是 2, 因此就有了 sign1,digit1, exp, D digit2 exp sign2 D 的状态命名。

注意这里是 D,不是 digit2。因为 digit2 可以接 E/e,因此需要单独定义一种状态

另外由于:dot 前面和后面必须有至少一个数字,并且有没有数字对选择也有影响,因此我们也需要对此区分。我这里用 dot1 表示前面有数字的 dot,dot2 表示前面没有数字的 dot

关于如何转化,我就不一一分析了,大家直接看代码吧。虽然思路不难理解,但是细节还是蛮多的,大家自己写写就知道了。

关键点

  • 建立状态机模型
  • 如果知道一共有多少状态

代码

代码上,我们 xxx1 表示前面的 xxx,xxx2 表示后面的 xxx。D 表示只能跟数字

  • 语言支持:Python3

Python3 Code:

class Solution:
    def isNumber(self, s: str) -> bool:
        # 任何状态机的核心都是建立如下的状态机模型
        states = {
            "start": {"SIGN":"sign1",  "DIGIT":"digit1",  "DOT":"dot1"},
            "sign1": {"DIGIT":"digit1",  "DOT":"dot1"},
            "sign2": {"DIGIT":"D"},
            "digit1": {"DIGIT":"digit1",  "DOT":"dot2",  "EXP":"exp",  "END": True},
            "digit2": {"DIGIT":"digit2",  "EXP":"exp",  "END": True},
            "dot1": {"DIGIT":"digit2"}, # 前面没数字
            "dot2": {"DIGIT":"digit2",  "EXP":"exp",  "END": True}, # 前面有数字
            "exp": {"SIGN":"sign2",  "DIGIT":"D"},
            "D": {"DIGIT":"D",  "END": True}
        }

        def get(ch):
            if ch == ".": return "DOT"
            elif ch in "+-": return "SIGN"
            elif ch in "Ee": return "EXP"
            elif ch.isdigit(): return "DIGIT"

        state = "start"
        for c in s:
            state = states[state].get(get(c))
            if not state: return False

        return "END" in states[state]

复杂度分析

令 n 为数组长度。

  • 时间复杂度:$O(n)$
  • 空间复杂度:虽然使用了 states 存放状态,但是其不会随着数字增大而变大,而是一个定值,因此空间复杂度为 $O(1)$

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。