Multiply Strings (M)
題目
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Example 1:
Input: num1 = "2", num2 = "3"
Output: "6"
Example 2:
Input: num1 = "123", num2 = "456"
Output: "56088"
Note:
- The length of both
num1andnum2is < 110. - Both
num1andnum2contain only digits0-9. - Both
num1andnum2do not contain any leading zero, except the number 0 itself. - You must not use any built-in BigInteger library or convert the inputs to integer directly.
題意
不使用內建庫實作大數乘法，
思路
- m位數乘n位數得到的積最大位數為m+n，直接開一個m+n大的陣列來存盤積的每一位數；
- num1中i位置的數與num2中j位置的數相乘，所得積在新陣列中的位置為i+j+1(位置i+j是留給進位的)，每次計算積后累加在對應位置，可以先不考慮進位，之后再處理；
- 從右向左遍歷新陣列，處理進位；
- 將新陣列轉化為字串，(注意第一個元素為0的情況)
代碼實作
Java
class Solution {
public String multiply(String num1, String num2) {
if (num1.equals("0") || num2.equals("0")) {
return "0";
}
int[] array = new int[num1.length() + num2.length()];
for (int i = 0; i < num1.length(); i++) {
for (int j = 0; j < num2.length(); j++) {
int x = num1.charAt(i) - '0';
int y = num2.charAt(j) - '0';
array[i + j + 1] += x * y;
}
}
int carry = 0;
for (int i = array.length - 1; i >= 0; i--) {
int sum = array[i] + carry;
array[i] = sum % 10;
carry = sum / 10;
}
StringBuilder sb = new StringBuilder();
// 第一個為0則不加入字串中
for (int i = array[0] == 0 ? 1 : 0; i < array.length; i++) {
sb.append((char) (array[i] + '0'));
}
return sb.toString();
}
}
JavaScript
/**
* @param {string} num1
* @param {string} num2
* @return {string}
*/
var multiply = function (num1, num2) {
if (num1 === '0' || num2 === '0') {
return '0'
}
let product = new Array(num1.length + num2.length).fill(0)
for (let i = 0; i < num1.length; i++) {
for (let j = 0; j < num2.length; j++) {
product[i + j + 1] += num1[i] * num2[j]
}
}
for (let i = product.length - 1; i >= 0; i--) {
if (i > 0 && product[i] >= 10) {
product[i - 1] += Math.trunc(product[i] / 10)
product[i] %= 10
}
}
if (product[0] === 0) {
product = product.slice(1)
}
return product.join('')
}
參考
Black_Knight - LeetCode 43. Multiply Strings
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/36585.html
標籤：其他