【第三轮】6.16-6.22 CareerCup 1.1

sanguine 发表于 2014-6-23 10:31
请问一下这个题如果用bitset该如何写？据说这样很好的节省了空间？

然后在stackoverflow上看到另外一种 ...

bitset知道如何解答了

Assume all the characters are ASCII, and need 256 bit to store characters, which means a int[8] is enough to store all the ASCII characters.

For Example: the code of characters 'b' is 98, 98/32=3, means it's in the int[3]
98%32=2, which means it's the bit 2 in the int[3]

Using English to explain the idea is difficult

sanguine 发表于 2014-6-23 10:38
能稍微解释下bitset吗？没有理解？

看你的代码感觉和普通的Boolean[256]或int[256]数组一样啊，就是用 ...

int[256]，一个单元就4个字节，bitset一个单元才一个bit，当然bitset节省空间了。

上周赶作业去了…这周抓紧赶上进度……

【解题思路】不要脸的先偷看了=。=
1. 捉对厮杀 O(n^2)
2. sort and compare O(nlogn)
3. assume ASCII set, use bool array/vector O(n)
【时间复杂度】
O(n)
【空间复杂度】
O(1) constant
【gist link】
https://gist.github.com/21ce1ff43745a9c10d4e
【test case】
null string returns true

serolins 发表于 2014-6-17 07:16
【解题思路】需要考虑string中character的类型，这个只有面试的时候自己问了。
如果是最general的characte ...

我比较好奇这个空间复杂度是怎么计算的，你的实现中isAllUniqueCharacterTypeKnown函数因为用的是boolean[128]，属于constant，所以是O(1)？但是isAllUniqueGeneral函数中我感觉用的HashSet是的空间是根据你输入的String类型的length有关，所以应该是O(n)？

是这样吗？我一直搞不懂如何计算空间复杂度

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]

【解题思路】

1. Use a set to store appeared chars, if anyone of them has already existed, then break.
2. Otherwise, brute-force comparison
【时间复杂度】
  1. O(n) 2. O(n^2)
【空间复杂度】
  O(1)
【gist link】
(Only implement the 1st one)
https://github.com/FinalF/CarrerUp/blob/master/uniqueChar.java   

/*Solution 1:
* implement with a nested loop, compare every characters behind it
* if ith character equals (i+j)th return false and break the loop
* return true after the loop is end*/
//the nested loop indicate the time complex should be O(N*N)
//and it is a in-place solution

/*Solution 2:
* Sort the string as an array
* then check if ith character equals the (i+1)th character*/
// O(nlgn)

// Solution 3:  answer in the book, time O(n) space O(1)

https://gist.github.com/qiamoe/9319797

好久不逛论坛什么时候又开始刷题啦混蛋！把之前刷一半的甩上来先好了

【解题思路】使用hashset，从头至尾便利string 2.两次for loop， 暴力解法
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link】https://gist.github.com/linyuhui5684/2ccb0a79a794d7bfbf3d


【解题思路】两次for loop， 暴力解法
【时间复杂度】O(n*n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/linyuhui5684/2ccb0a79a794d7bfbf3d

【解题思路】
用256位（Extended ASCII码的个数）的数组来判断该字符是否已出现过了
【时间复杂度】
  O(n)
【空间复杂度】
  O(1)
【gist link】
https://gist.github.com/WOLOHAHA/1408fb20ad4eaad7447a