【第三轮】6.16-6.22 CareerCup 1.1

【解题思路】就是最直接的，一个一个比较
【时间复杂度】O(n^2)
【空间复杂度】O(1)
【gist link】https://gist.github.com/5fbaddb1a56ef649e9dd

【解题思路】
1> 用 Hash Table 记录 String 中的 char； String 中 char 的位置就是 Hash Table 的 Key，char 本身是 Hash Table 的 value；
2> 每次记录之前，用 containValue method 来检验 Hash Table 中是否已经有了这个 Value；
3> 有则为 false；记录到最后一个 char 如果都没有的话，那么返回 true，证明这个 String 是只含有 unique char 的 String。

【时间复杂度】
O(n)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/Youchen/1596073837940c97a098

---------------Optional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】
随便自己编了3个 String，写在了mian 里面，不知道这算不算 test case。
Q: 看大家都用256的 Array，我没用这样的方法，难道我想错了。
看下大家的学习一下。

3angFeng945 发表于 2014-6-16 22:47
【解题思路】就是最直接的，一个一个比较
【时间复杂度】O(n^2)
【空间复杂度】O(1)

gist 的地址不对啊。
麻烦楼上的兄弟贴一下浏览器地址栏的地址。
谢谢~

3angFeng945 发表于 2014-6-16 22:47
【解题思路】就是最直接的，一个一个比较
【时间复杂度】O(n^2)
【空间复杂度】O(1)

gist 的地址不对啊。
麻烦楼上的兄弟贴一下浏览器地址栏的地址。
谢谢~

【解题思路】用了boolean array for ascii chars

• 我觉得假设char set是ascii不太好(虽然我也这么做了- -)，因为题目并没有明说，interview的时候最好问一下interviewer确认一下
• 其实boolean ascii array也是hash table的一种实现，ascii code -> array index
• Without using additional data structure, we can do this by either:
  

     a) comparison for all pairs of chars, O(N^2)
     b) in place sorting the string and checking equality between chars and the one next to it(O(NlgN) by quicksort)

【时间复杂度】
O(N)


【空间复杂度】
|CharSet| = O(1)


【gist link】
https://gist.github.com/chrislukkk/da436ce6b06838fd8ca0

【解题思路】设置一个256boolean的数组，这主要是不仅仅是常见的字符串，基本上所有可以出现的可能都包括了。
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link】https://gist.github.com/qiangusc/800a3e8d7edd63f593d6

【时间复杂度】O(n)
【空间复杂度】O(1)

【解题思路】
本来只想着记录26个字母是否出现过。看了前面的大神，才意识到string包括ascii里256种字符。
用了boolean array: AsciiTable[256] 判断该字符在string中是否出现过，如果出现过，就return false,否则将整个字符串遍历完成，return true.
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/jaly50/56eca3e90a8544451a54

【测试数据】
Am IeMptySTring?! has all unique characters: true

I have two versions:
version 1: using sort algorithm. time complexity O(nlogn) ,space complexity O(1)
version 2 : time complexity O(n) ,space complexity O(1)

[gist link] https://gist.github.com/daisyang/f6fbf6c9bf6c24d6ce13#file-1_1

qianhuang 发表于 2014-6-16 09:40
【解题思路】
1. 如果字符是ASCII码，用256大小的bool数组或者bitset去存该字符是否出现过。
2. 如果空间 ...

should CHAR_MAX be 127 ?

grassgigi 发表于 2014-6-17 00:17
【解题思路】用了boolean array for ascii chars

我觉得假设char set是ascii不太好(虽然我也这么做 ...

感觉return value 写反了；
你的 method 里面从上到下的三个 return，我感觉应该分别是return: true, false, true.

PS: 问下，怎么“点评”帖子 instead of “回复”？
多谢点评我的 Code。