力ボタンブラシ問題43.文字列乗算(Java)
8823 ワード
タイトル
文字列形式で表される非負の整数num 1とnum 2の2つを与え、num 1とnum 2の積を返し、それらの積も文字列形式で表される.
例1:
入力:num 1="2"、num 2="3"出力:"6"例2:
入力:num 1="123"、num 2="456"出力:"56088"説明:
num 1およびnum 2の長さは110未満である.num 1とnum 2には0-9の数字しか含まれていません.num 1およびnum 2は、数値0自体でない限り、ゼロで始まることはありません.BigIntegerなどの標準ライブラリの大数タイプや、入力を直接整数に変換して処理することはできません.
構想
アナログディジタル乗算の演算過程は,時間複雑度O(M*N)MNがそれぞれ2文字列の長さであり,空間複雑度はO(M+N)である.各人は乗算して比較する必要があります.
に答える
文字列形式で表される非負の整数num 1とnum 2の2つを与え、num 1とnum 2の積を返し、それらの積も文字列形式で表される.
例1:
入力:num 1="2"、num 2="3"出力:"6"例2:
入力:num 1="123"、num 2="456"出力:"56088"説明:
num 1およびnum 2の長さは110未満である.num 1とnum 2には0-9の数字しか含まれていません.num 1およびnum 2は、数値0自体でない限り、ゼロで始まることはありません.BigIntegerなどの標準ライブラリの大数タイプや、入力を直接整数に変換して処理することはできません.
構想
アナログディジタル乗算の演算過程は,時間複雑度O(M*N)MNがそれぞれ2文字列の長さであり,空間複雑度はO(M+N)である.各人は乗算して比較する必要があります.
に答える
class Solution {
public String multiply(String num1, String num2) {
if(num1.equals("0") || num2.equals("0")) return "0";
int len = num1.length()+num2.length(),flag = 0;
int[] data = new int[len];
StringBuilder res = new StringBuilder();
for (int i = num1.length()-1; i >=0 ; i--) {
for (int j = num2.length()-1; j >=0 ; j--) {
data[i+j+1] += (num1.charAt(i) -'0')*(num2.charAt(j)-'0');
if(data[i+j+1]>=10){
int tmp = data[i+j+1];
data[i+j+1] = tmp%10; //
data[i+j] += tmp/10; //
}
}
}
// 0
int k = 0;
for (; k < len; k++) {
if (data[k] != 0) break;
}
//
while(k<len) res.append(data[k++]);
return res.toString();
}
}