Groupon面经Prepare: Max Cycle Length - neverlandly - 博客园
Read full article from Groupon面经Prepare: Max Cycle Length - neverlandly - 博客园
题目是遇到偶数/2,遇到奇数 *3 + 1的题目,然后找一个range内所有数字的max cycle length。
对于一个数字,比如说44,按照题目的公式不停计算,过程是 44, 22, 11, 8, 9 ,1(瞎起的),
从44到1的这个sequence的长度,叫做cycle length。然后题目是给一个range,比如[2,300],
求这里面所有数字的cycle length的最大值。follow up跑1到1 million
一个数一个数慢慢算,如下算法求出每个数的cycle length
5 public List<Integer> maxCycleLen(int min, int max) { 6 List<Integer> maxCycle = new ArrayList<Integer>(); 7 for (int i=min; i<=max; i++) { 8 helper(maxCycle, i); 9 } 10 return maxCycle; 11 } 12 13 public void helper(List<Integer> maxCycle, int num) { 14 int len = 1; 15 while (num != 1) { 16 if (num%2 == 1) num = num*3+1; 17 else num = num/2; 18 len++; 19 } 20 maxCycle.add(len); 21 }
follow up: 建立一个Lookup table, 算过的数就不算了
5 HashMap<Integer, Integer> map; 6 public List<Integer> maxCycleLen(int min, int max) { 7 List<Integer> maxCycle = new ArrayList<Integer>(); 8 map = new HashMap<Integer, Integer>(); 9 for (int i=min; i<=max; i++) { 10 helper(maxCycle, i); 11 } 12 return maxCycle; 13 } 14 15 public void helper(List<Integer> maxCycle, int num) { 16 int len = 0; 17 int numcopy = num; 18 while (!map.containsKey(num)) { 19 if (num == 1) { 20 map.put(1, 1); 21 maxCycle.add(1); 22 return; 23 } 24 if (num%2 == 1) num = num*3+1; 25 else num = num/2; 26 len++; 27 } 28 len = len + map.get(num); 29 maxCycle.add(len); 30 map.put(numcopy, len); 31 }