题解 | #表示数值的字符串#采用递归法实现,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);