nowcoder NC10 大数乘法

题目链接： https://www.nowcoder.com/practice/c4c488d4d40d4c4e9824c3650f7d5571?tpId=196&tqId=37177&rp=1&ru=/exam/company&qru=/exam/company&sourceUrl=%2Fexam%2Fcompany&difficulty=undefined&judgeStatus=undefined&tags=&title=

 

题目描述：

以字符串的形式读入两个数字，编写一个函数计算它们的乘积，以字符串形式返回。

数据范围： 读入的数字大小满足 

要求：空间复杂度 O(m)，时间复杂度 O()（假设m是n的长度）

示例1：

输入："11","99"

返回值："1089"

说明：11*99=1089

示例2：

输入："1","0"

返回值："0"

答案：

import java.util.*;public class Solution {public String solve (String s, String t) {// write code hereif (s.charAt(0) == '0' || t.charAt(0) == '0'){return "0";}String ret = "0";String[] tmp = new String[t.length()]; for (int i = t.length() - 1; i >= 0; i--){tmp[i] = "";int j = t.length() - 1;while(j - i > 0){tmp[i] += '0';j--;}tmp[i] += alongMultiply(s, t.charAt(i));}for (int i = t.length() - 1; i >= 0; i--){ret = Add(tmp[i], ret);}StringBuffer stringBuffer = new StringBuffer();for (int i = ret.length() - 1; i >= 0; i--){stringBuffer.append(ret.charAt(i));}ret = stringBuffer.toString();return ret;}public String Add(String a, String b){String str = "";int aLen = a.length() - 1;int ai = 0;int bLen = b.length() - 1;int bi = 0;int ten = 0;while(aLen >= ai && bLen >= bi){int tmp = (a.charAt(ai++) - '0') + (b.charAt(bi++) - '0');tmp += ten;ten = tmp / 10;str += tmp % 10;}while(aLen >= ai){int tmp = a.charAt(ai++) - '0';tmp += ten;ten = tmp / 10;str += tmp % 10;}while(bLen >= bi){int tmp = b.charAt(bi++) - '0';tmp += ten;ten = tmp / 10;str += tmp % 10;}if (ten != 0){str += ten;}return str;}public String alongMultiply(String s, char t){String ret = "";if (s.charAt(0) == '0' || t == '0'){return "0";}int tt = t - '0';int ten = 0;for (int i = s.length() - 1; i >= 0; i--){int tmp = s.charAt(i) - '0';tmp *= tt;tmp += ten;ten = tmp / 10;ret += tmp % 10;}if (ten != 0){ret += ten;}return ret;}
}

详解： 

 从题目中我们可以得到以下几点信息：

1. 输入值和返回值都是字符串类型；
2. 输入值和返回值不可以直接转换成整数（因为数字过大）；
3. 对时间复杂度几乎没有要求；
4. 不会出现负数乘法。

 当我们清楚了题目要求之后就该考虑该如何解题了。

 首先我们应该考虑的是乘法是如何进行计算的！

我们以 11 * 99 为例：

 

我们可以分析得到无论是几位数的乘法都是按照以下步骤进行的：

1. 将第一个数字分别乘以第二个数的每一位；
2. 如果第一个数乘的是第二个数的个位就给结果乘一，十位就乘十 以此类推；
3. 最后一步就是将各各结果相加。

到这一步之后如果你想在题目给的那一个方法里面实现这些内容就会大大提高你写代码的难度，此时其实我推荐将其用三个方法来实现。

• 第一个为主函数，主要用来实现代码的整体思路；
• 第二个为相乘的方法，其主要功能是实现一个 n 位数与一位数相乘；
• 第三个为相加的方法，其主要功能是实现两个 n 位数的相加。

根据乘法的定义可以知道：0 与任何数相乘都是 0 所以我们的第一段代码就可以为：

    public String solve (String s, String t) {// write code hereif (s.charAt(0) == '0' || t.charAt(0) == '0'){return "0";}}

接下来就是对每一位进行相乘但是我们并不知道是 几位数与几位数进行相乘 所以我们此时应该根据 t 的长度来定义一个字符串数组 tmp 用来存储 t 中的每一位与 s 相乘的结果。

再定义一个名为 alongMultiply() 的方法 此方法就用来实现n 位数与一位数相乘并将其值以字符串的形式进行返回。（此方法可以先不急着实现）。

再定义一个名为 的字符串类型的变量，将其初始化为“0” 用来存储最终的返回值。

因为会有进位而导致最后结果的位数充满不确定性所以我们可以采用倒序的存储方式 

即：12345 存储为 54321

因为加法也会有进位所以我们可以在主方法的最后统一进行反转。

 public String solve (String s, String t) {// write code hereif (s.charAt(0) == '0' || t.charAt(0) == '0'){return "0";}String ret = "0";//新加的代码String[] tmp = new String[t.length()]; for (int i = t.length() - 1; i >= 0; i--){tmp[i] = "";int j = t.length() - 1;while(j - i > 0){ //相当于十位乘十 ， 百位乘一百……tmp[i] += '0';j--;}tmp[i] += alongMultiply(s, t.charAt(i));}
}

紧接着我们再将 tmp数组 中的所有值进行相加存储在 ret 中。

for (int i = t.length() - 1; i >= 0; i--){ret = Add(tmp[i], ret);
}

到这里我们的整体布局已经完成了，接下来就该实现 alongMultiply() 方法了：

public String alongMultiply(String s, char t){String ret = ""; //用来存储最后的返回值if (s.charAt(0) == '0' || t == '0'){return "0";}int tt = t - '0';int ten = 0; //用来存储每次的进位for (int i = s.length() - 1; i >= 0; i--){int tmp = s.charAt(i) - '0';tmp *= tt;tmp += ten;ten = tmp / 10;ret += tmp % 10;}if (ten != 0){ret += ten;}return ret;}

 Add() 方法的实现：

public String Add(String a, String b){String str = ""; //存储最终的返回值int aLen = a.length() - 1;int ai = 0;int bLen = b.length() - 1;int bi = 0;int ten = 0; //用来存储每次的进位while(aLen >= ai && bLen >= bi){int tmp = (a.charAt(ai++) - '0') + (b.charAt(bi++) - '0');tmp += ten;ten = tmp / 10;str += tmp % 10;}while(aLen >= ai){int tmp = a.charAt(ai++) - '0';tmp += ten;ten = tmp / 10;str += tmp % 10;}while(bLen >= bi){int tmp = b.charAt(bi++) - '0';tmp += ten;ten = tmp / 10;str += tmp % 10;}if (ten != 0){str += ten;}return str;}

接下来我们只要再将最终的值进行反转本题就算做完了：

        StringBuffer stringBuffer = new StringBuffer();for (int i = ret.length() - 1; i >= 0; i--){stringBuffer.append(ret.charAt(i));}ret = stringBuffer.toString();

 当然你也可以用（我用上面的方法主要是因为它比较快）：

        tmp[0] = ret;ret = "";for (int i = tmp[0].length() - 1; i >= 0; i--){ret += tmp[0].charAt(i);}