微信公众号：路人zhang
扫码关注微信公众号

回复“面试手册”，获取本站PDF版

回复“简历”，获取高质量简历模板

回复“加群”，加入程序员交流群

回复“电子书”，获取程序员类电子书

当前位置： 算法 > 剑指offer > 剑指offer 20.表示数值的字符串

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

题目描述

请实现一个函数用来判断字符串是否表示 数值 （包括整数和小数）。

数值 （按顺序）可以分成以下几个部分：

  1. 若干空格
  2. 一个  小数  或者  整数
  3. （可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个  整数
  4. 若干空格

小数 （按顺序）可以分成以下几个部分：

  1. （可选）一个符号字符（’+’ 或 ‘-‘）
  2. 下述格式之一：
    1. 至少一位数字，后面跟着一个点 ‘.’
    2. 至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字
    3. 一个点 ‘.’ ，后面跟着至少一位数字

整数 （按顺序）可以分成以下几个部分：

  1. （可选）一个符号字符（’+’ 或 ‘-‘）
  2. 至少一位数字

部分 数值 列举如下：

  • ["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]​

部分 非数值 列举如下：

  • ["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]​

示例 1：

输入：s = "0"
输出：true

示例 2：

输入：s = "e"
输出：false

示例 3：

输入：s = "."
输出：false

示例 4：

输入：s = "    .1  "
输出：true

提示：

  • 1 <= s.length <= 20
  • s 仅含英文字母（大写和小写），数字（0-9），加号 ‘+’ ，减号 ‘-‘ ，空格 ‘ ‘ 或者点 ‘.’ 。

算法

(模拟) O(n)

算法步骤：

  1. 先去除行首和行尾空格；
  2. 行首如果有一个正负号，直接忽略；
  3. 如果字符串为空或只有一个’.’，则不是一个合法数；
  4. 循环整个字符串，去掉以下几种情况： (1) ‘.’或’e’多于1个; (2) ‘.’在’e’后面出现； (3) ‘e’后面或前面为空，或者’e’前面紧跟着’.’； (4) ‘e’后面紧跟着正负号，但正负号后面为空；
  5. 剩下的情况都合法；

时间复杂度

O(n)

空间复杂度

O(1)

C++ 代码

class Solution {
public:
    bool isNumber(string s) {
        /* 1. 去前后空格 */
        // 去掉前空格
        int i = 0;
        while (i < s.size() && s[i] == ' ') i ++;
        // 去掉前后空格
        int j = s.size() - 1;
        while (j >= 0 && s[j] == ' ') j -- ;
        // 删完空格后字符串不合法
        if (i > j) return false;
        s = s.substr(i, j - i + 1);

        /* 2. 行首如果有一个正负号直接忽略 */
        if (s[0] == '+' || s[0] == '-') s = s.substr(1);
        /* 3. 如果字符串为空，或者只有一个 .，则不是一个合法数 */
        if (s.empty() || s[0] == '.' && s.size() == 1) return false; // +, -, .

        /* 4. 循环整个字符串，去掉以下几种情况：
        (1) '.'或'e'多于1个;
        (2) '.'在'e'后面出现；
        (3) 'e'后面或前面为空，或者'e'前面紧跟着'.'；
        (4) 'e'后面紧跟着正负号，但正负号后面为空； */
        // 字符串中点和 e 的数量
        int dot = 0, e = 0;
        for (int i = 0; i < s.size(); i ++ )
        {
            if (s[i] >= '0' && s[i] <= '9') ;
            else if (s[i] == '.')
            {
                dot ++ ;
                if (e || dot > 1) return false; // 21.1.1.2, 12e122.22
            }
            else if (s[i] == 'e' || s[i] == 'E') 
            {
                e ++ ;
                if (i + 1 == s.size() || !i || e > 1 || i == 1 && s[0] == '.') return false;
                if (s[i + 1] == '+' || s[i + 1] == '-')
                {
                    if (i + 2 == s.size()) return false; // 122e+ 或 122e-
                    i ++ ;
                }
            }
            // 不合法的字符就直接返回 false
            else return false;
        }

        /* 5. 其余情况都合法 */
        return true;
    }
};

Java 代码

public class Solution {
    public boolean isNumber(String s) {
        /* 1. 去前后空格 */
        // 去掉前空格
        int i = 0;
        while (i < s.length() && s.charAt(i) == ' ') i ++ ;
        // 去掉前后空格
        int j = s.length() - 1;
        while (j >= 0 && s.charAt(j) == ' ') j -- ;
        // 删完空格后字符串不合法
        if (i > j) return false;
        s = s.substring(i, j + 1);

        /* 2. 行首如果有一个正负号直接忽略 */
        if (s.charAt(0) == '+' || s.charAt(0) == '-') s = s.substring(1);
        /* 3. 如果字符串为空，或者只有一个 .，则不是一个合法数 */
        if (s.isEmpty() || (s.charAt(0) == '.' && s.length() == 1)) return false; // +, -, .

        /* 4. 循环整个字符串，去掉以下几种情况：
        (1) '.'或'e'多于1个;
        (2) '.'在'e'后面出现；
        (3) 'e'后面或前面为空，或者'e'前面紧跟着'.'；
        (4) 'e'后面紧跟着正负号，但正负号后面为空； */
        // 字符串中点和 e 的数量
        int dot = 0, e = 0;
        for (i = 0; i < s.length(); i ++ )
        {
            if (s.charAt(i) >= '0' && s.charAt(i) <= '9') ;
            else if (s.charAt(i) == '.')
            {
                dot ++ ;
                if (e > 0 || dot > 1) return false; // 21.1.1.2, 12e122.22
            }
            else if (s.charAt(i) == 'e' || s.charAt(i) == 'E')
            {
                e ++ ;
                if (i + 1 == s.length() || i == 0 || e > 1 || (i == 1 && s.charAt(0) == '.')) return false;
                if (s.charAt(i + 1) == '+' || s.charAt(i + 1) == '-')
                {
                    if (i + 2 == s.length()) return false; // 122e+ 或 122e-
                    i ++ ;
                }
            }
            // 不合法的字符就直接返回 false
            else return false;
        }

        /* 5. 其余情况都合法 */
        return true;
    }
}

Python 代码

class Solution:
    def isNumber(self, s: str) -> bool:
        # 1. 去前后空格
        i = 0
        while i < len(s) and s[i] == ' ':
            i += 1
        j = len(s) - 1
        while j >= 0 and s[j] == ' ':
            j -= 1
        if i > j:
            return False
        s = s[i:j+1]

        # 2. 行首如果有一个正负号直接忽略
        if s[0] == '+' or s[0] == '-':
            s = s[1:]
        
        # 3. 如果字符串为空，或者只有一个 .，则不是一个合法数
        if not s or (s[0] == '.' and len(s) == 1):
            return False
        
        dot = 0
        e = 0
        i = 0
        while i < len(s):
            c = s[i]
            if '0' <= c <= '9':
                i += 1
            elif c == '.':
                dot += 1
                if e or dot > 1:
                    return False  # 21.1.1.2, 12e122.22
                i += 1
            elif c == 'e' or c == 'E':
                e += 1
                if i + 1 == len(s) or i == 0 or e > 1 or (i == 1 and s[0] == '.'):
                    return False
                if s[i + 1] == '+' or s[i + 1] == '-':
                    if i + 2 == len(s):
                        return False  # 122e+ 或 122e-
                    i += 2
                else:
                    i += 1
            else:
                return False  # 不合法的字符就直接返回 false
        
        # 5. 其余情况都合法
        return True

本文由读者提供，Github地址：https://github.com/tonngw

点击面试手册，获取本站面试手册PDF完整版

剑指offer