leetcode
leetcode 2551 ~ 2600
有效数字

有效数字

难度:

标签:

题目描述

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)是处理这类字符串验证问题的合适选择?
有限状态自动机(FSM)是处理字符串验证问题的合适选择,因为它能够明确地表示和管理不同的输入字符应该导致的状态转换。FSM通过定义一系列的状态和在接收到特定输入时从一个状态到另一个状态的转移,可以清晰地模拟字符串分析的过程。对于复杂的规则,如有效数字的定义,FSM帮助我们组织和实现这些规则,使得每一个转换都是预定义和受控的。这种方法提高了代码的可维护性和扩展性,同时也便于调试和验证。
🦆
在构建状态转移图时,如何确定包括所有必要的状态和转移?有没有可能遗漏某些状态转移?
在构建状态转移图时,首先需要对问题的规则和要求有深刻理解,然后根据这些规则定义状态和可能的字符类型。通过分析每种字符在各个状态下的合法转移,构建状态转移表。为了确保包括所有必要的状态和转移,通常需要仔细考虑所有边界情况和特殊情况。尽管通过细致的规划和测试可以最小化遗漏,但在复杂的系统中完全避免遗漏是具有挑战性的,可能需要多次迭代和测试来发现并修正漏洞。
🦆
状态`STATE_POINT_WITHOUT_INT`表示什么意义,它与`STATE_POINT`状态有什么不同?
`STATE_POINT_WITHOUT_INT`状态表示的是小数点前没有任何数字的情况,比如输入'.123',这种情况下,小数点是输入字符串的首个有效字符。而`STATE_POINT`状态则用于处理小数点后有整数部分的情况,即小数点前已经有数字了,如'123.'。这两个状态的区别在于对小数点前是否存在数字的处理,这反映了有效数字定义中小数的不同表现形式。
🦆
如果输入字符串以空格结尾,状态机如何确保最终状态是有效的?
在状态机的设计中,有一个专门的状态`STATE_END`用于处理字符串末尾的空格。如果输入字符串在经历了有效的数字状态(如整数、小数或指数部分)后遇到空格,状态会转移到`STATE_END`。在`STATE_END`状态下,任何额外的空格字符都会保持在`STATE_END`状态,确保字符串的结尾空格不会影响数字的有效性。最终,如果字符串在完成解析后处于`STATE_END`或其他接受状态,字符串被认为是有效的数字。

相关问题