每日一题——有效数字

有理想的菜鸡 2020-06-11

163

菜鸡每日一题系列打卡65天

每天一道算法题目

小伙伴们一起留言打卡

坚持就是胜利，我们一起努力！

题目描述(引自LeetCode)

验证给定的字符串是否可以解释为十进制数字。

例如:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
" -90e3   " => true
" 1e" => false
"e3" => false
" 6e-1" => true
" 99e2.5 " => false
"53.5e93" => true
" --6 " => false
"-+3" => false
"95a54e53" => false

说明:

我们有意将问题陈述地比较模糊。在实现代码之前，你应当事先思考所有可能的情况。

这里给出一份可能存在于有效十进制数字中的字符列表：

数字 0-9
指数 - "e"
正/负号 - "+"/"-"
小数点 - "."
当然，在输入中，这些字符的上下文也很重要。

题目分析

这道题是一道极其偏向于有限状态自动机(DFA)解法的题目。DFA的概念之前的题目中已经提到过了，在这里就不赘述，对DFA不了解的小伙伴请移步文末相关链接进行学习。该解法的关键是判断具体有几种状态以及状态的转换条件。话不多说，上代码！

代码实现

class Solution {


    class Automaton {


        private int[][] dfa;


        public Automaton() {
            this.dfa = new int[][]{{0, 1, 2, 3, -1},
                                  {-1, -1, 2, 3, -1},
                                  {8, -1, 2, 5, 4},
                                  {-1, -1, 5, -1, -1},
                                  {-1, 6, 7, -1, -1},
                                  {8, -1, 5, -1, 4},
                                  {-1, -1, 7, -1, -1},
                                  {8, -1, 7, -1, -1},
                                  {8, -1, -1, -1, -1}};
        }


        public int[][] getDfa() {
            return this.dfa;
        }


        public int getIndex(char c) {
            switch(c) {
                case ' ': return 0;
                case '+':
                case '-': return 1;
                case '.': return 3;
                case 'e': return 4;
                default:
                    if(c - '0' >= 0 && c - '0' <= 9) return 2;
            }
            return -1;
        }
    }
    
    public boolean isNumber(String s) {
        int state = 0;
        Automaton automaton = new Automaton();
        for(char c : s.toCharArray()) {
            int id = automaton.getIndex(c);
            if (id < 0) return false;
            state = automaton.dfa[state][id];
            if (state < 0) return false;
        }
        return (0b110100100 & (1 << state)) > 0;
    }
}

代码分析

对代码进行分析，程序对字符串进行了最多一次遍历，因此，时间复杂度为O(n)，而就空间而言，仅仅使用了常数级别的额外空间，因此，空间复杂度为O(1)。

执行结果

相关链接

每日一题——字符串转换整数（atoi）

学习 | 工作 | 分享

👆长按关注“有理想的菜鸡”

只有你想不到，没有你学不到

数据库

文章转载自有理想的菜鸡，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

每日一题——有效数字

评论