楼主: wrj5518
跳转到指定楼层
上一主题 下一主题
收起左侧

[CareerCup] 【第三轮】6.16-6.22 CareerCup 1.1

 
🔗
sanguine 2014-6-23 11:27:02 | 只看该作者
全局:
sanguine 发表于 2014-6-23 10:31
请问一下这个题如果用bitset该如何写?据说这样很好的节省了空间?

然后在stackoverflow上看到另外一种 ...

bitset知道如何解答了

Assume all the characters are ASCII, and need 256 bit to store characters, which means a int[8] is enough to store all the ASCII characters.

For Example: the code of characters 'b' is 98, 98/32=3, means it's in the int[3]
98%32=2, which means it's the bit 2 in the int[3]

Using English to explain the idea is difficult
回复

使用道具 举报

🔗
qianhuang 2014-6-23 19:53:32 | 只看该作者
全局:
sanguine 发表于 2014-6-23 10:38
能稍微解释下bitset吗?没有理解?

看你的代码感觉和普通的Boolean[256]或int[256]数组一样啊,就是用 ...

int[256],一个单元就4个字节,bitset一个单元才一个bit,当然bitset节省空间了。
回复

使用道具 举报

🔗
ivycheung1208 2014-6-24 02:14:45 | 只看该作者
全局:
上周赶作业去了…这周抓紧赶上进度……

【解题思路】不要脸的先偷看了=。=
1. 捉对厮杀 O(n^2)
2. sort and compare O(nlogn)
3. assume ASCII set, use bool array/vector O(n)
【时间复杂度】
O(n)
【空间复杂度】
O(1) constant
【gist link】
https://gist.github.com/21ce1ff43745a9c10d4e
【test case】
null string returns true
回复

使用道具 举报

🔗
sanguine 2014-6-24 22:31:02 | 只看该作者
全局:
serolins 发表于 2014-6-17 07:16
【解题思路】需要考虑string中character的类型,这个只有面试的时候自己问了。
如果是最general的characte ...

我比较好奇这个空间复杂度是怎么计算的,你的实现中isAllUniqueCharacterTypeKnown函数因为用的是boolean[128],属于constant,所以是O(1)?但是isAllUniqueGeneral函数中我感觉用的HashSet是的空间是根据你输入的String类型的length有关,所以应该是O(n)?

是这样吗?我一直搞不懂如何计算空间复杂度
回复

使用道具 举报

🔗
sanguine 2014-6-25 16:39:51 | 只看该作者
全局:
Solution 1
The most inefficient way is using two loops.
Time Complexity: O(n^2)

Solution 2
Assume all the input are ASCII, we can use a Boolean[] to check whether the characters in the string is duplicated. First, you can ask the interviewer whether the ASCII are 128 or extended 256, then initial a Boolean[] such as checkBoolean[256], initial each elements in the array to be false. After that, traverse all the elements, if the checkBoolean == true, which means the element has been duplicated. Output False to the console and exit. Otherwise, mark the checkBoolean[i] to be true, and check the next element.
Time Complexity: O(n)
Space Complexity: O(1)

Solution 3
Use the HashSet to fast implement. (general solution that not satisfied the Question requirement: no additional data structure)
As we all known, the Set collections cannot have same elements. So we can use the HashSet to check whether there are duplicate characters.
Time Complexity: O(n)
Space Complexity: O(n)

Solution 4
1. using the toCharArray() method to change the string type into Char[]
2. Use the Arrays.sort() Collections to sorted the Char[] by ascending order.
3. check whether the char[i] and char[i+1] is equal, and return the result.

Time Complexity: O(nlogn)
Space Complexity: O(n)

Solution5:
use bit to store the status of the character.

Link is here: http://www.jyuan92.com/post-259

望补充!


[/i][/i]
回复

使用道具 举报

🔗
心焰 2014-6-25 21:38:38 | 只看该作者
全局:
【解题思路】

1. Use a set to store appeared chars, if anyone of them has already existed, then break.
2. Otherwise, brute-force comparison
【时间复杂度】
  1. O(n) 2. O(n^2)
【空间复杂度】
  O(1)
【gist link】
(Only implement the 1st one)
https://github.com/FinalF/CarrerUp/blob/master/uniqueChar.java   
回复

使用道具 举报

🔗
qiamoe 2014-6-26 00:07:47 | 只看该作者
全局:
/*Solution 1:
* implement with a nested loop, compare every characters behind it
* if ith character equals (i+j)th return false and break the loop
* return true after the loop is end*/
//the nested loop indicate the time complex should be O(N*N)
//and it is a in-place solution

/*Solution 2:
* Sort the string as an array
* then check if ith character equals the (i+1)th character*/
// O(nlgn)

// Solution 3:  answer in the book, time O(n) space O(1)

https://gist.github.com/qiamoe/9319797

好久不逛论坛什么时候又开始刷题啦混蛋!把之前刷一半的甩上来先好了
回复

使用道具 举报

🔗
辉哥哥 2014-6-26 05:50:14 | 只看该作者
全局:
【解题思路】使用hashset,从头至尾便利string 2.两次for loop, 暴力解法
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link】https://gist.github.com/linyuhui5684/2ccb0a79a794d7bfbf3d


【解题思路】两次for loop, 暴力解法
【时间复杂度】O(n*n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/linyuhui5684/2ccb0a79a794d7bfbf3d
回复

使用道具 举报

🔗
kimi81017 2014-6-27 22:52:27 | 只看该作者
全局:
【解题思路】
用256位(Extended ASCII码的个数)的数组来判断该字符是否已出现过了
【时间复杂度】
  O(n)
【空间复杂度】
  O(1)
【gist link】
https://gist.github.com/WOLOHAHA/1408fb20ad4eaad7447a
回复

使用道具 举报

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

本版积分规则

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