首页 > 其他 > 详细

【LeetCode】Multiply Strings

时间:2014-05-18 01:24:35      阅读:349      评论:0      收藏: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.

这道题目首先我想到是不能用乘法,那就全部用加法将

然后超时

bubuko.com,布布扣
public class Solution {
    public String multiply(String num1, String num2) {
        if(num1.equalsIgnoreCase("")||num2.equalsIgnoreCase(""))
            return "";
        if(num1.equalsIgnoreCase("0")||num2.equalsIgnoreCase("0"))
            return "0";
        Map<Integer,String> map = new HashMap<Integer,String>();
        map.put(0, "0");
        map.put(1, num2);
        for(int i=2;i<10;i++){
            map.put(i, "");
        }
        char[] ch = new char[num1.length()*num2.length()+1];
        Arrays.fill(ch, ‘0‘);
        int xx=ch.length-1;
        for(int i=num1.length()-1;i>=0;i--){
            int temp = num1.charAt(i)-‘0‘;
            String base="";
            if(map.get(temp).equalsIgnoreCase("")){
                base=plus(temp,num2);
                map.put(temp, base);
            }else{
                base=map.get(temp);
            }
            int x=xx;
            int y=base.length()-1;
            int pre=0;
            while(y>=0){
                int tt = base.charAt(y)-‘0‘+ch[x]-‘0‘+pre;
                if(tt>=10){
                    pre=1;
                    ch[x]=String.valueOf(tt-10).charAt(0);
                }else{
                    pre=0;
                    ch[x]=String.valueOf(tt).charAt(0);
                }
                x--;
                y--;
            }
            if(pre!=0){
                if(ch[x]!=‘0‘){
                    int tm = ch[x]-‘0‘+pre;
                    if(tm>=10){
                        ch[x]=‘0‘;
                        ch[x-1]=‘1‘;
                    }else{
                        ch[x]=String.valueOf(tm).charAt(0);
                    }
                    
                }else{
                    ch[x]=‘1‘;
                }
                    
            }
            xx--;
                
        }
        String re = String.valueOf(ch);
        while(re.startsWith("0")){
            re = re.substring(1);
        }
        return re;
        
    }
    
    private String plus(int times,String base){
        char[] ch = new char[base.length()+1];
        ch[0]=‘0‘;
        for(int m=base.length()-1;m>=0;m--){
            ch[m+1]=base.charAt(m);
        }
        for(int j=1;j<times;j++){
            int pre=0;
            int i=base.length()-1;
            int k=i+1;
            while(i>=0){
                int temp = base.charAt(i)-‘0‘+ch[k]-‘0‘+pre;
                if(temp>=10){
                    pre=1;
                    ch[k]=String.valueOf(temp-10).charAt(0);
                }else{
                    pre=0;
                    ch[k]=String.valueOf(temp).charAt(0);
                }
                i--;
                k--;
            }
            if(pre!=0){
                if(ch[k]!=‘0‘){
                    int tm = ch[k]-‘0‘+pre;
                    if(tm>=10){
                        ch[k]=‘0‘;
                        ch[k-1]=‘1‘;
                    }else{
                        ch[k]=String.valueOf(tm).charAt(0);
                    }
                    
                }else{
                    ch[k]=‘1‘;
                }
            }
                
            
        }
        if(ch[0]==‘0‘){
            return String.valueOf(ch, 1, ch.length-1);
            
        }else{
            return String.valueOf(ch);
        }
        
    }
}
bubuko.com,布布扣

 

后面再网上看到一种巧妙的解法。首先将每个位的数求出来,然后再遍历是不是需要进位

bubuko.com,布布扣
public class NSolution {
    public String multiply(String num1, String num2) {
        String n1 = new StringBuilder(num1).reverse().toString();
        String n2 = new StringBuilder(num2).reverse().toString();
        int[] re = new int[n1.length()+n2.length()];
    //把i j 设为 0 则 i+j就是新的数的第i+j位,很巧妙
for(int i=0;i<n1.length();i++){ for(int j=0;j<n2.length();j++) re[i+j] += (n1.charAt(i)-‘0‘) * (n2.charAt(j)-‘0‘); } StringBuilder sb = new StringBuilder(); for(int k=0;k<re.length;k++){ int low = re[k]%10; int high = re[k]/10; if(k+1<re.length) re[k+1]+=high; sb.insert(0, low); } while(sb.charAt(0)==‘0‘ && sb.length()>1){ sb.deleteCharAt(0); } return sb.toString(); } }
bubuko.com,布布扣

 

 

【LeetCode】Multiply Strings,布布扣,bubuko.com

【LeetCode】Multiply Strings

原文:http://www.cnblogs.com/yixianyixian/p/3734033.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!