📣 VIP通行证夏日特惠 限时立减$68
查看: 5463| 回复: 33
跳转到指定楼层
上一主题 下一主题
收起左侧

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

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改


上一篇:请问database administrator如何刷题?
下一篇:【第四轮】3.30 - 4.5 Career Cup 1.2
推荐
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大米 +7 收起 理由
pure0909 + 7 感谢分享!

查看全部评分

回复

使用道具 举报

全局:
【解题思路】
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

评分

参与人数 1大米 +7 收起 理由
pure0909 + 7 感谢分享!

查看全部评分

回复

使用道具 举报

推荐
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大米 +7 收起 理由
pure0909 + 7 感谢分享!

查看全部评分

回复

使用道具 举报

🔗
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大米 +7 收起 理由
pure0909 + 7 感谢分享!

查看全部评分

回复

使用道具 举报

🔗
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大米 +7 收起 理由
pure0909 + 7 感谢分享!

查看全部评分

回复

使用道具 举报

地里匿名用户
🔗
匿名用户-BRFXB  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大米 +7 收起 理由
pure0909 + 7 感谢分享!

查看全部评分

回复

使用道具 举报

🔗
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大米 +7 收起 理由
pure0909 + 7 感谢分享!

查看全部评分

回复

使用道具 举报

🔗
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大米 +7 收起 理由
pure0909 + 7 感谢分享!

查看全部评分

回复

使用道具 举报

🔗
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大米 +7 收起 理由
pure0909 + 7 感谢分享!

查看全部评分

回复

使用道具 举报

🔗
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大米 +7 收起 理由
pure0909 + 7 感谢分享!

查看全部评分

回复

使用道具 举报

🔗
芒果舞 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大米 +7 收起 理由
pure0909 + 7 感谢分享!

查看全部评分

回复

使用道具 举报

🔗
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大米 +7 收起 理由
pure0909 + 7 感谢分享!

查看全部评分

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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