空气床电面

houpy 发表于 2017-12-27 08:09
对，应该就是数据类型的问题，我用java 写了一下，也得改写数据类型才能得出525

不过要是可以用python ...

用python的话，到底需不需要改数据类型才能得出525？

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

不知道你有没有试过在leetcode playground 里面跑一下，java 换成long 依旧跪。。。

kqxqx 发表于 2017-12-27 08:28
用python的话，到底需不需要改数据类型才能得出525？

上面打错了，python里面也有long， 我觉得也还是需要考虑这个问题的

但貌似改成了也还是没有解决算法运行速度的瓶颈啊

houpy 发表于 2017-12-27 09:19
不知道你有没有试过在leetcode playground 里面跑一下，java 换成long 依旧跪。。。

我是在自己机器上跑的，用的gcc编译器，用long型可以。但要严格考究起来，应该是用long long型，因为long型c++标准至少32位就行，但实际上在现在大多数64位机器上都是64位，long long型好像是至少64位。

所以，我不知道java或者python有没有类似的问题？

用recursion + cache的话，主要就是stack空间可能会overflow的问题，big O应该是最优的了

kqxqx 发表于 2017-12-27 10:22
我是在自己机器上跑的，用的gcc编译器，用long型可以。但要严格考究起来，应该是用long long型，因为long ...

分析是对的。。