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();
}