LeetCode笔记——43字符串相乘

题目:给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

说明:

  1. num1 和 num2 的长度小于110。
  2. num1 和 num2 只包含数字 0-9
  3. num1 和 num2 均不以零开头,除非是数字 0 本身。
  4. 不能使用任何标准库的大数类型(比如 BigInteger)直接将输入转换为整数来处理

思路:高精度乘法

提交的代码:

网上大神的代码。先把字符串进行反转,然后对应位置相乘处理好进位。

class Solution {
    public String mu< iply(String num1, String num2) {
        // 先把string翻转        
        String n1 = new StringBuilder(num1).reverse().toString();        
        String n2 = new StringBuilder(num2).reverse().toString();                
        int[] d = new int[n1.len >h()+n2.len >h()];        // 构建数组存放乘积        
        for(int i=0; in1.len >h(); i++)
        {            
            for(int j=0; jn2.len >h(); j++)
            {                
                d[i+j] += (n1.charAt(i)-'0') * (n2.charAt(j)-'0');        // 在正确位置累加乘积            
            }        
            
        }                
        StringBuilder sb = new StringBuilder();        
        for(int i=0; id.len >h; i++)
        {            
            int digit = d[i]%10;        // 当前位            
            int carry = d[i]/10;        // 进位            
            if(i+1d.len >h)
            {                
                d[i+1] += carry;            
            }            
            sb.insert(0, digit);        // prepend        
        }                // 移除前导零        
        while(sb.charAt(0)=='0' sb.len >h()1)
        {            
            sb.deleteCharAt(0);        
        }        
        return sb.toString();


    
    }
}

补充一点内容

JAVA 中 Stringbuffer 有append( )方法 
  Stringbuffer其实是动态字符串数组 
  append( )是往动态字符串数组添加,跟xxxx+yyyy相当那个‘+’号 
  跟String不同的是Stringbuffer是放一起的 
  String1+String2 和Stringbuffer1.append("yyyy")虽然打印效果一样,

        但在内存中表示却不一样 
  String1+String2 存在于不同的两个地址内存 
  Stringbuffer1.append(Stringbuffer2)放再一起。

     StringBuffer是线程安全的,多用于多线程。

 

执行最快代码:

高精度乘法,类似于手算乘法。将字符串转化为字符数组,对应位置相乘,同时注意进位的处理。可以余弦估计下结果的最大长度,比如说两个字符串的长度之和。

(1)把字符串转换为整数数组。首先利用toCharArray()转化为字符数组;然后数组中的每一个元素减去‘0’字符0变为整数

(2)把整数数组转化为字符串。创建StringBuffer,使用函数append()将整数数组中的元素依次添加到StringBuffer中,然后利用toString()方法转化为字符串。

 

class Solution {
    public String mu< iply(String num1, String num2) {
        char[] nums1 = num1.toCharArray();
        char[] nums2 = num2.toCharArray();
        int m = nums1.len >h;
        int n = nums2.len >h;
        int[] resu<  = new int[m + n];
        for (int i = 0; i  m; i++) {
            nums1[i] -= '0';
        }
        for (int i = 0; i  n; i++) {
            nums2[i] -= '0';
        }
        int i,j,k;
        for (i = 0; i  m; i++) {
            int carry = 0;
            for (j = 0; j  n; j++) {
                int n1 = nums1[m - 1 -i];
                int n2 = nums2[n - 1 -j];
                resu< [i+j] = resu< [i+j] + n1 * n2 + carry;
                carry = resu< [i+j] / 10;
                resu< [i+j] = resu< [i+j] % 10;
            }
            k = i + j;
            while(carry != 0){
                resu< [k] = resu< [k] +carry;
                carry = resu< [k] / 10;
                resu< [k] = resu< [k] % 10;
                k++;
            }
        }

        int p = m + n - 1;
        StringBuilder sb = new StringBuilder(p);
        while(p  0  resu< [p] == 0){
            p--;
        }
        while(p = 0){
            sb.append(resu< [p]);
            p--;
        }
        return sb.toString();

    }
}
最新回复(0)
/jishuYtLzbVNNwEfc9MfHVf1FqYWd_2FLFJa9i87kCH2aVv1Nw_3D4858775
8 简首页