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

上一篇文章我们通过一种模式识别的方法（字符串转换成一个 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）