【第三轮】6.16-6.22 CareerCup 1.1

daisyang 发表于 2014-6-18 00:25
should CHAR_MAX be 127 ?

http://www.cplusplus.com/reference/climits/
either SCHAR_MAX or UCHAR_MAX
一般一个char是一个字节，所以我默认ASCII码也是256了。。网上查了一下，标准ASCII码是128种，后面的128是扩展的。

smzfeng 发表于 2014-6-18 15:18
space complexity should be O(N)
more comments in your code

谢谢学长啊，我先继续学学算法，还是有点不太熟悉复杂度这个东西

jaly50 发表于 2014-6-18 00:00
【解题思路】
本来只想着记录26个字母是否出现过。看了前面的大神，才意识到string包括ascii里256种字符。 ...

不要大神，我就是一小菜。。。

monkerek 发表于 2014-6-16 00:20
【解题思路】
我理解的是题意是不能用hash和bitmap等其他数据结构？
直接对string排序， 逐次比较相邻的 ...

用了sorted（）产生链表空间在赋值前空间复杂度还是O(1)吗？这个sort不是in_place的

【解题思路】sort and compare
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link】
https://gist.github.com/tangxukai/8780729bd26dab49d068
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】简洁的代码胜于一切，LOL

【解题思路】
看了之前有人的思路，直接进行了排序，然后再一一比较
【时间复杂度】
使用了merge sort，时间复杂度就是sort的时间，O(nlogn)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/UncleGarden/424b3153a728220aa1c8

【解题思路】
利用bitmap记录每个出现过的字符。
根据字符先判断该位是否为0，若是则该位置1；否则返回false.
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/Tsien/a39a2edf6c4535eba329

【解题思路】
两层FOR循环从前往后挨个对比，相同的就return false, 全部检测完毕，return true, 没有考虑其他边界条件
【时间复杂度】

【空间复杂度】

【gist link】https://gist.github.com/5bb7914c8336d1166f41.git

请问一下这个题如果用bitset该如何写？据说这样很好的节省了空间？

然后在stackoverflow上看到另外一种解法，用位运算的==但是完全看不懂==也不知道思路在什么地方，能帮忙讲解吗

1. public static boolean isUniqueChars(String str) {
   
2.   int checker = 0;
   
3.   for (int i = 0; i < str.length(); ++i) {
   
4.     int val = str.charAt(i) - ‘a’;
   
5.     if ((checker & (1 << val)) > 0) return false;
   
6.     checker |= (1 << val);
   
7.   }
   
8.   return true;
   
9. }

复制代码

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

能稍微解释下bitset吗？没有理解？

看你的代码感觉和普通的Boolean[256]或int[256]数组一样啊，就是用了bitset类，每次有值则set设置为1，为什么这样就节省空间了呢？