加减乘除最新算法(大数加减乘除一文彻底搞定)

加减乘除最新算法(大数加减乘除一文彻底搞定)(1)

【CSDN 编者按】最近大数运算频频出现在面试中,在代码编写的过程中也经常涉及比较大的数的运算,当它们超出程序基本类型所能表示的范围时,就会造成溢出,整形一般的加减乘除已经无法实现了,这时候需要自己写一个程序来实现。

作者 | bigsai 责编 | 欧阳姝黎

加减乘除最新算法(大数加减乘除一文彻底搞定)(2)

前言

各位有过分类刷题的小伙伴,可能看到很多人分类 字符串、贪心、动态规划、bfs、dfs、大数、数论等,初听大数,你可能会差异:大数是个啥?听起来怪高大上的。

这个数字一般用字符串、链表等形式表示、返回,大数运算的核心就是:模拟,模拟我们日常用纸笔算数字的加减乘除流程,然后再根据计算机、编程语言等特性适当存储计算即可,不过,大数除法运算稍微特殊一点,和我们直接模拟的思维方式稍有不同,它就是转换了一下成特殊的加减法运算,后面会细谈。

加减乘除最新算法(大数加减乘除一文彻底搞定)(3)

大数加法

大数加法是最简单的,简单模拟即可。首先,我们想一下两个数加法的流程:从右向左计算求和、进位,一直到最后。

在编程语言中同样也是模拟从右向左逐位相加的过程,不过在具体实现上需要注意一些细节。

  1. 枚举字符串将其转换成 char提高效率

  2. 从右往左进行计算,可以将结果放到一个数组中最后组成字符串,也可以使用 StringBuider 拼接,拼接的时候最后要逆置一下顺序。

  3. 余数每次叠加过需要清零,两数相加如果大于等于 10 即有余数,添加到结果中该位置的数也应该是该数  的结果。

  4. 计算完最后还要看看余数是否为1,如果为1需要将其添加到结果,例如 "991" "11"算三个位置为002但还有一个余数需要添加,所以应该是1002。

加减乘除最新算法(大数加减乘除一文彻底搞定)(4)

一个加法流程

当然在具体实现上方法较多,你可以首先就将字符串逆置然后从前往后就可以计算了。当然我这里实现的是字符串从后向前各个位对应计算,然后将结果顺序添加到 StringBuilder 上。

这题在力扣【415两数相加】可以检验自己代码,实现代码为:

public String addStrings(String num1, String num2) {// 公众号:bigsai 欢迎你的关注int len1=num1.length-1,len2=num2.length-1;char ch1=num1.toCharArray;char ch2=num2.toCharArray;StringBuilder sb=new StringBuilder;int remainder =0;//计算余数while (len1>=0||len2>=0){int n1=len1>=0?(ch1[len1--]-'0'):0;int n2=len2>=0?(ch2[len2--]-'0'):0;int num=n1 n2 remainder;//求和对应数字remainder=num/10;//是否进位sb.append(num);// 添加到结果字符串中}if(remainder>0)//是否还需要进位{sb.append(remainder);}//反装即为结果return sb.reverse.toString;}

加减乘除最新算法(大数加减乘除一文彻底搞定)(5)

大数减法

加法对应的就是减法,有了上面大数加法的实现思路,那么我想你在大数减法也应该有点想法,但是减法和加法不同的是减法有位置的区别,加法需要进位而减法需要借位。并且大整正数减法可能产生正负也不一定。

两个正数,如果大数减去小数,那么一切正常,结果是一个正数;但如果小数减去大数,那么结果将是一个负数,并且结果处理起来比较麻烦。所以在这里全部转成大-小处理(大-小不存在不能借位的情况)。

加减乘除最新算法(大数加减乘除一文彻底搞定)(6)

减法转成大-小

  1. 执行计算前首先比较减数(num1)和被减数(num2)的大小,如果num1>num2,那么就模拟num1-num2的过程,如果num1<num2,那么结果就为-(num2-num1) 。当然可以为了稳定模拟时候一个大一个小,可将 num1 始终指向较大的那个数,少写一个 if/else.

  2. 在比较两个数字大小的时候,因为是字符形式,首先比较两个字符串的长度,长的那个更大短的那个更小,如果两个字符串等大,那么就可以通过字典序从前往后进行比较(Java 可直接使用 compareTo 方法)。

  3. 和加法不同的是,减法前面可能产生若干前缀 0,这些0是需要你去掉的,例如"1100"-"1000"计算得到的结果为"0100",你就要把前面的0去掉返回"100"。

  4. 具体实现的时候和加法相似,如果使用 StringBuilder 存储,需要逆置顺序,如果是个负数,前面还要加上'-'.

  5. 每个位置正常进行减法运算,如果值小于0,那么就需要向上借位( 10),那么处理上一位进行减法时候还要将借位的处理一下。

加减乘除最新算法(大数加减乘除一文彻底搞定)(7)

这题在力扣上没有原题,但是可以在小米 OJ【大数相减】上验证自己代码的正确性,具体实现的代码为:

public static boolean compare(String num1,String num2){if(num1.length<num2.length)return false;else if(num1.length>num2.length)return true;elsereturn num1.compareTo(num2)>0;}public static String subtractString(String num1,String num2) {char sign=' ';//正负号//让num1>num2 如果num1<num2 那么结果就是—(num2-num1)//可以先将num1和num2交换和前面情况统一if(!compare(num1,num2)){sign='-';String team = num2;num2 = num1;num1 = team;}int len1=num1.length-1;int len2=num2.length-1;char ch1 = num1.toCharArray;char ch2 = num2.toCharArray;StringBuilder sb=new StringBuilder;int borrow=0;//借位while (len1>=0||len2>=0){int n1=len1>=0?(ch1[len1--]-'0'):0;int n2=len2>=0?(ch2[len2--]-'0'):0;int num=n1-n2-borrow;borrow=0;if(num<0)//需要向前借位{borrow=1;num =10;}sb.append(num);}sb=sb.reverse;//需要先翻转int index = 0;//去掉前面没用的’0‘while (index<sb.length&&sb.charAt(index) == '0'){index ;}//如果两个数相同 直接返回"0"if(index==sb.length)return "0";if(sign==' ')//如果正数return sb.substring(index);else return sign sb.substring(index);//负数需要返回}

加减乘除最新算法(大数加减乘除一文彻底搞定)(8)

大数乘法

大数乘法乍一想可能比较复杂,因为乘法比起加法可能进位不光是1,还有两个数各种位置都需要相乘计算,这时候就需要我们化繁为简了。

多*多考虑起来可能有些麻烦,但是如果多*一考虑起来呢?如果是多位乘以一位数,那么就拿一位的分别乘以多位数的个位、十位、百位,在计算的同时考虑一下进位的情况。

但是也可以先直接用 int 类型数组存储各位的乘积然后从右向左进行进位,如下图所示。

加减乘除最新算法(大数加减乘除一文彻底搞定)(9)

而多*多 也是这个道理,将不同位乘积先叠加到对应位置上,然后从右向左进位,一直到不需要进位为止。

加减乘除最新算法(大数加减乘除一文彻底搞定)(10)

一个乘法流程

你可能会疑问,如果两个数组的长度分别为a和b这个数组到底该开多大呢?

  • a b大小就够了,怎么分析呢?其中一个a不变。另一个b变成最小b 1数字即十的倍数,那么这样在相乘的时候也不过是a b长度,所以这里a b长度就够了。

这题有力扣对应题可以去试试【43字符串相乘】,具体代码为:

public String multiply(String num1, String num2) {if("0".equals(num1)||"0".equals(num2))return "0";char a=num1.toCharArray;char b=num2.toCharArray;int value=new int[a.length b.length];for(int i=a.length-1;i>=0;i--){for(int j=b.length-1;j>=0;j--){int index=a.length-1-i b.length-1-j;value[index] =(a[i]-'0')*(b[j]-'0');}}for(int i=0;i<value.length-1;i ){value[i 1] =value[i]/10;value[i]=value[i];}int index=value.length-1;while(value[index]==0){index--;}StringBuilder sBuilder=new StringBuilder;while (index>=0) {sBuilder.append(value[index--]);}return sBuilder.toString;}

加减乘除最新算法(大数加减乘除一文彻底搞定)(11)

大数除法

大数加减乘都搞定了,通过模拟来实现,但是大数除法也通过模拟来实现?

并不是,对于大数a/b,一般最多要求求到其整数解或者余数,即a/b=c……d(a,b,c,d均为整);也就是a里面有c个b,并且还剩下d。核心是先求c是多少,对于程序来说,可以通过枚举啊,将除法变成减法,从a中不断减d,一直到不能减为止。

加减乘除最新算法(大数加减乘除一文彻底搞定)(12)

除法转成减法运算

但是有个问题,如果被除数a很大很大,可能有居多个b,那么这样时间复杂度太高了,不可能执行那么多次,那么需要怎么样去优化这个方法呢?

那就要加速寻找次数,减少这个减法的次数了,减法次数减小的一个最好方案就是能不能扩大除数b。如果b后面加个'0',那么算出来的结果就乘以10,减法的次数变成原来十分之一。根据这个思想我们可以一直每次找到b的最大10的倍数(小于a)计算减的次数再换算成减b的总词数,将结果要以字符串方式保留,后面一直迭代到最后为止,这虽然是一道除法运算的题,但是也蕴含减法和加法(次数叠加到结果中)。

加减乘除最新算法(大数加减乘除一文彻底搞定)(13)

计算思想

当然,也有一些人使用二分法来压缩寻找可以被减的次数也是可以的(加法可以迭代数字实现二分倍数),具体实现的话也不是很困难,但是代码量可能比较多所以一般的面试笔试不会让你现场写的,所以好好掌握前面的减法、减法、乘法的代码即可。

这部分代码我也简单给一下(其他函数上面贴过就不重复贴啦):

//假设 num1>num2public static String divideString(String num1,String num2){String value="0";//结果while (compare(num1,num2)){StringBuilder sbTeam=new StringBuilder(num2);//用这个往后面不断加0 和num做减法StringBuilder sbCount=new StringBuilder("1");//次数 可能很大int subLen=num1.length-num2.length;//统计大概要加几个零for(int i=0;i<subLen;i ){sbTeam.append('0');sbCount.append('0');}//如果0 加多了 那么要删一个 类似"12300" / "23" "12300"比"23000"小//所以要 "2300" 对应比"23"扩大 "100"倍数,每减一次"2300" 则结果加"100"if(!compare(num1,sbTeam.toString)){sbTeam=sbTeam.deleteCharAt(sbTeam.length-1);sbCount=sbCount.deleteCharAt(sbCount.length-1);}// 一直能减的时候while (compare(num1,sbTeam.toString)){num1=subtractString(num1,sbTeam.toString);value=addStrings(sbCount.toString,value);}}return value;}

简单测试了下,正确性还是ok的:

加减乘除最新算法(大数加减乘除一文彻底搞定)(14)

除法测试

加减乘除最新算法(大数加减乘除一文彻底搞定)(15)

番外篇

除了上面直接的大数加减乘除,还有一些变形的题目需要我们特殊处理一下,比如可能会使用链表等存储处理,下面分享两道题。

两数相加(力扣02)

题目描述:

给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。请你将两个数相加,并以相同形式返回一个表示和的链表

你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

加减乘除最新算法(大数加减乘除一文彻底搞定)(16)

img

提示:

  • 每个链表中的节点数在范围 [1, 100] 内

  • 0 &lt;= Node.val &lt;= 9

  • 题目数据保证列表表示的数字不含前导零

本题其实就是用一个链表存储一个数字(逆序存储),你需要给它计算出结果后在 逆序 存储到一个链表中返回。

所谓加法的运算规则:从两个数的最低位进行计算,进行到下一位的时候需要考虑进位问题。一直到最后,而本题所给的链表刚好可以用来直接计算,因为链表头都是数字最低位可以直接相加,然后一直遍历到结束。可以用一个常数表示进位。

加减乘除最新算法(大数加减乘除一文彻底搞定)(17)

在具体实现(链表)的时候:

  • 创建新的链表,每次将计算的数值插入到链表尾部即可。

  • 需要准确表示进位,并且最后要考虑以下进位

  • 妥善返回正确节点,可以用一个头节点用来使得所有节点都正常操作,而不需要特殊判断。通过代码第一次比较啰嗦的写法:

当然,如果你遍历链表把各个数字取出来,使用字符串、数字转换然后相加得到一个数字,最后在转成字符串、链表的理论可以,可以自行实现。

优化后的代码为:

//更简洁的写法public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode node=new ListNode(0);ListNode team=node;int jin=0;//进位while(l1!=||l2!=){int num=jin;if(l1!=){num =l1.val;l1=l1.next;}if(l2!=){num =l2.val;l2=l2.next;}jin=num/10;num%=10;team.next=new ListNode(num);team=team.next;}if(jin!=0)team.next=new ListNode(jin);return node.next;}

两数相加2(力扣445)

题目描述:

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外,这两个数字都不会以零开头。

进阶:如果输入链表不能修改该如何处理?换句话说,你不能对列表中的节点进行翻转。

示例:

输入:(7 -> 2 -> 4 -> 3) (5 -> 6 -> 4)

输出:7 -> 8 -> 0 -> 7

本题的话和上面不一样链表不是逆置的,但是加法运算其实需要从最后面对齐开始,也就是理论上应该从链表尾部开始向前,但是这是个单链表,这样运算的话时间复杂度太高,所以我们要用空间换时间:用栈来解决。

将链表的节点依次放到两个栈中,然后两个栈同时取数计算。但是待返回的是个链表,所以采取头插法即可(如果不头插最后反转也可),具体流程可以参考如下图:

加减乘除最新算法(大数加减乘除一文彻底搞定)(18)

逻辑

实现代码为:

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {Stack<Integer>stack1=new Stack<>;Stack<Integer>stack2=new Stack<>;while (l1!=){stack1.add(l1.val);l1=l1.next;}while (l2!=){stack2.add(l2.val);l2=l2.next;}ListNode val=new ListNode(0);//带头结点int moreadd=0;//余数while (!stack1.isEmpty||!stack2.isEmpty||moreadd!=0){int num=moreadd;//num=余数 链表1 链表2if(!stack1.isEmpty)num =stack1.pop;if(!stack2.isEmpty)num =stack2.pop;moreadd=num/10;num=num;//链表头插ListNode node=new ListNode(num);node.next=val.next;val.next=node;}return val.next;}}

加减乘除最新算法(大数加减乘除一文彻底搞定)(19)

结语

到这里,大数的加减乘除基本都讲解完啦,不知道你有没有收获,因为这里的大数都是用字符串的方式存储和处理,遇到的最多,但是也可能遇到一些链表、数组等其他形式存储的需要处理,但是整体的思想都是一样的。

光看没有还要多多练习对应的题目,当然本人水平有限上面理解可能有误或者不到位还请指正!

加减乘除最新算法(大数加减乘除一文彻底搞定)(20)

4月23日晚8点,欢迎来到CSDN直播间,与资深行业专家雷明老师一起探讨机器学习所必须掌握的数学知识。

为了写论文给 Linux “投毒”,导致整个大学都被 Linux 拉黑!

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页