空气床电面

blueiceni 发表于 2019-1-28 01:18
这样的是迭代没错的。不过这样完全没有优化（比如最基本的2^n就是n步，hash存下已经算过的步数之类的）的 ...

对是的，加了个cache存一下

1. private static int findLongestIterative(int n) {
   
2.     if (n < 1) {
   
3.       return 0;  
   
4.     }
   
5.    
   
6.     int longest = 1;
   
7.     Map<Integer, Integer> map = new HashMap<>();
   
8.     map.put(1, 1);
   
9.    
   
10.     for (int i = 2; i <= n; i++) {
    
11.       int step = 0, num = i;
    
12.       while (num != 1 && num >= i) {
    
13.         if (num % 2 == 0) {
    
14.           num /= 2;
    
15.         } else {
    
16.           num = 3 * num + 1;
    
17.         }
    
18.         step++;
    
19.       }
    
20.       map.put(i, step + map.get(num));
    
21.       longest = Math.max(longest, map.get(i));
    
22.     }
    
23.    
    
24.     return longest;
    
25.   }

复制代码