415. 字符串相加——【Leetcode每日一题】

墨蓝 2024-03-24 12:18 75阅读 0赞

### 415. 字符串相加 ###

给定两个字符串形式的非负整数 `num1` 和 `num2` ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 `BigInteger`）， 也不能直接将输入的字符串转换为整数形式。

##### 示例 1： #####

> 输入：num1 = “11”, num2 = “123”  
> 输出：“134”

##### 示例 2： #####

> 输入：num1 = “456”, num2 = “77”  
> 输出：“533”

##### 示例 3： #####

> 输入：num1 = “0”, num2 = “0”  
> 输出：“0”

##### 提示： #####

*   1 < = n u m 1. l e n g t h , n u m 2. l e n g t h < = 1 0 4 1 <= num1.length, num2.length <= 10^4 1<=num1.length,num2.length<=104
 *  num1 和 `num2` 都只包含数字 0-9
 *  `num1` 和 `num2` 都不包含任何前导零

#### 思路：(数学求和) ####

*  任意一位相加，要加三个数，分别为:
    
     *  `a` 的第 `i` 位，
     *  `b` 的第 `i` 位 ，
     *  以及前一位的进位 `carry`

#### 代码：(Java、C++) ####

Java

public class AddStrings {
        
    
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    		String num1 = "11";
    		String num2 = "123";
    		System.out.println(addStrings(num1, num2));
    	}
    	public static String addStrings(String num1, String num2) {
        
    		
    		StringBuilder str = new StringBuilder();
    		
    		int i = num1.length() - 1, j = num2.length() - 1, carry = 0;
    		while(i >= 0 || j >= 0|| carry == 1) {
        
    			if(i >= 0) {
        
    				carry += num1.charAt(i--) - '0';
    			}
    			if(j >= 0) {
        
    				carry += num2.charAt(j--) - '0';
    			}
    			str.append(carry % 10);
    			carry /= 10;
    		}
    		
    		return str.reverse().toString();
        }
    }

C++

#include <iostream>
    #include <string>
    #include <algorithm>
    
    using namespace std;
    
    class AddStrings {
        
    public:
    	string addStrings(string num1, string num2) {
        
    		string str;
    		int i = num1.size() - 1, j = num2.size() - 1, carry = 0;
    		while (i >= 0 || j >= 0 || carry == 1) 
    		{
        
    			if (i >= 0)
    			{
        
    				carry += num1[i--] - '0';
    			}
    			if (j >= 0)
    			{
        
    				carry += num2[j--] - '0';
    			}
    			str += carry % 10 + '0';
    			carry /= 10;
    
    		}
    		reverse(str.begin(), str.end());
    		return str;
    	}
    };
    
    int main() {
        
    
    	AddStrings a;
    
    	string b = "11";
    	string c = "123";
    
    	cout << a.addStrings(b,c) << endl;
    
    	system("pause");
    	return 0;
    }

##### 运行结果： #####

![在这里插入图片描述][8f801c246a8b492fb2c1d17b7259430a.png]

##### 复杂度分析： #####

*  **时间复杂度**： O ( n ) O(n) O(n)，n位字符串`a` 和 `b` 中长度最长的那个。
 *  **空间复杂度**： O ( 1 ) O(1) O(1)，除去答案所占用的空间，这里使用了常数个临时变量。

题目来源：[力扣。][Link 1]

##### 注：仅供学习参考， 如有不足，欢迎指正！ #####

[8f801c246a8b492fb2c1d17b7259430a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/75f9747efee2443eb91cf3f12bd3aa24.png
[Link 1]: https://leetcode.cn/problems/add-strings/description/