複雜度分析：

時間複雜度：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系列：

二叉樹系列：