题解 | #表示数值的字符串# | 条件判断 | 正则匹配 | 有限状态机 |
表示数值的字符串
http://www.nowcoder.com/practice/e69148f8528c4039ad89bb2546fd4ff8
题目描述
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
示例1
输入： "123.45e+6" 返回值： true
示例2
输入： "1.2.3" 返回值： false
从题已知信息
数值（按顺序）可以分成以下几个部分：
- （空格的情况）若干空格
- （e的情况）只能出现一个 'e' 或 'E' ，后面跟着一个 整数，且e前面必须有数字
- （ . 的情况）. 之前不能出现e，且点只能出现一次
- （+-的情况）+- 出现在0位置或者e/E的后第一个位置
- （数字的情况）至少出现一个数字
方法一: 常规解法，条件判断
思路和算法
题目本身不难，难的是归纳各种情况，我们来把上面几种情况都分析一下
先用3个变量标记一下各种情况
//标记是否出现数字 boolean showNum = false; //标记是否出现点 boolean showDot = false; //标记是否出现E boolean showE = false;
若干空格
s = s.trim();
只能出现一个 'e' 或 'E' ，后面跟着一个 整数，且e前面必须有数字
if (c == 'e' || c == 'E') {
//只能出现一个 'e' 或 'E' ，后面跟着一个 整数，且e前面必须有数字
if (showE || !showNum) {
return false;
}
//标记E出现
showE = true;
} - . 之前不能出现e，且点只能出现一次
//. 之前不能出现e，且点只能出现一次
if (showDot || showE) {
return false;
}
//标记.出现了
showDot = true;
//. 点可以作为结尾， 这里showNum不用变成false 3. = true- +- 出现在0位置或者e/E的后第一个位置
//+- 出现在0位置或者e/E的后第一个位置
if (i != 0 && str.charAt(i - 1) != 'E' && str.charAt(i - 1) != 'e') {
return false;
}- 必须要有数字
//标记出现数字 showNum = true;
全部代码如下：
import java.util.*;
public class Solution {
public boolean isNumeric (String str) {
//1) 若干空格,去掉
str = str.trim();
//标记是否出现数字
boolean showNum = false;
//标记是否出现点
boolean showDot = false;
//标记是否出现E
boolean showE = false;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (c >= '0' && c <= '9') {
//5) 标记出现数字
showNum = true;
} else if (c == 'e' || c == 'E') {
//2) 只能出现一个 'e' 或 'E' ，后面跟着一个 整数，且e前面必须有数字
if (showE || !showNum) {
return false;
}
//标记E出现
showE = true;
//E不能结尾，如12e这样的，在把showNum标记为false
showNum = false;
} else if (c == '.') {
//3) . 之前不能出现e，且点只能出现一次
if (showDot || showE) {
return false;
}
//标记.出现了
showDot = true;
//. 点可以作为结尾， 这里showNum不用变成false 3. = true
} else if (c == '-' || c == '+') {
//4) +- 出现在0位置或者e/E的后第一个位置
if (i != 0 && str.charAt(i - 1) != 'E' && str.charAt(i - 1) != 'e') {
return false;
}
} else {
//其他情况都是false
return false;
}
}
// 5) 至少出现一次数字
return showNum;
}
}复杂度分析
时间复杂度：O(N)，需要遍历每个字符
空间复杂度：O(1)，3个额外变量，常数空空间大小
方法二：正则匹配
正则匹配实现的话，需要对正则比较熟练
思路和算法
- . = 任意字符 除开
\n \d= 数字*= 0次或者多次 =｛0， ｝+= 1次或者多次=｛1， ｝？= 0次或者1次 =｛0，1｝\\= 表示一个\()是为了提取匹配的字符串。表达式中有几个()就有几个相应的匹配字符串。
若干空格
s = s.trim();
只能出现一个 'e' 或 'E' ，后面跟着一个 整数，且e前面必须有数字
//只能出现一个 'e' 或 'E' ，后面跟着一个 整数，且e前面必须有数字 (\\d+|\\d+\\.\\d*|\\.\\d+) // e前面必须有数字 (\\d+[eE][+-]?\\d+) // 后有数字,且 e / +- 只出现一次
. 之前不能出现e，且点只能出现一次
//. 之前不能出现e，且点只能出现一次 \\d+\\.\\d* // 737这样的形式 \\.\\d+ // .7 这样的
+- 出现在0位置或者e/E的后第一个位置
//+- 出现在0位置或者e/E的后第一个位置 [+-]? //出现在0位置,且只能{0,1} [eE][+-]? //e/E的后第一个位置,且只能{0,1}必须要有数字
//标记出现数字 \\d+ // 7 这样的形式 \\d+\\.\\d*|\\.\\d+ // 7.7 这样的形式 \\.\\d+ // .7 这样的形式
综合起来全部代码如下：
import java.util.*;
public class Solution {
public boolean isNumeric (String str) {
return str.matches("[+-]?(\\d+|\\d+\\.\\d*|\\.\\d+)([eE][+-]?\\d+)?");
}
}方法三：有限状态机
有限状态自动机（FSM "finite state machine" 或者FSA "finite state automaton" ）是为研究有限内存的计算过程和某些语言类而抽象出的一种计算模型。有限状态自动机拥有有限数量的状态，每个状态可以迁移到零个或多个状态，输入字串决定执行哪个状态的迁移。有限状态自动机可以表示为一个有向图。有限状态自动机是自动机理论的研究对象。
思路和算法
根据字符类型和合法数值的特点，先确定一个正常数值有那些字符。
字符类型：
- 空格
- 数字
- +-号
- 小数点
- e幂符号
定义状态：
定义状态是比较难的，如何找出所有的状态呢？ 如果按照字符串从左到右的顺序，要穷举出所有的状态，一个符合条件的数字有如下状态
- 前空格
- +-号
- 整数
- 左边有整数的小数点
- 左边没有整数的小数点
- 小数
- e
- e后面的+-
- e后面的数字
- 后空格
对状态进行分析：
将每种可以转移的状态先定义在状态下方(就是每种状态后面可以接什么字符)，以0为开始的下标
- 0)前空格
- 前空格
- +-号
- 左边没有整数的小数点
- 1)+-号
- 整数
- 左边没有整数的小数点
- 2)整数
- 整数
- 左边有整数的小数点
- e
- 后空格
- 3)左边有整数的小数点
- 小数
- e
- 后空格
- 4)左边没有整数的小数点
- 小数
- 5)小数
- 小数
- e
- 后空格
- 6)e
- e后面的+-
- e后面的数字
- 7)e后面的+-
- e后面的数字
- 8)e后面的数字
- e后面的数字
- 后空格
- 9)后空格
- 后空格
整理成图：
状态出口：
状态出口怎么确定？对上面的状态进行分析：
- 0）前空格 // false
- 1）+-号 // false
- 2）整数 // true
- 3）左边有整数的小数点 // true 3. 这样的
- 4）左边没有整数的小数点 // false . 这样的
- 5）小数 // true .3 或者 3.3 都OK
- 6）e // false
- 7）e后面的+- // false
- 8）e后面的数字 // true 3e3
- 9）后空格 // true 上面的状态都是正确的才跳后空格的
可以知道，状态出口有：2，3，5，8，9
进行代码编写
import java.util.*;
public class Solution {
public boolean isNumeric (String str) {
//先定义几个字符
// s = sign = +- 号
// d = 数字
// . = .
// e = e
// 第0种， 前空格
HashMap<Character, Integer> zero = new HashMap<>();
//可以转移的状态
zero.put(' ', 0); // 前空格
zero.put('s', 1); // +-号
zero.put('d', 2); // 整数
zero.put('.', 4); // 左边没有整数的小数点
// 第1种， +-号
HashMap<Character, Integer> one = new HashMap<>();
//可以转移的状态
one.put('d', 2); // 整数
one.put('.', 4); // 左边没有整数的小数点
// 第2种， 整数
HashMap<Character, Integer> two = new HashMap<>();
//可以转移的状态
two.put('d', 2); // 整数
two.put('.', 3); // 左边有整数的小数点
two.put('e', 6); // e
two.put(' ', 9); // 后空格
// 第3种， 左边有整数的小数点
HashMap<Character, Integer> three = new HashMap<>();
//可以转移的状态
three.put('d', 5); // 小数
three.put('e', 6); // e
three.put(' ', 9); // 后空格
// 第4种， 左边没有整数的小数点
HashMap<Character, Integer> four = new HashMap<>();
//可以转移的状态
four.put('d', 5); // 小数
// 第5种， 小数
HashMap<Character, Integer> five = new HashMap<>();
//可以转移的状态
five.put('d', 5); // 小数
five.put('e', 6); // e
five.put(' ', 9); // 后空格
// 第6种， e
HashMap<Character, Integer> six = new HashMap<>();
//可以转移的状态
six.put('s', 7); // e后面的+-
six.put('d', 8); // e后面的数字
// 第7种，e后面的+-
HashMap<Character, Integer> seven = new HashMap<>();
//可以转移的状态
seven.put('d', 8); // e后面的数字
// 第8种，e后面的数字
HashMap<Character, Integer> eight = new HashMap<>();
//可以转移的状态
eight.put('d', 8); // e后面的数字
eight.put(' ', 9); // 后空格
// 第9种，后空格
HashMap<Character, Integer> nine = new HashMap<>();
//可以转移的状态
nine.put(' ', 9); // 后空格
//先定义一个状态数组 用来标识上面10种状态
HashMap[] states = {zero, one, two, three, four, five, six, seven, eight, nine};
int index = 0;
char key;
for (char c : str.toCharArray()) {
if (c >= '0' && c <= '9') {
key = 'd';
} else if (c == '+' || c == '-') {
key = 's';
} else if (c == 'e' || c == 'E') {
key = 'e';
} else if (c == '.' || c == ' ') {
key = c;
} else {
key = '?';
}
if (!states[index].containsKey(key)) {
return false;
}
index = (int) states[index].get(key);
}
//合法的结束状态
return index == 2 || index == 3 || index == 5 || index == 8 || index == 9;
}
}复杂度分析
时间复杂度：O(n)，其中 n 为字符串的长度。我们需要遍历字符串的每个字符
空间复杂度：O(1)。固定大小的状态转移表。