大数运算(加法,减法,乘法,除法)

ゝ一纸荒年。 2024-03-22 17:55 66阅读 0赞

**目录**

一.大数加法

1.题目描述

2.问题分析

3.代码实现

二.大数减法

1.题目描述

2.问题分析

3.代码实现

三.大数乘法

1.题目描述

2.问题分析

3.代码实现

四.大数除法

1.题目描述

2.问题分析

3.代码实现

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

## 一.大数加法 ##

### 1.题目描述 ###

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

牛客:[大数加法\_牛客题霸\_牛客网][Link 1]

### 2.问题分析 ###

如果直接使用Java的API--BigInteger,这一题可以直接秒了,但是我们这里不推荐使用,因为我们做题的目的是锻炼我们的思维,而不是API的调用能力.

那我们这一题该如何解决呢?我们可以采取我们小时候做加法的形式进行运算.

就拿456+646举例进行解说.我们从最低位开始运算,相加的结果求余10,作为此位的结果,然后如果大于等于10就进位(进位标志位),下一位计算自动加1进行计算.全部计算完成之后,如果进位标志位true,还需要加一位为1.

![b19498a0c495402e9e50a8af520bcf61.png][]

上面是位数相同的两位数做加法运算,如果位数不同怎么办?我们可以在位数小的前边补零(补零操作),或者当遍历到当前位置的时候,(**循环结束为当两个数都遍历完了之后再结束**)如果其中一个数已经遍历完了,可以直接将当前位置变为0,参与另一个数的运算;

我们可以使用StringBuilder每次append计算的结果,最后将字符串反转就是我们需要的答案了.

### 3.代码实现 ###

public String solve (String num1, String num2) {
            //1.保持数位一致,不够的前边补0
            int len1 = num1.length(), len2 = num2.length();
            while (len1 < len2) {
                num1 = "0" + num1;
                len1++;
            }
            while (len1 > len2) {
                num2 = "0" + num2;
                len2++;
            }
            StringBuilder ans = new StringBuilder();
            boolean isCarry = false;
            for (int i = len1 - 1; i >= 0; --i) {
                int temp = (num1.charAt(i) - '0' + num2.charAt(i) - '0' + (isCarry ? 1 : 0));
                ans.append(temp % 10);
                isCarry = temp >= 10;
            }
            if (isCarry) {
                ans.append(1);
            }
            ans.reverse();
            return new String(ans);
    
        }

**下面的代码会超时.**

public String add(String num1, String num2) {
            //1.保持数位一致,不够的前边补0
            int len1 = num1.length(), len2 = num2.length();
            int i = len1 - 1, j = len2 - 1;
            StringBuilder ans = new StringBuilder();
            boolean isCarry = false;
            while (i >= 0 || j >= 0) {
                int x = i >= 0 ? num1.charAt(i) - '0' : 0;
                int y = j >= 0 ? num2.charAt(j) - '0' : 0;
                int temp = (x + y) + (isCarry ? 1 : 0);
                isCarry = temp >= 10;
    
                ans.append(temp % 10);
                i--;
                j--;
            }
            if (isCarry) {
                ans.append(1);
            }
            ans.reverse();
            return new String(ans);
    
    
        }

## 二.大数减法 ##

### 1.题目描述 ###

> 数据范围：两个数字的长度都满足 1≤num1,num2≤105 1 \\le num1,num2 \\le 10^5 \\ 1≤num1,num2≤105 ，数字中仅包含 0≤val≤9 0 \\le val \\le 9 \\ 0≤val≤9 ，第一位不可能是0

牛客: [大数相减\_牛客题霸\_牛客网][Link 2]

### 2.问题分析 ###

大数减法和大数加法的思路基本相同,和我们小学的时候做的减法运算是一样的,当这一位减不动的时候,要考虑向高位进行借位.

这里我们考虑一个问题,如何通过字符串判断两个数的大小.我们不能简单的进行字符串的字典序比较(比如"123"和"23",23的字典序比123大,但是23小于123),当num1.length()>num2.length()的时候,num1的值肯定是大于num2的值的.反之,num1<num2.当他们的长度相同的时候,我们可以进行字典序的比较,也就是num1.conpareTo(num2)可以比较出数的大小.

### 3.代码实现 ###

public String subtract(String num1, String num2) {
            if (num1.equals(num2)) {
                return "0";
            }
            //此时num1-num2一定大于0
            int len1 = num1.length(), len2 = num2.length();
            if (len2 > len1) {
                return "-" + subtract(num2, num1);
            }
            if (len1 == len2 && num1.compareTo(num2) < 0) {
                return "-" + subtract(num2, num1);
    
            }
            boolean isBorrow = false;
            StringBuffer sb = new StringBuffer();
            int i = len1 - 1;
            int j = len2 - 1;
            while (i >= 0 || j >= 0) {
                int x = i >= 0 ? num1.charAt(i) - '0' : 0;
                int y = j >= 0 ? num2.charAt(j) - '0' : 0;
                int temp = (x - y) - (isBorrow ? 1 : 0);
                isBorrow = temp < 0;
                if (temp < 0) {
                    temp += 10;
                }
                sb.append(temp);
                i--;
                j--;
            }
            //去除后导0
            for (int x = sb.length() - 1; x >= 0; --x) {
                if (sb.charAt(x) == '0') {
                    sb.deleteCharAt(x);
                } else {
                    return new String(sb.reverse());
                }
            }
    
            return new String(sb.reverse());
    
        }

## 三.大数乘法 ##

### 1.题目描述 ###

> 以字符串的形式读入两个数字，编写一个函数计算它们的乘积，以字符串形式返回。
> 
> 数据范围： 读入的数字大小满足 0≤n≤1010000 \\le n \\le 10^\{1000\}0≤n≤101000
> 
> 要求：空间复杂度 O(m)，时间复杂度 O()（假设m是n的长度）

牛客: [大数乘法\_牛客题霸\_牛客网][Link 3]

### 2.问题分析 ###

在进行乘法的运算时候,我们不妨将两个字符串数转换为整数数组.然后将他们不同的下标相乘放入到数组的对应位置,最后在进行进位的操作.比如89\*12进行运算的时候,8\*1累加放在(1+1+1)的下标,8\*2累加放在(1+0+1)的下标,(9\*1)累加放在(0+1+1)的下标,(9\*2)累加放在(0+0+1)的下标,然后此时数组为\[0,8,27,18\],进位之后\[1,0,6,8\];

![8a56937c9ea3471793ea395d68cef250.png][]

### 3.代码实现 ###

public String multiply(String s, String t) {
            //将字符串转化为数组形式
            int lenS = s.length(), lenT = t.length();
            int[] arrS = new int[lenS];
            int[] arrT = new int[lenT];
            for (int i = 0; i < lenS; i++) {
                arrS[i] = s.charAt(i) - '0';
            }
            for (int i = 0; i < lenT; i++) {
                arrT[i] = t.charAt(i) - '0';
            }
            // 存放结果
            int[] res = new int[lenS + lenT];
            // 中间 i * j 会有重复出现，如89 * 12, 会有res = [0, 8*1, 8*2+9*1, 9*2]
            for (int i = 0; i < lenS; i++) {
                for (int j = 0; j < lenT; j++) {
                    // i + j + 1 是为了给进位留一个位置
                    res[i + j + 1] += arrS[i] * arrT[j];
                }
            }
            // 进位的值
            int carry = 0;
            // 从最低位，也就是数组res最右边元素开始处理进位
            for (int i = lenS + lenT - 1; i >= 0; i--) {
                res[i] += carry;
                carry = res[i] / 10;
                res[i] = res[i] % 10;
            }
            StringBuilder ans = new StringBuilder();
            // 表示当前位在数组的索引，目的是找出高位的0的位置，前置的0需要忽略掉
            int cur = 0;
            while (cur < lenS + lenT && res[cur] == 0) {
                cur++;
            }
            // 收集结果
            for (int i = cur; i < res.length; i++) {
                ans.append(res[i]);
            }
            return ans.length() == 0 ? "0" : ans.toString();
        }

## 四.大数除法 ##

### 1.题目描述 ###

> 当一个数字很大的时候,我们常用字符串进行表达,(超过了int和long等数据类型可以存储的最大范围),但是这个时候我们该如何判断他是否可以被另一个数整除呢?

### 2.问题分析 ###

我们这里讨论一个大数除以一个整数(int类型),是否可以除尽,以及除了之后的结果.我们可以将上一次除法运算的结果保存在last中,到下一次运算的时候\*10+这一次运算的数进行除法运算即可.

判断是否可以除尽只需要判断最后的last是否为0即可.

![98b3372ecc07461e922c651a0051144d.png][]

### 3.代码实现 ###

**判断是否可以整除的函数**

public boolean isDivide(String num, int k) {
            if (num.charAt(0) == '-') {
                num = num.substring(1);
            }
            long left = 0;
            for (int i = 0; i < num.length(); ++i) {
                left = (left * 10 + num.charAt(i) - '0') % k;
            }
            return left == 0;
        }

**一个大数除以整数的结果:**

/**
         * 
         * @param num
         * @param k
         * @return  第一位保存上商,第二位保存余数
         */
        public String[] divide(String num, int k) {
            StringBuilder ans = new StringBuilder();
            long left = 0;
            for (int i = 0; i < num.length(); ++i) {
                long x = left * 10 + num.charAt(i) - '0';
                ans.append(x / k);
                left = x % k;
            }
            //去除前导0;
            int cur = 0;
            while (cur < ans.length() && ans.charAt(cur) == '0') {
                cur++;
            }
    
            String s = new String(ans.substring(cur));
    
            return s.length() == 0 ? new String[]{"0", left + ""} : new String[]{s, left + ""};
    
        }

这里有一些大数除法题目可以用来练习:[找出字符串的可整除数组][Link 4] [4589. 大数除法][4589.]

[Link 1]: https://www.nowcoder.com/practice/11ae12e8c6fe48f883cad618c2e81475?tpId=196&tqId=37176&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=%E5%A4%A7%E6%95%B0
[b19498a0c495402e9e50a8af520bcf61.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/33a25f850cf24c6da1d1b47337532290.png
[Link 2]: https://www.nowcoder.com/practice/ae4d84312e384a1fa100b613f93f3fe0?tpId=196&tqId=40449&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=%E5%A4%A7%E6%95%B0
[Link 3]: https://www.nowcoder.com/practice/c4c488d4d40d4c4e9824c3650f7d5571?tpId=196&tqId=37177&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=%E5%A4%A7%E6%95%B0
[8a56937c9ea3471793ea395d68cef250.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/fa2c42eaf064482d8914e43e344bc063.png
[98b3372ecc07461e922c651a0051144d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/752db1757ddd45008044950a75f20d81.png
[Link 4]: https://leetcode.cn/problems/find-the-divisibility-array-of-a-string/description/
[4589.]: https://www.acwing.com/problem/content/4592/