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

cqx83 发表于 2013-2-17 16:36
https://gist.github.com/cqx83/4970678

测试了是对的 代码也清晰

我不清楚能不能写python，不过我觉得python比较方便，不用考虑内存分配，变量类型之类的。。。先贴一份吧，要是大家不推荐python的话我再转到c/c++上。。。https://gist.github.com/starcroce/4972658

starcroce 发表于 2013-2-18 02:29
我不清楚能不能写python，不过我觉得python比较方便，不用考虑内存分配，变量类型之类的。。。先贴一份吧， ...

I think you need improve your code style. Your python code looks very messy.
Here is mine, you can take it as reference.

https://github.com/lyyjohn45/CP1 ... ster/ifDuplicate.py

paradox 发表于 2013-2-18 03:12
I think you need improve your code style. Your python code looks very messy.
Here is mine, you ca ...

的确不用完全遍历一遍。。。小程序写多了code style的确是个问题，一直也就写个脚本什么的自己想到哪写到哪，跟写现代诗似的。。。这点以后会注意下。。。

https://gist.github.com/lynntian/4973171

Use boolean array, loop over the string. for every char in the array mark true correspondingly in the boolean array.(assume string is in ASCII code)
When the value at that position is already true, return false. Otherwise, after the for loop return true.

I think no more data structure allowed need to be more specified. I will ask if I am in an interview.

Anyway, here is my solution without extra data structure: https://gist.github.com/czhoume/4973720

use a for loop to test each char and only compare to chars that I have tested, because the substring before the current char is unique, otherwise it has returned already.

but it's still O(n^2) time.

https://github.com/quantumrose/C ... .IsUniqueChars.java

boolean array / bit vector: O(n) time, O(1) space
nested loop: O(n^2) time, O(1) space, no additional data structures

C language: https://gist.github.com/hukun01/4942084

思路：
   算法1、循环遍历string。每个字符与它后面的所有字符比较，遇到相等的字符返回false。循环到最后没有遇到的话，返回true。
              算法复杂度O(n^2)
   算法2、先sort排序后再循环遍历字符串，每次与它后面的一个字符比较。遇到相等的字符返回false。循环到最后没有遇到的话，返回true。
              算法复杂度O(nlog(n))

https://gist.github.com/KuangyinWang/4974838

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

boolean array / bit v ...

nice job.有个疑问：关于 method 2 的 if 条件判断，java 编程需要常用位运算么？