当前位置： 首页 > news >正文

leetcode 65

news 2025/6/27 8:12:07 
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;class Solution {
public:bool isNumber(string s) {// 定义状态转移表vector<unordered_map<char, int>> states = {{{' ', 0}, {'s', 1}, {'d', 2}, {'.', 4}}, // 状态0：初始状态{{'d', 2}, {'.', 4}},                   // 状态1：符号位{{'d', 2}, {'.', 3}, {'e', 5}, {' ', 8}}, // 状态2：整数部分{{'d', 3}, {'e', 5}, {' ', 8}},         // 状态3：小数部分（有整数部分）{{'d', 3}},                             // 状态4：小数部分（无整数部分）{{'s', 6}, {'d', 7}},                   // 状态5：指数符号{{'d', 7}},                             // 状态6：指数符号后的符号位{{'d', 7}, {' ', 8}},                   // 状态7：指数部分{{' ', 8}}                              // 状态8：结尾空格};int currentState = 0;for (char c : s) {char type;if (isdigit(c)) type = 'd';else if (c == '+' || c == '-') type = 's';else if (c == 'e' || c == 'E') type = 'e';else if (c == '.') type = '.';else if (c == ' ') type = ' ';else return false; // 非法字符if (states[currentState].find(type) == states[currentState].end()) {return false; // 无法转移到下一个状态}currentState = states[currentState][type];}// 最终有效状态：2（整数）、3（小数）、7（指数）、8（结尾空格）return currentState == 2 || currentState == 3 || currentState == 7 || currentState == 8;}
};

代码解析：使用确定有限状态自动机验证有效数字

这段代码通过**确定有限状态自动机（DFA）**来验证一个字符串是否表示有效数字。下面我将从状态定义、转移规则到完整逻辑逐步解析：

一、整体思路

DFA 是一种计算模型，它包含：

  • 状态集合：不同处理阶段（如初始状态、符号位、整数部分等）
  • 转移规则：基于当前状态和输入字符决定下一个状态
  • 初始状态：验证开始的状态
  • 接受状态：验证成功的最终状态

这个解法将字符串处理过程划分为9个状态，通过转移表定义状态间的转换规则，最终根据结束状态判断是否有效。

二、状态定义与转移表

1. 状态定义

状态用整数表示（0-8），每个状态对应数字字符串的一个解析阶段：

  • 0：初始状态（可接受空格、符号、数字、小数点）
  • 1：符号位（+/-）
  • 2：整数部分（数字序列）
  • 3：小数部分（有整数的小数点后数字）
  • 4：小数部分（无整数的小数点后数字，如 .123）
  • 5：指数符号（e/E）
  • 6：指数部分的符号位（如 123e+4 中的 +）
  • 7：指数部分的整数
  • 8：结尾空格
2. 转移表结构
vector<unordered_map<char, int>> states = { ... };
  • 外层 vector 索引表示当前状态（0-8）
  • 内层 unordered_map 存储当前状态接受的字符类型及其对应的下一状态
  • 字符类型包括：
    • 'd'：数字（0-9）
    • 's'：符号（+/-）
    • 'e'：指数符号（e/E）
    • '.'：小数点
    • ' '：空格

三、状态转移规则详解

1. 初始状态（0）
{{' ', 0}, {'s', 1}, {'d', 2}, {'.', 4}}
  • 空格 → 保持初始状态（处理前导空格）
  • 符号 → 进入符号位状态（如 +123）
  • 数字 → 进入整数部分（如 123）
  • 小数点 → 进入无整数的小数部分（如 .123）
2. 符号位状态（1）
{{'d', 2}, {'.', 4}}
  • 数字 → 进入整数部分（如 +123）
  • 小数点 → 进入无整数的小数部分（如 -.123）
3. 整数部分（2）
{{'d', 2}, {'.', 3}, {'e', 5}, {' ', 8}}
  • 数字 → 保持整数部分（如 123）
  • 小数点 → 进入有整数的小数部分（如 123.45）
  • 指数符号 → 进入指数符号状态（如 123e4）
  • 空格 → 进入结尾空格状态（如 123 ）
4. 小数部分（3）
{{'d', 3}, {'e', 5}, {' ', 8}}
  • 数字 → 保持小数部分（如 1.23）
  • 指数符号 → 进入指数符号状态（如 1.23e4）
  • 空格 → 进入结尾空格状态（如 1.23 ）
5. 无整数的小数部分（4）
{{'d', 3}}
  • 数字 → 进入有整数的小数部分（如 .123 变为 0.123）
6. 指数符号（5）
{{'s', 6}, {'d', 7}}
  • 符号 → 进入指数符号位（如 123e+4）
  • 数字 → 进入指数整数部分（如 123e4）
7. 指数符号位（6）
{{'d', 7}}
  • 数字 → 进入指数整数部分（如 123e+4）
8. 指数整数部分（7）
{{'d', 7}, {' ', 8}}
  • 数字 → 保持指数部分（如 123e4）
  • 空格 → 进入结尾空格状态（如 123e4 ）
9. 结尾空格（8）
{{' ', 8}}
  • 空格 → 保持结尾空格状态（处理 trailing 空格）

四、字符类型映射

char type;
if (isdigit(c)) type = 'd';
else if (c == '+' || c == '-') type = 's';
else if (c == 'e' || c == 'E') type = 'e';
else if (c == '.') type = '.';
else if (c == ' ') type = ' ';
else return false; // 非法字符
  • 将输入字符映射为5种类型之一
  • 非法字符（如字母、其他符号）直接判定为无效

五、主验证逻辑

int currentState = 0;
for (char c : s) {// 字符类型映射...if (states[currentState].find(type) == states[currentState].end()) {return false; // 无法转移到下一个状态}currentState = states[currentState][type];
}// 最终有效状态：2（整数）、3（小数）、7（指数）、8（结尾空格）
return currentState == 2 || currentState == 3 || currentState == 7 || currentState == 8;
  • 流程：
    1. 从初始状态（0）开始
    2. 遍历每个字符，映射为类型 type
    3. 检查当前状态是否接受该类型：
      • 若接受，转移到下一状态
      • 若不接受，返回 false
    4. 遍历结束后，检查最终状态是否为有效接受状态

六、接受状态说明

有效数字的最终状态必须是：

  • 2：整数部分（如 "123"）
  • 3：小数部分（如 "1.23"、"123."、".123"）
  • 7：指数部分（如 "123e4"、"1.23e-4"）
  • 8：结尾空格（如 " 123 "、"123e4 "）

七、示例验证

1. 合法数字
  • "123"：0 → 2 → 2 → 2（最终状态2，有效）
  • "+1.23"：0 → 1 → 2 → 3 → 3 → 3（最终状态3，有效）
  • " 123e-4 "：0 → 0 → 2 → 2 → 2 → 5 → 6 → 7 → 8 → 8（最终状态8，有效）
2. 非法数字
  • "123."：0 → 2 → 2 → 2 → 3（最终状态3，有效，但实际应为无效，此处代码存在漏洞）
  • "e123"：0 → 5（无法继续转移，无效）
  • "123e"：0 → 2 → 2 → 2 → 5（无法继续转移，无效）

八、代码优化建议

  1. 修复小数点问题：当前代码允许 "123." 为有效，需调整状态3的定义
  2. 使用更安全的类型：用枚举替代状态数字，提高可读性
  3. 预计算字符类型映射：避免每次循环都进行条件判断
  4. 添加测试用例：覆盖所有边界情况（如 "123e"、".e123" 等）

九、总结

该代码通过DFA实现了有效数字的验证，将复杂的语法规则转化为清晰的状态转移表。虽然存在一些边界处理问题，但核心思路正确，适用于大多数常见场景。

leetcode 官方解答：

 class Solution {
public:enum State {STATE_INITIAL,STATE_INT_SIGN,STATE_INTEGER,STATE_POINT,STATE_POINT_WITHOUT_INT,STATE_FRACTION,STATE_EXP,STATE_EXP_SIGN,STATE_EXP_NUMBER,STATE_END};enum CharType {CHAR_NUMBER,CHAR_EXP,CHAR_POINT,CHAR_SIGN,CHAR_ILLEGAL};CharType toCharType(char ch) {if (ch >= '0' && ch <= '9') {return CHAR_NUMBER;} else if (ch == 'e' || ch == 'E') {return CHAR_EXP;} else if (ch == '.') {return CHAR_POINT;} else if (ch == '+' || ch == '-') {return CHAR_SIGN;} else {return CHAR_ILLEGAL;}}bool isNumber(string s) {unordered_map<State, unordered_map<CharType, State>> transfer{{STATE_INITIAL, {{CHAR_NUMBER, STATE_INTEGER},{CHAR_POINT, STATE_POINT_WITHOUT_INT},{CHAR_SIGN, STATE_INT_SIGN}}}, {STATE_INT_SIGN, {{CHAR_NUMBER, STATE_INTEGER},{CHAR_POINT, STATE_POINT_WITHOUT_INT}}}, {STATE_INTEGER, {{CHAR_NUMBER, STATE_INTEGER},{CHAR_EXP, STATE_EXP},{CHAR_POINT, STATE_POINT}}}, {STATE_POINT, {{CHAR_NUMBER, STATE_FRACTION},{CHAR_EXP, STATE_EXP}}}, {STATE_POINT_WITHOUT_INT, {{CHAR_NUMBER, STATE_FRACTION}}}, {STATE_FRACTION,{{CHAR_NUMBER, STATE_FRACTION},{CHAR_EXP, STATE_EXP}}}, {STATE_EXP,{{CHAR_NUMBER, STATE_EXP_NUMBER},{CHAR_SIGN, STATE_EXP_SIGN}}}, {STATE_EXP_SIGN, {{CHAR_NUMBER, STATE_EXP_NUMBER}}}, {STATE_EXP_NUMBER, {{CHAR_NUMBER, STATE_EXP_NUMBER}}}};int len = s.length();State st = STATE_INITIAL;for (int i = 0; i < len; i++) {CharType typ = toCharType(s[i]);if (transfer[st].find(typ) == transfer[st].end()) {return false;} else {st = transfer[st][typ];}}return st == STATE_INTEGER || st == STATE_POINT || st == STATE_FRACTION || st == STATE_EXP_NUMBER || st == STATE_END;}
};

代码解析：使用确定有限状态自动机验证有效数字

这段代码实现了LeetCode 65题「有效数字」的判断，采用了确定有限状态自动机(DFA)的思路。下面从整体到细节逐步解析：

一、整体解决方案概述

该解决方案通过以下步骤验证字符串是否为有效数字：

  1. 定义状态：将数字字符串的解析过程划分为不同阶段（状态）
  2. 定义字符类型：将输入字符分类为数字、指数符号等类型
  3. 构建状态转移表：定义每个状态在不同字符类型下的转移规则
  4. 状态转移遍历：从初始状态开始，按规则转移并判断最终状态

二、枚举类型定义

1. 状态枚举 (State)
enum State {STATE_INITIAL,        // 初始状态（允许前导空格，但代码中未处理空格）STATE_INT_SIGN,       // 整数符号位（+/-）STATE_INTEGER,        // 整数部分（数字序列）STATE_POINT,          // 小数点（左侧有整数）STATE_POINT_WITHOUT_INT, // 小数点（左侧无整数）STATE_FRACTION,       // 小数部分（小数点后的数字）STATE_EXP,            // 指数符号（e/E）STATE_EXP_SIGN,       // 指数符号后的符号位（+/-）STATE_EXP_NUMBER,     // 指数部分的整数STATE_END             // 结束状态（示例中未充分使用）
};
  • 每个状态代表当前解析到数字字符串的哪个阶段
  • 例如：STATE_POINT 表示已解析完整数部分，遇到小数点
2. 字符类型枚举 (CharType)
enum CharType {CHAR_NUMBER,  // 数字（0-9）CHAR_EXP,     // 指数符号（e/E）CHAR_POINT,   // 小数点（.）CHAR_SIGN,    // 符号位（+/-）CHAR_ILLEGAL  // 非法字符
};
  • 将输入字符分类，简化状态转移表的定义
  • 例如：所有数字字符（‘0’-‘9’）都归为 CHAR_NUMBER

三、字符类型转换函数

CharType toCharType(char ch) {if (ch >= '0' && ch <= '9') {return CHAR_NUMBER;} else if (ch == 'e' || ch == 'E') {return CHAR_EXP;} else if (ch == '.') {return CHAR_POINT;} else if (ch == '+' || ch == '-') {return CHAR_SIGN;} else {return CHAR_ILLEGAL;}
}
  • 功能：将输入字符映射到对应的 CharType 枚举值
  • 逻辑：判断字符是否为数字、指数符号、小数点、符号位或非法字符
  • 作用：使状态转移表只需关注字符类型，而非具体字符

四、状态转移表解析

unordered_map<State, unordered_map<CharType, State>> transfer{// 状态转移规则...
};

这是DFA的核心，定义了每个状态在不同字符类型下的转移目标。

1. 初始状态 (STATE_INITIAL)
{STATE_INITIAL, {{CHAR_NUMBER, STATE_INTEGER},      // 数字 → 整数部分{CHAR_POINT, STATE_POINT_WITHOUT_INT}, // 小数点 → 无整数的小数{CHAR_SIGN, STATE_INT_SIGN}        // 符号 → 符号位}
},
  • 初始状态可以接受数字、小数点或符号：
    • 数字：进入整数部分解析
    • 小数点：进入无整数的小数解析（如 .123）
    • 符号：进入符号位解析（如 +123）
2. 整数符号位 (STATE_INT_SIGN)
{STATE_INT_SIGN, {{CHAR_NUMBER, STATE_INTEGER},      // 数字 → 整数部分{CHAR_POINT, STATE_POINT_WITHOUT_INT} // 小数点 → 无整数的小数}
},
  • 符号位后只能接数字或小数点：
    • 例如：+123（符号→数字）、-.456（符号→小数点）
3. 整数部分 (STATE_INTEGER)
{STATE_INTEGER, {{CHAR_NUMBER, STATE_INTEGER},  // 数字 → 保持整数部分{CHAR_EXP, STATE_EXP},        // 指数符号 → 指数解析{CHAR_POINT, STATE_POINT}     // 小数点 → 有整数的小数}
},
  • 整数部分后可接：
    • 更多数字（保持整数部分）
    • 指数符号（如 123e4）
    • 小数点（如 123.45）
4. 有整数的小数点 (STATE_POINT)
{STATE_POINT, {{CHAR_NUMBER, STATE_FRACTION},  // 数字 → 小数部分{CHAR_EXP, STATE_EXP}           // 指数符号 → 指数解析}
},
  • 小数点后可接：
    • 数字（如 123.45）
    • 指数符号（如 123.e4）
5. 无整数的小数点 (STATE_POINT_WITHOUT_INT)
{STATE_POINT_WITHOUT_INT, {{CHAR_NUMBER, STATE_FRACTION}  // 数字 → 小数部分}
},
  • 无整数的小数点后必须接数字（如 .123）
  • 若小数点后无数字（如 .），则转移失败
6. 小数部分 (STATE_FRACTION)
{STATE_FRACTION, {{CHAR_NUMBER, STATE_FRACTION},  // 数字 → 保持小数部分{CHAR_EXP, STATE_EXP}           // 指数符号 → 指数解析}
},
  • 小数部分后可接：
    • 更多数字（如 1.234）
    • 指数符号（如 1.23e4）
7. 指数符号 (STATE_EXP)
{STATE_EXP, {{CHAR_NUMBER, STATE_EXP_NUMBER},  // 数字 → 指数整数部分{CHAR_SIGN, STATE_EXP_SIGN}       // 符号 → 指数符号位}
},
  • 指数符号后可接：
    • 数字（如 123e4）
    • 符号（如 123e+4、123e-4）
8. 指数符号位 (STATE_EXP_SIGN)
{STATE_EXP_SIGN, {{CHAR_NUMBER, STATE_EXP_NUMBER}  // 数字 → 指数整数部分}
},
  • 指数符号位后必须接数字（如 123e+4）
  • 若符号后无数字（如 123e+），则转移失败
9. 指数整数部分 (STATE_EXP_NUMBER)
{STATE_EXP_NUMBER, {{CHAR_NUMBER, STATE_EXP_NUMBER}  // 数字 → 保持指数部分}
},
  • 指数整数部分后可接更多数字（如 123e12）

五、主验证逻辑

bool isNumber(string s) {int len = s.length();State st = STATE_INITIAL;for (int i = 0; i < len; i++) {CharType typ = toCharType(s[i]);if (transfer[st].find(typ) == transfer[st].end()) {return false; // 转移失败，非有效数字} else {st = transfer[st][typ]; // 更新状态}}// 最终状态必须是有效接受状态return st == STATE_INTEGER || st == STATE_POINT || st == STATE_FRACTION || st == STATE_EXP_NUMBER || st == STATE_END;
}

  • 流程：

    1. 从初始状态 STATE_INITIAL 开始
    2. 逐个字符处理，转换为类型 CharType
    3. 根据当前状态和字符类型查找转移表
    4. 若转移规则不存在，直接返回 false
    5. 处理完所有字符后，检查最终状态是否为接受状态

  • 接受状态：

    • STATE_INTEGER：以整数结尾（如 123）
    • STATE_POINT：以有整数的小数点结尾（如 123.）
    • STATE_FRACTION：以小数结尾（如 1.23）
    • STATE_EXP_NUMBER：以指数部分结尾（如 123e4）
    • STATE_END：（示例中未充分使用，可用于结尾空格等场景）

六、代码注意事项

  1. 空格处理：当前代码未处理前导/ trailing 空格，实际有效数字可能包含空格（如 " 123 "）
  2. 状态转移表效率：使用 unordered_map 实现转移表，查找效率为 O(1)，但可优化为数组进一步提高性能
  3. 非法字符处理：遇到 CHAR_ILLEGAL 类型时直接判定为无效
  4. 边界情况覆盖：
    • 整数："123"
    • 小数："1.23"、".456"
    • 指数："123e4"、"1.2e-3"
    • 符号："+123"、"-4.5"

七、总结

该解决方案通过DFA清晰地建模了有效数字的解析过程，每个状态对应数字字符串的一个解析阶段，状态转移表定义了合法的字符接续规则。这种方法将复杂的规则判断转化为状态机的状态转移，逻辑清晰且易于维护，是解决字符串验证问题的经典思路。

http://www.lqws.cn/news/528049.html

相关文章：

  • Autosar方法论
  • 力扣2311：小于等于K的最长二进制子序列
  • 【TIDB】了解，MySQL和TiDB的取舍，差异
  • postman设置接口关联，实现参数化
  • kotlin中::class.java的意义
  • Redis 为什么选用跳跃表，而不是红黑树
  • PHP基础2（流程控制，函数）
  • 【机器学习深度学习】交互式线性回归 demo
  • C语言再出发：2025年AI时代的关键语言
  • notepad++ 怎么快速给 python (nginx、shell) 文件加 # 注释
  • VUE3入门很简单（3）--- watch
  • MR30分布式 IO在物流堆垛机的应用
  • 解锁AI无限潜能！景联文科技数据产品矩阵再升级：多语言题库、海量语料、垂域代码库，全面赋能大模型训练
  • 力扣第45题-跳跃游戏2
  • 【智能记录系统Blinko】从0到1搭建个人云端笔记本：Blinko+Docker环境配置
  • JVM OutOfMemoryError原因及排查解决方案
  • java解决超大二维矩阵数组引起的内存占用过大问题
  • 深入解析synchronized实现原理
  • 【2-入门与调试设置】1.坐标辅助器与轨道控制器
  • 英特尔汽车业务败走中国，喊出“All in”才过两个月
  • 观测云产品更新 | 外部数据源、日志、监控、事件、基础设施等
  • TCP 协议安全性全面分析：漏洞、应用场景与防护策略
  • 芯谷科技--降压型DC-DC转换器D4005
  • [OS_27] 现代应用程序架构
  • ESP32 VSCODE进入menuconfig时ESP-IDF idf.py menuconfig卡进度条，setuptools版本太高解决方法
  • 小程序学习笔记：实现上拉触底加载随机颜色案例全解析
  • 深度剖析 Apache Pulsar：架构、优势与选型指南
  • 图像质量对比感悟
  • [论文阅读] 人工智能 + 软件工程 | AI 与敏捷开发的破局之路：从挫败到成功的工作坊纪实
  • 推荐一个前端基于vue3.x，vite7.x，后端基于springboot3.4.x的完全开源的前后端分离的中后台管理系统基础项目（纯净版）