文章目录2021/6/17

• 一、LeetCode每日一题

---

一、LeetCode每日一题

题目链接

有效数字

题解

观察数据范围 1 < = s . l e n g t h < = 20 1 <= s.length <= 20 1<=s.length<=20,提示我们可以设计最坏 O ( 2 n ) O(2^n) O(2n)的算法。

解法一暴力匹配

按照题目中所给出的条件模拟匹配即可。坏处，逻辑复杂易出错。

解法二DFA(确定有限状态自动机)

D F A DFA DFA简介：

• D F A DFA DFA是确定有限状态自动机的首字母简写 D e t e r m i n i s t i c F i n i t e A u t o m a t o n Deterministic Finite Automaton DeterministicFiniteAutomaton,这是一类计算模型，主要由以下两点组成。
  • 状态(节点)
  • 状态转移(边)

题解

• 首先定义状态
  • 0 0 0:初始状态
  • 1 1 1:符号位 ( + / − ) (+/-) (+/−)
  • 2 2 2:小数点 ( . ) (.) (.)
  • 3 3 3:小数点后的数字 ( 0 − 9 ) (0-9) (0−9)
  • 4 4 4:指数符号 ( e / E ) (e/E) (e/E)
  • 5 5 5:指数符号后的数字 ( 0 − 9 ) (0-9) (0−9)
  • 6 6 6:普通数字 ( 0 − 9 ) (0-9) (0−9)
  • 7 7 7:指数符号后的符号位 ( + / − ) (+/-) (+/−)
  • 8 8 8:空格
• 起初我们有一个初始状态 0 0 0
• 思考由初始状态可以转移到哪些状态？
  • 我们把同类型的状态压缩成一个，例如：普通数字、小数点后的数字、指数符号后的数字统一称作数字(0,9),只要在转移时根据当前状态判断即可，再把类型作为数组下标的第二维即可，当前不理解没关系，继续往下看。
  • 显然可以转移到空格、符号位、小数点、普通数字
  • 其他状态均不可以。列表如下：

当前状态	空格(下标为0)	符号(+/-)(下标为1)	数字(0,9)(下标为2)	小数点(.) (下标为3)	指数符号(e/E)(下标为4)	其他
0	0(初始状态)	1(符号位)	6(普通数字)	2(小数点)	-1	-1

• 再举个例子：
  • 比如现在的状态是 4 4 4(指数符号)，现在可以转移到哪些状态？
    • 显然指数符号后的符号位、指数符号后的数字，列表如下：

当前状态	空格	符号(+/-)	数字(0,9)	小数点(.)	指数符号(e/E)	其他
4	-1	7(指数符号后的符号位)	5(指数符号后的数字)	-1	-1	-1

• 给出所有的状态转移的表(到时只要把这个表作为二维数组去转移状态即可)：

当前状态	空格	符号(+/-)	数字(0,9)	小数点(.)	指数符号(e/E)	其他
0	0	1	6	2	-1	-1
1	-1	-1	6	2	-1	-1
2	-1	-1	3	-1	-1	-1
3	8	-1	3	-1	4	-1
4	-1	7	5	-1	-1	-1
5	8	-1	5	-1	-1	-1
6	8	-1	6	3	4	-1
7	-1	-1	5	-1	-1	-1
8	8	-1	-1	-1	-1	-1

• 什么时候算是合法的结束状态呢？
  • 可以是小数点后的数字、普通数字、指数符号后的数字

代码

int DFA[][5] = {{ 0, 1, 6, 2,-1},
                {-1,-1, 6, 2,-1},
                {-1,-1, 3,-1,-1},
                { 8,-1, 3,-1, 4},
                {-1, 7, 5,-1,-1},
                { 8,-1, 5,-1,-1},
                { 8,-1, 6, 3, 4},
                {-1,-1, 5,-1,-1},
                { 8,-1,-1,-1,-1}};

int getType(char c) {
    switch (c) {
        case ' ': return 0;
        case '+':
        case '-': return 1;
        case '.': return 3;
        case 'e':
        case 'E': return 4;
        default:
            if (c >= '0' && c <= '9') return 2;
            return -1;
    }
}

bool isNumber(string s) {
    int curState = 0;
    for (char c : s) {
        int type = getType(c);
        if (type == -1) return false;
        curState = DFA[curState][type];
        if (curState == -1) return false;
    }
    // 3 5 6代表上边说的那三种合法的结束状态
    return curState == 3 || curState == 6 || curState == 5;
}

时空复杂度分析

• D F A DFA DFA按字符求解，每个字符状态转移过程为 O ( 1 ) O(1) O(1)的时间复杂度，一共有 ∣ s ∣ |s| ∣s∣个字符，总的时间复杂度为 O ( ∣ s ∣ ) O(|s|) O(∣s∣)。
• 使用了常数的空间，空间复杂度为 O ( 1 ) O(1) O(1)。