【第三轮】6.16-6.22 CareerCup 1.1

【解题思路】 put every character in a hash table, and determine whether there is a same character in it
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link】https://gist.github.com/JoshuaTang/ab96ff7fe5700f81f328
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

【解题思路】Assuming the string is ASCII, we use a 256 boolean array to record whether each character has ever appeared
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/2ded9ef087b0f61317da.git
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

虽然这么做没有问题，但是在空间复杂度和时间复杂度的分析上感觉有些地方不太清楚。首先，既然假设了是ASCII码，那么必然只需要一个常数空间的数组，那么空间复杂度是O(1)应该没有太大异议，但是时间复杂度呢？在我上面的代码中，我们将整个string扫了一遍，理论上是O(N)，但是根据抽屉原理，string长度一旦超过256，必然有两个字符重复，我们完全可以直接返回FALSE，所以我认为实际的amortized time complexity应该是O(1)，希望有大牛来解答。

【解题思路】受大家启发，建立一个bool[256]的数组
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】
https://github.com/donnice/donnice/blob/master/Q1_1

【解题思路】整型保存标志, 位运算
【时间复杂度】 O(n)
【空间复杂度】 O(1)
【gist link】
python解法 https://gist.github.com/nerowong/1f08eed70776b859d207#file-cc150_1_1-py

【解题思路】
对于Extended ASCII，使用长度为256的boolean数组来保存某个字符是否已经出现。

【时间复杂度】
O(N)


【空间复杂度】
O(1)

【gist link】
https://gist.github.com/happyWinner/9f0298c454fcc1f194a6

【test case】
输入为NULL或者空字符串的时候都返回True

【解题思路】
1、利用256位的boolean数组来看是否字符已经出现过。
2、利用bitset来处理，剩下的思路基本和上题一样。

【时间复杂度】
O(N)


【空间复杂度】
O(1)

【gist link】
https://gist.github.com/Free99/da1dfbf89b2aa9159dcf

【test case】
随便敲的0.0

我有个疑问就是，似乎大家都没有做input处理是吗？就是用scanner来读取用户输入在检测unique character，而都是用的hard-code test吗？