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

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

最近有一位明星挺火的，因為在他的直播間送車，導致很多人到他直播間觀看，在線人數已經超過了10萬，具體有多少人看過就不知道了，但點贊人數直接超出了 int 的最大值，溢出了，變成了負數 -1669450377 。

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

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

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

問題描述

來源：LeetCode第415題

難度：中等

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

示例1：

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

示例2：

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

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

• num1 和num2 都只包含數字 0-9

• num1 和num2 都不包含任何前導零

問題分析

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

如果某一位沒有數字我們就默認它是 0 ，如下圖所示，第一個數字的千位是 2 ，而第二個數字只有兩位數，我們就默認它的千位是 0 ，就這樣相加。因為是從個位相加，最后還需要把相加的結果進行反轉即可。

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();//對字符串反轉
}

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());// 對字符串反轉
        return s;
    }

筆者簡介

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