leetcode筆記：String to Integer (atoi)

leetcode筆記：String to Integer (atoi)

一. 題目描述

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Requirements for atoi:

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

二. 題目分析

該問題的內容很長，其實主要是描述一些可能的邊界問題。對於整數來說，兩大問題就是是正負號的問題和是整數范圍是否越界的問題。

思路比較簡單，就是先去掉多余的空格字符，然後讀符號（注意正負號都有可能，也有可能沒有符號），接下來按順序讀數字，結束條件有三種情況：

三. 示例代碼

只要注意邊界問題，編程沒有太大難度，由於時間有限，先借鑒了別人的程序。

// 時間復雜度O(n)，空間復雜度O(1)
class Solution {
public:
    int atoi(const char *str) {
        int num = 0;
        int sign = 1;
        const int n = strlen(str);
        int i = 0;
        while (str[i] == ' ' && i < n) i++;
        if (str[i] == '+') 
            i++;
        else if (str[i] == '-') 
        {
            sign = -1;
            i++;
        }
        for (; i < n; i++)
        {
            if (str[i] < '0' || str[i] > '9')
                break;
            if (num > INT_MAX / 10 ||
            (num == INT_MAX / 10 &&
            (str[i] - '0') > INT_MAX % 10)) 
            {
                return sign == -1 ? INT_MIN : INT_MAX;
            }
            num = num * 10 + str[i] - '0';
        }
        return num * sign;
    }
};

四. 小結

面試中還是經常出現這種問題的，對應的有整數轉字符串。這類問題中考慮好邊界條件是關鍵。