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位的long
long _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);
//整数部分为0
if(_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加上当前的数add
add += 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减去对应的add
dividend -= add[i];
}
}
解法二: 二分查找 + 快速乘
还有一种办法是尝试每一个n,看当前的n*divisor和dividend的关系,因为dividend和divisor都变成了负数,因此dividend < n*divisor才能满足条件,n继续增大去比较。这里的n*divisor就用上述的快速乘去实现——需要改动一点,就是最后返回dividend 和 n*divisor 大小关系。
n是0到2^31-1之间的一个数,要找到合适的n,可以用二分法,相较于依次挨个比较,时间复杂度更优,代码如下(C++):文章来源:https://www.toymoban.com/news/detail-689476.html
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太大了,直接返回false
if(dividend - add > ans )
return false;
ans += add;
}
//如果当前不是最后一位,还要循环几轮
if(n!=1){
//而下一轮要用到的add已经比dividend更小【里面包括的divisor的倍数更多】
//直接终止,返回false
if(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,先赋值给and
if(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是不正确的。文章来源地址https://www.toymoban.com/news/detail-689476.html
到了这里,关于【leetcode 力扣刷题】数学题之除法:哈希表解决商的循环节➕快速乘求解商的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!