题解 | #表示数值的字符串#采用递归法实现,T(n)=O(n)
表示数值的字符串
http://www.nowcoder.com/practice/e69148f8528c4039ad89bb2546fd4ff8
思路:
数值主要是整形和浮点型:
首先,字符串中不能包含除数字、小数点、e、E、正负号以外的字符。
第二,分两种情况:
- 整形:首字符可为+、-,除开+、-后其次字符不能为数字外的其他字符。
- 浮点数:
- 小数点形式:小数点前为一个整形、后也为一个整形。
- 科学计数法: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);