[第二轮] 2/18-2/24 CareerCup 1.1

jerrysun 发表于 2013-2-19 00:35
看了一会才明白，ls是把 unique characters 当作输入并且放到bitmap里去的；
大概对题目的理解不一样吧. ...

https://gist.github.com/anonymous/4985790
https://gist.github.com/anonymous/4985912

可能我理解错题目意思了，这是3个solutions！

1. sort，比较临近元素是否有相同的
2. 利用unordered_map实现O(1)查找

https://gist.github.com/skxie/f0b5978eebe86f1eefc4

https://github.com/ltongrc/CareerCup/blob/master/UniqueChar.java

https://github.com/1094401996/Ca ... ot1/UniqueChar.java

方法一：快排之后扫以便
方法二：hashtable
方法三:bitmap....

新手求指教，扫描一遍string，对于每一个char判断它之后有无相等的
https://gist.github.com/ThunderXu/5013616

bainikolaus 发表于 2013-2-17 16:44
先排序, 然后再把每个字符和它后面一个字符比较:
https://gist.github.com/bainikolaus/4970686

排序算法需要额外的空间吧

“you cannot use additional data structures”是指不能使用额外的空间么？ data structure要怎么理解呢，array这些才叫做data structure？

最容易想到的是这个：
将当前字符跟之后的所以字符逐个比较，找到相同的字符则返回；否则循环结束返回。
时间复杂度O(n^2).

好一点的算法：
先排序(O(nlogn)), 再比较当前字符跟后面的第一个字符(O(n))。
时间复杂度O(nlogn)

https://gist.github.com/Andy1989/6cc0a170344e9da23206

额，多发了一次。

https://gist.github.com/sjtuzyt/5028673

https://gist.github.com/sjtuzyt/5028620