leetcode-166-分数到小数(fraction to recurring decimal)-java

题目及测试

package pid166;
/* 分数到小数

给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以字符串形式返回小数。

如果小数部分为循环小数，则将循环的部分括在括号内。

示例 1:

输入: numerator = 1, denominator = 2
输出: "0.5"

示例 2:

输入: numerator = 2, denominator = 1
输出: "2"

示例 3:

输入: numerator = 2, denominator = 3
输出: "0.(6)"


*/




public class main {
	
	public static void main(String[] args) {
		int[] testTable1 = new int[]{1,2,2};
		int[] testTable2 = new int[]{2,1,3};
		for(int i=0;i<testTable1.length;i++){
			test(testTable1[i],testTable2[i]);
		}
	}
		 
	private static void test(int ito,int ito2) {
		Solution solution = new Solution();
		String rtn;
		long begin = System.currentTimeMillis();
		
		System.out.print(ito+" "+ito2);		    
		
		System.out.println();
		//开始时打印数组
		
		rtn = solution.fractionToDecimal(ito,ito2);//执行程序
		long end = System.currentTimeMillis();	
		
		//System.out.println(ito + ": rtn=" + rtn);
		System.out.println( " rtn=" +rtn);
//		for (int i = 0; i < ito.length; i++) {
//		    System.out.print(ito[i]+" ");
//		}//打印结果几数组
		
		System.out.println();
		System.out.println("耗时：" + (end - begin) + "ms");
		System.out.println("-------------------");
	}

}
           

自己没想出来

解法1（别人的）

分析：这里面需要考虑下面几个问题：

1、如何循环求数？

2、如何判断重复？

3、如何结束循环？

4、会不会溢出？

对于第一个问题：如果直接除数除以被除数，然后去逐位来找，那样的话是非常难以实现的（即使可以实现，那找循环体简直变成了不可能事件）。那换个思路，我们每次都作除，然后取整数部分，然后余数*10，继续下去。这样就简单多了，因为取整是非常简单的（强制类型转换即可）。

第二个问题：如何判断重复，对于这种思路而言，当余数在以前的历史中出现过，就可以判断剩下的数据也会不断重复。因此，我们可以存一个hashmap，key就是出现的除数，然后value就是结果数组的index值。只要包含该key时，就可以停止了。

第三个问题：已经回答了，只要包含有key或者除数为0时就可以停止了。

第四个问题：溢出怎么办？对待溢出最简单的解决方案是将其转换为更大的类型。

/**实现除法运算，结果返回为String类型的浮点数。
 * 必须要考虑的就是循环小数，当余数跟之前重复的时候就出现了循环小数
 * 可以根据这个来设计我们的算法*/
public String fractionToDecimal(int numerator, int denominator) {
	
	   /**首先考虑除数为0，被除数为0的特殊情况*/
	   if(numerator==0) return "0";
	   if(denominator==0) return String.valueOf(Integer.MAX_VALUE);
	   
	   /**其次考虑两个数的符号不一致的情况*/
	   String res=new String();
	   if((numerator<0)^(denominator<0))
		   res=res+"-";
	   
	   /**考虑到Int类型为-2^32的溢出，所以转化为long，一定要先转换再求绝对值
	    * 既然已经考虑了符号，就可以直接转为绝对值**/
	   long num=Math.abs((long)numerator);
	   long den=Math.abs((long)denominator);
	   
	   /**区别整数部分和小数部分*/
	   long ren=num/den;
	   long rem=num%den;
	   res=res+String.valueOf(ren);
	   
	   /**没有小数部分，直接返回**/
	   if(rem==0) return res;
	   
	   
	   res+='.';
	   /**采用map来存储余数，以及该余数对应的小数的位置，这样方便我们为循环小数打括号*/
	   Map<Long,Integer> map=new HashMap<Long,Integer>();
	   int beg=res.length();
	   while(rem>0)
	   {
		   rem=rem*10;
		   ren=rem/den;
		   /**如果出现重复，需要截取出循环的部分打括号**/
		   if(map.containsKey(rem))
		   {
			   /**循环前**/
			   String part1=res.substring(0,map.get(rem));
			   /** 循环后*/
			   String part2=res.substring(map.get(rem));
			   res=part1+"("+part2+")";
			   break;
		   }
		   else
		   {
			   res+=String.valueOf(ren);
			   map.put(rem, beg);
		   }
		   /**更新位置计数和余数**/
		   beg++;
		   rem=rem%den;
		   
	   }
	   
		 return res;  
        
    }
           

解法2（别人的）

类似，循环的本质是：例如

a=x*b+y    然后a=y*10，然后a=x*b+y   下一次出现的y与上一次的y相同。

注意：y不一定只有一位，如果被除数b超过1位，比如17，y可能为15之类的，所以记录下每次的余数y即可。

public String fractionToDecimal(int numerator, int denominator) {
    if (numerator == 0) {
        return "0";
    }
    StringBuilder fraction = new StringBuilder();
    // If either one is negative (not both)
    if (numerator < 0 ^ denominator < 0) {
        fraction.append("-");
    }
    // Convert to Long or else abs(-2147483648) overflows
    long dividend = Math.abs(Long.valueOf(numerator));
    long divisor = Math.abs(Long.valueOf(denominator));
    fraction.append(String.valueOf(dividend / divisor));
    long remainder = dividend % divisor;
    if (remainder == 0) {
        return fraction.toString();
    }
    fraction.append(".");
    Map<Long, Integer> map = new HashMap<>();
    while (remainder != 0) {
        if (map.containsKey(remainder)) {
            fraction.insert(map.get(remainder), "(");
            fraction.append(")");
            break;
        }
        map.put(remainder, fraction.length());
        remainder *= 10;
        fraction.append(String.valueOf(remainder / divisor));
        remainder %= divisor;
    }
    return fraction.toString();
}