- 💻 劍指Offer & LeetCode刷題倉庫：https://github.com/Damaer/CodeSolution
- 文檔位址：https://damaer.github.io/CodeSolution/
- 倉庫介紹：刷題倉庫：CodeSolution
- 📒 程式設計知識庫：https://github.com/Damaer/Coding
- 文檔位址：https://damaer.github.io/Coding/#/
題目
請你來實作一個
myAtoi(string s)
函數，使其能将字元串轉換成一個
32
位有符号整數（類似
C/C++
中的
atoi
函數）。
函數
myAtoi(string s)
的算法如下：
讀入字元串并丢棄無用的前導空格 檢查下一個字元（假設還未到字元末尾）為正還是負号，讀取該字元（如果有）。确定最終結果是負數還是正數。如果兩者都不存在，則假定結果為正。讀入下一個字元，直到到達下一個非數字字元或到達輸入的結尾。字元串的其餘部分将被忽略。
将前面步驟讀入的這些數字轉換為整數（即，"
123
" ->
123
， "
0032
" ->
32
）。如果沒有讀入數字，則整數為
。必要時更改符号（從步驟
2
開始）。
如果整數數超過
32
位有符号整數範圍
[−231, 231 − 1]
，需要截斷這個整數，使其保持在這個範圍内。具體來說，小于
−231
的整數應該被固定為
−231
，大于
231 − 1
的整數應該被固定為
231 − 1
。
傳回整數作為最終結果。
注意：
- 本題中的空白字元隻包括空格字元 ' ' 。
- 除前導空格或數字後的其餘字元串外，請勿忽略 任何其他字元。
示例 1：
輸入：s = "42"
輸出：42
解釋：加粗的字元串為已經讀入的字元，插入符号是目前讀取的字元。
第 1 步："42"（目前沒有讀入字元，因為沒有前導空格）
^
第 2 步："42"（目前沒有讀入字元，因為這裡不存在 '-' 或者 '+'）
^
第 3 步："42"（讀入 "42"）
^
解析得到整數 42 。
由于 "42" 在範圍 [-231, 231 - 1] 内，最終結果為 42 。
複制
示例 2：
輸入：s = " -42"
輸出：-42
解釋：
第 1 步：" -42"（讀入前導空格，但忽視掉）
^
第 2 步：" -42"（讀入 '-' 字元，是以結果應該是負數）
^
第 3 步：" -42"（讀入 "42"）
^
解析得到整數 -42 。
由于 "-42" 在範圍 [-231, 231 - 1] 内，最終結果為 -42 。
複制
示例 3：
輸入：s = "4193 with words"
輸出：4193
解釋：
第 1 步："4193 with words"（目前沒有讀入字元，因為沒有前導空格）
^
第 2 步："4193 with words"（目前沒有讀入字元，因為這裡不存在 '-' 或者 '+'）
^
第 3 步："4193 with words"（讀入 "4193"；由于下一個字元不是一個數字，是以讀入停止）
^
解析得到整數 4193 。
由于 "4193" 在範圍 [-231, 231 - 1] 内，最終結果為 4193 。
複制
示例 4：
輸入：s = "words and 987"
輸出：0
解釋：
第 1 步："words and 987"（目前沒有讀入字元，因為沒有前導空格）
^
第 2 步："words and 987"（目前沒有讀入字元，因為這裡不存在 '-' 或者 '+'）
^
第 3 步："words and 987"（由于目前字元 'w' 不是一個數字，是以讀入停止）
^
解析得到整數 0 ，因為沒有讀入任何數字。
由于 0 在範圍 [-231, 231 - 1] 内，最終結果為 0 。
複制
示例 5：
輸入：s = "-91283472332"
輸出：-2147483648
解釋：
第 1 步："-91283472332"（目前沒有讀入字元，因為沒有前導空格）
^
第 2 步："-91283472332"（讀入 '-' 字元，是以結果應該是負數）
^
第 3 步："-91283472332"（讀入 "91283472332"）
^
解析得到整數 -91283472332 。
由于 -91283472332 小于範圍 [-231, 231 - 1] 的下界，最終結果被截斷為 -231 = -2147483648 。
複制
提示：
0 <= s.length <= 200 s 由英文字母（大寫和小寫）、數字（0-9）、' '、'+'、'-' 和 '.' 組成
思路與解答
這道題目看起來很長，但是實際上邏輯很清晰，就是将字元串解析成為數字，裡面有幾個特殊的規則：
- 1.前面的空格去掉，不讀取
- 2.接下來的字元必須是數字，“
+
-
- 2.1 如果是“
+
-
- 2.2 沒有符号預設是“
+
- 2.1 如果是“
- 3.接下來的字元必須是數字，遇到其他字元會直接結束
- 4.需要考慮溢出的問題
在将字元串轉換成數字的時候，用下面這句核心代碼：
sum = sum * 10 + (str.charAt(i) - '0');
複制
但是在這個過程中，我們依然需要考慮數字溢出的問題，這個問題其實和我們上一道題【反轉整數】一樣：
針對這種情況，我們可以在加和之前判斷，針對大于0的情況，如果大于最大值整除10，或者等于最大值整除10，但是個位數超過了，都直接傳回0。
假設最大值是127，那麼sum如果大于12，肯定會超過，如果sum ==12，但是個位數大于7，乘以10相加，也肯定會超。
if (sum > Integer.MAX_VALUE/10 || (sum == Integer.MAX_VALUE / 10 && (str.charAt(i) - '0') > 7)) return 0;
複制
對于小于
的情況，假設最小值是
-128
，那麼
sum
是數字部分
128
, 如果目前
sum
大于
12
，那麼就一定超出，或者
sum == 12
，但是個位數大于
8
，乘以
10
，相加也會大于
128
，不符合要求，是以直接傳回
。
if (sum < Integer.MIN_VALUE/10 || (sum == Integer.MIN_VALUE / 10 && x (str.charAt(i) - '0') > 8)) return 0;
複制
java代碼實作如下：
class Solution {
public static int myAtoi(String str) {
if (str == null) {
return 0;
}
int i = 0;
while (i < str.length() && str.charAt(i) == ' ') {
i++;
}
if (i >= str.length()
|| (str.charAt(i) != '-'
&& str.charAt(i) != '+' && !((str.charAt(i) >= '0') && (str.charAt(i) <= '9')))) {
return 0;
}
int sign = 1;
if (i < str.length() && (str.charAt(i) == '-' || i < str.length() && str.charAt(i) == '+')) {
sign = str.charAt(i) == '-' ? -1 : 1;
i++;
}
int sum = 0;
for (; i < str.length(); i++) {
if (str.charAt(i) >= '0' && str.charAt(i) <= '9') {
if (sign == 1) {
if (sum > Integer.MAX_VALUE / 10 || sum == Integer.MAX_VALUE / 10 && (str.charAt(i) - '0') > 7) {
return Integer.MAX_VALUE;
}
} else {
if (sum > (Integer.MAX_VALUE) / 10 || sum == (Integer.MAX_VALUE) / 10 && (str.charAt(i) - '0') > 8) {
return Integer.MIN_VALUE;
}
}
sum = sum * 10 + (str.charAt(i) - '0');
} else {
return sum * sign;
}
}
return sum * sign;
}
}
複制
C++ 代碼實作如下：
#include<iostream>
#include<string>
using namespace std;
class Solution {
public:
int myAtoi(string str) {
if (str.size() == 0) {
return 0;
}
int i = 0;
while (i < str.length() && str[i] == ' ') {
i++;
}
if (i >= str.length()
|| (str[i]!= '-'
&& str[i] != '+' && !((str[i] >= '0') && (str[i] <= '9')))) {
return 0;
}
int sign = 1;
if (i < str.length() && (str[i] == '-' || i < str.length() && str[i] == '+')) {
sign = str[i] == '-' ? -1 : 1;
i++;
}
// 需要無符号數，否則 -2147483648會溢出
unsigned int sum = 0;
for (; i < str.length(); i++) {
if (str[i] >= '0' && str[i] <= '9') {
if (sign == 1) {
if (sum > INT_MAX / 10 || sum == INT_MAX / 10 && (str[i]- '0') > 7) {
return INT_MAX;
}
} else {
if (sum > (INT_MAX) / 10 || sum == (INT_MAX) / 10 && (str[i] - '0') > 8) {
return INT_MIN;
}
}
sum = sum * 10 + (str[i] - '0');
} else {
return sum * sign;
}
}
return sum * sign;
}
};
int main(){
Solution solution;
cout<< solution.myAtoi(" -2147483648")<<endl;
return 0;
}
複制
時間複雜度為 O(n)，空間複雜度為O(1)。
【作者簡介】
秦懷，公衆号【秦懷雜貨店】作者，技術之路不在一時，山高水長，縱使緩慢，馳而不息。個人寫作方向：Java源碼解析，JDBC，Mybatis，Spring，Redis，分布式，劍指Offer，LeetCode等，認真寫好每一篇文章，不喜歡标題黨，不喜歡花裡胡哨，大多寫系列文章，不能保證我寫的都完全正确，但是我保證所寫的均經過實踐或者查找資料。遺漏或者錯誤之處，還望指正。
平日時間寶貴，隻能使用晚上以及周末時間學習寫作
- END -