【第四轮】3.30 - 4.5 Career Cup 1.1

yiyizheliu 发表于 2015-4-1 00:22
看到大家基本建立的都是256的数组，作为一个小白，弱弱的问一句为什么是256？我明明百度的ascii码表里只有1 ...

因为大家说ascii不是真的指ascii，而是指是否是一个字母一个字节，还是一个字母多个字节（比如unicode），所以都会开256的数组。

解题思路】
考虑extended-ascII, 建立一个256的bool数组，每个数组保存查询后的信息。扫一遍string，并将对应的char保存在数组中，若数组中有对应的char，return false。若所有元素均为unique，return true。
【时间复杂度】
O(n)
【空间复杂度】
O(1)
[gist link]        C++
https://gist.github.com/b1341cb8c0b9dc00c485.git

【解题思路】
Using a 256 space to record the occurrence of each char in the string.
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link]
python solution
https://gist.github.com/zhangjiang2013/5ffdc5a90f3c9c9526ab
【test case】(optional，如果觉得比较好，欢迎贴出来分享）

【解题思路】
Tips:
* 1.Use a boolean array to mark if this char is unique or not.
* 2.Use a binary digit to mark if this char is unique or not.
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】
https://gist.github.com/74d3213161b70991c28b
【test case】

【解题思路】
1.使用数组记录某字符是否已存在
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】
https://gist.github.com/zh355245849/86d76277d56f37385d6e

[solution]
1.create a hashmap to indicate whether a char existed before, if yes, return false
2.After scanning the whole string, if no false returned, return true.

[time complexity]
O(n)

[space complexity]
O(n)

[gist link]
https://gist.github.com/kelly-us/0e9a3411371aca3b36ee

yiyizheliu 发表于 2015-4-1 00:22
看到大家基本建立的都是256的数组，作为一个小白，弱弱的问一句为什么是256？我明明百度的ascii码表里只有1 ...

包括extended-ascii一共256

yiyizheliu 发表于 2015-3-31 11:22
看到大家基本建立的都是256的数组，作为一个小白，弱弱的问一句为什么是256？我明明百度的ascii码表里只有1 ...

ASCII加上extended ASCII一共是256···

【解题思路】
1.如果我们假设字符集是ASCII字符，那么我们可以开一个大小为256的bool数组来表征每个字 符的出现。数组初始化为false，遍历一遍字符串中的字符，当bool数组对应位置的值为真， 表明该字符在之前已经出现过，即可得出该字符串中有重复字符。否则将该位置的bool数组 值置为true。
2. 如果不能额外的空间，一种是直接两便循环找，一种是sort后看是否相邻的元素相同，如果有相同返回false, otherwise 返回true. 不知到有些同学说过一边string如果有重复count+1这个是如何实现？

【时间复杂度】
1，O(N)
2 O(N^2)，O（NLogN）
【空间复杂度】
1.O(N)
2.O(1)
[gist link]
https://gist.github.com/songpu2015617/9ea54fad07435a202dac

最后一天交作业啦

【解题思路】
*We assume that it is ASCII string. It means we can use at most 256 number to represent all characters
*I set a int array for all possible characters. Initial value are all 0.
*When we scan one character from the string, we add its value by 1.
*When we detect a character is 1, it means it has appeared. Then we return false

【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link]
https://gist.github.com/leonw007/dbb503b3459780f5bd32

【test case】included in the above link