Loading...
墨滴

amu

2021/06/20  阅读:78  主题:默认主题

Leetcode: 65.有效数字 (C++解法)

65.有效数字

题目描述

有效数字(按顺序)可以分成以下几个部分:

  1. 一个 小数 或者 整数
  2. (可选)一个 'e' 或 'E' ,后面跟着一个 整数

小数(按顺序)可以分成以下几个部分:

  1. (可选)一个符号字符('+' 或 '-')
  2. 下述格式之一:
  • 至少一位数字,后面跟着一个点 '.'
  • 至少一位数字,后面跟着一个点 '.' ,后面再跟着至少一位数字
  • 一个点 '.' ,后面跟着至少一位数字

整数(按顺序)可以分成以下几个部分:

  1. (可选)一个符号字符('+' 或 '-')
  2. 至少一位数字

部分有效数字列举如下:

["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"]

部分无效数字列举如下:

["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"]

给你一个字符串 s ,如果 s 是一个 有效数字 ,请返回 true 。

=============

https://leetcode-cn.com/problems/valid-number/

思路

状态驱动法

  • 有无e/E分开讨论

  • 有e/E有效数字特征:e/E右边是整数或者+/-整数;e/E左边是整数或者浮点数

  • 无e/E有效数字特征:(+/-)整数或者浮点数,数字至少出现1次

实现:

class Solution {
public:
    bool isNum(char c) {
        if(c<58&&c>47) return true;
        return false;
    }

    bool isValid(string s, int a, int b, int idx) {
        if(a>b) return false;
        if(s[a] == '+' || s[a] == '-') a++;
        bool dot = false;
        bool num = false;
        // 不含e
        if(idx == -1) {
            for(int i=a;i<=b;i++) {
                if(s[i] == '.') {
                    if(dot) {
                        return false;
                    }
                    else {
                        dot = true;
                    }
                }
                else if(!isNum(s[i])) {
                    return false;
                }
                else {
                    num = true;
                }
            }
            return num;
        }
        //e左边
        if(b<idx) {
            for(int i=a;i<=b;i++) {
                if(s[i] == '.') {
                    if(dot) {
                        return false;
                    }
                    else {
                        dot = true;
                    }
                }
                else if(!isNum(s[i])) {
                    return false;
                }
                else {
                    num = true;
                }
            }
            return num;
        }
        // e右边
        else if(b>idx) {
            for(int i=a;i<=b;i++) {
                if(!isNum(s[i])) return false;
                num = true;
            }
        }
        return num;
    }

    bool isNumber(string s) {
        if(s == "."return false;
        int len = s.length();
        int e_idx = -1;
        for(int i=0;i<len;i++) {
            if(s[i] == 'e' || s[i] == 'E') {
                if(e_idx == -1) e_idx = i;
                else return false;
            }
        }
        bool res = true;
        if(e_idx != -1) {
            res &= isValid(s, 0, e_idx-1, e_idx);
            res &= isValid(s, e_idx+1, len-1, e_idx);
        }
        else {
            res &= isValid(s, 0, len-1, -1);
        }
        return res;
    }    
};

amu

2021/06/20  阅读:78  主题:默认主题

作者介绍

amu