目录

剑指Offer之表示数值的字符串

Gsscsd 收录于剑指Offer

2019-04-09 约 1054 字预计阅读 3 分钟次阅读

目录

题目描述：

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

解题思路一：

几个关键点：

1.基本边界 string == NULL || *string == ‘\0’

2.检测是否有符号位(检测第一位)

3.检测除符号位外的第一个有效位，有效位只能是数字或者小数点.

4.检测是否有E或者e，且不能重复出现

5.小数点不能重复出现，E或者e后面不能出现小数点

6.中间的符号位必须出现在E或者e后面

7.数字的合法性，不能是其他字母如‘a’等

设置参数hasPoint、hasEe来判断E、e、小数点是否重复出现

时间复杂度：$O(n), $空间复杂度：$O(1)$.

 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73


class Solution {
public:
bool isNumeric(char* string)
    {
        bool hasPoint = false;
        bool hasEe = false;
        
        // 基本边界
        if(string == NULL || *string == '\0') return false;
        // 检测是否有符号位
        bool isMinus = false;
        if(*string == '-') 
        {
            isMinus = true;
            string++;
        } 
        else if(*string == '+')
        {
            isMinus = false;
            string++;
        }
 
        // 检测第一个数字或者小数点是否存在
        if((*string >= '0' && *string <= '9')) string++;
        if(*string == '.')
        {
            hasPoint = true;
            string++;
        }
        while(*string != '\0') 
        {
            // 是否为E或者e
            if(*string == 'E' || *string == 'e') 
            {
                if(hasEe == true) 
                {
                    return false;
                } 
                else 
                {
                    hasEe = true;
                    string++;
                }
            }
            // 是否为小数点.
            if(*string == '.') 
            {
                if(hasPoint == true) 
                {
                    return false;
                } 
                else 
                {
                    if(hasEe == true) return false;
                    hasPoint = true; 
                    string++;
                }
            } 
            // 是否为符号
            if(*string == '-' || *string == '+') 
            {
                if(hasEe == true) string++;
                else return false;
            }
            // 是否为合法数字
            else if(*string >= '0' && *string <= '9') string++;
            else return false;
        }
 
        // 如果不是所有不合法，则返回true
        return true;
    }
};

解题思路二：

注意表示数值的字符串遵循的规则；在数值之前可能有一个“+”或“-”，接下来是0到9的数位表示数值的整数部分，如果数值是一个小数，那么小数点后面可能会有若干个0到9的数位表示数值的小数部分。如果用科学计数法表示，接下来是一个‘e’或者‘E’，以及紧跟着一个整数（可以有正负号）表示指数。

时间复杂度：$O(n)$,空间复杂度：$O(1)$.

 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
36


 bool isNumeric(char* string)
    {
        if(string==NULL)
            return false;
        if(*string=='+'||*string=='-')
            string++;
        if(*string=='\0')
            return false;
        int dot=0,num=0,nume=0;//分别用来标记小数点、整数部分和e指数是否存在
        while(*string!='\0'){
            if(*string>='0'&&*string<='9')
            {  
                string++;
                num=1;
            }
            else if(*string=='.'){
                if(dot>0||nume>0)
                    return false;
                string++;
                dot=1;
            }
            else if(*string=='e'||*string=='E')
                {
                  if(num==0||nume>0)
                      return false;
                  string++;
                  nume++;
                  if(*string=='+'||*string=='-')
                      string++;
                 if(*string=='\0')
                     return false;
                }
            else
                return false;
        }
        return true;