大数的加减乘除一篇文章搞定

本文转载自微信公众号“bigsai”，作者bigsai。转载本文请联系bigsai公众号。前言大家好，我是bigsai！（忘了加原文，扩充了今天帖子的内容）最近大数的加减法频繁出现在笔试的舞台上，小伙伴们也在群里分享了自己遇到的面试官方遇到的话题大数计算的，想着这么重要又简单的知识点我都没有写出来，只好跟大家总结一下。群里的情况，做过分类题的朋友，可能看到很多人对字符串进行分类，贪心，动态规划，bfs，dfs，大数，数论等等，当你第一次听到大数的时候，你可能会有所不同：大数字是什么？听起来怪怪的。大数其实就是非常大的数的加减法（可能远超32、64位，无法表示基本类型）。在Java中，我们可以使用大数类（BigInteger等）来轻松解决大数的各种问题。这种计算，但是如果遇到面试官，他肯定会让你手写的。这个数字一般以字符串、链表等形式表示和返回。大数运算的核心是：模拟，模拟我们用纸笔计算数字的加减乘除过程，然后根据计算机、编程语言等特点进行适当的存储和计算，不过大数除法运算有点特殊，和我们直接模拟的思维方式略有不同。转化为特殊的加减运算，后面会详细讲到。大数相加大数相加最简单，简单的模拟一下就可以了。首先我们想一下两个数相加的过程：求和并从右向左进位，直到结束。在编程语言中，也模拟了从右到左逐位相加的过程，但在具体实现中需要注意一些细节。1、枚举字符串，转成char[]，提高效率。2.从右到左计算。你可以将结果放在一个数组中，最后形成一个字符串。也可以使用StringBuider进行拼接。拼接的时候需要在最后倒序检查。3、每次叠加都需要清零余数。如果两个数相加大于或等于10，就会有余数。结果中的位置加上的数字也应该是数字%10的结果。4.计算结束时，检查余数是否为1，如果为1，则需要将其加到结果中。比如"991"+"11"算三位是002，但是还有余数需要相加，所以应该是1002。当然，实现一个加法过程的方法有很多种。可以先把字符串倒过来，从前到后计算。当然，我这里实现的是从后往前计算字符串的对应位，然后将结果按顺序添加到StringBuilder中。这道题的代码可以在【415两数相加】中查看自己的代码，实现代码为：publicStringaddStrings(Stringnum1,Stringnum2){//公众号：bigsai欢迎关注intlen1=num1.length()-1,len2=num2.length()-1;charch1[]=num1.toCharArray();charch2[]=num2.toCharArray();StringBuildersb=newStringBuilder();intremainder=0;//计算余数while(len1>=0||len2>=0){intn1=len1>=0?(ch1[len1--]-'0'):0;intn2=len2>=0?(ch2[len2--]-'0'):0;intnum=n1+n2+remainder;//求和对应的数remainder=num/10;//是否携带sb.append(num%10);//添加到结果字符串}if(remainder>0)//a进位是否还需要进位{sb.append(remainder);}//reverse就是结果returnsb.reverse().toString();}大数的减法和加法对应减法，有上面的实现思路大数的加法，那我想你在大数的减法上应该也有一些想法，但是减法和加法的区别是减法有位置上的差异。加法需要进位，而减法需要借位。并且大整数正数的减法可能产生正数或负数。对于两个正数，如果用小数减去大数，则一切正常，结果为正数；但是如果用大数减去小数，结果就是负数，处理起来比较麻烦。所以这里就全部变成big-small的处理了（不存在不能借用的big-small情况）。减法转换为大小1。在进行计算之前，先比较减数（num1）和被减数（num2）的大小。如果num1>num2，则模拟num1-num2的过程。如果是num12，比较两个数的大小，因为是字符形式，所以先比较两个字符串的长度。较长的较大，较短的较小。compareTo方法可以直接使用）。3、和加法不同的是，减法前面可能有几个前缀0，这些0需要你自己去掉。比如“1100”-“1000”的计算结果是“0100”，就得去掉前面的0，返回“100”。4.具体实现与加法类似。如果使用StringBuilder存储，则需要倒序。若为负数，则在其前加“-”。5.每个位置正常减去。如果该值小于0，那么如果需要向上借位（+10），那么需要在对前一位进行减法时处理借位。一个减法的大概过程这道题在力口上没有原题，不过你可以在小米OJ【大数减法】上验证一下你的代码是否正确。具体实现代码为：publicstaticbooleancompare(Stringnum1,Stringnum2){if(num1.length()num2.length())返回真；elsereturnnum1.compareTo(num2)>0;}publicstaticStringsubtractString(Stringnum1,Stringnum2){charsign='+';//加号//令num1>num2ifnum1=0||len2>=0){intn1=len1>=0?(ch1[len1--]-'0'):0;intn2=len2>=0?(ch2[len2--]-'0'):0;intnum=n1-n2-borrow;borrow=0;if(num<0)//需要向前借{borrow=1;num+=10;}sb.append(num);}sb=sb.reverse();//需要先翻转intindex=0;//去掉无用的'0'while(index=0;i--){for(intj=b.length-1;j>=0;j--){intindex=a.length-1-i+b.length-1-j;value[索引]+=(a[i]-'0')*(b[j]-'0');}}for(inti=0;i=0){sBuilder.append(value[index--]);}returnsBuilder.toString();}大数除法和大数加减乘法都搞定了，是模拟实现的，但是大数除法也是模拟实现的？不是，对于一个很大的数a/b，一般要求最多求它的整数解或余数，即a/b=c...d（a,b,c,d都是整数）；即a中有cb，剩下d。核心是先找出c是多少。对于程序，可以用枚举把除法变成减法，不断地从a中减去d，直到不能再减去。除法转换为减法运算，但是有一个问题。如果被除数a很大，可能有多个b，那么时间复杂度就太高了，不可能执行这么多次，那这个方法怎么优化呢？那么就要加快查找的次数，减少减法的次数。减少减法次数的最佳方法之一是扩大除数b。如果在b之后加一个'0'，那么计算的结果乘以10，减法的次数就变成原来的十分之一。按照这个思路，我们每次总能找到b的10的最大倍数（小于a），计算减去的次数然后转换成总词数减去b，将结果保存为字符串，并迭代直到结束。虽然是除法题，但是也涉及到减法和加法（将次数加到结果上）。计算思维当然有人用二分法压缩求可以减去的次数。不会让你当场写的，所以掌握前面的减法、减法、乘法代码就可以了。我也简单给出这部分代码（其他函数不再重复粘贴）：//假设num1>num2publicstaticStringdivideString(Stringnum1,Stringnum2){Stringvalue="0";//结果while(compare(num1,num2)){StringBuildersbTeam=newStringBuilder(num2);//用这个连续加0和num做减法StringBuildersbCount=newStringBuilder("1");//次数可能会很大intsubLen=num1.length()-num2.length();//统计大概需要加几个零for(inti=0;i2->4->3)+(5->6->4)输出：7->8->0->7这道题和上面的不一样，链表是不是反的，但是加法操作其实需要从最后一个对齐开始，也就是理论上应该从链表的尾部开始，但是这是单链表，这个操作的时间复杂度太高了，所以我们需要用空间换取时间：用栈来解决。将链表的节点依次放入两个栈中，然后两个栈同时取值计算。但是要返回的是一个链表，所以可以用头插入的方式（如果不用头插入，最后倒过来也可以）。具体过程可以参考下图：逻辑实现代码为：//更简洁的写法ublicListNodeaddTwoNumbers(ListNode1,ListNode2){ListNodenode=newListNode(0);ListNodeteam=node;intjin=0;//携带while(l1!=null||l2!=null){intnum=jin;if(l1!=null){num+=l1.val;l1=l1.next;}if(l2!=null){num+=l2.val;l2=l2.next;}jin=num/10;num%=10;team.next=newListNode(num);team=team.next;}if(jin!=0)team.next=newListNode(jin);returnnode.next;结语至此，大数的加减乘除基本讲解完毕。不知道大家有没有收获，因为这里的大数都是以字符串的形式存储和处理的，是遇到最多的，但是可能还有一些链表，数组等存储形式需要进行处理，但总体思路是一样的。