Sogou笔试题之求无限循环小数循环节

这道题目是搜狗笔试题第一道大题,求无限循环小数的循环节,例如1/7=0.14285714285714285,则循环节为428571 拿到这道题目第一想法就是当作普通字符串来处理,依次截取前面部分与后面部分进行比较,直到找到重复的,则重复部分为循环节 侥幸进了面试,面试官第一题就问我这题的解题思路,我把思路讲给他听,被他抓了N了Bug,最后也找不出好的解决方案,于是第一题就以失败告终…

回来之后,用笔算了一下,发现了规律,思路如下:

  回想我们使用手算时如何发现循环节: 
  如果除得的余数等于0,则说明整除; 
  如果除得的余数不等于0,则将余数乘以10,继续相除; 
  直到发现两次获得的余数相等,则找到了循环节。
  以下程序用一个ArrayList来存储余数,当某次求得的余数在这个ArrayList里面已存在,则循环找到

代码如下:

import java.util.ArrayList;
import java.util.List;

public class CircleDigitsInDivision {

	/**
	 * 题目:求循环节,若整除则返回NULL,否则返回循环节
	 * 解答: 回想我们使用手算时如何发现循环节: 
	 * -如果除得的余数等于0,则说明整除; 
	 * -如果除得的余数不等于0,则将余数乘以10,继续相除; 
	 * -直到发现两次获得的余数相等,则找到了循环节。
	 * 以下程序用一个ArrayList来存储余数,当某次求得的余数在这个ArrayList里面已存在,则循环找到
	 */
	public static void main(String[] args) {
		int dividend=1;
		for(int i=1;i<50;i++){
			String str = circleDigits(dividend,i);
			if(str!=null){
				System.out.println(dividend+"/"+i+"-"+str+"-"+(0.0+dividend)/i);
			}
		}
	}

	public static String circleDigits(int dividend, int divisor) {
		if (dividend < 0 || divisor <= 0) {
			return null;
		}
		if (dividend % divisor == 0) {
			return null;
		}
		List<Integer> quotientList = new ArrayList<Integer>();//store a/b
		List<Integer> leftList = new ArrayList<Integer>();//store a%b
		int left= dividend % divisor;
		while(!leftList.contains(left)){
			leftList.add(left);
			left*=10;
			int quotient=left / divisor;
			quotientList.add(quotient);
			left%=divisor;
			if(left==0){
				return null;
			}
		}
		int circleBegin=leftList.indexOf(left);
		quotientList = quotientList.subList(circleBegin,quotientList.size());
		StringBuilder sb=new StringBuilder();
		for(int i=0,len=quotientList.size();i<len;i++){
			sb.append(quotientList.get(i));
		}
		return sb.toString();
	}
}