Given two non-negative integers?num1?and?num2?represented as strings, return the product of?num1?and?num2, also represented as a string.
Note:You must not use any built-in BigInteger library or convert the inputs to integer directly.
Example 1:
Input:num1 = "2", num2 = "3"Output:"6"
Example 2:
Input:num1 = "123", num2 = "456"Output:"56088"
Constraints:
1 <= num1.length, num2.length <= 200
num1?and?num2?consist of digits only.
Both?num1?and?num2do not contain any leading zero, except the number?0?itself.
class Solution {
? ? public String multiply(String num1, String num2) {
? ? ? ? // 兩個長度為a, b的數(shù)字相乘, 結(jié)果程度不超過a+b. 比如99 * 99 < 100 * 100 = 10000
? ? ? ? // 0,1,2依次是最高位,第二高位,第三高位,以此類推
? ? ? ? // 比如 10400,對應(yīng)的下標(biāo)是
? ? ? ? //? ? ? 01234
? ? ? ? // 這樣的好處是轉(zhuǎn)換位字符串的時候不需要再倒序一遍
? ? ? ? char[] res = new char[num1.length() + num2.length()];
? ? ? ? // 用'0'初始化結(jié)果數(shù)組
? ? ? ? Arrays.fill(res, '0');? ? ?
? ? ? ? // 兩個數(shù)字當(dāng)前正在處理的位置, 位置0代表個位. 比如123, 第0位代表0
? ? ? ? // 為了方便理解,就不用i和j來推算出pos了
? ? ? ? int pos1 = -1;
? ? ? ? for (int i = num1.length() - 1; i >= 0; i--) {
? ? ? ? ? ? int d1 = num1.charAt(i) - '0';
? ? ? ? ? ? // 每次循環(huán)表示處理第一個數(shù)的高一位
? ? ? ? ? ? pos1++;
? ? ? ? ? ? // 每次內(nèi)層循環(huán),第二個數(shù)從新從個位開始算起
? ? ? ? ? ? int pos2 = -1;
? ? ? ? ? ? for (int j = num2.length() - 1; j >= 0; j--) {
? ? ? ? ? ? ? ? int d2 = num2.charAt(j) - '0';
? ? ? ? ? ? ? ? pos2++;
? ? ? ? ? ? ? ? // 個位數(shù)相乘, 結(jié)果不超過兩位
? ? ? ? ? ? ? ? int prod = d1 * d2;
? ? ? ? ? ? ? ? // 假如個位跟十位相乘, 結(jié)果的個位要放在最終結(jié)果的十位, 即 pos1 + pos2 = 0 + 1 = 1
? ? ? ? ? ? ? ? // 假如有10位, 現(xiàn)在要賦值給第0位, 則實際要操作的是第10位,即 10 - 0 = 10
? ? ? ? ? ? ? ? // 舉個例子, 12345, 現(xiàn)在要給十位加一,實際上要操作的下標(biāo)是 4 - 1 = 3
? ? ? ? ? ? ? ? res[res.length - 1 - (pos1 + pos2)] += prod % 10;
? ? ? ? ? ? ? ? // System.out.printf("res[%d] += %d \n", res.length - 1 - (pos1 + pos2),? prod % 10);
? ? ? ? ? ? ? ? // 結(jié)果的十位要再往高一位累加
? ? ? ? ? ? ? ? res[res.length - 1 - (pos1 + pos2 + 1)] += prod / 10;
? ? ? ? ? ? ? ? // System.out.printf("res[%d] += %d \n", res.length - 1 - (pos1 + pos2 + 1), prod / 10);
? ? ? ? ? ? ? ? // 進(jìn)位先不管, 最后再統(tǒng)一處理
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? // 從十位開始統(tǒng)一往后處理進(jìn)位; 最低為和最高位肯定沒有進(jìn)位, 所以不處理
? ? ? ? for (int i = res.length - 2; i >= 1; i--) {
? ? ? ? ? ? if (res[i] - '0' >= 10) {
? ? ? ? ? ? ? ? res[i - 1] += (res[i] - '0') / 10;
? ? ? ? ? ? ? ? res[i] = (char)(((res[i] - '0') % 10) + '0');
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? // 最后把前面的0除掉, 但是最后一位肯定是要保留的(全0的情況)
? ? ? ? int left = 0;
? ? ? ? for (; left < res.length - 1; left++) {
? ? ? ? ? ? if (res[left] != '0') break;
? ? ? ? }
? ? ? ? // debug: 輸出數(shù)組看看
? ? ? ? // for (char c : res) System.out.println((int)(c - '0'));
? ? ? ? // 比如00511, left=2, 實際長度位3, 即 res.length - left = 5 - 2 = 3
? ? ? ? //? ? 01234
? ? ? ? return new String(res, left, res.length - left);
? ? }
}
