有效数字
难度:
标签:
题目描述
English description is not available for the problem. Please switch to Chinese.
代码结果
运行时间: 404 ms, 内存: 15 MB
/*
* 思路:
* 使用Java Stream进行同样的操作。
* 将字符串首尾空格去除后转换为字符流,使用过滤器和映射操作判断每个字符的合法性。
* 通过所有字符的判断结果最终确定字符串是否为有效数字。
*/
import java.util.stream.Stream;
public class Solution {
public boolean isNumber(String s) {
s = s.trim();
boolean[] hasE = {false};
boolean[] hasDot = {false};
boolean[] numberSeen = {false};
boolean[] numberAfterE = {true};
int n = s.length();
return Stream.iterate(0, i -> i + 1).limit(n).allMatch(i -> {
char c = s.charAt(i);
if (c >= '0' && c <= '9') {
numberSeen[0] = true;
numberAfterE[0] = true;
return true;
} else if (c == '.') {
if (hasDot[0] || hasE[0]) return false;
hasDot[0] = true;
return true;
} else if (c == 'e' || c == 'E') {
if (hasE[0] || !numberSeen[0]) return false;
hasE[0] = true;
numberAfterE[0] = false;
return true;
} else if (c == '+' || c == '-') {
if (i != 0 && s.charAt(i - 1) != 'e' && s.charAt(i - 1) != 'E') return false;
return true;
} else {
return false;
}
}) && numberSeen[0] && numberAfterE[0];
}
}
解释
方法:
该题解使用了有限状态自动机(Finite State Machine, FSM)的方法来解决问题。首先,定义了不同的状态(State)和字符类型(CharType)。然后,根据题目给出的有效数字的定义,构建了状态转移图,其中包含了各个状态下对应字符类型的下一个状态。最后,遍历输入字符串,根据当前字符的类型和当前状态,进行状态转移,如果遇到非法字符或者无法转移的状态,则返回false。最终,如果字符串遍历完成后,状态机处于接受状态(即整数、小数、指数部分的数字、或者末尾空格状态),则返回true,表示字符串是一个有效数字。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么有限状态自动机(FSM)是处理这类字符串验证问题的合适选择?
▷🦆
在构建状态转移图时,如何确定包括所有必要的状态和转移?有没有可能遗漏某些状态转移?
▷🦆
状态`STATE_POINT_WITHOUT_INT`表示什么意义,它与`STATE_POINT`状态有什么不同?
▷🦆
如果输入字符串以空格结尾,状态机如何确保最终状态是有效的?
▷