大数运算(乘法&加法)

2020-08-13

给定两个字符串形式的非负整数num1 和num2，计算它们的和。
提示：

num1 和num2的长度都小于 5100
num1 和num2 都只包含数字0-9
num1 和num2 都不包含任何前导零
你不能使用任何內建 BigInteger 库，也不能直接将输入的字符串转换为整数形式

思路:模仿竖式相加的过程，巧妙运用carry解决进位的问题，主要注意最后一次进位，当carry不是0的时候，在append一个1

class Solution {
    public String addStrings(String num1, String num2) {
       int i = num1.length()-1;
		int j = num2.length()-1;
		int carry = 0;
		StringBuilder res = new StringBuilder();
		while(j>=0||i>=0) {
			int n1 = i>=0?num1.charAt(i)-'0':0;
			int n2 = j>=0?num2.charAt(j)-'0':0;
			int temp = n1+n2+carry;
			carry = temp/10;
			res.append(temp%10);
			i--;
			j--;
		}
		if(carry==0) {
			
			return res.reverse().toString();
		}
		return res.append(1).reverse().toString();
    }
}

给定两个以字符串形式表示的非负整数num1和num2，返回num1和num2的乘积，它们的乘积也表示为字符串形式。

示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例2:
输入: num1 = "123", num2 = "456"
输出: "56088"
说明：
num1和num2的长度小于110。
num1 和num2 只包含数字0-9。
num1 和num2均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理

思路:主要细节见注释:

class Solution {
    public  String multiply(String num1, String num2) {
        if(num1=="0"||num2=="0") {
			return "0";
		}
		int i = num1.length()-1;
		int j = num2.length()-1;
		String s = "0";
		String ans = null;
		int numOfZero = 0;//用于num1和num2的每一位相乘时错位相加
		while(j>=0) {
			StringBuilder res = new StringBuilder();
			int carry = 0;
			while(i>=0) {//num1和num2的每一位相乘
				int n1 = num1.charAt(i)-'0';
				int n2 = num2.charAt(j)-'0';
				int temp = n1*n2+carry;
				carry = temp/10;
				res.append(temp%10);
				i--;
			}
			//记得加上最后一个carry
			if(carry==0) {
				res = res.reverse();
			}else {
				res = res.append(carry+"").reverse();
			}
			//用于错位相加
			for(int k = 0;k<numOfZero;k++) {
				res = res.append("0");
			}
			ans = add(s, res.toString());
			s = ans;
			i = num1.length()-1;
			j--;
			numOfZero++;
		}
		return ans;
			
    }
	public  String add(String num1,String num2) {
		int i = num1.length()-1;
		int j = num2.length()-1;
		int carry = 0;
		StringBuilder res = new StringBuilder();
		while(j>=0||i>=0) {
			int n1 = i>=0?num1.charAt(i)-'0':0;
			int n2 = j>=0?num2.charAt(j)-'0':0;
			int temp = n1+n2+carry;
			carry = temp/10;
			res.append(temp%10);
			i--;
			j--;
		}
		if(carry==0) {
			
			return res.reverse().toString();
		}
		return res.append(1).reverse().toString();
	}
}