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

总结：
1.1 mplement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?
边界条件:
1.长度为0（null）直接返回false,因为啥也没有啊
多种思路：
1.可以先排序再判断，不过需要原地排序
Clarification：
1.要问清是否可以改变原字符串，可以的话才能排序呢
总结：
if 如果可以用额外空间
    if 是unicode, 用hashtable
    if 是ascii, bitmap 就解决了
else
    if 不可以更改现有代码， 先原地快排再邻居比较
    else 就两层loop解决吧

来晚了，哎。迟到的刷题生啊。

https://gist.github.com/5565573.git

https://gist.github.com/5565582.git

不知道面试的时候会不会要求把递归的快排变成迭代？
有木有大神指导一下这个是不是重点？

https://gist.github.com/mogutou1214/5581704
刚刚开始练习写CODE，用最土的O(n*n)

I am using brute force to do this problem

https://gist.github.com/yaoqimin2013/5804402

另外sort法也可以用inplace的merge sort。。merge上来如果相同就删掉一个，这般sort好就不必再过一遍了

grassgigi 发表于 2013-2-17 17:43
if we can use additional array, then use bitmap for all characters
with no additional data structur ...

Looks good. BTW, I m wondering is there an easy way to envalue the Bitmap initial value to be all 0, except for the iteration.

Fanyare 发表于 2013-2-18 07:10
https://github.com/quantumrose/CareerCup/blob/master/1.1.IsUniqueChars.java

boolean array / bit v ...

Hi Fanyare,
I just read ur code. On method 2, why do u need to %8 to val ?
Thx

Fanyare 发表于 2013-2-18 07:10
https://github.com/quantumrose/CareerCup/blob/master/1.1.IsUniqueChars.java

boolean array / bit v ...

Let's see: if val=160, we check "(bitVector[val / 8] & 1 << val % 8) != 0". In this statement, val%8 is always 0 when val is multiple of 16. So if val = 160 again, it won't return false.

Use a int, which is 4 bytes, and 32 bits, as a bitmap
https://gist.github.com/GTCoder/8091561