这是一个创建于 3529 天前的主题，其中的信息可能已经有所发展或是发生改变。
https://leetcode.com/problems/palindrome-number/
"Do this without extra space."
extra space诸位都是怎么理解的？然后诸位有什么巧妙的方法吗？
"Do this without extra space."
extra space诸位都是怎么理解的？然后诸位有什么巧妙的方法吗？
 |
1
jiang42 2015-03-26 16:55:21 +08:00
点开Discuss会比在这里有效率多了。。。
|
 |
3
chlx 2015-03-26 16:58:32 +08:00  1
应该是要求O(1)的空间复杂度,
|
 |
4
liprais 2015-03-26 17:02:27 +08:00
x.to_s.reverse == x.to_s
|
 |
5
sneezry OP @liprais 我开始也是这么想的，然后看到题目下的提示“If you are thinking of converting the integer to string, note the restriction of using extra space.”，当时就懵了，对“extra space”一下子就敬畏起来了……
|
 |
9
billlee 2015-03-26 17:21:54 +08:00
我是用除和模来做的，Accepted 了
但是我发现运行时间落在了 js 的区间里。。。（我是用 C++ 写的） |
 |
10
zhyu 2015-03-26 17:30:25 +08:00
@liprais 我的意思是不要被accepted误导了，不是accepted之后就完了，可能还有更好的答案存在，何况题目描述里已经明确给出提示了
|
 |
11
Andiry 2015-03-26 17:36:06 +08:00 via Android
只要用循环生成回文数和源数比较就可以，O1 space
|
|
12
liprais 2015-03-26 17:37:02 +08:00
@zhyu 你还在脑补吧
1.从哪里看出我被accpeted误导了? 2.你有看主题么，楼主是在问extra space是怎么理解的,我给出了一个解法说明我理解的extra space,和OJ对此的态度，你脑补到哪去了? |
 |
13
msg7086 2015-03-26 17:37:40 +08:00
@sneezry 当你把数字转换成字符串的时候，你就不得不在内存里开辟一块空间来保存字符串。
同理 reverse 也会新开辟一块空间来保存翻转后的字符串。 题目就是叫你不要这样做。（因为这样就太简单了 做 leetcode 的目的是要你自己去实现一个算法，而不是用实现了算法的库函数去搭一行积木。 |
|
14
msg7086 2015-03-26 17:41:57 +08:00
|
 |
16
raincious 2015-03-26 17:46:30 +08:00
|
|
17
zhyu 2015-03-26 17:48:31 +08:00
@liprais 你被没被误导，你怎么理解extra space和我没关系，脑补你对我没任何好处
我是不希望看到你的答案的人被误导，我说你的答案不是最好的有问题？ |
|
18
raincious 2015-03-26 17:57:33 +08:00 1
好吧，刚才搜了下，看到SegmentFault另一份答案（忍住不要点->）： http://segmentfault.com/a/1190000000453441
然后我就和楼主有一样的疑问了——到底怎么样才算Extra Space。 如果转换成字符串的话，那么肯定是用到了Extra Space了，毕竟隐式来了个变量，而且用字符串存数字的话，肯定也会有空间的浪费（毕竟一串char能是好多个int）。 但是SF上的那题是用了零时变量的，然后取反跑出结果。如果这道题不允许建立任何零时变量的话，那也太难了是吧？ 大家其实可以和气点…… |
|
19
msg7086 2015-03-26 21:42:41 +08:00 via iPhone
@raincious 一个int型变量不需要内存空间，因为可以存储在寄存器里。字符串只能存在内存里。
临时变量不一定会占空间，不用变量直接串函数也不一定不占空间。 题目的本意是考你算法，就是要你别去用字符串来解罢了。 另外你贴的答案应该是可以继续优化的… |
 |
20
misaka 2015-03-26 21:52:22 +08:00
"玛丽说:你坏，你讨厌，你无理取闹。大表哥说:我哪里坏，哪里讨厌，哪里无理取闹。玛丽:你就是坏讨厌无理取闹。大表哥:你才。。。" // 我刚才帖子看下来怎么有这样的即视感。。。
|
 |
21
bsbgong 2015-03-26 23:03:49 +08:00
这里的space指的是堆内存，也就是你创建了额外的对象来存储数据，比如new ArrayList<E>(size)
函数内的局部变量是栈内存，不算做extra space |
Select Language