## Saturday, February 20, 2016

### Groupon面经Prepare: Max Cycle Length - neverlandly - 博客园

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         }
21     }```
``` 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);
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);
30         map.put(numcopy, len);
31     }
```