【剑指Offer】个人学习笔记_20_表示数值的字符串

2023-12-02 21:09:40

目录

刷题日期：19:3124 星期一2021年3月29日

个人刷题记录，代码收集，来源皆为leetcode

经过多方讨论和请教，现在打算往Java方向发力

主要答题语言为Java

题目：

剑指 Offer 20. 表示数值的字符串

难度中等169

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、“5e2”、"-123"、“3.1416”、"-1E-16"、“0123"都表示数值，但"12e”、“1a3.14”、“1.2.3”、"±5"及"12e+5.4"都不是。

题目分析

题干比较简单，也没有其他提示。

考的是穷举的能力，肯定不能一次把所有的情况考虑完，一次次提交就好。

最复杂的数字情况：正负号+整数+小数点+整数+e/E+正负号+指数

整数部分和指数部分都是可有可无的。

初始解答：

参考书籍尝试写出代码：

class Solution {
    public boolean isNumber(String s) {
        /* 最复杂的数字情况：正负号+整数+小数点+整数+e/E+正负号+指数
        整数部分和指数部分都是可有可无的。*/
        if (s == null) return false; //为空则错误
        //考虑完特殊情况就得被遍历一遍分情况讨论了
        //这里也得用到上一道题的从字符串里识别指定字符的函数
        int n = s.length(), i = 0;  //求得长度
        boolean[] f = new boolean[n]; //判断相应的位是否满足要求

        //判断整数部分
        while(scanInteger(s.charAt(i))) {

            //出现小数部分的话
            if (s.charAt(i) == '.') {
                i++;
            }
            //出现指数部分的话
            if (s.charAt(i) == 'e' || s.charAt(i) == 'E') {
                i++;
            }
        }
                //判断是否为整数的函数
        public boolean scanInteger(String a) {
            if (a != '\0' && a >= '0' && a <= '9') return true;
            return false;
        }
        return true;
    }
}

放弃了，什么玩意嘛，大的套小的，各种判断，参考其他人

徐树 2020-09-01

这题简直就是：试用例猜规则。 现在基本可以明确规则如下：

  1. 数字两边可以有空格，但是中间插空格不行；
  2. 除了数字之外，合法字符还有’e’、‘E’、’+’、’-’、’.’；
  3. ‘e’、'E’等价，用来划分底数与指数，只能出现一次，前面为科学计数法的底数，后面为指数；
  4. ‘+’、’-'只能作为正负号，但是不可以作为加减号，也就是只能出现在底数和指数的前面，不能出现在两个数字中间；
  5. '.‘只能在底数上，不能在指数上，且只能出现一次，’.‘两边任一边有数字均算一个完整的数字，但单独一个’.'不行。

最后，这个题适合拿去考产品经理，但是考程序员恐怕不太合适。

题目本身就比较难，参考方法三尝试一下。

class Solution {
    public boolean isNumber(String s) {
        /* 最复杂的数字情况：正负号+整数+小数点+整数+e/E+正负号+指数
        整数部分和指数部分都是可有可无的。*/
        if (s == null || s.length == 0) return false; //为空则错误
        //考虑完特殊情况就得被遍历一遍分情况讨论了
        //这里也得用到上一道题的从字符串里识别指定字符的函数
        /*trim() 方法用于删除字符串的头尾空白符，空白符包括：空格、制表符 tab、换行符等其他空白符等。
        trim() 方法不会改变原始字符串。
        trim() 方法不适用于 null, undefined, Number 类型。*/
        s = s.trim();//去掉首位空格
        int n = s.length(), i = 0;  //求得长度
        boolean numF = false; //数字是否有错
        boolean dotF = false; //小数点是否有错
        boolean eF = false; //指数是否有错
        //挨个判断
        for (int i = 0; i < s.length; i++) {
            //判断整数部分 还是用定长循环
            if (s.charAt(i) >= '0' && s.charAt(i) <= '9') numF = true;

            //出现小数部分的话，并且前面没.或e
            else if (s.charAt(i) == '.' && !dotF && !eF) dotF = true;
            //出现指数部分的话，前面得有数字而且不能有e
            else if (s.charAt(i) == 'e' || s.charAt(i) == 'E' && !eF &&numF) {
                eF = true;
                numF = false; //为了避免123e这种请求，出现e之后就标志为false
            }
            //判定为+-符号，只能出现在第一位或者紧接e后面
            else if ((s.charAt(i) == '-' || s.charAt(i) == '+') && (i ==0 || s.charAt(i - 1) == 'e' || s.charAt(i - 1) == 'E')) 
            else {
                return false;
            }
        }
        return numF;
    }
}

这里还以为是别人写的习惯不对，看了说明发现，Java的条件语句就是要把关键词写在上一条的后面，修改后的代码：

class Solution {
    public boolean isNumber(String s) {
        /* 最复杂的数字情况：正负号+整数+小数点+整数+e/E+正负号+指数
        整数部分和指数部分都是可有可无的。*/
        if (s == null || s.length() == 0) return false; //为空则错误
        //考虑完特殊情况就得被遍历一遍分情况讨论了
        //这里也得用到上一道题的从字符串里识别指定字符的函数
        /*trim() 方法用于删除字符串的头尾空白符，空白符包括：空格、制表符 tab、换行符等其他空白符等。
        trim() 方法不会改变原始字符串。
        trim() 方法不适用于 null, undefined, Number 类型。*/
        s = s.trim();//去掉首位空格
        int n = s.length();  //求得长度
        boolean numF = false; //数字是否有错
        boolean dotF = false; //小数点是否有错
        boolean eF = false; //指数是否有错
        //挨个判断
        for (int i = 0; i < n; i++) { //s.length后面必须有()
            //判断整数部分 还是用定长循环
            if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                numF = true;
            } else if (s.charAt(i) == '.' && !dotF && !eF) {
                //出现小数部分的话，并且前面没.或e
                dotF = true;
            } else if ((s.charAt(i) == 'e' || s.charAt(i) == 'E') && !eF &&numF) { //不加括号的话解答错误
                //出现指数部分的话，前面得有数字而且不能有e           
                eF = true;
                numF = false; //为了避免123e这种请求，出现e之后就标志为false
            } else if ((s.charAt(i) == '-' || s.charAt(i) == '+') && (i ==0 || s.charAt(i - 1) == 'e' || s.charAt(i - 1) == 'E')) {
                //判定为+-符号，只能出现在第一位或者紧接e后面
            } else {
                return false;
            }
        }
        return numF;
    }
}

执行结果： 通过

显示详情

执行用时：2 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：38.4 MB, 在所有 Java 提交中击败了68.91%的用户

面试遇到能讲清楚思路就行了，不强求写出答案。

参考方法四转换了常见条件语句的方法。

class Solution {
    public boolean isNumber(String s) {
        /* 最复杂的数字情况：正负号+整数+小数点+整数+e/E+正负号+指数
        整数部分和指数部分都是可有可无的。*/
        if (s == null || s.length() == 0) return false; //为空则错误
        //考虑完特殊情况就得被遍历一遍分情况讨论了
        //这里也得用到上一道题的从字符串里识别指定字符的函数
        /*trim() 方法用于删除字符串的头尾空白符，空白符包括：空格、制表符 tab、换行符等其他空白符等。
        trim() 方法不会改变原始字符串。
        trim() 方法不适用于 null, undefined, Number 类型。*/
        s = s.trim();//去掉首位空格
        int n = s.length();  //求得长度
        boolean numF = false; //数字是否有错
        boolean dotF = false; //小数点是否有错
        boolean eF = false; //指数是否有错
        //挨个判断
        for (int i = 0; i < n; i++) { //s.length后面必须有()
            //判断整数部分 还是用定长循环
            if (s.charAt(i) >= '0' && s.charAt(i) <= '9') numF = true;
            else if (s.charAt(i) == '.' && !dotF && !eF) dotF = true;
            //出现小数部分的话，并且前面没.或e 
            else if ((s.charAt(i) == 'e' || s.charAt(i) == 'E') && !eF &&numF) { //不加括号的话解答错误
                //出现指数部分的话，前面得有数字而且不能有e           
                eF = true;
                numF = false; //为了避免123e这种请求，出现e之后就标志为false
            } 
            else if ((s.charAt(i) == '-' || s.charAt(i) == '+') && (i ==0 || s.charAt(i - 1) == 'e' || s.charAt(i - 1) == 'E')) {
                //判定为+-符号，只能出现在第一位或者紧接e后面
            } 
            else return false;
        }
        return numF;
    }
}

效果反而更好了 接近双百

执行结果： 通过

显示详情

执行用时：2 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗：38.3 MB, 在所有 Java 提交中击败了90.22%的用户

学习他人：

方法一:

罗马仲夏 （编辑过）2020-12-10

正则搞定，收工。

class Solution {
    public boolean isNumber(String s) {
        s = s.trim();
        String regex = "\\s*|([+-]?\\.?[eE][\\s\\S]*)|([+-]?\\.)";
        if (s.matches(regex)) return false;
        regex = "(([+-])?\\d*\\.?\\d*)([eE][+-]?\\d+)?";
        return s.matches(regex);
    }
}

方法二：

啊哈哈哈哈哈 2020-02-25

抖机灵python版本：

class Solution:
    def isNumber(self, s):
        try:
            float(s)
            return True
        except ValueError:
            return False

方法三：

恩L1

（编辑过）2020-06-25

Java 双100%

编码没什么难度，难点在于归纳各种正确的情况

‘.’出现正确情况：只出现一次，且在e的前面

‘e’出现正确情况：只出现一次，且出现前有数字

‘+’‘-’出现正确情况：只能在开头和e后一位

class Solution {
    public boolean isNumber(String s) {
        if (s == null || s.length() == 0) return false;
        //去掉首位空格
        s = s.trim();
        boolean numFlag = false;
        boolean dotFlag = false;
        boolean eFlag = false;
        for (int i = 0; i < s.length(); i++) {
            //判定为数字，则标记numFlag
            if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                numFlag = true;
                //判定为.  需要没出现过.并且没出现过e
            } else if (s.charAt(i) == '.' && !dotFlag && !eFlag) {
                dotFlag = true;
                //判定为e，需要没出现过e，并且出过数字了
            } else if ((s.charAt(i) == 'e' || s.charAt(i) == 'E') && !eFlag && numFlag) {
                eFlag = true;
                numFlag = false;//为了避免123e这种请求，出现e之后就标志为false
                //判定为+-符号，只能出现在第一位或者紧接e后面
            } else if ((s.charAt(i) == '+' || s.charAt(i) == '-') && (i == 0 || s.charAt(i - 1) == 'e' || s.charAt(i - 1) == 'E')) {

                //其他情况，都是非法的
            } else {
                return false;
            }
        }
        return numFlag;
    }
}

方法四：

和方法三差不多，并没有用那种强制的条件判断语法，也能通过

夜尽天明…L1 （编辑过）2020-07-29

大佬，个人感觉还是常规思路好理解= =，直接逐位遍历一遍，并做好标记

class Solution {
    public boolean isNumber(String s) {
        if(s == null || s.length() == 0) return false; // s为空对象或 s长度为0(空字符串)时, 不能表示数值
        boolean isNum = false, isDot = false, ise_or_E = false; // 标记是否遇到数位、小数点、‘e’或'E'
        char[] str = s.trim().toCharArray();  // 删除字符串头尾的空格，转为字符数组，方便遍历判断每个字符
        for(int i=0; i<str.length; i++) {
            if(str[i] >= '0' && str[i] <= '9') isNum = true; // 判断当前字符是否为 0~9 的数位
            else if(str[i] == '.') { // 遇到小数点
                if(isDot || ise_or_E) return false; // 小数点之前可以没有整数，但是不能重复出现小数点、或出现‘e’、'E'
                isDot = true; // 标记已经遇到小数点
            }
            else if(str[i] == 'e' || str[i] == 'E') { // 遇到‘e’或'E'
                if(!isNum || ise_or_E) return false; // ‘e’或'E'前面必须有整数，且前面不能重复出现‘e’或'E'
                ise_or_E = true; // 标记已经遇到‘e’或'E'
                isNum = false; // 重置isNum，因为‘e’或'E'之后也必须接上整数，防止出现 123e或者123e+的非法情况
            }
            else if(str[i] == '-' ||str[i] == '+') { 
                if(i!=0 && str[i-1] != 'e' && str[i-1] != 'E') return false; // 正负号只可能出现在第一个位置，或者出现在‘e’或'E'的后面一个位置
            }
            else return false; // 其它情况均为不合法字符
        }
        return isNum;
    }
}

方法五

K神，作者：jyd
链接：https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/solution/mian-shi-ti-20-biao-shi-shu-zhi-de-zi-fu-chuan-y-2/
来源：力扣（LeetCode）

状态定义：

按照字符串从左到右的顺序，定义以下 9 种状态。

  1. 开始的空格
  2. 幂符号前的正负号
  3. 小数点前的数字
  4. 小数点、小数点后的数字
  5. 当小数点前为空格时，小数点、小数点后的数字
  6. 幂符号
  7. 幂符号后的正负号
  8. 幂符号后的数字
  9. 结尾的空格

【剑指Offer】个人学习笔记_20_表示数值的字符串

Java 的状态转移表 statesstate**s 使用 Map[]Map[] 数组存储。


class Solution {
    public boolean isNumber(String s) {
        Map[] states = {
            new HashMap<>() {{ put(' ', 0); put('s', 1); put('d', 2); put('.', 4); }}, // 0.
            new HashMap<>() {{ put('d', 2); put('.', 4); }},                           // 1.
            new HashMap<>() {{ put('d', 2); put('.', 3); put('e', 5); put(' ', 8); }}, // 2.
            new HashMap<>() {{ put('d', 3); put('e', 5); put(' ', 8); }},              // 3.
            new HashMap<>() {{ put('d', 3); }},                                        // 4.
            new HashMap<>() {{ put('s', 6); put('d', 7); }},                           // 5.
            new HashMap<>() {{ put('d', 7); }},                                        // 6.
            new HashMap<>() {{ put('d', 7); put(' ', 8); }},                           // 7.
            new HashMap<>() {{ put(' ', 8); }}                                         // 8.
        };
        int p = 0;
        char t;
        for(char c : s.toCharArray()) {
            if(c >= '0' && c <= '9') t = 'd';
            else if(c == '+' || c == '-') t = 's';
            else if(c == 'e' || c == 'E') t = 'e';
            else if(c == '.' || c == ' ') t = c;
            else t = '?';
            if(!states[p].containsKey(t)) return false;
            p = (int)states[p].get(t);
        }
        return p == 2 || p == 3 || p == 7 || p == 8;
    }
}

总结

以上就是本题的内容和学习过程了，还是普通解法比较实用一点，值得注意的是Java条件语句的写法，要养成良好的编程习惯。

欢迎讨论，共同进步。

上一篇：leetcode5962. 连接两字母单词得到的最长回文串(mid)(69双周赛)


下一篇：LightProxy 全能代理抓包工具