ValidNumber

有效数字

题目介绍

有效数字

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

  1. 一个 小数 或者 整数
  2. （可选）一个 'e' 或 'E' ，后面跟着一个 整数

小数（按顺序）可以分成以下几个部分：

  1. （可选）一个符号字符（'+' 或 '-'）
  2. 下述格式之一：
    1. 至少一位数字，后面跟着一个点 '.'
    2. 至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
    3. 一个点 '.' ，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：

  1. （可选）一个符号字符（'+' 或 '-'）
  2. 至少一位数字

部分有效数字列举如下：

  • [“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：

1
2
输入：s = "0"
输出：true

示例2：

1
2
输入：s = "e"
输出：false

示例 3：

1
2
输入：s = "."
输出：false

示例 4：

1
2
输入：s = ".1"
输出：true

提示：

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

题目解法

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
package algorithm;

import java.util.HashMap;
import java.util.Map;

public class ValidNumber {

    public static boolean isNumber(String s) {

        Map<State, Map<CharType, State>> transfer = new HashMap<>();

        // 开始的字符，以及这个字符目前所处的状态
        Map<CharType, State> initialMap = new HashMap<CharType, State>() {{
            put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
            put(CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT);
            put(CharType.CHAR_SIGN, State.STATE_INT_SIGN);
        }};
        // 开始状态所包含的下一步能含有的字符及状态，下面依次类推
        transfer.put(State.STATE_INITIAL, initialMap);

        // +/-，以及这个字符目前所处的状态
        Map<CharType, State> intSignMap = new HashMap<CharType, State>() {{
            put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
            put(CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT);
        }};
        transfer.put(State.STATE_INT_SIGN, intSignMap);

        // 0-9
        Map<CharType, State> integerMap = new HashMap<CharType, State>() {{
            put(CharType.CHAR_NUMBER, State.STATE_INTEGER);
            put(CharType.CHAR_EXP, State.STATE_EXP);
            put(CharType.CHAR_POINT, State.STATE_POINT);
        }};
        transfer.put(State.STATE_INTEGER, integerMap);

        // .
        Map<CharType, State> pointMap = new HashMap<CharType, State>() {{
            put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
            put(CharType.CHAR_EXP, State.STATE_EXP);
        }};
        transfer.put(State.STATE_POINT, pointMap);

        // .
        Map<CharType, State> pointWithoutIntMap = new HashMap<CharType, State>() {{
            put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
        }};
        transfer.put(State.STATE_POINT_WITHOUT_INT, pointWithoutIntMap);

        Map<CharType, State> fractionMap = new HashMap<CharType, State>() {{
            put(CharType.CHAR_NUMBER, State.STATE_FRACTION);
            put(CharType.CHAR_EXP, State.STATE_EXP);
        }};
        transfer.put(State.STATE_FRACTION, fractionMap);

        // E/e
        Map<CharType, State> expMap = new HashMap<CharType, State>() {{
            put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
            put(CharType.CHAR_SIGN, State.STATE_EXP_SIGN);
        }};
        transfer.put(State.STATE_EXP, expMap);

        Map<CharType, State> expSignMap = new HashMap<CharType, State>() {{
            put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
        }};
        transfer.put(State.STATE_EXP_SIGN, expSignMap);

        Map<CharType, State> expNumberMap = new HashMap<CharType, State>() {{
            put(CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER);
        }};
        transfer.put(State.STATE_EXP_NUMBER, expNumberMap);

        int length = s.length();
        State state = State.STATE_INITIAL;

        for (int i = 0; i < length; i++) {
            CharType type = toCharType(s.charAt(i));
            if (!transfer.get(state).containsKey(type)) {
                return false;
            }
            state = transfer.get(state).get(type);
        }

        return state == State.STATE_INTEGER || state == State.STATE_POINT
                || state == State.STATE_FRACTION || state == State.STATE_EXP_NUMBER
                || state == State.STATE_END;
    }

    public static CharType toCharType(char ch) {
        if (ch >= '0' && ch <= '9') {
            return CharType.CHAR_NUMBER;
        } else if (ch == 'e' || ch == 'E') {
            return CharType.CHAR_EXP;
        } else if (ch == '.') {
            return CharType.CHAR_POINT;
        } else if (ch == '+' || ch == '-') {
            return CharType.CHAR_SIGN;
        } else {
            return CharType.CHAR_ILLEGAL;
        }
    }

    enum State {
        // 初始
        STATE_INITIAL,
        // 符号位+/-
        STATE_INT_SIGN,
        // 整数部分
        STATE_INTEGER,
        // 左侧有整数的小数点
        STATE_POINT,
        // 左侧无整数的小数点
        STATE_POINT_WITHOUT_INT,
        // 小数部分
        STATE_FRACTION,
        // 字符e
        STATE_EXP,
        // 指数部分的符号位+/-
        STATE_EXP_SIGN,
        // 指数部分的整数部分
        STATE_EXP_NUMBER,
        // 结束
        STATE_END,
    }

    enum CharType {
        CHAR_NUMBER,
        CHAR_EXP,
        CHAR_POINT,
        CHAR_SIGN,
        CHAR_ILLEGAL,
    }

    public static void main(String[] args) {
        System.out.println(isNumber("0"));
        System.out.println(isNumber("e"));
        System.out.println(isNumber("."));
        System.out.println(isNumber(".1"));
    }
}

打印：

1
2
3
4
true
false
false
true

思路：

思路上直接抄了官方，虽然效率不是很高，主要是解题方式是有限状态机的设计。

Leetcode
ValidNumber
https://yangtzeshore.github.io/2021/04/22/ValidNumber/
作者
Chen Peng
发布于
2021年4月22日
许可协议