phpnumtochar技巧_大年夜数加减乘除一文彻底搞定

序言

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

这个数字一样平常用字符串、链表等形式表示、返回，大数运算的核心便是：仿照，仿照我们日常用纸笔算数字的加减乘除流程，然后再根据打算机、编程措辞等特性适当存储打算即可，不过，大数除法运算轻微分外一点，和我们直接仿照的思维办法稍有不同，它便是转换了一下成分外的加减法运算，后面会细谈。

大数加法

大数加法是最大略的，大略仿照即可。
首先，我们想一下两个数加法的流程：从右向左打算求和、进位，一贯到末了。

在编程措辞中同样也是仿照从右向左逐位相加的过程，不过在详细实现上须要把稳一些细节。

列举字符串将其转换成 char[]提高效率

从右往左进行打算，可以将结果放到一个数组中末了组成字符串，也可以利用 StringBuider 拼接，拼接的时候末了要逆置一下顺序。

余数每次叠加过须要清零，两数相加如果大于即是 10 即有余数，添加到结果中该位置的数也该当是该数 %10 的结果。

打算完末了还要看看余数是否为1，如果为1须要将其添加到结果，例如 \"大众991\"大众+\"大众11\公众算三个位置为002但还有一个余数须要添加，以是该当是1002。

一个加法流程

当然在详细实现上方法较多，你可以首先就将字符串逆置然后从前今后就可以打算了。
当然我这里实现的是字符串从后向前各个位对应打算，然后将结果顺序添加到 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%10);// 添加到结果字符串中 }if(remainder>0)//是否还须要进位 { sb.append(remainder); }//反装即为结果return sb.reverse().toString();}

大数减法

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

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

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

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

和加法不同的是，减法前面可能产生多少前缀 0，这些0是须要你去掉的，例如\公众1100\"大众-\"大众1000\"大众打算得到的结果为\"大众0100\公众,你就要把前面的0去掉返回\"大众100\公众。

详细实现的时候和加法相似，如果利用 StringBuilder 存储，须要逆置顺序，如果是个负数，前面还要加上'-'.

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

这题在力扣上没有原题，但是可以在小米 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);//负数须要返回}

大数乘法

大数乘法乍一想可能比较繁芜，由于乘法比起加法可能进位不只是1，还有两个数各种位置都须要相乘打算，这时候就须要我们化繁为简了。

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

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

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

一个乘法流程

你可能会疑问，如果两个数组的长度分别为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]%10; }int index=value.length-1;while(value[index]==0) {index--;} StringBuilder sBuilder=new StringBuilder();while (index>=0) { sBuilder.append(value[index--]); }return sBuilder.toString();}

大数除法

大数加减乘都搞定了，通过仿照来实现，但是大数除法也通过仿照来实现？

并不是，对付大数a/b，一样平常最多哀求求到其整数解或者余数，即a/b=c……d（a,b,c,d均为整）;也便是a里面有c个b，并且还剩下d。
核心是先求c是多少，对付程序来说，可以通过列举啊，将除法变成减法，从a中不断减d，一贯到不能减为止。

但是有个问题，如果被除数a很大很大，可能有居多个b，那么这样韶光繁芜度太高了，不可能实行那么多次，那么须要怎么样去优化这个方法呢？

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

当然，也有一些人利用二分法来压缩探求可以被减的次数也是可以的(加法可以迭代数字实现二分倍数)，详细实现的话也不是很困难，但是代码量可能比较多以是一样平常的口试笔试不会让你现场写的，以是好好节制前面的减法、减法、乘法的代码即可。

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

//假设 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的：

番外篇

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

两数相加(力扣02)

题目描述：

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

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

img

提示：

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

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

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

本题实在便是用一个链表存储一个数字(逆序存储)，你须要给它打算出结果后在 逆序 存储到一个链表中返回。

所谓加法的运算规则：从两个数的最低位进行打算，进行到下一位的时候须要考虑进位问题。
一贯到末了，而本题所给的链表刚好可以用来直接打算，由于链表头都是数字最低位可以直接相加，然后一贯遍历到结束。
可以用一个常数表示进位。

在详细实现(链表)的时候：

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

须要准确表示进位，并且末了要考虑以下进位

妥善返回精确节点，可以用一个头节点用来使得所有节点都正常操作，而不须要分外判断。
通过代码第一次比较啰嗦的写法：

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

优化后的代码为：

//更简洁的写法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

本题的话和上面不一样链表不是逆置的，但是加法运算实在须要从末了面对齐开始，也便是理论上该当从链表尾部开始向前，但是这是个单链表，这样运算的话韶光繁芜度太高，以是我们要用空间换韶光：用栈来办理。

将链表的节点依次放到两个栈中，然后两个栈同时取数打算。
但是待返回的是个链表，以是采纳头插法即可(如果不头插末了反转也可)，详细流程可以参考如下图：

逻辑

实当代码为：

/ 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%10;//链表头插 ListNode node=new ListNode(num); node.next=val.next; val.next=node; }return val.next; }}

结语

到这里，大数的加减乘除基本都讲解完啦，不知道你有没有收成，由于这里的大数都是用字符串的办法存储和处理，碰着的最多，但是也可能碰着一些链表、数组等其他形式存储的须要处理，但是整体的思想都是一样的。

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

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

为了写论文给 Linux “投毒”，导致全体大学都被 Linux 拉黑！

标签：大众大数