找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1764|回复: 2
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Multiply Strings】-【刷题第一弹】

[复制链接]

24

主题

9

精华

602

积分

超级会员

Rank: 4

积分
602
发表于 10-23-2014 06:04 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 MengMa 于 12-7-2014 12:51 AM 编辑

快捷通道:
https://oj.leetcode.com/problems/multiply-strings/


=========点击传送门查看所有题目哟========
                            汇总贴 传送门
==================================



思路:用两个int数组存储String每一位的值,进位和累加。在结果转成String之前需要去零
java代码:
  1. public String multiply(String num1, String num2) {
  2.         if(num1==null||num1.length()==0||num2==null||num2.length()==0)  return "0";
  3.         int m=num1.length(),n=num2.length();
  4.         int [] a=new int[m];
  5.         int [] b=new int[n];
  6.         int [] c=new int[m+n];
  7.         for(int i=0;i<m;++i)
  8.             a【i】=(int)(num1.charAt(m-1-i)-'0');
  9.         for(int j=0;j<n;++j)
  10.             b[j]=(int)(num2.charAt(n-1-j)-'0');
  11.         for(int i=0;i<m;++i){
  12.             int plus=0,j=0;
  13.             for(;j<n;++j){
  14.                 c[i+j]+=a【i】*b[j]+plus;
  15.                 plus=c[i+j]/10;
  16.                 c[i+j]%=10;
  17.             }
  18.             c[i+j]+=plus;
  19.         }
  20.         StringBuffer sb = new StringBuffer();
  21.         boolean omit=true;
  22.         for(int i=m+n-1;i>=0;--i){
  23.             if(c【i】==0&&omit){
  24.                 continue;   
  25.             }
  26.             else if(c【i】!=0){
  27.                 if(omit)    omit=false;
  28.                 sb.append(c【i】);
  29.             }
  30.             else{
  31.                 sb.append(c【i】);
  32.             }
  33.         }
  34.         if(omit)    return "0";
  35.         return sb.toString();
  36.     }
复制代码


复杂度:O(m*n)

本帖被以下淘专辑推荐:

8

主题

5

精华

1243

积分

顶级会员

Rank: 6Rank: 6

积分
1243

热心会员推广达人

发表于 11-19-2014 04:26 PM | 显示全部楼层
学习了,之前也是偷懒用biginteger...

补充内容 (11-19-2014 04:45 PM):
借着楼主的思想,也来写一发:
思路和楼主的一致,同时稍微做了点代码的修改,第一次层主是直接用Java的BigInteger,直接偷懒无视overflow问题,后来改用数组记录,每一位进行乘的方法,废话不多说,直接上代码
  1. public String multiply(String num1, String num2) {
  2.         if(num1==null || num1.length()==0 || num1=="0") return "0";
  3.         if(num2==null || num2.length()==0 || num2=="0") return "0";
  4.         String tmp1 = new StringBuilder(num1).reverse().toString();
  5.         String tmp2 = new StringBuilder(num2).reverse().toString();
  6.         int[] array = new int[tmp1.length()+tmp2.length()];
  7.         for(int i = 0; i<tmp1.length(); i++){
  8.             for(int j = 0; j<tmp2.length(); j++){
  9.                 array[i+j] += (tmp1.charAt(i)-'0')*(tmp2.charAt(j)-'0');
  10.             }
  11.         }
  12.         StringBuilder sb = new StringBuilder("");
  13.         for(int i=0; i<tmp1.length()+tmp2.length(); i++){
  14.             int carry = 0;
  15.             carry = array[i]/10;
  16.             array[i] = array[i]%10;
  17.             sb.insert(0, array[i]);
  18.             if(i<tmp1.length()+tmp2.length()-1)
  19.                 array[i+1] += carry;
  20.         }
  21.         int i = 0;
  22.         while(sb.length()>1 && sb.charAt(i)=='0')
  23.             sb.deleteCharAt(0);
  24.         return sb.toString();
  25.     }
复制代码



补充内容 (11-19-2014 04:48 PM):
有个小bug,num1==“0” ==> num1.equals("0")。。
回复 支持 反对

使用道具 举报

发表于 11-28-2014 11:28 AM | 显示全部楼层
我觉得只要维持result的一个int string就行了,对于两个输入的string,每次用charAt取值就行了。有可能会因为每次都需要把char换成int更慢,但是时间复杂度来讲没变化,空间省了两个int数组
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表