8. String to Integer (atoi)(medium)

字元串轉數字,要求如下

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.

總結一下就是

輸入里有冗餘的空格,數目不定的正負號和非數字字元。

據此,有解題思路

1.預處理,去除多餘的空格(到第一個非空格字元停止,字元串中間和末尾的字元可以忽略)

2.判斷正負號,多個正負號則認為非法,返回0

3.計數,遇到非數字字元則停止,在int範圍內則返回,不在int範圍內則返回邊界值

實現不難,關鍵是把代碼寫得簡潔而高效。

參考實現:

class Solution {public: int myAtoi(string str) { int i = str.find_first_not_of( ), s = 1; long res = 0; if(str[i]==+||str[i]==-) s = (str[i++]==+)?1:-1; while(isdigit(str[i])) { res = res*10 + (str[i++]-0); if(res>INT_MAX) return s>0?INT_MAX:INT_MIN; } return s*res; }};

這題給我的啟發是代碼如何寫得簡潔優雅

多用標準庫函數,把簡單的邏輯寫到一起,關於int的溢出問題巧用long


推薦閱讀:

[leetcode algorithms]題目20
[leetcode algorithms]題目12
Leetcode-Maximum Subarray
LeetCode 簡略題解 - 301~400
1. Two Sum

TAG:LeetCode | 演算法設計 | 演算法與數據結構 |