專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

據每日經濟網報道英偉達員工有一半的人凈資產已達到2500萬美元，約合人民幣1.83億。不少英偉達員工反映為了支撐英偉達的高市值，他們經常每周工作 7 天，經常加班到凌晨 2 點。這工作量比起996嚴重多了，不過收入也確實很誘人。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第8題：字符串轉換整數 (atoi)

問題描述

來源：LeetCode第8題

難度：中等

把一個字符串s轉化為整數，前面如果有空格要去掉，還要注意正負號，讀入下一個字符，直到到達 下一個非數字字符或到達輸入的結尾 ，字符串的其余部分將被忽略。

如果整數超過 32 位有符號整數范圍 [?2^31, 2^31 ? 1] ，需要截斷這個整數，使其保持在這個范圍內。具體來說，小于 ?2^31 的整數應該被固定為 ?2^31 ，大于 2^31 ? 1 的整數應該被固定為 2^31 ? 1 。

示例1：

輸入：s = " -42" 輸出：-42 解釋：" -42"（讀入前導空格，但忽視掉）

示例2：

輸入：s = "4193 with words" 輸出：4193 解釋："4193 with words"（讀入 "4193"；由于下一個字符不是一個數字，所以讀入停止），解析得到整數 4193 。

• 0 <= s.length <= 200

• s 由英文字母（大寫和小寫）、數字（0-9）、' '、'+'、'-' 和 '.' 組成

問題分析

這題是讓把一個字符串轉成一個整數，難度不是很大，但細節挺多，一不小心有可能就會做錯。

首先如果字符串前面有空格要去掉，去掉最前面的空格之后如果遇到符號，還要記錄符號，如果沒有遇到符號就默認是正數。后面開始把字符串轉成數字，如果遇到不是數字的直接停止，后面的忽略掉，就不要再轉了。還有一點就是轉成的數字不能超出int的范圍，如果超出了直接截取。

我們需要使用一個變量sign來記錄符號位， 1 表示正數， -1 表示負數，轉的時候就不需要在考慮符號了，但最后返回的時候還要注意符號不能漏掉。

java：

public int myAtoi(String str) {     str = str.trim();// 去掉前后的空格     if (str.length() == 0)         return 0;     int num = 0;// 最終結果     int index = 0;// 遍歷字符串中字符的位置     int sign = 1;// 符號，1是正數，-1是負數，默認為正數     int length = str.length();     // 判斷符號     if (str.charAt(index) == '-' || str.charAt(index) == '+')         sign = str.charAt(index++) == '+' ? 1 : -1;     for (; index < length; ++index) {         // 取出字符串中字符，然后轉化為數字         int digit = str.charAt(index) - '0';         // 按照題中的要求，讀入下一個字符，直到到達下一個非數字字符或到達輸入的結尾。         // 字符串的其余部分將被忽略。如果讀取了非數字，后面的都要忽略。         if (digit < 0 || digit > 9)             break;         // 越界處理         if (num > Integer.MAX_VALUE / 10 ||                 (num == Integer.MAX_VALUE / 10 && digit > Integer.MAX_VALUE % 10))             return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;         else             num = num * 10 + digit;     }     return sign * num; }

C++：

public:     int myAtoi(string str) {         if (str.empty())             return 0;         int length = str.size();         int index = 0;// 遍歷字符串中字符的位置         while (str[index] == ' ')// 去掉前面的空格             if (++index == length)                 return 0;         int num = 0;// 最終結果         int sign = 1;// 符號，1是正數，-1是負數，默認為正數         // 判斷符號         if (str[index] == '-' || str[index] == '+')             sign = str[index++] == '+' ? 1 : -1;         for (; index < length; ++index) {             // 取出字符串中字符，然后轉化為數字             int digit = str[index] - '0';             // 按照題中的要求，讀入下一個字符，直到到達下一個非數字字符或到達輸入的結尾。             // 字符串的其余部分將被忽略。如果讀取了非數字，后面的都要忽略。             if (digit < 0 || digit > 9)                 break;             // 越界處理             if (num > INT_MAX / 10 ||                 (num == INT_MAX / 10 && digit > INT_MAX % 10))                 return sign == 1 ? INT_MAX : INT_MIN;             else                 num = num * 10 + digit;         }         return sign * num;     }

python：

def myAtoi(self, s: str) -> int:     s = s.strip()  # 刪除首尾空格     if not s:         return 0  # 字符串為空則直接返回     num = 0  # 最終結果     index = 0  # 遍歷字符串中字符的位置     sign = 1  # 符號，1是正數，-1是負數，默認為正數     int_max, int_min = 2 ** 31 - 1, -2 ** 31     if s[index] == '-' or s[index] == '+':         sign = 1 if s[index] == '+' else -1         index += 1     for c in s[index:]:         digit = ord(c) - ord('0')         if digit < 0 or digit > 9:             break  # 遇到非數字的字符則跳出             # 越界處理         if num > int_max // 10 or (num == int_max // 10 and digit > int_max % 10):             return int_max if sign == 1 else int_min         num = 10 * num + digit     return sign * num

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。