LeetCode 中一道难度为 Easy 的题的疑问

[sneezry]

https://leetcode.com/problems/palindrome-number/

"Do this without extra space."

extra space诸位都是怎么理解的？然后诸位有什么巧妙的方法吗？

[jiang42]

点开Discuss会比在这里有效率多了。。。

[sneezry]

@jiang42 Discuss里同样的疑问，没人在下面讨论。

[chlx]

应该是要求O(1)的空间复杂度,

[liprais]

x.to_s.reverse == x.to_s

[sneezry]

@liprais 我开始也是这么想的，然后看到题目下的提示“If you are thinking of converting the integer to string, note the restriction of using extra space.”，当时就懵了，对“extra space”一下子就敬畏起来了……

[liprais]

@sneezry 我写了这个答案被accepted了...

[zhyu]

@liprais accepted的答案不等于最好的答案

[liprais]

@zhyu 我没说是最好的答案啊?

[billlee]

我是用除和模来做的，Accepted 了

但是我发现运行时间落在了 js 的区间里。。。（我是用 C++ 写的）

[zhyu]

@liprais 我的意思是不要被accepted误导了，不是accepted之后就完了，可能还有更好的答案存在，何况题目描述里已经明确给出提示了

[Andiry]

只要用循环生成回文数和源数比较就可以，O1 space

[liprais]

@zhyu 你还在脑补吧
1.从哪里看出我被accpeted误导了?
2.你有看主题么，楼主是在问extra space是怎么理解的,我给出了一个解法说明我理解的extra space,和OJ对此的态度，你脑补到哪去了?

[msg7086]

@sneezry 当你把数字转换成字符串的时候，你就不得不在内存里开辟一块空间来保存字符串。
同理 reverse 也会新开辟一块空间来保存翻转后的字符串。
题目就是叫你不要这样做。（因为这样就太简单了

做 leetcode 的目的是要你自己去实现一个算法，而不是用实现了算法的库函数去搭一行积木。

[msg7086]

@billlee 我之前 C++ 的代码是 700ms+ 和你一样落在 JS 里。
刚才重新提交了一次，变成 122ms 了。
换成 C 语言，50ms 了。
所以试试看换个语言？

[msg7086]

@liprais OJ 没法检测你是否有用额外空间，所以只检查答案正确与否，是否正确做题靠自觉。

[raincious]

@liprais

我觉得这就是标准答案了吧？Easy级别的+不允许extra space（也就是不能用临时变量玩）的条件来说的话。

C++渣路过。

[zhyu]

@liprais 你被没被误导，你怎么理解extra space和我没关系，脑补你对我没任何好处
我是不希望看到你的答案的人被误导，我说你的答案不是最好的有问题？

[raincious]

好吧，刚才搜了下，看到SegmentFault另一份答案（忍住不要点->）： http://segmentfault.com/a/1190000000453441

然后我就和楼主有一样的疑问了——到底怎么样才算Extra Space。

如果转换成字符串的话，那么肯定是用到了Extra Space了，毕竟隐式来了个变量，而且用字符串存数字的话，肯定也会有空间的浪费（毕竟一串char能是好多个int）。

但是SF上的那题是用了零时变量的，然后取反跑出结果。如果这道题不允许建立任何零时变量的话，那也太难了是吧？

大家其实可以和气点……

[msg7086]

@raincious 一个int型变量不需要内存空间，因为可以存储在寄存器里。字符串只能存在内存里。
临时变量不一定会占空间，不用变量直接串函数也不一定不占空间。
题目的本意是考你算法，就是要你别去用字符串来解罢了。
另外你贴的答案应该是可以继续优化的…

[misaka]

"玛丽说:你坏，你讨厌，你无理取闹。大表哥说:我哪里坏，哪里讨厌，哪里无理取闹。玛丽:你就是坏讨厌无理取闹。大表哥:你才。。。" // 我刚才帖子看下来怎么有这样的即视感。。。

[bsbgong]

这里的space指的是堆内存，也就是你创建了额外的对象来存储数据，比如new ArrayList<E>(size)
函数内的局部变量是栈内存，不算做extra space