一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1411|回复: 33
收起左侧

[CareerCup] 【第四轮】3.30 - 4.5 Career Cup 1.1

[复制链接] |试试Instant~ |关注本帖
pure0909 发表于 2015-3-30 10:06:17 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
1.1 Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures.

按照国内的时间,已经是30号啦,所以正式开始第四轮刷题~

请参加活动的童鞋跟帖回复自己的解法,回复请参考以下格式:

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link]
【test case】(optional,如果觉得比较好,欢迎贴出来分享)

Notice:
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子,除了贴解法,欢迎探讨各种follow up questions,集思广益
4、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改

JamesJi 发表于 2015-3-30 20:49:29 | 显示全部楼层
【解题思路】
首先考虑String的编码类型,这样子决定了定义boolean数组的长度,assume使用的是ASCII,将整个字符串扫一遍来得到结果。存在的boolean为true、
思路二是也可以考虑将字符串先变成字符串数组,然后将所有元素的index设置为1,再将数组扫一遍,如果有出现过的,就--i,判断条件是if(index<0),return false
【时间复杂度】
思路一:O(n)
思路二:O(n)
【空间复杂度】
O(1),O(n)
【gist link]
https://gist.github.com/JamesJi9277/8ca1fc9a81316f40bd65
【test case】

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

laonong15 发表于 2015-3-30 22:40:40 | 显示全部楼层
【解题思路】
1, create an char array  for 256 ascII chars,
2, check every character from the   input string
if  the  array contains the  character   means  duplicate charactor
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link]
https://gist.github.com/michaelniu/2b74fae8c0025a9a3122
【test case】
https://gist.github.com/michaelniu/2b74fae8c0025a9a3122

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

alikewmk 发表于 2015-3-30 23:13:39 | 显示全部楼层
【解题思路】
逐个对比string内的char。
【时间复杂度】
O(n^2)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/alikewmk ... e-1-1-uniqchar-java

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

A30041839 发表于 2015-3-30 23:16:55 | 显示全部楼层
【解题思路】
1.建立一个长度256的int数组,初始化0
2.扫描字符串并计数,如果count>1返回false
【时间复杂度】
O(n)
【空间复杂度】
O(1)
[gist link]
https://gist.github.com/A30041839/8c49221bad8df5d43247
[test case]
https://gist.github.com/A30041839/8c49221bad8df5d43247

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

mnmunknown 发表于 2015-3-30 23:54:35 | 显示全部楼层
本帖最后由 mnmunknown 于 2015-3-31 00:05 编辑

【解题思路】
     Java中,String的每个character用ASCII编码的int值在0~255之间,建立一个初始值为false,大小为256的boolean array
     遍历整个String,如果每个character对应的table都是0(即首次看到),则所有character为unique,否则立即return false.
【时间复杂度】
      O(n)
【空间复杂度】
      O(1)
【gist link]
      https://gist.github.com/jiaodong/0d6309d1694f6e08ad83
【test case】(optional,如果觉得比较好,欢迎贴出来分享)

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

Fiona杀G 发表于 2015-3-31 01:02:42 | 显示全部楼层
[solution]
1.we can create a boolean arrary with size of 256 since there are
256 ascii character in total.
2.Then for each char in the string, we use the array to test whether
the current char existed before, if existed, return false.
3.After scanning the whole string, if no false returned, the function
will return true.

[time complexity]
O(n), n is the size of the string

[space complexity]
O(1), for the array with size of 256

[gist link]
https://gist.github.com/FionaT/029c6c4fc4c4e443517b

[test case]
""
"abca"
"abcde"
"bbb"

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

Howie 发表于 2015-3-31 01:22:17 | 显示全部楼层

[solution]
Create an array of boolean with size of 256. If the length of the string is above 256, it must have duplicate character. If not, for every character in the string, set its position in the array true if it is false now. If any position is true, return false.

[time complexity]
O(n)
[space complexity]
O(1)

[gist link]
https://gist.github.com/Howiezhang226/0d0c0a2a92ea07c1fa19
[test case]
""
"  "
"abcde"
"aancasd"

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

芒果舞 发表于 2015-3-31 04:20:04 | 显示全部楼层
【解题思路】
1.考虑只有ASICC码,建立一个长度256的boolean数组.
2.扫描字符串,得到字符的ASIC码的值,此值为index,查看boolean数组,如果true返回false,不是true就设为true.
【时间复杂度】
O(n)
【空间复杂度】
O(1)
[gist link]        Java
https://gist.github.com/LinyinWu/3a9634d00595de30aca5
[test case]
"" true
" " true
"  " false
"abc" true
"aba" false

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

reality 发表于 2015-3-31 07:42:34 | 显示全部楼层
Don't really understand ASCII. Solved this question by comparing every character to every other character.
time complexity: O(n^2)
space complexity: O(1)

gist link: https://gist.github.com/jocelynzz/dd561729ee00a08f99c4

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

slaink 发表于 2015-3-31 07:51:41 | 显示全部楼层
本帖最后由 slaink 于 2015-3-31 07:56 编辑

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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

coperdli 发表于 2015-3-31 10:31:01 | 显示全部楼层
本帖最后由 coperdli 于 2015-3-31 10:44 编辑

思路:假设字符串中均为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

查看全部评分

回复 支持 反对

使用道具 举报

mything 发表于 2015-3-31 12:20:49 | 显示全部楼层
【解题思路】
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】

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

A30041839 发表于 2015-3-31 12:21:06 | 显示全部楼层
coperdli 发表于 2015-3-31 10:31
思路:假设字符串中均为ascii字符,建立一个数组,以各个字符为下标,对应数组元素为该字符在字符串中出现 ...

因为一个char是8 bit吧。
回复 支持 反对

使用道具 举报

mything 发表于 2015-3-31 12:36:03 | 显示全部楼层
coperdli 发表于 2015-3-31 10:31
思路:假设字符串中均为ascii字符,建立一个数组,以各个字符为下标,对应数组元素为该字符在字符串中出现 ...

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

使用道具 举报

coperdli 发表于 2015-3-31 20:21:48 | 显示全部楼层
A30041839 发表于 2015-3-31 12:21
因为一个char是8 bit吧。

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

使用道具 举报

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

赞同(1)(2)(4),

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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

mything 发表于 2015-3-31 22:01:16 | 显示全部楼层
coperdli 发表于 2015-3-31 20:43
赞同(1)(2)(4),

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

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

使用道具 举报

yiyizheliu 发表于 2015-4-1 00:19:29 | 显示全部楼层

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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

yiyizheliu 发表于 2015-4-1 00:22:40 | 显示全部楼层
看到大家基本建立的都是256的数组,作为一个小白,弱弱的问一句为什么是256?我明明百度的ascii码表里只有128个字符。谢谢
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 00:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表