最近在準(zhǔn)備算法面試的同學(xué)應(yīng)該都遇到過“大數(shù)相加”這類經(jīng)典問題。力扣LeetCode第 415 題“字符串相加”正是這類問題的典型代表。題目看似簡(jiǎn)單但能很好地考察我們對(duì)字符串操作、進(jìn)位處理以及邊界條件的把控能力。很多同學(xué)在初次嘗試時(shí)容易在字符與數(shù)字轉(zhuǎn)換、循環(huán)終止條件或最高位進(jìn)位等細(xì)節(jié)上出錯(cuò)。本文將圍繞力扣 415. 字符串相加這道題從題目解析、思路分析、代碼實(shí)現(xiàn)到復(fù)雜度分析進(jìn)行一次完整的拆解。我們會(huì)提供多種語(yǔ)言Python, Java, JavaScript的清晰解法并深入探討其中的關(guān)鍵技巧和易錯(cuò)點(diǎn)。無論你是剛開始刷題的新手還是想鞏固基礎(chǔ)算法的同學(xué)都能從中獲得清晰的解題路徑和可復(fù)用的代碼模板。1. 題目背景與核心概念1.1 題目描述力扣第 415 題“字符串相加”的官方描述如下給定兩個(gè)字符串形式的非負(fù)整數(shù)num1和num2計(jì)算它們的和并以字符串形式返回。注意你不能使用任何內(nèi)建的用于處理大整數(shù)的庫(kù)比如BigInteger也不能直接將輸入的字符串轉(zhuǎn)換為整數(shù)形式。num1和num2的長(zhǎng)度都小于 5100。num1和num2都只包含數(shù)字0-9。num1和num2都不包含任何前導(dǎo)零除了數(shù)字0本身。示例 1輸入num1 11, num2 123 輸出134示例 2輸入num1 456, num2 77 輸出533示例 3輸入num1 0, num2 0 輸出01.2 問題本質(zhì)與考察點(diǎn)這道題的核心是模擬人工豎式加法的過程。我們從小學(xué)習(xí)的加法就是從個(gè)位開始逐位相加處理進(jìn)位最后得到結(jié)果。題目禁止使用大數(shù)庫(kù)和直接轉(zhuǎn)整數(shù)就是為了讓我們手動(dòng)實(shí)現(xiàn)這個(gè)過程。它主要考察以下幾個(gè)能力字符串的基本操作如何從字符串中按位取出數(shù)字。雙指針或索引的運(yùn)用如何從兩個(gè)字符串的末尾個(gè)位開始向前遍歷。進(jìn)位Carry的處理這是本題的核心邏輯需要仔細(xì)處理相加后進(jìn)位值的計(jì)算與傳遞。邊界條件處理包括兩個(gè)字符串長(zhǎng)度不同、最高位相加后產(chǎn)生新進(jìn)位如 “9” “1” “10”、以及輸入為 “0” 的情況。結(jié)果字符串的構(gòu)建由于我們從個(gè)位開始計(jì)算得到的結(jié)果數(shù)字順序是反的最后需要反轉(zhuǎn)。理解這些考察點(diǎn)是寫出健壯、高效代碼的關(guān)鍵。2. 環(huán)境準(zhǔn)備與解題思路2.1 解題環(huán)境說明對(duì)于算法題我們通常不需要復(fù)雜的項(xiàng)目環(huán)境。你只需要一個(gè)在線的力扣刷題平臺(tái)或者本地的代碼編輯器如 VS Code, PyCharm, IntelliJ IDEA。掌握一門編程語(yǔ)言的基礎(chǔ)語(yǔ)法本文以 Python, Java, JavaScript 為例。理解基本的字符串和數(shù)組操作。本文的代碼示例均假設(shè)在力扣的答題環(huán)境中運(yùn)行即你只需要實(shí)現(xiàn)Solution類中的特定方法。代碼可以直接復(fù)制到力扣的代碼編輯器中提交。2.2 核心算法思路豎式加法模擬解決此問題的通用思路可以分解為以下幾步初始化定義兩個(gè)指針i和j分別指向num1和num2的末尾即個(gè)位。定義一個(gè)變量carry來存儲(chǔ)進(jìn)位值初始為0。定義一個(gè)列表或StringBuilderres來存儲(chǔ)計(jì)算結(jié)果的每一位注意是逆序存儲(chǔ)的。循環(huán)計(jì)算只要i 0或j 0或carry ! 0就繼續(xù)循環(huán)。carry ! 0這個(gè)條件是為了處理最高位相加后仍有進(jìn)位的情況例如 “999” “1”。在循環(huán)體內(nèi) a. 獲取當(dāng)前位數(shù)字如果指針有效0則通過ord(num1[i]) - ord(0)或int(num1[i])等方式將字符轉(zhuǎn)為數(shù)字否則當(dāng)前位數(shù)字視為0。 b. 計(jì)算當(dāng)前位和sum digit1 digit2 carry。 c. 處理進(jìn)位和當(dāng)前位結(jié)果當(dāng)前位結(jié)果應(yīng)放入res為sum % 10。新的進(jìn)位carry sum // 10。 d. 將當(dāng)前位結(jié)果數(shù)字轉(zhuǎn)換為字符并添加到res中。 e. 移動(dòng)指針i--,j--。反轉(zhuǎn)并返回結(jié)果循環(huán)結(jié)束后res中存儲(chǔ)的是從個(gè)位到最高位的數(shù)字字符。需要將res反轉(zhuǎn)然后連接成一個(gè)字符串返回。流程圖示意開始 | 初始化 i, j, carry0, res[] | while (i0 或 j0 或 carry0): | digit1 num1[i] if i0 else 0 | digit2 num2[j] if j0 else 0 | total digit1 digit2 carry | carry total // 10 | res.append(str(total % 10)) | i--, j-- | 反轉(zhuǎn) res | 將 res 連接成字符串 | 返回字符串 結(jié)束3. 多語(yǔ)言代碼實(shí)現(xiàn)與逐行解析下面我們分別用 Python、Java 和 JavaScript 來實(shí)現(xiàn)上述算法并對(duì)關(guān)鍵代碼行進(jìn)行詳細(xì)解釋。3.1 Python 實(shí)現(xiàn)Python 的字符串操作非常靈活代碼也最為簡(jiǎn)潔。class Solution: def addStrings(self, num1: str, num2: str) - str: # 初始化指針和進(jìn)位 i, j len(num1) - 1, len(num2) - 1 carry 0 res [] # 使用列表存儲(chǔ)結(jié)果字符效率高于字符串拼接 # 循環(huán)條件任一字符串還有位或者還有進(jìn)位 while i 0 or j 0 or carry: # 獲取當(dāng)前位的數(shù)字如果指針已越界則視為0 digit1 int(num1[i]) if i 0 else 0 digit2 int(num2[j]) if j 0 else 0 # 計(jì)算當(dāng)前位的總和包括進(jìn)位 total digit1 digit2 carry # 計(jì)算新的進(jìn)位和當(dāng)前位的結(jié)果 carry total // 10 digit total % 10 # 將當(dāng)前位數(shù)字轉(zhuǎn)為字符并加入結(jié)果列表此時(shí)是逆序 res.append(str(digit)) # 移動(dòng)指針 i - 1 j - 1 # 將結(jié)果列表反轉(zhuǎn)并連接成字符串 # 因?yàn)槲覀兪前磦€(gè)位、十位...的順序添加的所以需要反轉(zhuǎn) return .join(res[::-1])代碼解析int(num1[i])Python 中可以直接將數(shù)字字符如5轉(zhuǎn)換為整數(shù)5。res []使用列表append操作來構(gòu)建結(jié)果其時(shí)間復(fù)雜度為 O(1)最后用join拼接。這比在循環(huán)中反復(fù)進(jìn)行字符串拼接str str效率高得多因?yàn)樽址?Python 中是不可變對(duì)象每次拼接都會(huì)生成新對(duì)象。while i 0 or j 0 or carry:這是循環(huán)的關(guān)鍵條件。or carry確保了即使兩個(gè)字符串都遍歷完了如果最后還有進(jìn)位如“1” “9”循環(huán)還會(huì)再進(jìn)行一次將進(jìn)位1作為最高位加入結(jié)果。res[::-1]這是 Python 的切片語(yǔ)法表示將列表res完全反轉(zhuǎn)。.join(...)將反轉(zhuǎn)后的字符列表連接成一個(gè)完整的字符串。3.2 Java 實(shí)現(xiàn)Java 的實(shí)現(xiàn)需要更多的手動(dòng)字符處理并通常使用StringBuilder來高效構(gòu)建字符串。class Solution { public String addStrings(String num1, String num2) { // 初始化指針和進(jìn)位 int i num1.length() - 1; int j num2.length() - 1; int carry 0; // 使用 StringBuilder 構(gòu)建結(jié)果效率高 StringBuilder res new StringBuilder(); // 循環(huán)條件任一字符串還有位或者還有進(jìn)位 while (i 0 || j 0 || carry 0) { // 獲取當(dāng)前位的數(shù)字如果指針已越界則視為0 int digit1 (i 0) ? num1.charAt(i) - 0 : 0; int digit2 (j 0) ? num2.charAt(j) - 0 : 0; // 計(jì)算當(dāng)前位的總和包括進(jìn)位 int sum digit1 digit2 carry; // 計(jì)算新的進(jìn)位 carry sum / 10; // 計(jì)算當(dāng)前位的結(jié)果 int digit sum % 10; // 將當(dāng)前位數(shù)字加入 StringBuilder此時(shí)是逆序 res.append(digit); // 移動(dòng)指針 i--; j--; } // 將結(jié)果反轉(zhuǎn)并轉(zhuǎn)換為字符串 // 因?yàn)?append 是順序添加我們得到的是個(gè)位在前所以需要反轉(zhuǎn) return res.reverse().toString(); } }代碼解析num1.charAt(i) - 0這是 Java 中將字符數(shù)字轉(zhuǎn)換為整數(shù)的經(jīng)典方法。字符‘0’到‘9’在 ASCII 表中是連續(xù)的‘0’的值是 48?！?’ - ‘0’的結(jié)果就是53 - 48 5。StringBuilder在 Java 中String是不可變的。在循環(huán)中拼接字符串會(huì)產(chǎn)生大量臨時(shí)對(duì)象影響性能。StringBuilder是可變的字符序列append操作效率很高。res.reverse().toString()StringBuilder的reverse()方法會(huì)原地反轉(zhuǎn)字符序列然后toString()將其轉(zhuǎn)換為String返回。循環(huán)條件carry 0與carry ! 0在此處等價(jià)因?yàn)檫M(jìn)位值carry只可能是 0 或 1兩個(gè)一位數(shù)相加最大為 99119進(jìn)位最大為1。但寫成carry 0更直觀。3.3 JavaScript 實(shí)現(xiàn)JavaScript 的實(shí)現(xiàn)思路與 Python 和 Java 類似注意其數(shù)字轉(zhuǎn)換和字符串構(gòu)建方式。/** * param {string} num1 * param {string} num2 * return {string} */ var addStrings function(num1, num2) { let i num1.length - 1; let j num2.length - 1; let carry 0; const res []; // 使用數(shù)組存儲(chǔ)結(jié)果數(shù)字 while (i 0 || j 0 || carry) { // 獲取當(dāng)前位的數(shù)字如果指針已越界則視為0 const digit1 i 0 ? parseInt(num1[i]) : 0; const digit2 j 0 ? parseInt(num2[j]) : 0; // 計(jì)算當(dāng)前位的總和包括進(jìn)位 const sum digit1 digit2 carry; // 計(jì)算新的進(jìn)位和當(dāng)前位的結(jié)果 carry Math.floor(sum / 10); const digit sum % 10; // 將當(dāng)前位數(shù)字加入數(shù)組此時(shí)是逆序 res.push(digit); // 移動(dòng)指針 i--; j--; } // 將數(shù)組反轉(zhuǎn)并連接成字符串 // 因?yàn)?push 是順序添加我們得到的是個(gè)位在前所以需要反轉(zhuǎn) return res.reverse().join(); };代碼解析parseInt(num1[i])JavaScript 中parseInt可以將字符串轉(zhuǎn)換為整數(shù)。num1[i]是一個(gè)字符parseInt(‘5’)得到5。也可以使用num1.charCodeAt(i) - ‘0’.charCodeAt(0)但parseInt更直觀。Math.floor(sum / 10)在 JavaScript 中除法/默認(rèn)返回浮點(diǎn)數(shù)。我們需要使用Math.floor來獲取整數(shù)商即進(jìn)位值。因?yàn)閮蓚€(gè)一位數(shù)相加最大為 19sum / 10的結(jié)果只能是 0 或 1Math.floor可以正確獲取。res.push(digit)和res.reverse().join(‘’)使用數(shù)組push方法添加元素最后反轉(zhuǎn)數(shù)組并用join方法拼接成字符串。這與 Python 的列表操作類似。4. 復(fù)雜度分析與算法評(píng)價(jià)4.1 時(shí)間復(fù)雜度我們使用了一個(gè)while循環(huán)循環(huán)的次數(shù)最多為max(len(num1), len(num2)) 11 是處理最高位進(jìn)位的情況。循環(huán)體內(nèi)的操作取數(shù)字、計(jì)算、追加字符都是常數(shù)時(shí)間O(1)。因此總的時(shí)間復(fù)雜度為O(max(N, M))其中 N 和 M 分別是兩個(gè)輸入字符串的長(zhǎng)度。這是一個(gè)非常高效的線性時(shí)間復(fù)雜度。4.2 空間復(fù)雜度我們使用了一個(gè)額外的列表/數(shù)組/StringBuilder 來存儲(chǔ)結(jié)果其長(zhǎng)度最多為max(N, M) 1。除了輸入和輸出我們只使用了幾個(gè)整型變量i,j,carry,digit1,digit2,sum。因此總的空間復(fù)雜度為O(max(N, M))主要用于存儲(chǔ)結(jié)果字符串。這是無法避免的因?yàn)槲覀儽仨毞祷匾粋€(gè)新的字符串。4.3 算法評(píng)價(jià)優(yōu)點(diǎn)直觀易懂完全模擬了人工計(jì)算加法的過程邏輯清晰。高效時(shí)間和空間復(fù)雜度都是線性的是最優(yōu)解。健壯正確處理了長(zhǎng)度不等、最高位進(jìn)位、全零輸入等邊界情況。缺點(diǎn)無明顯缺點(diǎn)是該問題的標(biāo)準(zhǔn)解法。5. 常見錯(cuò)誤與排查思路在實(shí)現(xiàn)“字符串相加”時(shí)初學(xué)者常會(huì)遇到以下幾個(gè)問題問題現(xiàn)象常見原因解決思路輸出結(jié)果比預(yù)期少一位例如 “99” “1” 輸出 “00”循環(huán)條件缺少對(duì)最后進(jìn)位的判斷。當(dāng)最高位相加產(chǎn)生進(jìn)位時(shí)循環(huán)在遍歷完字符串后即停止漏掉了進(jìn)位。將循環(huán)條件改為 while (i 0輸出結(jié)果順序是反的例如 “11” “123” 輸出 “431”忘記反轉(zhuǎn)結(jié)果。我們從個(gè)位開始計(jì)算并將結(jié)果依次存入列表得到的是逆序的字符串。在返回結(jié)果前務(wù)必對(duì)存儲(chǔ)結(jié)果的列表或StringBuilder進(jìn)行反轉(zhuǎn)操作。遇到非數(shù)字字符或空字符串時(shí)報(bào)錯(cuò)題目已保證輸入是合法數(shù)字字符串但自己測(cè)試時(shí)可能輸入錯(cuò)誤。代碼未做防御性檢查。對(duì)于生產(chǎn)代碼可以在開頭添加輸入驗(yàn)證。對(duì)于算法題通常信任題目約束。確保測(cè)試用例符合題目要求。在 Java 中使用String拼接導(dǎo)致性能極差在循環(huán)內(nèi)使用result digit result或result digit。每次操作都會(huì)創(chuàng)建新的String對(duì)象。務(wù)必使用StringBuilder來構(gòu)建字符串。JavaScript 中進(jìn)位計(jì)算錯(cuò)誤得到小數(shù)使用sum / 10直接賦值給carry在 JavaScript 中這會(huì)得到浮點(diǎn)數(shù)如 0.1。使用Math.floor(sum / 10)或~~(sum / 10)來獲取整數(shù)進(jìn)位。Python 中結(jié)果字符串包含方括號(hào)和逗號(hào)錯(cuò)誤地直接返回了列表res而不是拼接后的字符串。使用return .join(res[::-1])確保返回的是字符串。自檢清單循環(huán)條件是否包含了carry ! 0指針越界時(shí)當(dāng)前位數(shù)字是否正確地設(shè)為 0進(jìn)位carry的計(jì)算是否正確total // 10或sum / 10取整當(dāng)前位結(jié)果是否正確total % 10是否將數(shù)字轉(zhuǎn)換成了字符再存儲(chǔ)最終返回前是否反轉(zhuǎn)了結(jié)果序列對(duì)于輸入“0”和“0”是否能正確返回“0”而不是“”或[]6. 變種問題與最佳實(shí)踐掌握了“字符串相加”后你可以輕松解決一系列類似問題。同時(shí)遵循一些最佳實(shí)踐能讓你的代碼更健壯、更優(yōu)雅。6.1 相關(guān)變種問題力扣 2. 兩數(shù)相加這是“字符串相加”的鏈表版本。給你兩個(gè)非空鏈表表示兩個(gè)非負(fù)整數(shù)每位數(shù)字逆序存儲(chǔ)。你需要返回一個(gè)同樣形式的鏈表。解題思路完全一致只是數(shù)據(jù)結(jié)構(gòu)從字符串/數(shù)組變成了鏈表。力扣 67. 二進(jìn)制求和給你兩個(gè)二進(jìn)制字符串返回它們的和用二進(jìn)制表示。算法一模一樣只是把進(jìn)制從10改為2。計(jì)算進(jìn)位時(shí)carry sum // 2當(dāng)前位結(jié)果為sum % 2。大數(shù)相乘力扣 43. 字符串相乘這是更復(fù)雜的題目。核心思路是模擬豎式乘法但需要嵌套循環(huán)并處理好每一層部分積的累加和進(jìn)位。大數(shù)減法和除法思路類似但減法需要考慮借位處理起來比加法稍復(fù)雜。除法則是模擬豎式除法。6.2 代碼最佳實(shí)踐使用雙指針從末尾遍歷這是處理字符串/數(shù)組表示的數(shù)字計(jì)算的最標(biāo)準(zhǔn)模式。統(tǒng)一使用while (i 0 || j 0 || carry)作為循環(huán)條件這個(gè)條件最完備能覆蓋所有情況。使用列表/StringBuilder/數(shù)組存儲(chǔ)中間結(jié)果避免在循環(huán)中進(jìn)行字符串拼接這是保證算法效率的關(guān)鍵。清晰命名變量使用carry(進(jìn)位)、digit1/digit2(當(dāng)前位數(shù)字)、sum/total(總和)、res(結(jié)果) 等有意義的變量名提高代碼可讀性。添加注釋對(duì)于算法題清晰的注釋能幫助面試官快速理解你的思路尤其是在處理進(jìn)位和邊界條件的地方?？紤]邊界用例在寫完代碼后主動(dòng)測(cè)試以下用例“0” “0”“1” “9”(產(chǎn)生進(jìn)位)“999” “1”(多位數(shù)進(jìn)位)“123” “4567”(長(zhǎng)度不同)手動(dòng)模擬對(duì)于復(fù)雜的邊界條件可以在紙上或心里手動(dòng)模擬一遍算法流程確保邏輯正確。6.3 面試技巧如果這道題出現(xiàn)在面試中先溝通不要急于寫代碼。先向面試官?gòu)?fù)述題目確認(rèn)理解無誤例如數(shù)字是否非負(fù)是否可能為空。闡述思路說出你要模擬豎式加法使用雙指針從末尾開始用一個(gè)變量記錄進(jìn)位。邊寫邊講在寫代碼時(shí)解釋你在做什么“我現(xiàn)在初始化兩個(gè)指針和進(jìn)位變量…”“這個(gè)循環(huán)條件是為了處理最高位進(jìn)位…”。寫完測(cè)試寫完后用1-2個(gè)簡(jiǎn)單的例子如“11” “123”和1個(gè)邊界例子如“999” “1”來演示代碼運(yùn)行過程。分析復(fù)雜度主動(dòng)分析時(shí)間和空間復(fù)雜度并說明這是最優(yōu)解。7. 總結(jié)與擴(kuò)展學(xué)習(xí)力扣 415 題“字符串相加”是一道非常好的入門算法題它不涉及復(fù)雜的數(shù)據(jù)結(jié)構(gòu)但完整地考察了基本的編程能力循環(huán)、條件判斷、數(shù)據(jù)類型轉(zhuǎn)換、邊界處理以及字符串/數(shù)組操作。掌握它就掌握了解決所有“大數(shù)運(yùn)算”模擬題的基礎(chǔ)框架。核心要點(diǎn)回顧模擬人工計(jì)算從最低位末尾開始逐位相加處理進(jìn)位。循環(huán)條件三要素指針i, 指針j, 進(jìn)位carry缺一不可。高效構(gòu)建結(jié)果使用可變?nèi)萜鱌ython list, Java StringBuilder, JS Array存儲(chǔ)逆序結(jié)果最后反轉(zhuǎn)。小心邊界長(zhǎng)度不同的字符串、最高位的進(jìn)位、全零輸入。下一步學(xué)習(xí)建議鞏固嘗試獨(dú)立完成力扣 67. 二進(jìn)制求和和力扣 2. 兩數(shù)相加感受算法框架的復(fù)用性。挑戰(zhàn)嘗試解決力扣 43. 字符串相乘這是大數(shù)運(yùn)算的進(jìn)階版。拓展學(xué)習(xí)更多字符串相關(guān)的高頻題目如反轉(zhuǎn)字符串、驗(yàn)證回文串、字符串轉(zhuǎn)換整數(shù)等。系統(tǒng)訓(xùn)練將此類“模擬”算法歸入你的知識(shí)體系它通常與“數(shù)學(xué)”、“字符串”標(biāo)簽相關(guān)。在力扣上可以按標(biāo)簽或題目列表進(jìn)行專項(xiàng)練習(xí)。算法學(xué)習(xí)是一個(gè)循序漸進(jìn)的過程。從這道題出發(fā)理解其背后的“模擬”思想并能夠舉一反三你的解題能力就會(huì)穩(wěn)步提升。多寫、多練、多總結(jié)是通往算法高手的必經(jīng)之路。