☆打卡算法☆LeetCode 65、有效数字 算法解析

发表于

这是我参与11月更文挑战的第29天，活动详情查看：2021最后一次更文挑战

推荐阅读

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个字符串，判断是否是有效数字。”

题目链接：

来源：力扣（LeetCode）

链接：65. 有效数字 - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

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

  • 1.一个 小数 或者 整数
  • 2.（可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个 整数
    小数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（’+’ 或 ‘-‘）
下述格式之一：

  • 1.至少一位数字，后面跟着一个点 ‘.’
  • 2.至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字
  • 3.一个点 ‘.’ ，后面跟着至少一位数字
    整数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（’+’ 或 ‘-‘）
至少一位数字
部分有效数字列举如下：

  • [“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
ini复制代码示例 1：
输入： s = "0"
输出： true
1
2
3
ini复制代码示例 2：
输入： s = "e"
输出： false

二、解题

1、思路分析

这道题可以使用有限状态机的思路解决问题，有限状态机是一种计算模型，包含一系列的状态，然后根据不同的状态进行切换。

然后，就按顺序去读取字符串中的每一个字符，如果是实现约定好的庄毅规则，就从当前状态转移到下一个状态，状态转移完成后，就读取下一个字符。

当所有的字符串读取完毕，如果状态机处于正确状态就说明该字符串正确，否则，不正确。

2、代码实现

代码参考：

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
csharp复制代码public class Solution {
    public bool IsNumber(string s) {
        Dictionary<State, Dictionary<CharType, State>> transfer = new Dictionary<State, Dictionary<CharType, State>>();
        Dictionary<CharType, State> initialDictionary = new Dictionary<CharType, State> {
            {CharType.CHAR_NUMBER, State.STATE_INTEGER},
            {CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT},
            {CharType.CHAR_SIGN, State.STATE_INT_SIGN}
        };
        transfer.Add(State.STATE_INITIAL, initialDictionary);
        Dictionary<CharType, State> intSignDictionary = new Dictionary<CharType, State> {
            {CharType.CHAR_NUMBER, State.STATE_INTEGER},
            {CharType.CHAR_POINT, State.STATE_POINT_WITHOUT_INT}
        };
        transfer.Add(State.STATE_INT_SIGN, intSignDictionary);
        Dictionary<CharType, State> integerDictionary = new Dictionary<CharType, State> {
            {CharType.CHAR_NUMBER, State.STATE_INTEGER},
            {CharType.CHAR_EXP, State.STATE_EXP},
            {CharType.CHAR_POINT, State.STATE_POINT}
        };
        transfer.Add(State.STATE_INTEGER, integerDictionary);
        Dictionary<CharType, State> pointDictionary = new Dictionary<CharType, State> {
            {CharType.CHAR_NUMBER, State.STATE_FRACTION},
            {CharType.CHAR_EXP, State.STATE_EXP}
        };
        transfer.Add(State.STATE_POINT, pointDictionary);
        Dictionary<CharType, State> pointWithoutIntDictionary = new Dictionary<CharType, State> {
            {CharType.CHAR_NUMBER, State.STATE_FRACTION}
        };
        transfer.Add(State.STATE_POINT_WITHOUT_INT, pointWithoutIntDictionary);
        Dictionary<CharType, State> fractionDictionary = new Dictionary<CharType, State> {
            {CharType.CHAR_NUMBER, State.STATE_FRACTION},
            {CharType.CHAR_EXP, State.STATE_EXP}
        };
        transfer.Add(State.STATE_FRACTION, fractionDictionary);
        Dictionary<CharType, State> expDictionary = new Dictionary<CharType, State> {
            {CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER},
            {CharType.CHAR_SIGN, State.STATE_EXP_SIGN}
        };
        transfer.Add(State.STATE_EXP, expDictionary);
        Dictionary<CharType, State> expSignDictionary = new Dictionary<CharType, State> {
            {CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER}
        };
        transfer.Add(State.STATE_EXP_SIGN, expSignDictionary);
        Dictionary<CharType, State> expNumberDictionary = new Dictionary<CharType, State> {
            {CharType.CHAR_NUMBER, State.STATE_EXP_NUMBER}
        };
        transfer.Add(State.STATE_EXP_NUMBER, expNumberDictionary);

        int length = s.Length;
        State state = State.STATE_INITIAL;

        for (int i = 0; i < length; i++) {
            CharType type = ToCharType(s[i]);
            if (!transfer[state].ContainsKey(type)) {
                return false;
            } else {
                state = transfer[state][type];
            }
        }
        return state == State.STATE_INTEGER || state == State.STATE_POINT || state == State.STATE_FRACTION || state == State.STATE_EXP_NUMBER || state == State.STATE_END;
    }

    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,
        STATE_EXP,
        STATE_EXP_SIGN,
        STATE_EXP_NUMBER,
        STATE_END
    }

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

image.png

3、时间复杂度

时间复杂度 ： O(n)

其中n是数组的长度，只需要遍历一遍数组即可求得答案。

空间复杂度： O(1)

只需要常数级别的空间存放变量。

三、总结

当然这道题有更加简便的方法解决。

就是用正则表达式匹配：

1
2
3
4
5
6
7
8
9
10
arduino复制代码class Solution {
public:
    static const regex pattern;

    bool isNumber(string str) {
        return regex_match(str, pattern);
    }
};

const regex Solution::pattern("[+-]?(?:\d+\.?\d*|\.\d+)(?:[Ee][+-]?\d+)?");

但是要注意，c++ 用正则表达式记得作为类的静态变量或全局变量，避免重复构造的开销，否则会超时。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%