【第三轮】6.16-6.22 CareerCup 1.1

1.1 Implement an algorithm to determine if a string has all unique characters. Whatif you cannot use additional data structures?

回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------optional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

Notice：
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子，除了贴解法，欢迎讨论，集思广益
4、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改。

【解题思路】
我理解的是题意是不能用hash和bitmap等其他数据结构？
直接对string排序， 逐次比较相邻的字符
【时间复杂度】
O(nlog(n)) -- 取决于排序算法
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/monkerek/f008f983280c2daf755d

Solution 1
The most inefficient way is using two loops.
Time Complexity: O(n^2)

Solution 2
Assume all the input are ASCII, we can use a Boolean[] to check whether the characters in the string is duplicated. First, you can ask the interviewer whether the ASCII are 128 or extended 256, then initial a Boolean[] such as checkBoolean[256], initial each elements in the array to be false. After that, traverse all the elements, if the checkBoolean == true, which means the element has been duplicated. Output False to the console and exit. Otherwise, mark the checkBoolean[i] to be true, and check the next element.
Time Complexity: O(n)
Space Complexity: O(1)

Solution 3
Use the HashSet to fast implement. (general solution that not satisfied the Question requirement: no additional data structure)
As we all known, the Set collections cannot have same elements. So we can use the HashSet to check whether there are duplicate characters.
Time Complexity: O(n)
Space Complexity: O(n)

Solution 4
1. using the toCharArray() method to change the string type into Char[]
2. Use the Arrays.sort() Collections to sorted the Char[] by ascending order.
3. check whether the char[i] and char[i+1] is equal, and return the result.

Time Complexity: O(nlogn)
Space Complexity: O(n)

Solution5：
use bit to store the status of the character.

Link is here: http://www.jyuan92.com/post-259

望补充！


[/i][/i]

【解题思路】
假设是aci把..256的大小.unicode什么的..太复杂了.
【时间复杂度】
N
【空间复杂度】
N
【gist link】
无
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】
"" 空String 是true把..也是unique..


https://gist.github.com/gaoyike/bedec0889b830a813902

【解题思路】假设string里所有的字符都是ascii，以各个字符的ascii为索引查询一个大小为128的boolean数组就好。
【时间复杂度】O(n)
【空间复杂度】O(1)+O(n)
【gist link】https://gist.github.com/anonymous/071cbca01a61d0fb3e9a
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】
null 返回false.

【解题思路】

• 用一个数组储存 每次储存新字符的时候检查数组 如果存在直接return
• 如果字符库只限于26个英文，那么用下标0-25代表a－z即可 存在为1 不存在为0 有1则return
• 依旧是数组，如果空间无限制，可以将2扩展为所有asc编码（忘了asc编码总共有几个 255个还是多少？都还给c语言老师了）
• 如果不使用数据结构，暂时想不出来，有个思路是继续利用asc码，然后维护一个int来加减或其他运算，最后通过动态加减的结果判断是否有重复的。
  

【时间复杂度】

• 最坏 N^2（忘了怎么算了 明天一定学会）
• N
• N
• 待解决
  

【空间复杂度】

• N
• 26
• 255/？
• 待解决
  

【gist link】

https://gist.github.com/immortaliqi/c50de4e2df35e7b27f69

【解题思路】
  Create a boolean array with all initial value True
  Read one character at a time, and set the corresponding array index of ASCII value to be False,
  Return True if the string has been fully iterated, otherwise return False
【时间复杂度】
  O(n)
【空间复杂度】
  O(1)
【gist link】
https://gist.github.com/habina/aeb70fa03ad97d370c5a

【解题思路】
如果不用其它data structure可以对其中所有的char 两两之间比较 前提是有至少两个char的话
【时间复杂度】
O(N^2)  
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/atlas1017/5d38b4919be4b3a96109

【解题思路】
参考了下大牛们的思路。把字符转换为ASCII。创建bool 数组检验选中字符是否已经在bool数组里存在。
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/anonymous/efaa69ffe8d5af283ff1

【解题思路】
1. 如果字符是ASCII码，用256大小的bool数组或者bitset去存该字符是否出现过。
2. 如果空间复杂度限制在O(1)，暴力搜索。
3. 如果string可以被毁坏的话，可以sort in place，然后对比相邻元素。
【时间复杂度】
1. O(n)
2. O(n^2)
3. O(nlogn)
【空间复杂度】
1. O(字符集大小)
2. O(1)
3. O(1)
【gist link】
https://gist.github.com/qianhuang/970914734385592bc39a

【解题思路】
Hash，假设字符集是ASCII的话就用一个int count[256]数出现的次数，如果某个字符出现次数大于1，就不unqiue。
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/anonymous/6b88e0640729b97e460b