摘要：題目要求將兩個(gè)形式的數(shù)字相乘的結(jié)果用的形式返回。不準(zhǔn)使用以外的形式來(lái)記錄數(shù)字。假設(shè)，則將結(jié)果的十位和個(gè)位分別放在數(shù)組下標(biāo)為和的位置上。存儲(chǔ)的位置等同于上一思路。然后再通過(guò)一輪遍歷將進(jìn)位處理一下。

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

 1. The length of both num1 and num2 is < 110. 
 2. Both num1 and num2 contains only digits 0-9.
 3. Both num1 and num2 does not contain any
    leading zero. 
 4. You must not use any built-in BigInteger library or
    convert the inputs to integer directly.
    
    

將兩個(gè)String形式的數(shù)字相乘的結(jié)果用String的形式返回。不準(zhǔn)使用Int（java）以外的形式來(lái)記錄數(shù)字。

通過(guò)隊(duì)列存儲(chǔ)每一輪計(jì)算的結(jié)果。進(jìn)行下一輪計(jì)算的時(shí)候，將上一輪的值deque出來(lái)加到當(dāng)前的值上。

    public String multiply(String num1, String num2) {
        if(num1.equals("0") || num2.equals("0")){
            return "0";
        }
        
        StringBuilder result = new StringBuilder();
        //使用鏈表的方式實(shí)現(xiàn)隊(duì)列
        LinkedList queue = new LinkedList();
        int count = 0;
        //將隊(duì)尾的0添加到結(jié)果值中，并消去結(jié)尾的結(jié)果值
        if(num1.endsWith("0")){
            for(int i = num1.length() - 1 ; i>=0 ; i--){
                if(num1.charAt(i) == "0"){
                    count++;
                    result.append("0");
                }else{
                    break;
                }
            }
            num1 = num1.substring(0, num1.length()-count);
        }
        
        count = 0;
        if(num2.endsWith("0")){
            for(int i = num2.length() - 1 ; i>=0 ; i--){
                if(num2.charAt(i) == "0"){
                    count++;
                    result.append("0");
                }else{
                    break;
                }
            }
            num2 = num2.substring(0, num2.length()-count);
        }
        
        
        for(int i = num1.length()-1 ; i>=0 ; i--){    
            //乘數(shù)的值，如果乘數(shù)為0，則直接將上一輪的值添加到結(jié)果值
            int number1 = num1.charAt(i) - "0";
            if(number1 == 0){
                result.append(queue.removeFirst());
                //補(bǔ)進(jìn)位0
                queue.add(0);
                continue;
            }
            int carry = 0;
            for(int j = num2.length()-1 ; j>=0 ; j--){
                //被乘數(shù)的值
                int number2 = num2.charAt(j) - "0";
                //第一輪無(wú)需考慮上一輪的進(jìn)位
                int currentVal = number1 * number2 + carry + (i==num1.length()-1?0:queue.removeFirst());
                //如果是這一輪的末尾，直接將值添加到結(jié)果值中
                if(j== num2.length()-1){
                    result.append(currentVal % 10);
                }else{
                    queue.add(currentVal % 10);
                }
                carry = currentVal/10;
            }
            queue.add(carry);
            carry = 0;
        }
        while(!queue.isEmpty() && queue.getLast() == 0){
            queue.removeLast();
        }
        //將隊(duì)列中的非零開(kāi)頭的進(jìn)位添加到結(jié)果中
        while(!queue.isEmpty()){
            result.append(queue.removeFirst());
        }
        return result.reverse().toString();
        
    }

根據(jù)乘法計(jì)算的規(guī)則，我們可以判斷兩個(gè)值計(jì)算后應(yīng)該填到哪一個(gè)位置上。假設(shè)num1[i]*num2[j]，則將結(jié)果的十位和個(gè)位分別放在數(shù)組下標(biāo)為i+j和i+j+1的位置上。記得計(jì)算的時(shí)候要加上上一輪的進(jìn)位。

public String multiply(String num1, String num2) {
    int m = num1.length(), n = num2.length();
    int[] pos = new int[m + n];
   
    for(int i = m - 1; i >= 0; i--) {
        for(int j = n - 1; j >= 0; j--) {
            int mul = (num1.charAt(i) - "0") * (num2.charAt(j) - "0"); 
            int p1 = i + j, p2 = i + j + 1;
            int sum = mul + pos[p2];

            pos[p1] += sum / 10;
            pos[p2] = (sum) % 10;
        }
    }  
    
    StringBuilder sb = new StringBuilder();
    for(int p : pos) if(!(sb.length() == 0 && p == 0)) sb.append(p);
    return sb.length() == 0 ? "0" : sb.toString();
}

這里將每一位的計(jì)算結(jié)果都先存儲(chǔ)到當(dāng)前位置上，不管是否進(jìn)位。存儲(chǔ)的位置等同于上一思路。然后再通過(guò)一輪遍歷將進(jìn)位處理一下。

    public String multiply(String num1, String num2) {
       if(num1.isEmpty() || num2.isEmpty()) return "0";
        int m = num1.length(), n = num2.length();
        int[] ret = new int[m+n];
        
        for(int i = m-1; i >= 0; i--) {
            int n1 = num1.charAt(i)-"0";
            for(int j = n-1; j>=0; j--) {
                int n2 = num2.charAt(j)-"0";
                int mul = n1*n2;
                ret[i+j+1] += mul;
            }
        }
        
        int carryOver = 0;
        for(int i = ret.length-1; i>=0; i--) {
            ret[i]+=carryOver;
            carryOver = ret[i]/10;
            ret[i]%=10;
        }
        
        StringBuilder sb = new StringBuilder();
        for(int x : ret) {
            if(x == 0 && sb.length()==0) continue;
            sb.append(x);
        }
        return sb.length()==0?"0":sb.toString();
        
    }

想要了解更多開(kāi)發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~