nowcoder NC10 大数乘法

迈不过友情╰ 2023-10-15 18:14 53阅读 0赞

[题目链接： ![icon-default.png?t=N7T8][icon-default.png_t_N7T8]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=][_icon-default.png_t_N7T8_icon-default.png_t_N7T8_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]

**目录**

题目描述：

答案：

详解：

--------------------

# 题目描述： #

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

**数据范围：** 读入的数字大小满足 ![0 \\leqslant n \\leqslant \{10\}^\{1000\}][0 _leqslant n _leqslant _10_1000]

**要求：**空间复杂度 O(m)，时间复杂度 O(![m^\{2\}][m_2])（假设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 here
            if (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();
            //也可以写成这样
            //tmp[0] = ret;
            //ret = "";
            //for (int i = tmp[0].length() - 1; i >= 0; i--){
            //    ret += tmp[0].charAt(i);
            //}
            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 为例：

![b6c3ede5db8f4567ac99b2d19785e72e.png][]

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

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

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

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

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

public String solve (String s, String t) {
            // write code here
            if (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 here
            if (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);
            }

[icon-default.png_t_N7T8]: https://csdnimg.cn/release/blog_editor_html/release2.3.6/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=N7T8
[_icon-default.png_t_N7T8_icon-default.png_t_N7T8_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]: 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=
[0 _leqslant n _leqslant _10_1000]: https://latex.csdn.net/eq?0%20%5Cleqslant%20n%20%5Cleqslant%20%7B10%7D%5E%7B1000%7D
[m_2]: https://latex.csdn.net/eq?m%5E%7B2%7D
[b6c3ede5db8f4567ac99b2d19785e72e.png]: https://img-blog.csdnimg.cn/b6c3ede5db8f4567ac99b2d19785e72e.png