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

news/2024/10/31 3:23:07/

目录

一.大数加法

1.题目描述

2.问题分析

3.代码实现

二.大数减法

1.题目描述

2.问题分析

3.代码实现

三.大数乘法

1.题目描述

2.问题分析

3.代码实现

四.大数除法

1.题目描述

2.问题分析

3.代码实现


一.大数加法

1.题目描述

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

牛客:大数加法_牛客题霸_牛客网

2.问题分析

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

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

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

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

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

3.代码实现

    public String solve (String num1, String num2) {//1.保持数位一致,不够的前边补0int 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.保持数位一致,不够的前边补0int 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

牛客: 大数相减_牛客题霸_牛客网

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一定大于0int 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--;}//去除后导0for (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的长度)

牛客: 大数乘法_牛客题霸_牛客网

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];

 

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即可.

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 + ""};}

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


http://www.ppmy.cn/news/78436.html

相关文章

mapreduce技术

要实现操作hbase数据表首先要了解它的原理&#xff1a; 1,Hbase原理篇 HBASE就是基于Hadoop的一个开源项目&#xff0c;也是对Google的BigTable的一种实现。 BigTable最浅显来看就是一张很大的表&#xff0c;表的属性可以根据需求去动态增加&#xff0c;但是又没有表与表之间…

果汁脱色树脂,制糖行业脱色,医药行业脱色

具有控制孔径的大孔强碱性Ⅰ型阴特种脱色用离子交换树脂 Tulsimer A-722是一款具有便于颜色和有机物去除的控制孔径的&#xff0c;专门开发的大孔强碱性Ⅰ型阴离子交换树脂。 Tulsimer A-722 &#xff08;氯型&#xff09;专门应用于糖浆脱色。 Tulsimer A-722由于其本身…

云计算介绍

云计算是一种新的计算模式&#xff0c;是分布式处理、并行处理和网格计算、网络存储、虚拟化、 负载均衡等传统计算机技术和网络技术发展融合的产物。云计算将计算资源分布在由大量 计算机构成的资源池上&#xff0c;而非本地计算机或远程服务器中&#xff0c;用户根据需求通过…

分享18个好用的ChatGPT插件

上周ChatGPT又进化了&#xff0c;支持联网还有70几种第三方插件&#xff0c;不过还是老样子&#xff0c;只服务氪金玩家&#xff0c;免费端可能还得等等。之前只开放了俩插件&#xff0c;网络浏览器和代码解释器&#xff0c;只能说是真的不够用。 ChatGPT&#xff1a;不够&…

java基础知识

文章目录 1. 数据结构2.流3.线程池 多线程3.1线程3.2 线程池 4.锁5.面向对象5.2 封装、继承、多态5.2抽象、接口5.3重写 、 重载5.4final 6.设计模式7.反射8.异常9.常用类9.1 String9.2 Object9.3 数组 10 其他Linux基础cookie / session的区别转发 、 重定向的区别http与https…

外包干了五年,废了...

先说一下自己的情况。大专生&#xff0c;17年通过校招进入湖南某软件公司&#xff0c;干了接近5年的测试点点点&#xff0c;今年年上旬&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落&#xff01;而我已经在一个企业干了五年的点工…

小技巧notebook

小技巧notebook 1、MybatisPlus 批量保存 从BaseMapper接口方法可知&#xff0c;mybatis plus mapper只有根据id批量删除和查询&#xff0c;没有批量保存&#xff08;insert 、update&#xff09;&#xff0c;要实现也很简单&#xff0c;需要定义一个Service Service Slf4j …

回望大学,做个总结

一个普通大学生的回望 我准大一-痛苦大一-拼搏大二-忙碌大三-泄气大四-领悟写在最后 我 01年&#xff0c;甘肃人&#xff0c;本科贵州大学&#xff0c;数据科学与大数据技术。 2023应届毕业生&#xff0c;拿到金蝶的Offer&#xff0c;但最后去了交通银行软件开发中心&#xf…