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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3875 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

"Do this without extra space."

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

leetcode

extra

space

21 条回复 • 2015-03-26 23:03:49 +08:00

jiang42

2015-03-26 16:55:21 +08:00

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

sneezry

2015-03-26 16:56:16 +08:00

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

chlx

2015-03-26 16:58:32 +08:00

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

F281M6Dh8DXpD1g2

2015-03-26 17:02:27 +08:00

x.to_s.reverse == x.to_s

sneezry

2015-03-26 17:05:05 +08:00

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

F281M6Dh8DXpD1g2

2015-03-26 17:07:42 +08:00

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

zhyu

2015-03-26 17:09:03 +08:00

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

F281M6Dh8DXpD1g2

2015-03-26 17:21:39 +08:00

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

billlee

2015-03-26 17:21:54 +08:00

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

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

zhyu

2015-03-26 17:30:25 +08:00

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

Andiry

2015-03-26 17:36:06 +08:00 via Android

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

F281M6Dh8DXpD1g2

2015-03-26 17:37:02 +08:00

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

msg7086

2015-03-26 17:37:40 +08:00

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

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

msg7086

2015-03-26 17:41:57 +08:00

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

msg7086

2015-03-26 17:43:01 +08:00

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

raincious

2015-03-26 17:46:30 +08:00

@liprais

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

C++渣路过。

zhyu

2015-03-26 17:48:31 +08:00

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

raincious

2015-03-26 17:57:33 +08:00

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

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

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

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

大家其实可以和气点……

msg7086

2015-03-26 21:42:41 +08:00 via iPhone

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

misaka

2015-03-26 21:52:22 +08:00

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

bsbgong

2015-03-26 23:03:49 +08:00

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