首页 > 代码库 > Leetcode-Fraction to Recurring Decimal
Leetcode-Fraction to Recurring Decimal
Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.
If the fractional part is repeating, enclose the repeating part in parentheses.
For example,
- Given numerator = 1, denominator = 2, return "0.5".
- Given numerator = 2, denominator = 1, return "2".
- Given numerator = 2, denominator = 3, return "0.(6)".
Analysis:
We need to use long type.
Solution:
Store every digit in float part, and assemble the string at last.
1 public class Solution { 2 public String fractionToDecimal(int numerator, int denominator) { 3 if (denominator==0) return ""; 4 if (numerator==0) return "0"; 5 boolean neg = false; 6 if (numerator>0){ 7 numerator = -numerator; 8 neg = !neg; 9 }10 11 if (denominator>0){12 denominator = -denominator;13 neg = !neg;14 }15 16 17 long intPart = (long) numerator/ (long) denominator;18 long left = numerator%denominator;19 20 List<Integer> digitList = new ArrayList<Integer>();21 List<Long> leftList = new ArrayList<Long>();22 int iterStart = -1;23 while (left!=0){24 int digit = (int) (left*10/denominator);25 digitList.add(digit);26 leftList.add(left);27 long newLeft = (left*10)%denominator;28 if (leftList.contains(newLeft)){29 iterStart = leftList.indexOf(newLeft);30 break;31 }32 left = newLeft;33 }34 35 //Assemble the string.36 StringBuilder builder = new StringBuilder();37 if (neg) builder.append(‘-‘);38 builder.append(intPart);39 40 if (digitList.size()==0) return builder.toString();41 else {42 builder.append(‘.‘);43 if (iterStart==-1)44 for (int i=0;i<digitList.size();i++)45 builder.append(digitList.get(i));46 else {47 //append non-iter part.48 for (int i=0;i<iterStart;i++)49 builder.append(digitList.get(i));50 builder.append(‘(‘);51 //append iter part.52 for (int i=iterStart;i<digitList.size();i++)53 builder.append(digitList.get(i));54 builder.append(‘)‘);55 }56 return builder.toString();57 } 58 59 }60 }
Solution 2:
Store the postion of the corresponding left of every digit, assemble the result string in place.
1 public class Solution { 2 public String fractionToDecimal(long numerator, long denominator) { 3 if (denominator==0) return ""; 4 if (numerator==0) return "0"; 5 String res = ""; 6 if (numerator<0 ^ denominator<0) 7 res = "-"; 8 9 numerator = Math.abs(numerator);10 denominator = Math.abs(denominator);11 12 long intPart = numerator/denominator;13 long left = numerator%denominator;14 res = res.concat(Long.toString(intPart));15 Map<Long,Integer> posMap = new HashMap<Long,Integer>();16 if (left!=0) res = res.concat(".");17 while (left!=0){18 long digit = left*10/denominator;19 posMap.put(left,res.length());20 res = res.concat(Long.toString(digit));21 left = left*10%denominator;22 if (posMap.containsKey(left)){23 int pos = posMap.get(left);24 res = res.substring(0,pos)+"("+res.substring(pos,res.length())+")";25 left = 0;26 }27 } 28 29 return res; 30 31 }32 }
Leetcode-Fraction to Recurring Decimal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。