共计 4533 个字符,预计需要花费 12 分钟才能阅读完成。
前言
最近,大数加减频频登上口试的舞台,小伙伴们也分享本人遇到面试官碰到大数运算的题目,想着这么 重要而简略 的知识点我还没写过,那得好好和大家一起总结一下。
各位有过分类刷题的小伙伴,可能看到很多人分类 字符串、贪婪、动静布局、bfs、dfs、大数、数论等,初听大数,你可能会差别:大数是个啥?听起来怪高大上的。
大数,其实就是很大很大数字 (可能远超 32、64 位,根底类型无奈示意) 的加减法,在 Java 中咱们能够应用一个大数类 (BigInteger 等) 很容易解决大数的各种运算,但如果遇到面试官他必定会让你手写的。
这个数字个别用字符串、链表等模式示意、返回,大数运算的外围就是:模仿,模仿咱们日常用纸笔算数字的加减乘除流程,而后再依据计算机、编程语言等个性适当存储计算即可,不过,大数除法运算略微非凡一点,和咱们间接模仿的思维形式稍有不同。
大数加法
大数加法是最简略的,简略模仿即可。首先,咱们想一下两个数加法的流程:从右向左计算求和、进位,始终到最初。
在编程语言中同样也是模仿从右向左逐位相加的过程,不过在具体实现上须要留神一些细节。
1、枚举字符串将其转换程 char[]
提高效率
2、从右往左进行计算,能够将后果放到一个数组中最初组成字符串,也能够应用 StringBuider 拼接,拼接的时候最初要逆置一下程序。
3、余数每次叠加过须要清零,两数相加如果大于等于 10 即有余数,增加到后果中该地位的数也应该是该数 %10 的后果。
4、计算完最初还要看看余数是否为 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();
}
大数减法
加法对应的就是减法,有了下面大数加法的实现思路,那么我想你在大数减法也应该有点想法,然而减法和加法不同的是减法有地位的区别,加法须要进位而减法须要借位。并且大整负数减法可能产生正负也不肯定。
两个负数,如果大数减去小数,那么一切正常,后果是一个负数;但如果小数减去大数,那么后果将是一个正数,并且后果解决起来比拟麻烦。所以在这里全副转成大 - 小解决(大 - 小不存在不能借位的状况)。
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), 那么解决上一位进行减法时候还要将借位的解决一下。
这题在力扣上没有原题,然而能够在小米 OJ【大数相减】上验证本人代码的正确性,具体实现的代码为:
public static boolean compare(String num1,String num2) {if(num1.length()<num2.length())
return false;
else if(num1.length()>num2.length())
return true;
else
return 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 的总词数,将后果要以字符串形式保留,前面始终迭代到最初为止, 这尽管是一道除法运算的题,然而也蕴涵减法和加法(次数叠加到后果中)。
当然,也有一些人应用二分法来压缩寻找能够被减的次数也是能够的(加法能够迭代数字实现二分倍数),具体实现的话也不是很艰难,然而代码量可能比拟多所以个别的面试口试不会让你现场写的,所以好好把握后面的减法、减法、乘法的代码即可。
当然,如果你仍然很想看大数除法局部的代码,能够百度搜一下或者在文末评论催更一下,如果有感兴趣的能够前面把代码补充上。
结语
到这里,大数的加减乘除根本都解说完啦,不晓得你有没有播种,因为这里的大数都是用字符串的形式存储和解决,遇到的最多,然而也可能遇到一些链表、数组等其余模式存储的须要解决,然而整体的思维都是一样的。