除法转成减法运算
但是有个问题,如果被除数a很大很大,可能有居多个b,那么这样时间复杂度太高了,不可能执行那么多次,那么需要怎么样去优化这个方法呢?
那就要加速寻找次数,减少这个减法的次数了,减法次数减小的一个最好方案就是能不能扩大除数b。如果b后面加个'0',那么算出来的结果就乘以10,减法的次数变成原来十分之一。根据这个思想我们可以一直每次找到b的最大10的倍数(小于a)计算减的次数再换算成减b的总词数,将结果要以字符串方式保留,后面一直迭代到最后为止,这虽然是一道除法运算的题,但是也蕴含减法和加法(次数叠加到结果中)。
计算思想
当然,也有一些人使用二分法来压缩寻找可以被减的次数也是可以的(加法可以迭代数字实现二分倍数),具体实现的话也不是很困难,但是代码量可能比较多所以一般的面试笔试不会让你现场写的,所以好好掌握前面的减法、减法、乘法的代码即可。
这部分代码我也简单给一下(其他函数上面贴过就不重复贴啦):
//假设 num1>num2
public 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 开头。