题解 | #表示数值的字符串#
表示数值的字符串
http://www.nowcoder.com/practice/e69148f8528c4039ad89bb2546fd4ff8
题目的主要信息：
- 实现一个函数判断字符串是否表示数字
- 包括科学记数法的数字：一个整数或小数，后接一个可选的大小写字母e，后接一个可正可负的整数
- 小数，可选的正负号，小数点前后整数任意有一个即可
- 整数，可选的正负号，加上后面的整数
- 字符串可能包含前导、后导空格
举一反三：
学习完本题的思路你可以解决如下题目：
方法一：遍历（推荐使用）
思路：
既然是字符串，那我们使用一个遍历字符串的全局变量作为下标，然后遍历字符串依次检查每个字符，根据字符属于的类型进行判断。
具体做法：
- step 1：先判断空串的情况。
- step 2：遍历字符前面的空格，将下标移到第一个不是空格的位置。遍历字符串后面的空格，将长度限制在最后一个空格。若是长度小于下标，说明全是空格。
- step 3：剩余部分判断，开始找数字，判断是不是一个有符号的整数，优先判断符号，直到遇到非数字停止。
- step 4：如果有小数点，那么开始判断小数点后是不是一个无符号的整数，也是遍历直到遇到非数字为止，出现小数点的话，小数点前和小数点后的数字任意有一即可。
- step 5：若是出现字母e或者E，那么需要判断后面是不是一个有符号的整数，，也是遍历直到遇到非数字为止，e前后都要数字。
- step 6：最后检查下标是不是遍历到了刚刚限制的长度，若是没有，说明后面还有非空格，不符合要求。
图示：
Java实现代码：
import java.util.*;
public class Solution {
//遍历字符串的下标
private int index = 0;
//有符号判断
private boolean integer(String s){
if(index < s.length() && (s.charAt(index) == '-' || s.charAt(index) == '+'))
index++;
return unsigned_integer(s);
}
//无符号数判断
private boolean unsigned_integer(String s){
int temp = index;
while(index < s.length() && (s.charAt(index) >= '0' && s.charAt(index) <= '9'))
index++;
return index > temp;
}
public boolean isNumeric (String str) {
//先判断空串
if(str == null || str.length() == 0)
return false;
//去除前面的空格
while(index < str.length() && str.charAt(index) == ' ')
index++;
int n = str.length() - 1;
//去除字符串后面的空格
while(n >= 0 && str.charAt(n) == ' ')
n--;
//限制的长度比下标1
n++;
//全是空格情况
if(n < index)
return false;
//判断前面的字符是否是有符号的整数
boolean flag = integer(str);
//如果有小数点
if(index < n && str.charAt(index) == '.'){
index++;
//小数点前后有无数字可选
flag = unsigned_integer(str) || flag;
}
//如果有e
if(index < n && (str.charAt(index) == 'e' || str.charAt(index) == 'E')){
index++;
//e后面必须全是整数
flag = flag && integer(str);
}
//是否字符串遍历结束
return flag && (index == n);
}
}
C++实现代码：
class Solution {
public:
//遍历字符串的下标
int index = 0;
//有符号判断
bool integer(string& s){
if(index < s.length() && (s[index] == '-' || s[index] == '+'))
index++;
return unsigned_integer(s);
}
//无符号数判断
bool unsigned_integer(string& s){
int temp = index;
while(index < s.length() && (s[index] >= '0' && s[index] <= '9'))
index++;
return index > temp;
}
bool isNumeric(string str) {
//先判断空串
if(str.length() == 0)
return false;
//去除前面的空格
while(index < str.length() && str[index] == ' ')
index++;
int n = str.length() - 1;
//去除字符串后面的空格
while(n >= 0 && str[n] == ' ')
n--;
//限制的长度比下标1
n++;
//全是空格情况
if(n < index)
return false;
//判断前面的字符是否是有符号的整数
bool flag = integer(str);
//如果有小数点
if(index < n && str[index] == '.'){
index++;
//小数点前后有无数字可选
flag = unsigned_integer(str) || flag;
}
//如果有e
if(index < n && (str[index] == 'e' || str[index] == 'E')){
index++;
//e后面必须全是整数
flag = flag && integer(str);
}
//是否字符串遍历结束
return flag && (index == n);
}
};
Python实现代码：
class Solution:
def __init__(self):
#遍历字符串的下标
self.index = 0
#有符号判断
def integer(self, s: str) -> bool:
if self.index < len(s) and (s[self.index] == '-' or s[self.index] == '+'):
self.index += 1
return self.unsigned_integer(s)
#无符号数判断
def unsigned_integer(self, s: str) -> bool:
temp = self.index
while self.index < len(s) and (s[self.index] >= '0' and s[self.index] <= '9'):
self.index += 1
return self.index > temp
def isNumeric(self , str: str) -> bool:
#先判断空串
if len(str) == 0:
return False
#去除前面的空格
while self.index < len(str) and str[self.index] == ' ':
self.index += 1
n = len(str) - 1
#去除字符串后面的空格
while n >= 0 and str[n] == ' ':
n -= 1
#限制的长度比下标1
n += 1
#全是空格情况
if n < self.index:
return False
#判断前面的字符是否是有符号的整数
flag = self.integer(str)
#如果有小数点
if self.index < n and str[self.index] == '.':
self.index += 1
#小数点前后有无数字可选
flag = self.unsigned_integer(str) or flag
#如果有e
if self.index < n and (str[self.index] == 'e' or str[self.index] == 'E'):
self.index += 1
#e后面必须全是整数
flag = flag and self.integer(str)
#是否字符串遍历结束
return flag and (self.index == n)
复杂度分析：
- 时间复杂度：，其中为字符串长度，最坏遍历字符串每个字符一次
- 空间复杂度：，常数级变量，无额外辅助空间
方法二：正则表达式（扩展思路）
思路：
可以使用正则表示匹配直接匹配字符串是否表示数字。其中C++和Java中使用双斜杠，Python使用单斜杠。
具体做法：
- step 1：用\s表示匹配空格，*表示匹配0个或多个，写在正则表达式首尾。
- step 2：正负号可选，因此使用?匹配正负号。
- step 3：整数用\d匹配，小数点前有无数字可以用|表示：小数点前有数字，匹配小数点，后面的数字可有可无；小数前没有数字，匹配小数点后必须有数字。
- step 4：匹配大小写字母[Ee]，以及后面可有可无的正负号，后面必须匹配一个整数。
Java实现代码：
import java.util.regex.Pattern;
public class Solution {
public boolean isNumeric (String str) {
//正则表达式匹配
String pattern = "(\\s)*[+-]?((\\d+(\\.(\\d+)?)?)|(\\.\\d+))([Ee][+-]?\\d+)?(\\s)*";
//根据匹配值返回
return Pattern.matches(pattern, str);
}
}
C++实现代码：
#include<regex>
class Solution {
public:
bool isNumeric(string str) {
//正则表达式匹配
string pattern = "(\\s)*[+-]?((\\d+(\\.(\\d+)?)?)|(\\.\\d+))([Ee][+-]?\\d+)?(\\s)*";
regex re(pattern);
//根据匹配值返回
return regex_match(str, re);
}
};
Python实现代码：
import re
class Solution:
def isNumeric(self , str: str) -> bool:
#正则表达式匹配
pattern = "^(\s)*[+-]?((\d+(\.(\d+)?)?)|(\.\d+))([Ee][+-]?\d+)?(\s)*$"
#根据匹配值返回
if re.match(pattern, str):
return True
else:
return False
复杂度分析：
- 时间复杂度：，其中为字符串长度，正则表达式最坏遍历每个字符一次
- 空间复杂度：，常数级空间
