开发网站和电脑软件的区别,山西响应式网页建设报价,oa办公系统怎么注册,网站系统建设目标范本两道和除法相关的力扣题目 166. 分数到小数29. 两数相除快速乘解法一#xff1a;快速乘变种解法二#xff1a; 二分查找 快速乘 166. 分数到小数
题目链接#xff1a;166. 分数到小数 题目内容#xff1a; 题目是要我们把一个分数变成一个小数#xff0c;并以字符串的形… 两道和除法相关的力扣题目 166. 分数到小数29. 两数相除快速乘解法一快速乘变种解法二 二分查找 快速乘 166. 分数到小数
题目链接166. 分数到小数 题目内容 题目是要我们把一个分数变成一个小数并以字符串的形式返回。按道理直接将分子numerator除以分母denominator就得到了小数转换成string返回就好。题目要求里指出了特殊情况——小数部分如果有循环就把循环节括在括号里。
那么问题来了怎么知道有没有循环呢。循环节就是一段循环出现的数字我们即便是存下来小数部分的每一位数也不能说有数字重复了就是循环节的开始比如0.121113我们不能在1第二次出现的时候就判断上一个1到这个1之前就是循环节。那么是以什么重复出现判断是有循环节呢 A➗B得到商为C余数为R计算小数部分时每后移一位将当前余数补0进行运算 最终余数R0表示能够整除直接将结果转换成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(_numerator0_denominator0 || _numerator0_denominator0){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 -29/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可以看成是777775的二进制表示是(101)77777组合一下等于1*[(77)(77)] 0*(77) 1*7即第一次是7之后是(77)再下一轮是[(77)(77)]每一轮要加的是上一轮的2倍这个两倍直接用add add add来实现也不需要乘法。每一轮还需要乘以倍数的二进制表达式中对应位的数值【即0或者1】。代码模板如下C
int quick_mul(int x, int n){int ans 0; int add x;while(n){if(n1) //末位为1//【实际上由于n的右移操作这一步是在看对应位是否为1//比如5 101第一次循环101末位为1加上7//第二次10末位为0应该加77实际加0//第三次1末位为1加上(77)(77)】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之间addadd小于-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倍开始尝试这其实是多余的可以将addadd整翻倍过程的数值记录起来优化代码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(n1){//如果计算过程中发现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这个情况下结果是-2left一直为1right一直减小到3此时mid 2对应quick_mul返回trueleft 3此时仍然满足循环条件mid 更新为 3 但是此时quick_mul返回的是false。也就是一个quick_mul返回true的mid可能是答案需要记录之后如果还有mid满足条件就更新。但是满足条件后mid可能还会更新但更新后可能就不满足条件了。因此直接返回mul是不正确的。
