專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

專欄：50多種經(jīng)典圖論算法全部掌握

最近有一位明星挺火的，因?yàn)樵谒闹辈ラg送車，導(dǎo)致很多人到他直播間觀看，在線人數(shù)已經(jīng)超過了10萬，具體有多少人看過就不知道了，但點(diǎn)贊人數(shù)直接超出了 int 的最大值，溢出了，變成了負(fù)數(shù) -1669450377 。

我們知道抖音屬于字節(jié)旗下的，而字節(jié)一直以來因?yàn)橄矚g面試算法難題，被網(wǎng)友調(diào)侃為宇宙條。所以這種低級錯誤實(shí)在是不應(yīng)該犯，解決方式也很簡單，一種就是把 int 類型變成 long 類型（C++中可以換成long long），還一種方式就是使用字符串，先不考慮性能的問題，下面我們來看下使用字符串兩個數(shù)是怎么相加的。

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

來看下今天的算法題，這題是LeetCode的第415題：字符串相加。

問題描述

來源：LeetCode第415題

難度：中等

給定兩個字符串形式的非負(fù)整數(shù) num1 和num2 ，計(jì)算它們的和并同樣以字符串形式返回。你不能使用任何內(nèi)建的用于處理大整數(shù)的庫（比如 BigInteger）， 也不能直接將輸入的字符串轉(zhuǎn)換為整數(shù)形式。

示例1：

輸入：num1 = "11", num2 = "123" 輸出："134"

示例2：

輸入：num1 = "456", num2 = "77" 輸出："533"

• 1 <= num1.length, num2.length <= 10^4

• num1 和num2 都只包含數(shù)字 0-9

• num1 和num2 都不包含任何前導(dǎo)零

問題分析

我們知道加法是從個位加起的，我們可以使用兩個指針，剛開始的時候兩個指針分別指向兩個字符串最右邊的字符。還要使用一個變量carry來記錄進(jìn)位的值，因?yàn)閮蓚€數(shù)相加最多只能進(jìn)一位，所以carry要么是 0 要么是 1 。

如果某一位沒有數(shù)字我們就默認(rèn)它是 0 ，如下圖所示，第一個數(shù)字的千位是 2 ，而第二個數(shù)字只有兩位數(shù)，我們就默認(rèn)它的千位是 0 ，就這樣相加。因?yàn)槭菑膫€位相加，最后還需要把相加的結(jié)果進(jìn)行反轉(zhuǎn)即可。

JAVA：

public String addStrings(String num1, String num2) {
    StringBuilder s = new StringBuilder();
    int i = num1.length() - 1, j = num2.length() - 1, carry = 0;
    while (i >= 0 || j >= 0 || carry != 0) {
        int x = i < 0 ? 0 : num1.charAt(i--) - '0';
        int y = j < 0 ? 0 : num2.charAt(j--) - '0';
        int sum = x + y + carry;
        s.append(sum % 10);// 添加到字符串尾部
        carry = sum / 10;
    }
    return s.reverse().toString();//對字符串反轉(zhuǎn)
}

C++：

public:
    string addStrings(string num1, string num2) {
        string s;
        int i = num1.length() - 1, j = num2.length() - 1, carry = 0;
        while (i >= 0 || j >= 0 || carry != 0) {
            int x = i < 0 ? 0 : num1[i--] - '0';
            int y = j < 0 ? 0 : num2[j--] - '0';
            int sum = x + y + carry;
            s += to_string(sum % 10);// 添加到字符串尾部
            carry = sum / 10;
        }
        reverse(s.begin(), s.end());// 對字符串反轉(zhuǎn)
        return s;
    }

筆者簡介

博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個算法網(wǎng)站中累計(jì)做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨(dú)特的解題思路和解題技巧，喜歡的可以給個關(guān)注，也可以 下載我整理的1000多頁的PDF算法文檔 。