Multiply Strings, Leetcode 解题笔记

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

所谓的大整数乘法,因为数字不限长度,所以不能直接换成整数求解。怎么办呢,我们要先看一下乘法到底是怎么运算的:
181618228901716

如果我们把被乘数和乘数的每一位相乘,在一个新的array里记录下不进位的结果(红字),然后再处理进位问题。这个新array的长度最多不会超过num1和num2的长度之和。

除了以上的基本思路,还要注意处理前导0的问题,使得最后得到的string里的数不是以0开头的。

public class Solution {
    public String multiply(String num1, String num2) {
        
        int size = num1.length() + num2.length();
        int[] sum = new int[size];
        
        //每位相乘,注意index的规律,可以通过简单的几个例子总结出来。
        for(int i = 0; i < num1.length(); i++){
            for(int j = 0; j < num2.length(); j++){
                sum[sum.length-2-i-j] += (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
            }
        }
        
        //处理进位
        for(int i = 0; i < sum.length-1; i++){
            int carry = sum[i] / 10;
            sum[i] = sum[i] % 10;
            sum[i+1] += carry;
        }
        
        //处理前导0的问题
        int i = sum.length-1;
        while(sum[i] == 0 && i > 0) i--; 
        StringBuilder str = new StringBuilder();
        for(int q = i; q >=0; q--){
            str.append(sum[q]);
        }
        return str.toString();
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s