我的LeetCode：https://leetcode-cn.com/u/ituring/
我的LeetCode刷題原始碼[GitHub]：https://github.com/izhoujie/Algorithmcii
LeetCode 8. 字串轉換整數 (atoi)
題目
請你來實作一個 atoi 函式，使其能將字串轉換成整數，
首先，該函式會根據需要丟棄無用的開頭空格字符，直到尋找到第一個非空格的字符為止，接下來的轉化規則如下：
- 如果第一個非空字符為正或者負號時，則將該符號與之后面盡可能多的連續數字字符組合起來，形成一個有符號整數，
- 假如第一個非空字符是數字，則直接將其與之后連續的數字字符組合起來，形成一個整數，
- 該字串在有效的整數部分之后也可能會存在多余的字符，那么這些字符可以被忽略，它們對函式不應該造成影響，
注意：假如該字串中的第一個非空格字符不是一個有效整數字符、字串為慷訓字串僅包含空白字符時，則你的函式不需要進行轉換，即無法進行有效轉換，
在任何情況下，若函式不能進行有效的轉換時，請回傳 0 ，
提示：
- 本題中的空白字符只包括空格字符 ' ' ，
- 假設我們的環境只能存盤 32 位大小的有符號整數，那么其數值范圍為 [\(?2^{31}\), \(2^{31} ? 1\)]，如果數值超過這個范圍，請回傳 INT_MAX (\(2^{31} ? 1\)) 或 INT_MIN (\(?2^{31}\)) ，
示例 1:
輸入: "42"
輸出: 42
示例 2:
輸入: " -42"
輸出: -42
解釋: 第一個非空白字符為 '-', 它是一個負號，
我們盡可能將負號與后面所有連續出現的數字組合起來，最后得到 -42 ，
示例 3:
輸入: "4193 with words"
輸出: 4193
解釋: 轉換截止于數字 '3' ，因為它的下一個字符不為數字，
示例 4:
輸入: "words and 987"
輸出: 0
解釋: 第一個非空字符是 'w', 但它不是數字或正、負號，
因此無法執行有效的轉換，
示例 5:
輸入: "-91283472332"
輸出: -2147483648
解釋: 數字 "-91283472332" 超過 32 位有符號整數范圍，
因此回傳 INT_MIN ($2^{31} ? 1$) ，
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/string-to-integer-atoi
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
解題思路
思路1-先去空格再校驗首字符正負號最后逐個處理轉化
步驟：
- 先null校驗，trim去除首尾的空白字符；
- 校驗首個字符為‘+’或者‘-’的情況并用一個變數記錄正負號；
- 逐個轉化，注意溢位的校驗，這里用的是自校驗：若本次操作后會溢位，那么溢位后的數除以10后必不等于操作之前的數；
演算法復雜度:
- 時間復雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
- 空間復雜度： $ {\color{Magenta}{\Omicron\left(1\right)}} $
演算法原始碼示例
package leetcode;
/**
* @author ZhouJie
* @date 2019年12月10日 下午6:13:52
* @Description:8. 字串轉換整數 (atoi)
*
*/
public class LeetCode_0008 {
}
class Solution_0008 {
/**
* @author: ZhouJie
* @date: 2020年5月14日 下午10:57:42
* @param: @param str
* @param: @return
* @return: int
* @Description: 1-
*
*/
public int strToInt(String str) {
int len = 0;
// 首尾空白字符trim處理
if (str == null || ((len = (str = str.trim()).length()) == 0)) {
return 0;
}
int i = 0;
int f = 1;
char c = str.charAt(i);
// 首字符符號校驗
if (c == '+' || c == '-') {
i++;
if (c == '-') {
f = -1;
}
}
int before = 0, now = 0;
// 逐個字符轉化，每次/10與上一次的值校驗用以判斷是否溢位
while (i < len) {
c = str.charAt(i);
if (c >= '0' && c <= '9') {
before = now;
now = now * 10 + (c - '0') * f;
// 溢位校驗，若本次結果已溢位，那么當前值/10必不等于上一次的值，利用溢位去校驗溢位，巧妙
if (now / 10 != before) {
return f > 0 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
} else {
return now;
}
i++;
}
return now;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/195316.html
標籤：Java
下一篇：Java筆記：Java基礎