首页 > 其他分享 >LeetCode:65.有效数字

LeetCode:65.有效数字

时间:2025-01-12 22:10:43浏览次数:9  
标签:状态 digit 遍历 字符 有效数字 -- 65 字符串 LeetCode

LeetCode:65.有效数字

解题步骤构建一个表示状态的图。遍历字符串,并沿着图走,如果到了某个节点无路可走就返false。遍历结束,如走到3/5/6,就返回true,否则返回false。

extend 2 8 10 16进制

/**
 * 检查一个字符串是否可以表示为一个有效的数字
 * @param {string} s - 待检查的字符串
 * @returns {boolean} - 如果字符串是有效的数字表示,则返回true;否则返回false
 */
var isNumber = function(s) {
    // 状态转换图,定义了字符串中每个字符类型在不同状态下如何转换状态
    const graph = {
        0: {'blank': 0, 'sign': 1, '.': 2, 'digit': 6},
        1: {'digit': 6, '.': 2},
        2: {'digit': 3},
        3: {'digit': 3, 'e': 4},
        4: {'digit': 5, 'sign': 7},
        5: {'digit': 5},
        6: {'digit': 6, '.': 3, 'e': 4},
        7: {'digit': 5}
    };
    
    // 初始化状态为0
    let state = 0;
    
    // 遍历字符串中的每个字符,去除首尾空格
    for (let c of s.trim()) {
        // 将字符分类为digit、blank、.、e、sign
        if (c >= '0' && c <= '9') {
            c = 'digit';
        } else if (c === ' ') {
            c = 'blank';
        } else if (c === '.') {
            c = '.';
        } else if (c === 'e' || c === 'E') {
            c = 'e';
        } else if (c === '+' || c === '-') {
            c = 'sign';
        }
        
        // 根据当前状态和字符类型转换到下一个状态
        state = graph[state][c];
        
        // 如果转换结果为undefined,说明字符串不是有效的数字表示
        if (state === undefined) {
            return false;
        }
    }
    
    // 如果最终状态是3、5或6,则字符串是有效的数字表示
    return state === 3 || state === 5 || state === 6;
};

// 示例:检查字符串"1E9"是否是有效的数字表示
console.log(isNumber("1E9"));

代码功能详细解释

这段 JavaScript 代码的功能是判断给定的字符串是否表示一个有效的数字。它使用有限状态机(FSM)来处理字符串中的每个字符,并根据预定义的状态转换规则进行状态切换。具体步骤如下:

  1. 初始化状态机

    • 定义了一个 graph 对象,表示不同状态之间的转换规则。
    • 每个状态对应一个对象,键为字符类型(如 digit, blank, sign, ., e),值为下一个状态。
  2. 遍历字符串

    • 使用 trim() 方法去除字符串两端的空白字符。
    • 遍历处理后的字符串,逐个字符进行分类和状态转换。
  3. 字符分类

    • 数字字符(0-9):转换为 digit
    • 空格字符( ):转换为 blank
    • 小数点字符(.):保持不变。
    • 指数字符(eE):转换为 e
    • 符号字符(+-):转换为 sign
  4. 状态转换

    • 根据当前字符和当前状态,在 graph 中查找下一个状态。
    • 如果找不到对应的转换规则(即 state === undefined),则返回 false,表示字符串不是有效数字。
  5. 最终状态检查

    • 遍历结束后,检查最终状态是否为合法的终止状态(3, 5, 6)。只有当最终状态为这些状态之一时,才返回 true,否则返回 false

控制流图(CFG)

flowchart TD A[开始] --> B{字符串为空?} B -->|Yes| E[返回 false] B -->|No| C[初始化状态为0] C --> D[去除空白字符] D --> F[遍历字符串] F --> G{字符类型是什么?} G -->|digit| H[转换为 digit] G -->|blank| I[转换为 blank] G -->|.| J[转换为 .] G -->|e 或 E| K[转换为 e] G -->|+ 或 -| L[转换为 sign] H --> M[查找下一个状态] I --> M J --> M K --> M L --> M M --> N{找到下一个状态?} N -->|No| O[返回 false] N -->|Yes| P[更新状态] P --> Q{遍历结束?} Q -->|No| F Q -->|Yes| R{最终状态合法?} R -->|No| S[返回 false] R -->|Yes| T[返回 true]

关键点说明

  1. 状态机设计

    • 状态机的核心是 graph 对象,它定义了从一个状态到另一个状态的转换规则。
    • 每个状态都有不同的字符类型可以触发状态转换,例如在状态 0 下遇到 digit 会转移到状态 6
  2. 字符分类逻辑

    • 通过条件判断将字符分为五类:digitblank.esign
    • 这种分类简化了状态转换的复杂度,使得代码更加简洁易读。
  3. 循环遍历与状态更新

    • 使用 for...of 循环遍历字符串中的每个字符。
    • 在每次迭代中,根据当前字符和当前状态查找下一个状态,并更新状态变量 state
    • 如果在任何时刻找不到合适的转换规则,则立即返回 false
  4. 最终状态检查

    • 遍历结束后,检查最终状态是否为合法的终止状态(3, 5, 6)。
    • 只有当最终状态为这些状态之一时,才认为字符串是一个有效的数字,返回 true;否则返回 false

示例解析

console.log(isNumber("1E9")) 为例:

  1. 初始化状态为 0
  2. 去除空白字符后,字符串为 "1E9"
  3. 遍历第一个字符 '1'
    • 类型为 digit,根据 graph 规则从状态 0 转移到状态 6
  4. 遍历第二个字符 'E'
    • 类型为 e,根据 graph 规则从状态 6 转移到状态 4
  5. 遍历第三个字符 '9'
    • 类型为 digit,根据 graph 规则从状态 4 转移到状态 5
  6. 遍历结束,最终状态为 5,属于合法的终止状态,因此返回 true

希望这个详细的解释能够帮助你更好地理解这段代码的工作原理。
image

标签:状态,digit,遍历,字符,有效数字,--,65,字符串,LeetCode
From: https://www.cnblogs.com/KooTeam/p/18667461

相关文章