換整數(shù) (atoi)——單指針模擬法與 32 位整數(shù)邊界處理全解析)
教程文檔知識庫【免費下載鏈接】AlgoNote??「算法通關(guān)手冊」從零開始的「算法與數(shù)據(jù)結(jié)構(gòu)」學習教程200 道「算法面試熱門題目」1000 道「LeetCode 題目解析」持續(xù)更新中項目地址https://gitcode.com/gh_mirrors/le/AlgoNote點擊查看免費下載本篇文章基于「算法通關(guān)手冊」AlgoNote 倉庫中的 string-to-integer-atoi.md 題解文檔展開圍繞 LeetCode 第 0008 題「字符串轉(zhuǎn)換整數(shù) (atoi)」的完整算法規(guī)則、模擬實現(xiàn)、邊界條件與復雜度分析進行深入講解。讀完本文你將掌握如何用單指針線性掃描實現(xiàn)一個嚴格符合 C/Catoi語義的myAtoi(s)函數(shù)并能在面試中精準處理前導空格、正負號、非法字符與 32 位有符號整數(shù)溢出截斷等全部邊界場景。題目定位與背景本題是 LeetCode 熱題中的字符串模擬類經(jīng)典題在「算法通關(guān)手冊」中標記為字符串標簽、中等難度。它同時被收錄于倉庫的 面試 100 題列表 與 面試 200 題列表可見其在算法面試中的高頻地位。題目的核心難點不在于算法本身僅需一次線性掃描而在于對題意中繁瑣邊界規(guī)則的逐條精確還原這正是考察候選人對需求細節(jié)把控能力的經(jīng)典場景。題目大意與輸入約束給定一個字符串s要求實現(xiàn)myAtoi(s)函數(shù)使其能轉(zhuǎn)換成一個 32 位有符號整數(shù)類似 C/C 中的atoi函數(shù)。需要檢測有效性無法讀取時返回0。輸入與規(guī)則約束如下本題中的空白字符只包括空格字符 除前導空格或數(shù)字后的其余字符串外請勿忽略任何其他字符字符串長度滿足 $0 \le s.length \le 200$s由英文字母大寫和小寫、數(shù)字0-9、 、、-和.組成。之所以明確限定字符集與僅空格這一細節(jié)是因為真實的 Catoi在具體實現(xiàn)上存在平臺差異而本題將這些規(guī)則顯式固定下來避免了歧義——例如真實atoi可能把1.5解析為1而本題規(guī)定遇到第一個非數(shù)字字符即停止讀取.之后的內(nèi)容被忽略。函數(shù)算法規(guī)則六步流程官方算法描述是本題一切實現(xiàn)的規(guī)格說明書共六步任何解都必須逐條滿足丟棄前導空格讀入字符串并丟棄無用的前導空格。判定符號檢查下一個字符假設還未到字符末尾為正還是負號讀取該字符如果有。確定最終結(jié)果是負數(shù)還是正數(shù)。如果兩者都不存在則假定結(jié)果為正。連續(xù)讀入數(shù)字讀入下一個字符直到到達下一個非數(shù)字字符或到達輸入的結(jié)尾。字符串的其余部分將被忽略。數(shù)值轉(zhuǎn)換將前面步驟讀入的這些數(shù)字轉(zhuǎn)換為整數(shù)即123-1230032-32。如果沒有讀入數(shù)字則整數(shù)為0。必要時更改符號從步驟 2 開始。溢出截斷如果整數(shù)數(shù)超過 32 位有符號整數(shù)范圍 $[?2^{31}, 2^{31} ? 1]$需要截斷這個整數(shù)使其保持在這個范圍內(nèi)。具體來說小于 $?2^{31}$ 的整數(shù)應該被固定為 $?2^{31}$大于 $2^{31} ? 1$ 的整數(shù)應該被固定為 $2^{31} ? 1$。返回結(jié)果返回整數(shù)作為最終結(jié)果。可以提煉出一個判斷要點只有前導空格 可選正負號 連續(xù)數(shù)字這一前綴模式才能被合法解析一旦前綴中出現(xiàn)非數(shù)字字符字母、點號等解析立即終止若第一個非空格字符本身就不是合法起始字符則直接返回0。示例逐步解析文檔中給出了兩個關(guān)鍵示例用插入符號^標記當前讀取位置直觀展示了算法逐字符推進的過程。示例 1正數(shù)基礎場景輸入s 42 輸出42第 1 步42當前沒有讀入字符因為沒有前導空格第 2 步42當前沒有讀入字符因為這里不存在-或符號默認為正第 3 步讀入42解析得到整數(shù)42。由于42在范圍 $[-2^{31}, 2^{31} - 1]$ 內(nèi)最終結(jié)果為42。示例 2前導空格與負號場景輸入s -42 輸出-42第 1 步 -42讀入前導空格但忽視掉第 2 步 -42讀入-字符所以結(jié)果應該是負數(shù)第 3 步 -42讀入42解析得到整數(shù)-42。由于-42在范圍內(nèi)最終結(jié)果為-42。解題思路單指針線性模擬模擬流程設計文檔給出的解法是直接模擬核心流程分五步先去除前后空格實際只需去除前導空格用lstrip()即可檢測正負號讀入數(shù)字并用字符串存儲數(shù)字結(jié)果將數(shù)字字符串轉(zhuǎn)為整數(shù)并根據(jù)正負號轉(zhuǎn)換整數(shù)結(jié)果判斷整數(shù)范圍并返回最終結(jié)果。完整代碼實現(xiàn)以下是題解文檔中的完整參考實現(xiàn)class Solution: def myAtoi(self, s: str) - int: num_str positive True start 0 s s.lstrip() if not s: return 0 if s[0] -: positive False start 1 elif s[0] : positive True start 1 elif not s[0].isdigit(): return 0 for i in range(start, len(s)): if s[i].isdigit(): num_str s[i] else: break if not num_str: return 0 num int(num_str) if not positive: num -num return max(num, -2 ** 31) else: return min(num, 2 ** 31 - 1)代碼關(guān)鍵點逐行解讀前導空格處理s.lstrip()只移除開頭的空格字符與題意空白字符只包括空格嚴格對應。若去除后字符串為空原串為空或全為空格直接返回0。符號識別判斷s[0]為-時置positive False并從下標1開始讀數(shù)字為時保持正號同樣從下標1開始既非正負號又非數(shù)字如字母a、點號.立即返回0。這里需要注意符號之后必須緊跟數(shù)字才有效如果s[0]是符號但s[1]不是數(shù)字后續(xù)循環(huán)不會讀入任何字符num_str為空最終也會返回0。例如a、- 都會正確返回0。連續(xù)數(shù)字讀取從start開始遍歷isdigit()為真則累加進num_str遇到第一個非數(shù)字字符立即break。這意味著4193 with words會解析出4193而words and 987因首個字符不是數(shù)字而返回0。無數(shù)字保護num_str為空說明沒有讀到任何數(shù)字返回0覆蓋-12、--42等無效符號組合。溢出截斷利用 Python 整數(shù)無位數(shù)限制的特性先做int()轉(zhuǎn)換再通過max(num, -2 ** 31)與min(num, 2 ** 31 - 1)分別鉗制下界與上界一次性完成負數(shù)下溢與正數(shù)上溢的截斷邏輯簡潔且無需預先判斷長度。邊界用例快速驗證輸入輸出處理要點4242基礎正數(shù) -42-42前導空格 負號4193 with words4193數(shù)字后遇到空格停止忽略其余words and 9870首字符非法直接返回 0-91283472332-2147483648下溢截斷為 $-2^{31}$912834723322147483647上溢截斷為 $2^{31}-1$0空串 0僅含空格-120符號后無數(shù)字003232前導零被int()自然消除-00負零結(jié)果為 0其中0032 - 32的效果由int(0032)自動完成無需手工處理前導零。復雜度分析時間復雜度$O(n)$其中 $n$ 是字符串s的長度。整個流程只對字符串做一次從左到右的線性掃描lstrip()與數(shù)字讀取合計至多遍歷每個字符一次?？臻g復雜度$O(1)$。雖然代碼中用num_str暫存數(shù)字字符但從算法本身看只使用了常數(shù)級別的額外變量num_str、positive、start不隨輸入規(guī)模增長若追求極致也可直接邊掃描邊累加數(shù)值將空間嚴格降至 $O(1)$。倉庫中的同源變體LCR 192 把字符串轉(zhuǎn)換成整數(shù)值得一提的是這道題在《劍指 Offer》體系中有同源變體——LCR 192. 把字符串轉(zhuǎn)換成整數(shù) (atoi)二者算法思想完全一致僅在描述措辭與函數(shù)命名strToInt上有所不同。倉庫中的該題解給出了幾乎相同的模擬實現(xiàn)可作為對照練習class Solution: def strToInt(self, str: str) - int: num_str positive True start 0 s str.lstrip() if not s: return 0 if s[0] -: positive False start 1 elif s[0] : positive True start 1 elif not s[0].isdigit(): return 0 for i in range(start, len(s)): if s[i].isdigit(): num_str s[i] else: break if not num_str: return 0 num int(num_str) if not positive: num -num return max(num, -2 ** 31) else: return min(num, 2 ** 31 - 1)對比可見刷題時掌握一個版本的實現(xiàn)即可同時覆蓋 LeetCode 0008 與 LCR 192 兩道題目性價比很高。相關(guān)學習路徑字符串基礎概念、比較規(guī)則與存儲結(jié)構(gòu)可參考 04_01_string_basic.md全部題解索引見 00_05_solutions_list.md其中第 0008 題的完整題解位于 string-to-integer-atoi.md。小結(jié)字符串轉(zhuǎn)換整數(shù) (atoi) 是一道規(guī)則即算法的典型模擬題不需要復雜的數(shù)據(jù)結(jié)構(gòu)與高級算法拼的是對題意的精確拆解與邊界兜底。掌握去空格 → 判符號 → 連續(xù)取數(shù)字 → 轉(zhuǎn)整數(shù) → 溢出截斷這條主線配合isdigit()逐字符校驗與max/min鉗位技巧即可在面試中穩(wěn)定、快速地完成本題并順帶解決其劍指 Offer 變體。贊分享教程文檔知識庫【免費下載鏈接】AlgoNote??「算法通關(guān)手冊」從零開始的「算法與數(shù)據(jù)結(jié)構(gòu)」學習教程200 道「算法面試熱門題目」1000 道「LeetCode 題目解析」持續(xù)更新中項目地址https://gitcode.com/gh_mirrors/le/AlgoNote點擊查看免費下載相關(guān)推薦LeetCode-Go 題解 0008String to Integer (atoi)——Go 實現(xiàn) 32 位有符號整數(shù)字符串轉(zhuǎn)換LeetCode Go 題解 0008String to Integer atoi ——Go 實現(xiàn) 32 位有符號整數(shù)字符串轉(zhuǎn)換 導讀 本篇基于 LeetCo示例工程LeetCode 8. 字符串轉(zhuǎn)換整數(shù) (atoi) 全解字符處理、數(shù)字拼接與 32 位越界防護LeetCode-Book 精選 88 題LeetCode 8. 字符串轉(zhuǎn)換整數(shù) atoi 全解字符處理、數(shù)字拼接與 32 位越界防護LeetCode Book 精選 88 題 本篇技術(shù)指南基于示例工程LeetCode-Book 劍指 Offer 67把字符串轉(zhuǎn)換成整數(shù)atoi的邊界處理與三語言實現(xiàn)解析LeetCode Book 劍指 Offer 67把字符串轉(zhuǎn)換成整數(shù)atoi的邊界處理與三語言實現(xiàn)解析 導讀 本篇文章基于 LeetCode Book h示例工程上一篇GitHub Readme Stats行為驅(qū)動BDD測試框架集成下一篇WSA 怎么裝帶 Google Play 和 Magisk Root 的 Windows Android 子系統(tǒng)完整上手指南創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考 AlgoNote 題解：LeetCode 0008. 字符串轉(zhuǎn)換整數(shù) (atoi)——單指針模擬法與 32 位整數(shù)邊界處理全解析
教程文檔知識庫【免費下載鏈接】AlgoNote??「算法通關(guān)手冊」從零開始的「算法與數(shù)據(jù)結(jié)構(gòu)」學習教程200 道「算法面試熱門題目」1000 道「LeetCode 題目解析」持續(xù)更新中項目地址https://gitcode.com/gh_mirrors/le/AlgoNote點擊查看免費下載本篇文章基于「算法通關(guān)手冊」AlgoNote 倉庫中的 string-to-integer-atoi.md 題解文檔展開圍繞 LeetCode 第 0008 題「字符串轉(zhuǎn)換整數(shù) (atoi)」的完整算法規(guī)則、模擬實現(xiàn)、邊界條件與復雜度分析進行深入講解。讀完本文你將掌握如何用單指針線性掃描實現(xiàn)一個嚴格符合 C/Catoi語義的myAtoi(s)函數(shù)并能在面試中精準處理前導空格、正負號、非法字符與 32 位有符號整數(shù)溢出截斷等全部邊界場景。題目定位與背景本題是 LeetCode 熱題中的字符串模擬類經(jīng)典題在「算法通關(guān)手冊」中標記為字符串標簽、中等難度。它同時被收錄于倉庫的 面試 100 題列表 與 面試 200 題列表可見其在算法面試中的高頻地位。題目的核心難點不在于算法本身僅需一次線性掃描而在于對題意中繁瑣邊界規(guī)則的逐條精確還原這正是考察候選人對需求細節(jié)把控能力的經(jīng)典場景。題目大意與輸入約束給定一個字符串s要求實現(xiàn)myAtoi(s)函數(shù)使其能轉(zhuǎn)換成一個 32 位有符號整數(shù)類似 C/C 中的atoi函數(shù)。需要檢測有效性無法讀取時返回0。輸入與規(guī)則約束如下本題中的空白字符只包括空格字符 除前導空格或數(shù)字后的其余字符串外請勿忽略任何其他字符字符串長度滿足 $0 \le s.length \le 200$s由英文字母大寫和小寫、數(shù)字0-9、 、、-和.組成。之所以明確限定字符集與僅空格這一細節(jié)是因為真實的 Catoi在具體實現(xiàn)上存在平臺差異而本題將這些規(guī)則顯式固定下來避免了歧義——例如真實atoi可能把1.5解析為1而本題規(guī)定遇到第一個非數(shù)字字符即停止讀取.之后的內(nèi)容被忽略。函數(shù)算法規(guī)則六步流程官方算法描述是本題一切實現(xiàn)的規(guī)格說明書共六步任何解都必須逐條滿足丟棄前導空格讀入字符串并丟棄無用的前導空格。判定符號檢查下一個字符假設還未到字符末尾為正還是負號讀取該字符如果有。確定最終結(jié)果是負數(shù)還是正數(shù)。如果兩者都不存在則假定結(jié)果為正。連續(xù)讀入數(shù)字讀入下一個字符直到到達下一個非數(shù)字字符或到達輸入的結(jié)尾。字符串的其余部分將被忽略。數(shù)值轉(zhuǎn)換將前面步驟讀入的這些數(shù)字轉(zhuǎn)換為整數(shù)即123-1230032-32。如果沒有讀入數(shù)字則整數(shù)為0。必要時更改符號從步驟 2 開始。溢出截斷如果整數(shù)數(shù)超過 32 位有符號整數(shù)范圍 $[?2^{31}, 2^{31} ? 1]$需要截斷這個整數(shù)使其保持在這個范圍內(nèi)。具體來說小于 $?2^{31}$ 的整數(shù)應該被固定為 $?2^{31}$大于 $2^{31} ? 1$ 的整數(shù)應該被固定為 $2^{31} ? 1$。返回結(jié)果返回整數(shù)作為最終結(jié)果。可以提煉出一個判斷要點只有前導空格 可選正負號 連續(xù)數(shù)字這一前綴模式才能被合法解析一旦前綴中出現(xiàn)非數(shù)字字符字母、點號等解析立即終止若第一個非空格字符本身就不是合法起始字符則直接返回0。示例逐步解析文檔中給出了兩個關(guān)鍵示例用插入符號^標記當前讀取位置直觀展示了算法逐字符推進的過程。示例 1正數(shù)基礎場景輸入s 42 輸出42第 1 步42當前沒有讀入字符因為沒有前導空格第 2 步42當前沒有讀入字符因為這里不存在-或符號默認為正第 3 步讀入42解析得到整數(shù)42。由于42在范圍 $[-2^{31}, 2^{31} - 1]$ 內(nèi)最終結(jié)果為42。示例 2前導空格與負號場景輸入s -42 輸出-42第 1 步 -42讀入前導空格但忽視掉第 2 步 -42讀入-字符所以結(jié)果應該是負數(shù)第 3 步 -42讀入42解析得到整數(shù)-42。由于-42在范圍內(nèi)最終結(jié)果為-42。解題思路單指針線性模擬模擬流程設計文檔給出的解法是直接模擬核心流程分五步先去除前后空格實際只需去除前導空格用lstrip()即可檢測正負號讀入數(shù)字并用字符串存儲數(shù)字結(jié)果將數(shù)字字符串轉(zhuǎn)為整數(shù)并根據(jù)正負號轉(zhuǎn)換整數(shù)結(jié)果判斷整數(shù)范圍并返回最終結(jié)果。完整代碼實現(xiàn)以下是題解文檔中的完整參考實現(xiàn)class Solution: def myAtoi(self, s: str) - int: num_str positive True start 0 s s.lstrip() if not s: return 0 if s[0] -: positive False start 1 elif s[0] : positive True start 1 elif not s[0].isdigit(): return 0 for i in range(start, len(s)): if s[i].isdigit(): num_str s[i] else: break if not num_str: return 0 num int(num_str) if not positive: num -num return max(num, -2 ** 31) else: return min(num, 2 ** 31 - 1)代碼關(guān)鍵點逐行解讀前導空格處理s.lstrip()只移除開頭的空格字符與題意空白字符只包括空格嚴格對應。若去除后字符串為空原串為空或全為空格直接返回0。符號識別判斷s[0]為-時置positive False并從下標1開始讀數(shù)字為時保持正號同樣從下標1開始既非正負號又非數(shù)字如字母a、點號.立即返回0。這里需要注意符號之后必須緊跟數(shù)字才有效如果s[0]是符號但s[1]不是數(shù)字后續(xù)循環(huán)不會讀入任何字符num_str為空最終也會返回0。例如a、- 都會正確返回0。連續(xù)數(shù)字讀取從start開始遍歷isdigit()為真則累加進num_str遇到第一個非數(shù)字字符立即break。這意味著4193 with words會解析出4193而words and 987因首個字符不是數(shù)字而返回0。無數(shù)字保護num_str為空說明沒有讀到任何數(shù)字返回0覆蓋-12、--42等無效符號組合。溢出截斷利用 Python 整數(shù)無位數(shù)限制的特性先做int()轉(zhuǎn)換再通過max(num, -2 ** 31)與min(num, 2 ** 31 - 1)分別鉗制下界與上界一次性完成負數(shù)下溢與正數(shù)上溢的截斷邏輯簡潔且無需預先判斷長度。邊界用例快速驗證輸入輸出處理要點4242基礎正數(shù) -42-42前導空格 負號4193 with words4193數(shù)字后遇到空格停止忽略其余words and 9870首字符非法直接返回 0-91283472332-2147483648下溢截斷為 $-2^{31}$912834723322147483647上溢截斷為 $2^{31}-1$0空串 0僅含空格-120符號后無數(shù)字003232前導零被int()自然消除-00負零結(jié)果為 0其中0032 - 32的效果由int(0032)自動完成無需手工處理前導零。復雜度分析時間復雜度$O(n)$其中 $n$ 是字符串s的長度。整個流程只對字符串做一次從左到右的線性掃描lstrip()與數(shù)字讀取合計至多遍歷每個字符一次?？臻g復雜度$O(1)$。雖然代碼中用num_str暫存數(shù)字字符但從算法本身看只使用了常數(shù)級別的額外變量num_str、positive、start不隨輸入規(guī)模增長若追求極致也可直接邊掃描邊累加數(shù)值將空間嚴格降至 $O(1)$。倉庫中的同源變體LCR 192 把字符串轉(zhuǎn)換成整數(shù)值得一提的是這道題在《劍指 Offer》體系中有同源變體——LCR 192. 把字符串轉(zhuǎn)換成整數(shù) (atoi)二者算法思想完全一致僅在描述措辭與函數(shù)命名strToInt上有所不同。倉庫中的該題解給出了幾乎相同的模擬實現(xiàn)可作為對照練習class Solution: def strToInt(self, str: str) - int: num_str positive True start 0 s str.lstrip() if not s: return 0 if s[0] -: positive False start 1 elif s[0] : positive True start 1 elif not s[0].isdigit(): return 0 for i in range(start, len(s)): if s[i].isdigit(): num_str s[i] else: break if not num_str: return 0 num int(num_str) if not positive: num -num return max(num, -2 ** 31) else: return min(num, 2 ** 31 - 1)對比可見刷題時掌握一個版本的實現(xiàn)即可同時覆蓋 LeetCode 0008 與 LCR 192 兩道題目性價比很高。相關(guān)學習路徑字符串基礎概念、比較規(guī)則與存儲結(jié)構(gòu)可參考 04_01_string_basic.md全部題解索引見 00_05_solutions_list.md其中第 0008 題的完整題解位于 string-to-integer-atoi.md。小結(jié)字符串轉(zhuǎn)換整數(shù) (atoi) 是一道規(guī)則即算法的典型模擬題不需要復雜的數(shù)據(jù)結(jié)構(gòu)與高級算法拼的是對題意的精確拆解與邊界兜底。掌握去空格 → 判符號 → 連續(xù)取數(shù)字 → 轉(zhuǎn)整數(shù) → 溢出截斷這條主線配合isdigit()逐字符校驗與max/min鉗位技巧即可在面試中穩(wěn)定、快速地完成本題并順帶解決其劍指 Offer 變體。贊分享教程文檔知識庫【免費下載鏈接】AlgoNote??「算法通關(guān)手冊」從零開始的「算法與數(shù)據(jù)結(jié)構(gòu)」學習教程200 道「算法面試熱門題目」1000 道「LeetCode 題目解析」持續(xù)更新中項目地址https://gitcode.com/gh_mirrors/le/AlgoNote點擊查看免費下載相關(guān)推薦LeetCode-Go 題解 0008String to Integer (atoi)——Go 實現(xiàn) 32 位有符號整數(shù)字符串轉(zhuǎn)換LeetCode Go 題解 0008String to Integer atoi ——Go 實現(xiàn) 32 位有符號整數(shù)字符串轉(zhuǎn)換 導讀 本篇基于 LeetCo示例工程LeetCode 8. 字符串轉(zhuǎn)換整數(shù) (atoi) 全解字符處理、數(shù)字拼接與 32 位越界防護LeetCode-Book 精選 88 題LeetCode 8. 字符串轉(zhuǎn)換整數(shù) atoi 全解字符處理、數(shù)字拼接與 32 位越界防護LeetCode Book 精選 88 題 本篇技術(shù)指南基于示例工程LeetCode-Book 劍指 Offer 67把字符串轉(zhuǎn)換成整數(shù)atoi的邊界處理與三語言實現(xiàn)解析LeetCode Book 劍指 Offer 67把字符串轉(zhuǎn)換成整數(shù)atoi的邊界處理與三語言實現(xiàn)解析 導讀 本篇文章基于 LeetCode Book h示例工程上一篇GitHub Readme Stats行為驅(qū)動BDD測試框架集成下一篇WSA 怎么裝帶 Google Play 和 Magisk Root 的 Windows Android 子系統(tǒng)完整上手指南創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考