有效数字(Leetcode 65)

发表于 | 分类于 ， | | 本文总阅读数 次
| 字数统计: 1.5k | 阅读时长 ≈ 6
Leetcode 65

1

题目分析

   在博客中介绍过类似的题目leetcode剑指Offer第20题，但我认为那个题目稍微复杂一点点，只要思路明白了，做法都是相同的。只不过那个题目可能会出现空格，这个题目没用空格。

有限状态自动机

观察发现有效数字中字符出现的顺序是有规律可循的，我们将其称为状态，如起始状态我们设置为0
起始状态0后面可以跟正负号、数字和小数点，分别记正负号为状态1，数字为状态2，小数点为状态4
正负号状态1后面可以跟数字和小数点，数字为状态2，小数点为状态4
数字状态2后面可以跟数字、小数点、指数e和结束状态，数字已经标记过为状态2，注意此时的数字为状态2表示正负号之后小数点之前的数字，如+5.3中的5，记小数点为状态3，并不是之前定义过的状态4，这非常重要，因为两个小数点并不是同一个状态，因为起始状态后面直接跟随的小数点状态为.5中的小数点，此时小数点后面必须跟随数字，而这里定义的小数点状态是指数字后面的小数点，可以不跟随数字，如5.。所以虽然都是小数点，但是所在的状态不同。记指数e为状态6
小数点状态3后面可以跟数字、指数e和结束状态，此时的数字也不是状态2表示的数字，因为状态2表示的数字后可以跟小数点，而这里指的数字是小数点后面的数字，已经不能跟随小数点了，记为状态5，指数e已经标记过为状态6
小数点状态4后面只能跟数字状态5
数字状态5后面可以跟数字状态5、指数e状态6和结束状态
指数e状态6后面可以跟正负号和数字、此时正负号和状态1不相同，数字和状态2和状态5都不相同，记正负号为状态7，数字为状态8
正负号状态7后面只能跟数字状态8
数字状态8后面可以跟数字状态8和结束状态

经过上面的分析后，可以画出如下的状态转移图
1

我们使用一个字典记录当前状态的所有后继状态，从初始状态0出发，经过一个字符，状态产生一次转移，如果下一个字符是当前状态的后继状态其中之一，那么继续判断，否则直接返回false。如果所有字符都满足条件，那么在循环出口判断当前状态后面是否可以跟随结束状态即可。即最后一个字符一定是结束状态的前驱状态。

算法的时间复杂度为$O(n)$，空间复杂度为$O(1)$

下面是C++语言的题解

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
class Solution {
public:
    bool isNumber(string s) {
        vector<unordered_map<string, int>> dic = {
            {{"sign", 1}, {"digit", 2}, {"dot", 4}},
            {{"digit", 2}, {"dot", 4}},
            {{"digit", 2}, {"dot", 3}, {"e", 6}},
            {{"digit", 5}, {"e", 6}},
            {{"digit", 5}},
            {{"digit", 5}, {"e", 6}},
            {{"sign", 7}, {"digit", 8}},
            {{"digit", 8}},
            {{"digit", 8}}
        };
        int cur = 0;
        for (char c : s) {
            string p;
            if (c == '+' || c == '-') { p = "sign"; }
            else if (c == '.') { p = "dot"; }
            else if (c == 'e' || c == 'E') { p = "e"; }
            else if (c >= '0' && c <= '9') { p = "digit"; }
            else { return false; }
            if (dic[cur].count(p)) { cur = dic[cur][p]; }
            else { return false; }
        }
        return cur == 2 || cur == 3 || cur == 5 || cur == 8;
    }
};

下面是Java语言的题解

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
class Solution {
    public boolean isNumber(String s) {
        ArrayList<HashMap<String, Integer>> dic = new ArrayList<>(9);
        for (int i = 0; i < 9; i++) { dic.add(new HashMap<>()); }
        dic.get(0).put("sign", 1);
        dic.get(0).put("digit", 2);
        dic.get(0).put("dot", 4);
        dic.get(1).put("digit", 2);
        dic.get(1).put("dot", 4);
        dic.get(2).put("digit", 2);
        dic.get(2).put("dot", 3);
        dic.get(2).put("e", 6);
        dic.get(3).put("digit", 5);
        dic.get(3).put("e", 6);
        dic.get(4).put("digit", 5);
        dic.get(5).put("digit", 5);
        dic.get(5).put("e", 6);
        dic.get(6).put("sign", 7);
        dic.get(6).put("digit", 8);
        dic.get(7).put("digit", 8);
        dic.get(8).put("digit", 8);
        int cur = 0;
        for (int i = 0; i < s.length(); i++) {
            String p;
            if (s.charAt(i) == '+' || s.charAt(i) == '-') { p = "sign"; }
            else if (s.charAt(i) == '.') { p = "dot"; }
            else if (s.charAt(i) == 'e' || s.charAt(i) == 'E') { p = "e"; }
            else if (s.charAt(i) >= '0' && s.charAt(i) <= '9') { p = "digit"; }
            else { return false; }
            if (dic.get(cur).containsKey(p)) { cur = dic.get(cur).get(p); }
            else { return false; }
        }
        return cur == 2 || cur == 3 || cur == 5 || cur == 8;
    }
}

对比C++和Java两种语言，在C++中，字典创建比较简单，可以通过中括号[]来进行访问，花括号{}键值对的方式初始化，而Java要通过get方法进行访问，put方法进行初始化。而且在字符串的遍历过程中，C++可以直接使用for循环取出字符，Java必须转成CharArray类型，或者根据索引使用charAt访问，也不能使用中括号[]访问字符串中的字符。

刷题总结

  本题的重点是有限状态自动机，当然小伙伴们也可以使用if…else if…else进行分类讨论，不过讨论的过程非常繁琐，也不是本题考查的重点，因此不做讨论。

-------------本文结束感谢您的阅读-------------
0%