气垫床 店面挂

drool 发表于 2019-5-3 02:10
谢谢，我在想1M用递归会stack overflow吗？当中有可能超过Int.MAX吗

会的 也会超过int 的范围

qoobee 发表于 2019/05/03 07:57:58


会的 也会超过int 的范围

我是想说你是不是忘了用long

drool 发表于 2019-5-3 13:15
我是想说你是不是忘了用long

真可爱。。 嗯 用了啊。 这个bug在哪。。因为我后面还有面试 没时间思考。。面试我的天竺小哥和我一起研究了十几分钟也无解。。 没事儿！等两个星期我保证去研究！

谢谢分享

qoobee 发表于 2019-5-6 04:13
真可爱。。 嗯 用了啊。 这个bug在哪。。因为我后面还有面试 没时间思考。。面试我的天竺小哥和我一起研 ...

1M 如果你跑出475的话是overflow 的问题，主要原因 map的containsKey(Object key)

如果你传进去一个int，compiler是不会报错的。。。顺带去看了一个长久以来的疑问，为啥是object，不是K

https://www.youtube.com/watch?v=wDN_EYUvUq0

Collection 的作者给出了答案（需要看前8分钟，从0开始看，否则容易lost）
楼主是不是辉夜大小姐看多了，真是可爱

话说楼主怎么写的非递归，我觉得难度很高啊，也就是top down不行，只能bottom up，但bottom up的话不能保证从1开始往上涨是按顺序populate，不能保证之前已经出现过啊，楼主咋做的，求被吊打

jackalsin 发表于 2019-5-7 14:30
话说楼主怎么写的非递归，我觉得难度很高啊，也就是top down不行，只能bottom up，但bottom up的话不能保证 ...

话说 楼主和你们比可能太2 大概思想是这个样子我就觉得是非递归性质的了。至少不是反复通过function a调用function a, 迅速瞎涂下 就是这个样子的。。 你别嘲笑我。。

1. public static int getSteps(int n, HashMap<Long, Integer> m) {
   
2.         int step = 1;
   
3.         int next = n;
   
4.         if (m.containsKey(n))
   
5.            return m.get(n);
   
6. 
   
7.             while (next > 1) {
   
8.                 if (m.containsKey(next)) {
   
9.                     step += m.get(next);
   
10.                     break;
    
11.                 } else {
    
12.                     if (next % 2 == 1) {
    
13.                         next = next * 3 + 1;
    
14.                     } else {
    
15.                         next = next / 2;
    
16.                     }
    
17.                     step++;
    
18.                 }
    
19.             }
    
20. 
    
21.             m.put((long) n, step+1);
    
22.         return step;
    
23.     }

复制代码

qoobee 发表于 2019-5-8 09:56
话说 楼主和你们比可能太2 大概思想是这个样子我就觉得是非递归性质的了。至少不是反复通过function a调 ...

楼主，两个问题，你的bug 有两个，
第一个是你的每次运算都比维基百科上多1
第二个是我上一个帖子。。。<code>get(Object key) </code>

你这个solution中途步骤没有记录。。。我觉得那个面试官故意为难你，这个不记录中间步骤的结果也太傻了

比如 3 (not calculated) -> 10 -> 5 ....
这个10的步骤不会被记录。。。。如果强行不用recursion，倒是可以把中间数字push到stack，手动recursion

jackalsin 发表于 2019-5-9 00:24
楼主，两个问题，你的bug 有两个，
第一个是你的每次运算都比维基百科上多1
第二个是我上一个帖子。。 ...

大概理你的意思了！ 谢谢！

jackalsin 发表于 2019-5-7 14:23
1M 如果你跑出475的话是overflow 的问题，主要原因 map的containsKey(Object key)

如果你传进去一个in ...

1M 应该是524么？