确定有限状态机(DFA)-Leet

大家好，欢迎来到IT知识分享网。

上一篇文章我们通过一种模式识别的方法（字符串转换成一个 32 位有符号整数-atoi 函数Leet ），把字符串转换为有符号整数。解决这个问题还有一种有趣的方法可以尝试，那就是确定有限状态机（Deterministic Finite Automation，DFA）。

复杂度分析：

时间复杂度：O(n)，其中 n为字符串的长度。我们只需要依次处理所有的字符，处理每个字符需要的时间为 O(1)。

空间复杂度：O(1)，自动机的状态只需要常数空间存储。

首先需要建立状态转移图：

建立状态转移图

我们就得出如下表格：

状态转移表格

代码实现：

//宏定义所有状态 #define START 0 #define SIGNED 1 #define IN_NUMBER 2 #define END 3 #define MAX_STATE 4

//将表格转换为二维数组 int map[MAX_STATE][MAX_STATE] = { {START, SIGNED, IN_NUMBER, END}, {END, END, IN_NUMBER, END}, {END, END, IN_NUMBER, END}, {END, END, END, END} };

状态之间的转移，通过输入的不同来驱动：

 if(' ' == s[i]) { state = map[state][START]; } else if('+' == s[i] || '-' == s[i]) { state = map[state][SIGNED]; } else if(s[i] >= '0' && s[i] <= '9') { state = map[state][IN_NUMBER]; } else { state = map[state][END]; }

在不同的状态，要实现不同的动作：

 if(state == START) { continue; } if(state == SIGNED) { if ('-' == s[i]) {//如果存在-符号，flag取为-1 flag = -1; } } if(state == IN_NUMBER) { if (ans < IntMax / 10 || (ans == IntMax / 10 && (s[i] - '0') < 8)) { ans = ans * 10 + (s[i] - '0'); } else { return (flag == 1? IntMax:IntMin); } } if(state == END) { break; }

从提交结果来看，该方法还可以：

1082 / 1082 个通过测试用例

状态：通过

执行用时: 4 ms

内存消耗: 5.6 MB

完整代码如下：

 #include<stdio.h> #include<stdlib.h> #include<string.h> #define INTMAX ((unsigned)(-1)>>1) #define INTMIN (~INTMAX) //宏定义所有状态 #define START 0 #define SIGNED 1 #define IN_NUMBER 2 #define END 3 #define MAX_STATE 4 int myAtoi(char * s) { int IntMax = INTMAX; int IntMin = INTMIN; int map[MAX_STATE][MAX_STATE] = {//将表格转换为二维数组 {START, SIGNED, IN_NUMBER, END}, {END, END, IN_NUMBER, END}, {END, END, IN_NUMBER, END}, {END, END, END, END} }; int state = 0; int ans = 0; int flag = 1; for (int i = 0; i < strlen(s); i++) { //状态之间的转移，通过输入的不同来驱动： if(' ' == s[i]) { state = map[state][START]; } else if('+' == s[i] || '-' == s[i]) { state = map[state][SIGNED]; } else if(s[i] >= '0' && s[i] <= '9') { state = map[state][IN_NUMBER]; } else { state = map[state][END]; } //在不同的状态，要实现不同的动作： if(state == START) { continue; } if(state == SIGNED) { if ('-' == s[i]) {//如果存在-符号，flag取为-1 flag = -1; } } if(state == IN_NUMBER) { if (ans < IntMax / 10 || (ans == IntMax / 10 && (s[i] - '0') < 8)) { ans = ans * 10 + (s[i] - '0'); } else { return (flag == 1? IntMax:IntMin); } } if(state == END) { break; } } return flag * ans; } int main() { char s[] = "-91"; int ans = myAtoi(s); printf("%d\n", INTMAX); printf("%d\n", ans); return 0; }

LeetCode系列：

leetcode2. 两数相加-c语言-python3

LeetCode4. 寻找两个正序数组的中位数

LeetCode5.0-最长回文子串-中心扩展法-C语言

LeetCode5.1-马拉车算法求解最长回文子串

LeetCode5.2-动态规划求解最长回文子串

LeetCode7.翻转整数-C语言与python的异同点

字符串转换成一个 32 位有符号整数-atoi 函数Leet

二叉树系列：

判断二叉树是否为平衡二叉树

平衡二叉树

构建平衡二叉树

如何优雅地画好二叉树

二叉树的层序遍历及应用

二叉树遍历的思维导图

平衡二叉树的结点删除操作

不平衡二叉树的旋转（LL、RR、LR、RL）

二叉查找树（BST：Binary Search Tree）