【第三轮】6.16-6.22 CareerCup 1.1

【解题思路】
把字符转换为ASCII。创建bool 数组检验选中字符是否已经在bool数组里存在。（我的疑问是不允许用别的数据结构，那数组可以用？没有排序主要是因为要么原地排序破坏string，要么需要额外空间）
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/asdw3276/5b2abe1a0d6f23ca724b

感谢所有给我code review的小伙伴

【解题思路】
1. 如果字符是ASCII码，用256大小的int数组去储存字符出现的次数。若次数大于1，则说明有重复。
【时间复杂度】
1. O(n/2)
【空间复杂度】
1. O(256)
【gist link】
https://github.com/guchang/CC150/blob/master/CC1_1.java

【解题思路】
贴上来的太晚了，太久不写java了，参考了一些前面大牛写的 ＝＝！假设字符串是由asc ii编码，则asc ii一个有256个不同的字符。用一个 256的数组来判断同一个字符串里的字符是不是出现了两次，开始时初始化所有的位置上为false
如果 字符串为null 或者为空，那么返回 false
如果 字符串的某一位已经被置为 true，那么意味着已经出现了一次。如果再次遇到，就说明出现了重复，所以返回 false。
其他情况下 返回 true
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/ZhuGuanyu/7e28fcfb14cf5675ff07
【测试数据】
string = null ;
string = "" ;

habina 发表于 2014-6-16 04:24
【解题思路】
  Create a boolean array with all initial value True
  Read one character at a time, ...

Nice idea!

【解题思路】 Heapsort
(When checking others' posts, I realize that creating a constant-size array is permitted. My first thought is we cannot use extra data structures, including arrays.....nah)
【时间复杂度】O(NlogN)
【空间复杂度】O(1)
【gist link】https://gist.github.com/larry-liu/e2cc893aa60b01545c21<-so sad....

【解题思路】: 看字符的类型决定算法，ASCII/Extended ASCII/Unicode/'a~z'/'A~Z'
【时间复杂度】: brute-force: O(N^2)______map to boolean array + bit manipulation: O(N)
【空间复杂度】: O(1)
【gist link】: https://gist.github.com/xun-gong/a6c437bd3bab09f8a817

btw: 基本上是自己思考，写一下，然后参考 http://hawstein.com/posts/ctci-solutions-contents 修改和学习的... 好像也没有办法review每个人的代码。督促作用还是很明显的

MichaelYC 发表于 2014-6-17 11:58
gist 的地址不对啊。
麻烦楼上的兄弟贴一下浏览器地址栏的地址。
谢谢~

谢谢提醒，已经改了

3angFeng945 发表于 2014-6-16 22:47
【解题思路】就是最直接的，一个一个比较
【时间复杂度】O(n^2)
【空间复杂度】O(1)

时间复杂度可以降低的：
用 Data Structure（hash set）：变成 O(n)
不用：可以为 O(NlgN)

推荐你参考一下我楼下的或者我的。
特别是我楼下的，会有帮助的。

【解题思路】only tried ASCII characters
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist link】https://gist.github.com/liubonan/edb3cb3b99526c77c84f
【test case】simple test cases

锦木千束 发表于 2014-6-16 10:39
【解题思路】好像和前面好几个人都一样，开一个256的bool数组每个代表对应的ascii是否出现过，出现一样的就 ...

space complexity should be O(N)
more comments in your code