题解 | #表示数值的字符串#采用递归法实现,T(n)=O(n)

表示数值的字符串

http://www.nowcoder.com/practice/e69148f8528c4039ad89bb2546fd4ff8

思路:

数值主要是整形和浮点型:
首先,字符串中不能包含除数字、小数点、e、E、正负号以外的字符。
第二,分两种情况:

  1. 整形:首字符可为+、-,除开+、-后其次字符不能为数字外的其他字符。
  2. 浮点数:
  • 小数点形式:小数点前为一个整形、后也为一个整形。
  • 科学计数法:e或E之前可为整形或浮点型,后一个为整形。

代码:

class Solution {
public:
    /**
     * 整数和浮点数
     */
    bool isNumeric(string str) {
        return isInteger(str) || isFloat(str);
    }

    bool isInteger(string str){
        if(!str.size()){
            return false;
        }
        // 只有一个元素,但不是数字,则返回false
        if(str.size() == 1 && !isdigit(str[0])){
            return false;
        }
        for(int i = 0; i < str.size(); i++){
            if(str[i] == '+' || str[i] == '-'){
                // 若正负不出现在第一个位置,返回false
                if(i != 0)
                    return false;
            }
            // 除正负外不是数字,返回false
            else if(!isdigit(str[i])){
                return false;
            }
        }
        return true;
    }

    bool isFloat(string str){
        if(!str.size()){
            return false;
        }
        // 整形也是浮点型
        if(isInteger(str) == true){
            return true;
        }
        // 查找分隔位置
        // 先找e/E
        int finded = str.find_first_of("eE");
        if(finded == string::npos){
            // 再找'.'
            finded = str.find_first_of(".");
            if(finded == string::npos){
                return false;
            }
        }

        // 如果是e、E,则需要满足:左边为浮点型,右边为整形
        if(str[finded] == 'e' || str[finded] == 'E'){
            if(!isFloat(string(str.begin(), str.begin() + finded)) || 
               !isInteger(string(str.begin() + finded + 1, str.end()))){
                return false;
            }
        }
        // 如果是'.',则需要满足:左边为整型或'-',右边为整形
        else{
            string temp = string(str.begin(), str.begin() + finded);
            if((temp != "-" && !isInteger(temp)) || 
               !isInteger(string(str.begin() + finded + 1, str.end()))){
                return false;
            }
        }
        return true;
    }
};

分析

T(n)=O(n);S(n)=O(n);

全部评论

相关推荐

oppo 应用软开 22*15+0.5*12
拿到了ssp完美:真的坎坷,但是你至少拿到这么多offer了!
点赞 评论 收藏
分享
贺兰星辰:不要漏个人信息,除了简历模板不太好以外你这个个人简介是不是太夸大了...
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务