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

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

🔗
mything 2015-4-1 02:57:50 | 只看该作者
全局:
yiyizheliu 发表于 2015-4-1 00:22
看到大家基本建立的都是256的数组,作为一个小白,弱弱的问一句为什么是256?我明明百度的ascii码表里只有1 ...

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

使用道具 举报

🔗
chongtianzs 2015-4-1 09:12:53 | 只看该作者
全局:
解题思路】
考虑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

评分

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

查看全部评分

回复

使用道具 举报

🔗
iker01 2015-4-1 11:55:36 | 只看该作者
全局:
【解题思路】
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,如果觉得比较好,欢迎贴出来分享)

评分

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

查看全部评分

回复

使用道具 举报

🔗
beer 2015-4-1 22:23:10 | 只看该作者
全局:
本帖最后由 beer 于 2015-4-1 22:33 编辑

【解题思路】
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大米 +7 收起 理由
pure0909 + 7 感谢分享!

查看全部评分

回复

使用道具 举报

🔗
zh355245849 2015-4-2 00:44:23 | 只看该作者
全局:
【解题思路】
1.使用数组记录某字符是否已存在
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】
https://gist.github.com/zh355245849/86d76277d56f37385d6e

评分

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

查看全部评分

回复

使用道具 举报

🔗
daphne_ying 2015-4-3 15:29:27 | 只看该作者
全局:

[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

评分

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

查看全部评分

回复

使用道具 举报

🔗
daphne_ying 2015-4-3 15:29:59 | 只看该作者
全局:
yiyizheliu 发表于 2015-4-1 00:22
看到大家基本建立的都是256的数组,作为一个小白,弱弱的问一句为什么是256?我明明百度的ascii码表里只有1 ...

包括extended-ascii一共256
回复

使用道具 举报

🔗
JamesJi 2015-4-3 21:53:49 | 只看该作者
全局:
yiyizheliu 发表于 2015-3-31 11:22
看到大家基本建立的都是256的数组,作为一个小白,弱弱的问一句为什么是256?我明明百度的ascii码表里只有1 ...

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

使用道具 举报

🔗
sevenwonder 2015-4-4 01:11:29 | 只看该作者
全局:
【解题思路】
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 感谢分享!

查看全部评分

回复

使用道具 举报

全局:
最后一天交作业啦

【解题思路】
*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

评分

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

查看全部评分

回复

使用道具 举报

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

本版积分规则

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