两道和除法相关的力扣题目
- 166. 分数到小数
- 29. 两数相除
- 快速乘
- 解法一：快速乘变种
- 解法二： 二分查找 + 快速乘
166. 分数到小数
题目链接：166. 分数到小数
题目内容：
题目是要我们把一个分数变成一个小数，并以字符串的形式返回。按道理，直接将分子numerator除以分母denominator就得到了小数，转换成string返回就好。题目要求里指出了特殊情况——小数部分如果有循环，就把循环节括在括号里。
那么问题来了，怎么知道有没有循环呢。循环节就是一段循环出现的数字，我们即便是存下来小数部分的每一位数，也不能说有数字重复了就是循环节的开始，比如0.121113，我们不能在1第二次出现的时候就判断上一个1到这个1之前就是循环节。那么是以什么重复出现判断是有循环节呢？ A➗B得到商为C，余数为R，计算小数部分时每后移一位将当前余数补0进行运算， 最终余数R==0，表示能够整除，直接将结果转换成string即可；对于有循环节的小数部分，出现重复余数时，表示有循环节。因为从该余数开始计算，一定会再变成这个余数，这样循环下去。那么这个余数第一次计算出的小数，到第二次出现这个余数对应的那位小数，之间的小数就是循环节。 
判断一个余数是否出现过，用hash表记录。由于同时要记录余数，以及余数出现的位置【以便确定循环节开始和结束位置】，因此用map。代码如下（C++）：
class Solution {
public:string fractionToDecimal(int numerator, int denominator) {//防止溢出，32位int转换成64位的longlong _numerator = numerator;long _denominator = denominator;//如果分子为0，直接返回零if(_numerator == 0)return "0";//能够整除，直接返回if(_numerator % _denominator == 0) return to_string(_numerator/_denominator);//不能整除的情况，ans表示结果字符串string ans;//异号先添加负号if(_numerator>0&&_denominator<0 || _numerator<0&&_denominator>0){ans.push_back('-');}//都变成绝对值，计算结果数值部分_numerator = abs(_numerator);_denominator = abs(_denominator);//整数部分为0if(_numerator < _denominator)ans.push_back('0');//计算整数部分else{ ans = ans + to_string(_numerator/_denominator);//numerator变成余数_numerator = _numerator % _denominator;}//添加小数点ans.push_back('.'); //map记录余数以及出现的位置unordered_map <long,int> remainder;int idx = ans.size();remainder.insert({_numerator,idx});while(_numerator){_numerator *= 10;ans = ans + to_string(_numerator/_denominator);_numerator = _numerator % _denominator; //如果余数重复出现就break，有循环 if(remainder.count(_numerator))break;remainder.insert({_numerator,++idx}); }//如果余数不为0，就有循环，循环节部分添加()if(_numerator) {ans.insert(remainder[_numerator],"(");ans += ')';}return ans; }
};
29. 两数相除
题目链接：29. 两数相除
题目内容：
理解题意就是做整数除法，返回结果截取小数部分。比如-7/3 = -2，9/4 =2这样。问题在于两个地方：1、给的dividend和divisor，可能结果会溢出；2、不能使用乘法、除法和求余，但是要完成除法求得商。
对于第一个问题，单独考虑一些情况：
- 只有在dividend = -2^31，且divisor = -1的时候，结果为2^31，会溢出；
- 当dividend = 0 时，直接返回0；
- 当divisor = 1 时，直接返回dividend；
对于第二个问题，乘法的本质是加法，可以用快速乘这个方法，用加法来完成乘法操作。除法的本质是减法，而加减是一样的，因此也能用快速乘来完成。 因此本题的重点是快速乘。
另外还需要注意dividend和divisor的符号问题，两个数有四种符号组合，同为正、同为负、一正一负、一负一正，只有在异号的情况下，结果才为负。 确定结果负号后，数值部分计算，就可以将两个数变成都是正的。但此题当dividend 或者 divisor是-2^31时，变成正数就会溢出，因此统一变成负数。
快速乘
快速乘，即用加法来实现乘法，但是不是一个一个加，而是将数字每次翻倍，成倍成倍的加。7*5可以看成是7+7+7+7+7，5的二进制表示是(101)，7+7+7+7+7组合一下，等于1*[(7+7)+(7+7)] + 0*(7+7) + 1*7，即第一次是+7，之后是+(7+7)，再下一轮是+[(7+7)+(7+7)]，每一轮要加的是上一轮的2倍，这个两倍直接用add = add + add来实现，也不需要乘法。每一轮还需要乘以倍数的二进制表达式中对应位的数值【即0或者1】。代码模板如下（C++）：
int quick_mul(int x, int n){int ans = 0; int add = x;while(n){if(n&1) //末位为1//【实际上由于n的右移操作，这一步是在看对应位是否为1//比如5 = 101，第一次循环101，末位为1，加上7//第二次10，末位为0，应该加7+7，实际加0//第三次1，末位为1，加上(7+7)+(7+7)】ans += add; //结果ans加上当前的数addadd += add; //add翻倍n >>= 1; //n右移一位}return ans;
}
解法一：快速乘变种
快速乘是在知道了一个数要乘以几之后快速求解答案的过程，除法是要去求被除数是除数的几倍，因此不能直接使用快速乘，但是可以借用快速乘中数字加倍的思想，快速找到商。 判断dividend里面还能不能有一个完整的divisor，是需要|dividend| >= |divisor|，因为都变成了负数，即dividend <= divisor就证明dividend里面有至少一个divisor，商还能加上一部分。那么dividend里面有多少个divisor需要去试，先试有1个【add = divisor】，然后试有2个【add = add + add】，然后试有4个【继续add = add + add】，然后试有8个……这样循环下去，直到某个数使得dividend > add + add了，就说明add + add里面倍数太大了，应该是add里面的倍数。之后dividend减去当前add，剩下的继续去找里面有几个divisor。
这里需要注意判断dividend < add + add，可能有溢出：当add 在-2^31 ~ -2^30之间，add+add小于-2^31，就溢出了，所以应该改成dividend - add < add。
完整代码如下（C++）：
class Solution {
public:int divide(int dividend, int divisor) {//特殊情况if(dividend == 0) return 0;if(divisor == 1) return dividend;//可能溢出的情况if(dividend == INT_MIN && divisor == -1) return INT_MAX;if(divisor == INT_MIN){return dividend == INT_MIN ? 1:0;}//防止溢出，正数变复数int rev = 1;if(dividend > 0){dividend = -dividend;rev = -rev;}if(divisor > 0){divisor = -divisor;rev = -rev;}int ans = 0; //被除数和除数都为负数，被除数小于等于除数商才大于0 while(dividend <= divisor){int add = divisor;int result = 1;while(dividend - add <= add){result <<= 1; //当前商翻倍add <<= 1; //翻倍} ans += result; //加上部分结果dividend -= add; //剩余部分继续求商 }return ans*rev; //乘以符号翻转}
};
这里在dividend更新成dividend - add后，add又变成divisor从1倍开始尝试，这其实是多余的，可以将add+=add整翻倍过程的数值记录起来，优化代码（C++）：
//记录add翻倍过程中，比dividend小的数值while (add.back() >= dividend - add.back()) {add.push_back(add.back() + add.back());
}
int ans = 0;
for (int i = add.size() - 1; i >= 0; --i) {//dividend比add[i]更小，add里面的倍数能够加载商里面if (add[i] >= dividend) {//下标是i，对应的倍数是2^i，可以用左移i位来实现ans += (1 << i);//dividend减去对应的adddividend -= add[i];}
}
解法二： 二分查找 + 快速乘
还有一种办法是尝试每一个n，看当前的n*divisor和dividend的关系，因为dividend和divisor都变成了负数，因此dividend < n*divisor才能满足条件，n继续增大去比较。这里的n*divisor就用上述的快速乘去实现——需要改动一点，就是最后返回dividend 和 n*divisor 大小关系。
n是0到2^31-1之间的一个数，要找到合适的n，可以用二分法，相较于依次挨个比较，时间复杂度更优，代码如下（C++）：
class Solution {
public:bool quick_mul(int divisor, int n, int dividend){int ans = 0;int add = divisor;while(n){//末位为1，要加上一部分if(n&1){//如果计算过程中发现ans更小，就说明n太大了，直接返回falseif(dividend - add > ans ) return false;ans += add;}//如果当前不是最后一位，还要循环几轮if(n!=1){//而下一轮要用到的add已经比dividend更小【里面包括的divisor的倍数更多】//直接终止，返回falseif(dividend - add > add)return false;add += add;}n >>= 1;}return true;}int divide(int dividend, int divisor) {//特殊情况if(dividend == 0) return 0;if(divisor == 1) return dividend;//可能溢出的情况if(dividend == INT_MIN && divisor == -1) return INT_MAX;if(divisor == INT_MIN){return dividend == INT_MIN ? 1:0;}//防止溢出，正数变复数int rev = 1;if(dividend > 0){dividend = -dividend;rev = -rev;}if(divisor > 0){divisor = -divisor;rev = -rev;}int ans = 0, left = 1, right = INT_MAX;//二分查找的过程while(left <= right){int mid = left + ((right - left)>>1);if (quick_mul(divisor, mid, dividend)){ans = mid; //当前的mid是dividend <= mid * dividor，先赋值给andif(mid == INT_MAX)break;left = mid + 1;}else{right = mid - 1;}} return ans*rev; //乘以符号翻转}
};
二分查找过程是官方题解，但是我不太理解为什么一定要and = mid这一步赋值，直接返回mid是不对的……
解释：在-7/3这个情况下，结果是-2；left一直为1，right一直减小到3，此时mid = 2，对应quick_mul返回true，left = 3；此时仍然满足循环条件，mid 更新为 3 ，但是此时quick_mul返回的是false。也就是一个quick_mul返回true的mid可能是答案，需要记录，之后如果还有mid满足条件就更新。但是满足条件后mid可能还会更新，但更新后可能就不满足条件了。因此直接返回mul是不正确的。
