【第三轮】6.16-6.22 CareerCup 1.3

fang_wu 发表于 2014-6-24 21:15
为啥我试过不行啊？如果不转换的话，只是一个数组，那么只会比较首地址，在java中的equal，只有转换为str ...

我的意思是直接写for循环判断两个char[]字符是否equal

String的equal()一样用的是for循环遍历==只不过封装起来了而已，但是你这里用toString又会新建新的String对象

sanguine 发表于 2014-6-24 21:19
我的意思是直接写for循环判断两个char[]字符是否equal

String的equal()一样用的是for循环遍历==只不过 ...

自己写的再简单都可能有bug，还是封装的靠谱。不过你的建议也是很有道理的

sanguine 发表于 2014-6-24 20:18
空间复杂度为什么是O(1)？

不是利用了额外Int[]空间吗？

哪个是256个不同的字符..
当然, 你可以假设有无限个不同的字符.........

其实是n...

sanguine 发表于 2014-6-24 20:39
1. first to check whether the length of the two input string is equal is very important! Don't for ...

You are right. Thanks!

sanguine 发表于 2014-6-24 20:36
为什么Solution1的space complexity是O(1)，而Solution2是O(n)，一直都不太会计算space complexity~~~

...

我觉得他写反了。Solution1 应该是O(N)，因为把string转成了char[]，Solution2是O(1)，只开了一个int[256]的数组，大小是constant的，与N无关

serolins 发表于 2014-6-19 06:58
【解题思路】
基本思路，先看两个string中是不是有null，有直接返回false。再看长度是否相同，不同直接返 ...

我不同意你说的“256的时候space是O(1), 否则还是O(n)”，因为字符是有总数限制的（constant），输入的字符数量是可以近似无限的，但O(n)是一个线型关系

readman 发表于 2014-6-24 23:19
哪个是256个不同的字符..
当然, 你可以假设有无限个不同的字符.........

那HashMap的话，因为根据input String而改变空间大小，所以是O(n)？

serolins 发表于 2014-6-25 05:16
你的意思是说，只要字符种类的个数是有限的，那么就不是线性关系因为O(CONSTANT) = O(1)。有道理，谢谢纠 ...

我觉得是的。因为O(1)的定义就是存在某个n1和c1，N>n1时，恒有f(N) <= c1*1=c1，这里的c1就是所有的字符种类数。unicode可以表示目前已知的所有字符，最多也就100w个（全都遇到的几率基本上为0了。。。）。其实说它是O(n)从数学角度也是说得通的，但一般大家说的都是tight upper-bound。
P.S. 我觉得这题的空间使用写Theta(1)更合适，存在n1，c1和c2，N>n1时，恒有c2<=f(N) <=c1，c2可以N=n1时遇到的不同字符的个数，c2取所有字符的种类数。

chouclee 发表于 2014-6-25 09:57
我觉得是的。因为O(1)的定义就是存在某个n1和c1，N>n1时，恒有f(N) n1时，恒有c2

1.4里的题目写的是if implementing in Java, please use a character array so that you can perform this operation in place

这样的话，char[] = new string.tocharArray()
按道理是根据input String来分配空间，char[]不应该也是O(n)吗？为什么就是in place了？