53 剑指offer--字符串--表示数值的字符串
表示数值的字符串
题目
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
思路
这道题还是比较简单的。表示数值的字符串遵循如下模式：
[sign]integral-digits[.[fractional-digits]][e|E[sign]exponential-digits]
其中，('['和']'之间的为可有可无的部分)。
在数值之前可能有一个表示正负的'+'或者'-'。接下来是若干个0到9的数位表示数值的整数部分（在某些小数里可能没有数值的整数部分）。如果数值是一个小数，那么在小数后面可能会有若干个0到9的数位表示数值的小数部分。如果数值用科学记数法表示，接下来是一个'e'或者'E'，以及紧跟着的一个整数（可以有正负号）表示指数。
判断一个字符串是否符合上述模式时，首先看第一个字符是不是正负号。如果是，在字符串上移动一个字符，继续扫描剩余的字符串中0到9的数位。如果是一个小数，则将遇到小数点。另外，如果是用科学记数法表示的数值，在整数或者小数的后面还有可能遇到'e'或者'E'。
LeetCode
验证给定的字符串是否可以解释为十进制数字。
例如:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
" -90e3 " => true
" 1e" => false
"e3" => false
" 6e-1" => true
" 99e2.5 " => false
"53.5e93" => true
" --6 " => false
"-+3" => false
"95a54e53" => false
说明: 我们有意将问题陈述地比较模糊。在实现代码之前，你应当事先思考所有可能的情况。这里给出一份可能存在于有效十进制数字中的字符列表：
数字 0-9
指数 - "e"
正/负号 - "+"/"-"
小数点 - "."
当然，在输入中，这些字符的上下文也很重要。
代码
自己牛客网通过的代码
public class Solution {
public boolean isNumeric(char[] str) {
if(str == null || str.length ==0){
return false;
}
boolean hasnumber = false;
//是否有数字
boolean hasE = false;
//是否有e
boolean hasPoint = false;
for(int i = 0;i<str.length;i++){
if(str[i]-'0' >=0 && str[i]-'0' <=9){
hasnumber = true;
}else if(str[i] =='.'){
if(hasPoint || hasE){
return false;
}else{
hasPoint = true;
}
}else if(str[i] == 'e' || str[i] =='E'){
if(hasE || !hasnumber || i==str.length-1){
return false;
}else{
hasE = true;
}
}else if(str[i] =='+' ||str[i] =='-'){
if(i !=0 && (str[i-1] != 'e' && str[i-1] !='E')){
return false;
}
}else{
return false;
}
}
return true;
}
}
public boolean isNumeric(char[] str) {
boolean isNumber = false;
boolean isHasE = false;
boolean ishaspoint = false;
boolean isAddSub = false;
for(int i = 0;i < str.length;i++){
if(str[i] == '+' || str[i] == '-'){
if(i !=0 && !isHasE){
return false;
}
}else if(str[i]>='0' && str[i] <='9'){
isNumber =true;
}else if(str[i] =='.'){
if(ishaspoint || isHasE){
return false;
}
ishaspoint = true;
}else if(str[i] =='e' || str[i]=='E'){
if(!isNumber || i==str.length-1 ||isHasE){
return false;
}
isHasE = true;
}else{
return false;
}
}
return true;
}1 正则
class Solution {
public boolean isNumber(String s) {
boolean flag1=s.matches("(\\s)*[+-]?[0-9]+(\\.[0-9]*)?([eE][+-]?[0-9]+)?(\\s)*");//存在整数部分时，可以没有小数部分
boolean flag2=s.matches("(\\s)*[+-]?[0-9]*(\\.[0-9]+)([eE][+-]?[0-9]+)?(\\s)*");//可以没有整数部分,此时必须有小数部分
return flag1 || flag2;
}
}
2 有限状态机（DFA）1
本题可以采用《编译原理》里面的确定的有限状态机（DFA）解决。构造一个DFA并实现，构造方法可以先写正则表达式，然后转为 DFA，也可以直接写，我就是直接写的，虽然大概率不会是最简结构（具体请参考《编译器原理》图灵出版社），不过不影响解题。DFA 作为确定的有限状态机，比 NFA 更加实用，因为对于每一个状态接收的下一个字符，DFA 能确定唯一一条转换路径，所以使用简单的表驱动的一些方法就可以实现，并且只需要读一遍输入流，比起 NFA 需要回读在速度上会有所提升。
构建出来的状态机如封面图片所示（红色为 终止状态，蓝色为 中间状态）。根据《编译原理》的解释，DFA 从状态 0 接受串 s 作为输入。当s耗尽的时候如果当前状态处于中间状态，则拒绝；如果到达终止状态，则接受。
然后，根据 DFA 列出如下的状态跳转表，之后我们就可以采用 表驱动法 进行编程实现了。需要注意的是，这里面多了一个状态 8，是用于处理串后面的若干个多余空格的。所以，所有的终止态都要跟上一个状态 8。其中，有一些状态标识为-1，是表示遇到了一些意外的字符，可以直接停止后续的计算。状态跳转表如下：
class Solution {
public int make(char c) {
switch(c) {
case ' ': return 0;
case '+':
case '-': return 1;
case '.': return 3;
case 'e': return 4;
default:
if(c >= 48 && c <= 57) return 2;
}
return -1;
}
public boolean isNumber(String s) {
int state = 0;
int finals = 0b101101000;
int[][] transfer = new int[][]{
{ 0, 1, 6, 2,-1},
{-1,-1, 6, 2,-1},
{-1,-1, 3,-1,-1},
{ 8,-1, 3,-1, 4},
{-1, 7, 5,-1,-1},
{ 8,-1, 5,-1,-1},
{ 8,-1, 6, 3, 4},
{-1,-1, 5,-1,-1},
{ 8,-1,-1,-1,-1}};
char[] ss = s.toCharArray();
for(int i=0; i < ss.length; ++i) {
int id = make(ss[i]);
if (id < 0) return false;
state = transfer[state][id];
if (state < 0) return false;
}
return (finals & (1 << state)) > 0;
}
}
3 有限状态机（DFA）2
这种题目，采用的都是有限自动机的方法，要是依靠蛮力直接去写if语句，可能要写的吐血
注意：leetcode这道题有些特殊的case不太容易想到。比如："3.e10"这个是合法的，但是".e10"是不合法的。另外"3."是合法的。此外，还要最出现在首尾的空格进行剔除。
状态机状态转移图
4 直接法
public boolean isNumber(String s) {
s = s.trim();
boolean pointSeen = false;
//前面有没有 .
boolean eSeen = false;
//前面有没有E e
boolean numberSeen = false;
//前面是否数字
boolean numberAfterE = true;
//e不能结尾
for(int i=0; i<s.length(); i++) {
if('0' <= s.charAt(i) && s.charAt(i) <= '9') {
numberSeen = true;
numberAfterE = true;
} else if(s.charAt(i) == '.') {
if(eSeen || pointSeen) {
//如果前面存在e或者已经有 .了 --- 报错
return false;
}
pointSeen = true;
} else if(s.charAt(i) == 'e') {
if(eSeen || !numberSeen) {
//如果前面已经有e E或者是前面没有数字 --- 报错
return false;
}
numberAfterE = false;
eSeen = true;
} else if(s.charAt(i) == '-' || s.charAt(i) == '+') {
//如果是 + 或者是 - 的话 它不是第一个或者不是在e 的后面 --- 报错
if(i != 0 && s.charAt(i-1) != 'e') {
return false;
}
} else {
//以上全不是报错
return false;
}
}
return numberSeen && numberAfterE;
//这俩个是必须的
}5 责任链模式
这里作者提出来，利用责任链的设计模式，会使得写出的算法扩展性以及维护性更高。这里用到的思想就是，每个类只判断一种类型。比如判断是否是正数的类，判断是否是小数的类，判断是否是科学计数法的类，这样每个类只关心自己的部分，出了问题很好排查，而且互不影响。
//每个类都实现这个接口
interface NumberValidate {
boolean validate(String s);
}
//定义一个抽象类，用来检查一些基础的操作，是否为空，去掉首尾空格，去掉 +/-
//doValidate 交给子类自己去实现
abstract class NumberValidateTemplate implements NumberValidate{
public boolean validate(String s)
{
if (checkStringEmpty(s))
{
return false;
}
s = checkAndProcessHeader(s);
if (s.length() == 0)
{
return false;
}
return doValidate(s);
}
private boolean checkStringEmpty(String s)
{
if (s.equals(""))
{
return true;
}
return false;
}
private String checkAndProcessHeader(String value)
{
value = value.trim();
if (value.startsWith("+") || value.startsWith("-"))
{
value = value.substring(1);
}
return value;
}
protected abstract boolean doValidate(String s);
}
//实现 doValidate 判断是否是整数
class IntegerValidate extends NumberValidateTemplate{
protected boolean doValidate(String integer)
{
for (int i = 0; i < integer.length(); i++)
{
if(Character.isDigit(integer.charAt(i)) == false)
{
return false;
}
}
return true;
}
}
//实现 doValidate 判断是否是科学计数法
class SienceFormatValidate extends NumberValidateTemplate{
protected boolean doValidate(String s)
{
s = s.toLowerCase();
int pos = s.indexOf("e");
if (pos == -1)
{
return false;
}
if (s.length() == 1)
{
return false;
}
String first = s.substring(0, pos);
String second = s.substring(pos+1, s.length());
if (validatePartBeforeE(first) == false || validatePartAfterE(second) == false)
{
return false;
}
return true;
}
private boolean validatePartBeforeE(String first)
{
if (first.equals("") == true)
{
return false;
}
if (checkHeadAndEndForSpace(first) == false)
{
return false;
}
NumberValidate integerValidate = new IntegerValidate();
NumberValidate floatValidate = new FloatValidate();
if (integerValidate.validate(first) == false && floatValidate.validate(first) == false)
{
return false;
}
return true;
}
private boolean checkHeadAndEndForSpace(String part)
{
if (part.startsWith(" ") ||
part.endsWith(" "))
{
return false;
}
return true;
}
private boolean validatePartAfterE(String second)
{
if (second.equals("") == true)
{
return false;
}
if (checkHeadAndEndForSpace(second) == false)
{
return false;
}
NumberValidate integerValidate = new IntegerValidate();
if (integerValidate.validate(second) == false)
{
return false;
}
return true;
}
}
//实现 doValidate 判断是否是小数
class FloatValidate extends NumberValidateTemplate{
protected boolean doValidate(String floatVal)
{
int pos = floatVal.indexOf(".");
if (pos == -1)
{
return false;
}
if (floatVal.length() == 1)
{
return false;
}
NumberValidate nv = new IntegerValidate();
String first = floatVal.substring(0, pos);
String second = floatVal.substring(pos + 1, floatVal.length());
if (checkFirstPart(first) == true && checkFirstPart(second) == true)
{
return true;
}
return false;
}
private boolean checkFirstPart(String first)
{
if (first.equals("") == false && checkPart(first) == false)
{
return false;
}
return true;
}
private boolean checkPart(String part)
{
if (Character.isDigit(part.charAt(0)) == false ||
Character.isDigit(part.charAt(part.length() - 1)) == false)
{
return false;
}
NumberValidate nv = new IntegerValidate();
if (nv.validate(part) == false)
{
return false;
}
return true;
}
}
//定义一个执行者，我们把之前实现的各个类加到一个数组里，然后依次调用
class NumberValidator implements NumberValidate {
private ArrayList<NumberValidate> validators = new ArrayList<NumberValidate>();
public NumberValidator()
{
addValidators();
}
private void addValidators()
{
NumberValidate nv = new IntegerValidate();
validators.add(nv);
nv = new FloatValidate();
validators.add(nv);
nv = new HexValidate();
validators.add(nv);
nv = new SienceFormatValidate();
validators.add(nv);
}
@Override
public boolean validate(String s)
{
for (NumberValidate nv : validators)
{
if (nv.validate(s) == true)
{
return true;
}
}
return false;
}
}
public boolean isNumber(String s) {
NumberValidate nv = new NumberValidator();
return nv.validate(s);
}
查看9道真题和解析
投递华为等公司10个岗位 >