【第三轮】6.16-6.22 CareerCup 1.1

【解题思路】
Assume the input is an ASCII string(256). Create a boolean array to record all states. Traverse the string and return false if any char has seen before. Return true after the traversal. 参考了前面的思路。。
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/bindai/ee3b6b970e3c3cb4eadb

---------------Optional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】
input: empty String
output: true


https://gist.github.com/bindai/ee3b6b970e3c3cb4eadb

【解题思路】
可以使用hash table，但有点麻烦。替代方案是使用一个bool数组，长度设为ASCII的所有字符种类（256）即可，每一个元素的默认值为false。然后遍历这个字符串，如果一个字符第一次出现，对应的元素改为true；如果多于一次出现，则可以直接返回false。
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/seemuch/af64b140e576b6ea73ad#file-1_1-cc
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】
None

serolins 发表于 2014-6-17 07:21
额，sort的时候，是不是还是要先变成char的数组呢？如果是这样，也许就不是O(1)的空间复杂度了吧...

U ...

我也不是很清楚python的sorted函数的实现，不过应该是直接对字符串操作，所以用这个方法的前提是允许对原串进行改变。

【解题思路】 参考前面的总结，定义256 的列表，输入字符串，循环判断每一个字符是否出现过
【时间复杂度】不太会算复杂度，感觉像是O(n)...
【空间复杂度】
【gist link】https://gist.github.com/yokiy/78f19dc4d30a762cb4d9

刚开始学python，用python编的，第一次刷题蠢哭，希望和大家一起坚持下去～

【解题思路】 用256长度的数组作为哈希表记录是否重复
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/nealhu/39858575893644bc06d6

Solution 2:
【解题思路】
Assume  the string in under a certain encoding schema.  Use an extra boolean array of the size of the encoding schema, map each character in the string to its encoding, check for duplications
【时间复杂度】
O(n) time,
【空间复杂度】
  O(1) space

Solution 3:
【解题思路】
Compare each pair of characters in the string, if there are same ones then the string is not unique
【时间复杂度】
O(n^2) time,
【空间复杂度】
no extra space


【gist link】
https://gist.github.com/XiaoxiaoLi/fb7e79f68fd6b6861a44

【解题思路】Converting chars into ASCII number, then use a array of bool to lable if a char is already in the string.
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/pchong90/0b5d8edf151189658024
【test case】

【解题思路】 跟楼上各种一样用ascii做index
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/KikSamuel/f00a1a81f3ea353ccd82