【第四轮】3.30 - 4.5 Career Cup 1.1

If there is any grammar error, please feel free to correct me! I really need to improve my writing.

> Most of the string / array manipulation problem can be seen as either bin sort or normal sort problem.

【解题思路】
1. If character value range is [0,256], do bin sort with normal vector or bit vector.
2. If character value range is large, e.g. unicode32, one should use set instead of vector. (not implemented)
3. Sort the string, and check if adjacency characters are the same.
【时间复杂度】
1. O(n)
2. O(nlogn) <- according to http://en.cppreference.com/w/cpp/container/set/insert
3. O(nlogn)
【空间复杂度】
1. O(1)
2. O(1)
3. O(n) or O(1), depending on if we need to keep the original string or not.
【gist link]
https://gist.github.com/bxshi/dc9a136ca248edf7e641
【test case】(optional，如果觉得比较好，欢迎贴出来分享）
A simple test case, feel free to use if you are using C/C++
https://github.com/bxshi/intervi ... c/test/1_1_test.cpp

思路：假设字符串中均为ascii字符，建立一个数组，以各个字符为下标，对应数组元素为该字符在字符串中出现的次数。故而我们只需扫描一遍字符串便可得到各字符出现的字数，然后在扫描一遍数组，当且仅当所有数组元素的值小于等于1时才说明all unique characters
时间复杂度：两次遍历，时间开销为O(n+128)=O(n)
空间复杂度：需要建立一个额外的数组，开销为O(128)
Code Snippet & Test Case: https://gist.github.com/coperd/10522749
PS. 我的疑问，ASCII明明就是0-127， 为何楼上的各位都偏偏用256？?  默认说ASCII就是指extended-ASCII？？

【解题思路】
1、用Hash set保存出现过的每个字母，每一个字母检查一下set里有没有相同的字母，如果有则return false
2、如果是ascii字母，可以用256长的boolean数组，办法同上。
3、如果是UTF-16，开65536长boolean数组，办法同上。
4、不能用额外空间：两层嵌套loop搜索O(N^2)
5、如果给的是C之类语言的char array，而且不在乎保存输入被改变的话，可以排序之后，扫一遍，看相临位置的有没有相同字母，有则return false；

【时间复杂度】
1、2、3、O(N)
4、O(N^2)
5、O(NlogN)
【空间复杂度】
1、2、3、O(N)
4、5、O(1)
【gist link]
https://gist.github.com/n2iw/d8b52a7f67aaa553f62f
【test case】

coperdli 发表于 2015-3-31 10:31
思路：假设字符串中均为ascii字符，建立一个数组，以各个字符为下标，对应数组元素为该字符在字符串中出现 ...

因为一个char是8 bit吧。

coperdli 发表于 2015-3-31 10:31
思路：假设字符串中均为ascii字符，建立一个数组，以各个字符为下标，对应数组元素为该字符在字符串中出现 ...

看了楼上的代码，以下是我的想法
1、要考虑null输入的情况
2、第一遍扫输入的时候，每次判断一下是否当前字母计数器已经大于0了，如果是，直接return false，这样可以第一时间退出，不用管后面的数据。
3、我习惯用++i，效率比i++高一点点（可以乎略）
4、我个人绝不省略｛｝，即使只有一行，可以避免以后改代码要加一行时出现忘加｛｝的bug

A30041839 发表于 2015-3-31 12:21
因为一个char是8 bit吧。

跟char是8 bit没关系，标准的ASCII就只用了7个bit。。倒是extended-ASCII把128-255也给用了，大家假设256也没啥错。

mything 发表于 2015-3-31 12:36
看了楼上的代码，以下是我的想法
1、要考虑null输入的情况
2、第一遍扫输入的时候，每次判断一下是否当 ...

赞同(1)(2)(4)，

关于(3). 你说的不完全对，不过这倒是个蛮有意思的问题，可以看看这里的分析：http://stackoverflow.com/questio ... etween-i-and-i-in-c

coperdli 发表于 2015-3-31 20:43
赞同(1)(2)(4)，

关于(3). 你说的不完全对，不过这倒是个蛮有意思的问题，可以看看这里的分析：http:/ ...

结论是i++和++i在不使用返回值的时候，好的编译器可能会输出同样的代码，就是说，最好的情况下i++和++i是一样的效率，但使用++i可以不依赖编译器的优化，所以我个人会都使用++i，除非必须用i++的情况。

【解题思路】
1 ASCII码表有128个字符，建立一个128个元素的数组代表每个字符在输入字符串中出现的次数。初始值为0.遍历字符串，每一个字符出现时在相对应的数组元素处加1，最后检查数组元素是否有大于1的，如果有，则说明字符串中有重复字符出现
2 这里的空字符串我按错误处理
【时间复杂度】
O(n)
【空间复杂度】
O(1)
[gist link]        c++
https://gist.github.com/yiyizheliu/0ce99f8ec8e2f9db60f2
[test case]

看到大家基本建立的都是256的数组，作为一个小白，弱弱的问一句为什么是256？我明明百度的ascii码表里只有128个字符。谢谢