码疯窝

LeetCode 每日一题 — Multiply Strings

2014/12/30 11:54:49    分类: 日志连载    0人评论 次浏览

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.

算法分析: 算乘法, 方案是放入array, 然后一位一位的乘, 再去判断进位

Java:

public class Solution {
    public String multiply(String num1, String num2) {
        if (num1 == null || num2 == null)
            return null;
        if (num1.equals("0") || num2.equals("0"))
            return "0";
        
        int nl1 = num1.length();
        int nl2 = num2.length();
        int nlt = nl1 + nl2;
        char[] cnum1 = num1.toCharArray();
        char[] cnum2 = num2.toCharArray();
        int rst[] = new int[nlt];
        int i = 0;
        int p = 0;
        for (i = 0; i < nl1; i++) {
            for (p = 0; p < nl2; p++) {
                rst[i + p] = rst[i + p] + (cnum1[i] - '0') * (cnum2[p] - '0');   
            }
        }
        int carry = 0;
        for (i = nlt - 1; i >= 0; i--) {
            if (carry > 0) {
                rst[i] += carry;
                carry = 0;
            }
            if (rst[i] > 9) {
                carry = rst[i] / 10;
                rst[i] = rst[i] % 10;
            }
            if (i != nlt - 1)
                rst[i + 1] = rst[i];
        }
        rst[0] = carry;
        StringBuffer sb = new StringBuffer();
        
        for (i = 0; i < nlt; i++) {
            if (i == 0 && rst[0] == 0)
                continue;
            sb.append(rst[i]);
        }
        String r = sb.toString();
        i = 0;
        while(r.charAt(i) == '0') 
            i++;
        return r.substring(i);
        
    }
}

C++:

 

Python:

class Solution:
    # @param num1, a string
    # @param num2, a string
    # @return a string
    def multiply(self, num1, num2):
        if (num1 == None or num2 == None):
            return None
        if (num1 == '0' or num2 == '0'):
            return '0'
        nl1 = len(num1)
        nl2 = len(num2)
        nlt = nl1 + nl2
        rst = []
        for i in range(nlt):
            rst.append(0)
        for i in range(nl1):
            for p in range(nl2):
                rst[i + p] += int(num1[i]) * int(num2[p])
        carry = 0
        i = nlt - 1
        while (i >=0):
            if (carry > 0):
                rst[i] += carry
                carry = 0
            if (rst[i] > 9):
                carry = rst[i] / 10
                rst[i] %= 10
            if (i != nlt - 1):
                rst[i + 1] = rst[i]
            i -= 1
        rst[0] = carry
            
        
        r = ''
        for i in range(nlt):
            if (i == 0 and rst[0] == 0):
                continue
            r += str(rst[i])
        return r
继续查看有关 日志连载的文章

0个访客评论