admin 管理员组

文章数量: 1184232

1.代码记录 

class Solution {
    public String multiply(String num1, String num2) {
        if("0".equals(num1)||"0".equals(num2))return "0";
        char[] num1Ch = num1.toCharArray();
        char[] num2Ch = num2.toCharArray();
        String res = "0";
        for(int i=num2Ch.length-1;i>=0;i--){
            StringBuilder bu = new StringBuilder();
            for(int j=num2Ch.length-1-i;j>0;j--){
                bu.append(0);
            }
            int up=0;
            int first = num2Ch[i]-'0';
            for(int j=num1Ch.length-1;j>=0||up!=0;j--){
                int second = j<0?0:num1Ch[j]-'0';
                int mul = (first*second+up)%10;
                bu.append(mul);
                up = (first*second+up)/10;
            }
            res = addStrings(res,bu.reverse().toString());
        }
        return res;
    }
    public String addStrings(String num1, String num2) {
        StringBuilder bu = new StringBuilder();
        char[] num1Ch = num1.toCharArray();
        char[] num2Ch = num2.toCharArray();
        int up = 0;
        for(int i=num1Ch.length-1,j=num2Ch.length-1;i>=0||j>=0||up!=0;i--,j--){
            int first = i<0?0:num1Ch[i]-'0';
            int second = j<0?0:num2Ch[j]-'0';
            int sum = (first+second+up)%10;
            bu.append(sum);
            up = (first+second+up)/10;
        }
        return bu.reverse().toString();
    }
}

2.题解分析

2.1算法流程

*双指针定位，一个指针定位第一个整数的位置，另外一个指针定位后一个整数的位置。

*补0操作bu.append(0)，高位数字相乘需要对乘法结果先补0。

*计算进位， 运用 (first*second+up)/10来代表当前位相加是否产生进位。

*添加当前位置，运用(first*second+up)%10填充当前位置。

*索引溢出处理，当两个指针i和j走过数字首部后，给 first和second赋值为 0，相当于给 num1，num2 中长度较短的数字前面填 0，以便后续计算。

*运用字符串整数加法addStrings(String num1, String num2)累加乘法计算的中间字符串结果。

2.2复杂度分析

时间复杂度：O(m*n)，两层for循环。

空间复杂度：O(max(m,n))，m,n分别代码两个整数的位数长度，中间相乘的结果有保存。

本文标签： 挑战 位置 系统

版权声明：本文标题：LeetCode挑战43解答：以Adobe Flash Player为轴心的编程之旅 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1770630567a3535845.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。