妇科医院网站建设怎么做,填手机号码的广告,菏泽网站建设多少钱,百度手机卫士给定两个整数#xff0c;分别表示分数的分子 numerator 和分母 denominator#xff0c;以 字符串形式返回小数 。
如果小数部分为循环小数#xff0c;则将循环的部分括在括号内。
如果存在多个答案#xff0c;只需返回 任意一个 。
对于所有给定的输入#xff0c;保证 …给定两个整数分别表示分数的分子 numerator 和分母 denominator以 字符串形式返回小数 。
如果小数部分为循环小数则将循环的部分括在括号内。
如果存在多个答案只需返回 任意一个 。
对于所有给定的输入保证 答案字符串的长度小于 104 。 示例 1
输入numerator 1, denominator 2
输出0.5示例 2
输入numerator 2, denominator 1
输出2示例 3
输入numerator 4, denominator 333
输出0.(012)解法一
这道题说简单的话其实就是模拟下我们算除法的过程。
说难的话有很多坑的地方要注意下自己也是提交了好几次才 AC 的需要考虑很多东西。
首先说一下我们要模拟一下什么过程以 20/11 为例。
第一次得到的商就是我们的整数部分int 间运算就可以直接取到整数部分了记为 integer。
也就是 integer 20 / 11 1。
然后回想一下我们用竖式计算的过程。
如下图首先得到了商是 1余数是 9。在程序中得到余数的话可以用 被除数 - 商 * 除数。
也就是 20 - 1 * 11 9。 如下图接下来我们将余数乘以 10 做为新的被除数继续把 11 当做除数。然后得到商和新的余数。
也就是计算 90 / 11。 如下图接下来重复上边的过程用余数乘以 10 做为新的被除数继续把 11 当做除数。然后得到商和新的余数。
也就是计算 20 / 11。 如下图接下来继续重复上边的过程用余数乘以 10 做为新的被除数继续把 11 当做除数。然后得到商和新的余数。
也就是计算 90 / 11。 那么什么时候结束呢 第一种情况余数为 0说明没有循环小数。 第二种情况一开始这里爬坑了。开始觉得只要商里边出现重复的数字不考虑整数部分的数字也就是上边例子的第一个 1就可以认为出现了循环小数。 比如上边的例子8 第二次出现所以到这里不再计算。而循环小数部分就是和当前数字重复的位置到当前位置的前一个也就是 81。所以最终结果就是 1.(81)。 但提交的时候出现了一个反例如下图。 虽然出现了重复的 8但最终结果并不是 8 循环。很明显下次是 40 / 17需要商 2。至于原因就是两次商 8 所对应的被除数并不一样第一次是 150 第二次是 140。 所以为了判断是否出现循环小数我们不应该判断是否出现了重复的商而是应该判断是否出现了重复的被除数。
经过上边的分析循环也很明显了。被除数除以除数记录商。然后余数乘以 10 做为新的被除数继续除以除数。直到余数为 0 或者出现重复的被除数。
记录商的话我们将整数部分和小数部分单独记录。因为小数部分要累积记录一开始我用的是一个 int 去保存小数部分。比如第一个商是 1第二个商是 2我把之前的商乘以 10 再加上新的商。也就是 1 * 10 2 12当第三个商 5 来的时候就是 12 * 10 5 125看起来很完美。
但比如上边的例子 1/17 小数部分第一个商是 0第二个商是 5如果按上边的记录方法记录的就是 5而不是 05。另外如果商的部分数字过多的话还会产生溢出所以最终用 String 记录了商每次将新的商加到 String 中即可。
还有一个问题就是怎么判断是否出现了重复的商
很简单用一个 HashMapkey 记录出现过的被除数value 记录商出现的位置这样当出现重复被除数的时候通过 value 立刻知道循环的小数部分是多少。
最后一个问题我们只考虑了正数除以正数的例子对于正数除以负数或者负数除以负数呢和我们在纸上算一样先确定商的符号然后将被除数和除数都转为正数即可。
上边的操作会带来一个问题对于 java 而言int 类型的话负数的最小值是 -2147483648正数的最大值是 2147483647并不能把-2147483648 转成正数至于原因的话可以参考这篇文章补码。
溢出这个问题其实不是这个题的关键所以我们直接用数据范围更大的 long 去存数字就可以了。
public String fractionToDecimal(int numerator, int denominator) {long num numerator;long den denominator;String sign ;//确定符号if (num 0 den 0 || num 0 den 0) {sign -;}//转为正数num Math.abs(num);den Math.abs(den);//记录整数部分long integer num / den;//计算余数num num - integer * den;HashMapLong, Integer map new HashMap();int index 0;String decimal ;//记录小数部分int repeatIndex -1;//保存重复的位置while (num ! 0) {num * 10;//余数乘以 10 作为新的被除数if (map.containsKey(num)) {repeatIndex map.get(num);break;}//保存被除数map.put(num, index);//保存当前的商long decimalPlace num / den;//加到所有的商中decimal decimal decimalPlace;//计算新的余数num num - decimalPlace * den;index;}//是否存在循环小数if (repeatIndex ! -1) {String dec decimal;return sign integer . dec.substring(0, repeatIndex) ( dec.substring(repeatIndex) );} else {if (decimal ) {return sign integer;} else {return sign integer . decimal;}}
}有人可能会问如果数字很大又超过了 long 怎么办一种方案是之前写过的 29 题因为负数存的数更多所以我们可以把负数当做正数正数当做负数所有的计算都在负数范围内计算。另一种方案的话 java 其实已经提供了大数类 BigInteger 供我们使用就不存在溢出的问题了。至于原理的话应该和第 2 题 大数相加一样把数字用链表去存储这样多大的数字都能进行存储了然后把运算法则都封装成方法即可。
