空气床电面

kqxqx 发表于 2017-12-12 23:47
是的，不用recursion的话得注意逻辑，保证所有中间结果都能cover掉

我最后几分钟写的iteration的版本 ...

我就用的是java，结果爆了。我改成iteration的方法，异常的慢，但是我试了小的数字，比如100，结果都是一样的。所以我觉得你被面试官坑了

daguanyuan 发表于 2017-12-13 00:03
我就用的是java，结果爆了。我改成iteration的方法，异常的慢，但是我试了小的数字，比如100，结果都是一 ...

我写的那个iteration也慢，原因就是我说的不少中间结果没有放到cache里去，但是这个不好做，我现在也没有好的办法

recursion的话，结果是对的，N=1,000,000爆栈后，我试了N=100,000这个case，能跑出结果，但是面试官说他没有N=100,000的测试结果，所以不认

能问下大佬几年工作经验么？怎么我投A就被秒拒了

为了加速memoization表的存取可以用一个vector作为primary memo，一个unordered_map作为secondary memo

此外这题目有个坑就是对于N = 1000000，中间结果是会超过int表示范围的，比如n = 704511时，中间结果会到达 56991483520

写了一份参考代码，带优化编译的话大概100~200毫秒可以跑完：

1. #include <algorithm>
   
2. #include <cstdint>
   
3. #include <iostream>
   
4. #include <stack>
   
5. #include <unordered_map>
   
6. #include <vector>
   
7. 
   
8. class Solution {
   
9. public:
   
10.   std::int64_t exec(const std::int64_t N) {
    
11.     // 调整这个系数会影响性能
    
12.     // 系数越大，耗费空间越多，但速度也越快
    
13.     // 8应该是一个比较好的选择...
    
14.     constexpr std::int64_t kFactor = 8;
    
15. 
    
16.     bound_ = N * kFactor;
    
17.     primary_memo_ = std::vector<std::int64_t>(bound_, -1);
    
18.     secondary_memo_ = std::unordered_map<std::int64_t, std::int64_t>();
    
19. 
    
20.     std::vector<std::int64_t> stk;
    
21.     stk.reserve(N);
    
22. 
    
23.     setMemo(1, 0);
    
24.     for (std::int64_t i = 2; i < N; ++i) {
    
25.       // pre-check以加速运算
    
26.       if (getMemo(i) >= 0) {
    
27.         continue;
    
28.       }
    
29. 
    
30.       std::int64_t curr = i;
    
31.       std::int64_t ret = -1;
    
32.       stk.push_back(curr);
    
33. 
    
34.       // 模拟的递归调用
    
35.       while (ret < 0) {
    
36.         const std::int64_t next = (curr & 0x1) ? (curr * 3 + 1) : (curr >> 1);
    
37.         if ((ret = getMemo(next)) < 0) {
    
38.           stk.push_back(next);
    
39.           curr = next;
    
40.         }
    
41.       }
    
42. 
    
43.       // 模拟的递归返回
    
44.       while (!stk.empty()) {
    
45.         setMemo(stk.back(), ++ret);
    
46.         stk.pop_back();
    
47.       }
    
48.     }
    
49. 
    
50.     return *std::max_element(primary_memo_.begin() + 1,
    
51.                              primary_memo_.begin() + N);
    
52.   }
    
53. 
    
54. private:
    
55.   inline std::int64_t getMemo(const std::int64_t key) const {
    
56.     if (key < bound_) {
    
57.       return primary_memo_[key];
    
58.     } else {
    
59.       auto it = secondary_memo_.find(key);
    
60.       return it == secondary_memo_.end() ? -1 : it->second;
    
61.     }
    
62.   }
    
63. 
    
64.   inline void setMemo(const std::int64_t key, const std::int64_t value) {
    
65.     if (key < bound_) {
    
66.       primary_memo_[key] = value;
    
67.     } else {
    
68.       secondary_memo_.emplace(key, value);
    
69.     }
    
70.   }
    
71. 
    
72.   std::int64_t bound_;
    
73.   std::vector<std::int64_t> primary_memo_;
    
74.   std::unordered_map<std::int64_t, std::int64_t> secondary_memo_;
    
75. };
    
76. 
    
77. int main(int argc, char *argv[]) {
    
78.   Solution s;
    
79.   std::cout << s.exec(1000000) << "\n";
    
80. 
    
81.   return 0;
    
82. }

复制代码

自己用c++试了一下，确实是因为在113383 这个数overflow了， 然后就死循环了

magicsets 发表于 2017-12-21 14:33
为了加速memoization表的存取可以用一个vector作为primary memo，一个unordered_map作为secondary memo

...

太感谢了！看来这个题目的坑主要就是N=1,000,000的时候中间需要计算的n会超过32位int的表示范围，我回去改了一下我的code，把int换成long型，其余的不变，recursion + memorization就能跑出正确的结果了。哎，怎么当时就没有想到是这个问题呢 anyway，当时的code确实没有跑出正确结果，只好move on了

补充内容 (2017-12-22 00:50):
N=100,000，则中间需要计算的最大n=1570824736，没超出int范围；
N=1,000,000，则最大n=56991483520，远超int范围。看来这个1,000,000的测试数据是精心挑选的，就是个坑。

qiu_cqupt 发表于 2017-12-21 12:52
能问下大佬几年工作经验么？怎么我投A就被秒拒了

4年多一点

kqxqx 发表于 2017-12-21 23:54
太感谢了！看来这个题目的坑主要就是N=1,000,000的时候中间需要计算的n会超过32位int的表示范围，我回去 ...

所以，正确答案是524是么？

daguanyuan 发表于 2017-12-27 06:37
所以，正确答案是524是么？

我是按照525算的，初始条件1算1（指的是变化序列的长度）

kqxqx 发表于 2017-12-21 23:54
太感谢了！看来这个题目的坑主要就是N=1,000,000的时候中间需要计算的n会超过32位int的表示范围，我回去 ...

对，应该就是数据类型的问题，我用java 写了一下，也得改写数据类型才能得出525

不过要是可以用python写，可能真心就需要担心这个问题了。。。