一亩三分地论坛

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

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

[CareerCup] 【第三轮】6.23-6.29 CareerCup 2.1

[复制链接] |试试Instant~ |关注本帖
wrj5518 发表于 2014-6-22 23:59:57 | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 wrj5518 于 2014-6-23 09:32 编辑

2.1
Write code to remove duplicates from an unsorted linked list.
FOLLOW UP
How would you solve this problem if a temporary buffer is not allowed?

回复解法可以按照以下格式来
【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------optional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】


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

评分

1

查看全部评分

grassgigi 发表于 2014-6-23 03:05:38 | 显示全部楼层
【解题思路】
Use hash table to record elements showed up earlier, removed node if it shows up again later.
Follow up: for each node, scan through all of its following nodes and remove duplicates;

【时间复杂度】
O(N)
Follow up: O(N^2)

【空间复杂度】
O(N)
Follow up: O(1)

【gist link】
https://gist.github.com/chrislukkk/fc2ce325c06ab6e47c1e
回复 支持 1 反对 0

使用道具 举报

qianhuang 发表于 2014-6-23 09:58:38 | 显示全部楼层
【解题思路】
1. If the data of each node comes from a fixed character set like ASCII, we can create a array to store whether the character appear in the string. Thus, runtime is O(n), space is O(size of character set). If we don't know the range of data, we can use hashtable.
2. If the space must be O(1), we can search each character in the string, runtime time is O(n^2).
【时间复杂度】
1. O(n)
2. O(n^2)
【空间复杂度】
1. O(n)
2. O(1)
【gist link】
https://gist.github.com/qianhuang/fa817dd6f55c5c21aa39
回复 支持 反对

使用道具 举报

chouclee 发表于 2014-6-23 11:15:26 | 显示全部楼层
【解题思路】HashSet,遇到不重复的,添加进LinkedList,最后返回LinkedList。不允许用buffer的话,用brute force求解。
也考虑过先用quicksort,但是single linkedlist的交换不能做到array里面的O(1),并且two-way quicksort在应付[a,a,a,a,a,a]这种重复元素很多的数组时,复杂度接近于O(n^2)。3-way quicksort可以解决这个问题,但是算法里需要头尾两个指针依次向中间移动,而single linkedlist不能回溯到前一个元素。
【时间复杂度】O(n) / O(n^2)
【空间复杂度】O(n) / O(1)
【gist link】
HashSet: https://gist.github.com/chouclee/eba793a770b25674ad78
Brute-force: https://gist.github.com/chouclee/fddce83f4860442aa333
回复 支持 反对

使用道具 举报

readman 发表于 2014-6-23 12:21:58 | 显示全部楼层
【解题思路】
three pointers
【时间复杂度】
n2
【空间复杂度】
1
【gist link】
https://gist.github.com/gaoyike/badaff09f773e2a7707e


弱爆了我
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】
回复 支持 反对

使用道具 举报

habina 发表于 2014-6-23 14:04:36 | 显示全部楼层
Solution              : I am gonna sort the linked list first, and check value one by one, and reconnect the link and free the duplicate node
Time Complexity  : O(n^2)
Space Complexity : O(n)
Gist Link              : https://gist.github.com/habina/3896531754d629b2032f
回复 支持 反对

使用道具 举报

bearkino 发表于 2014-6-23 14:35:52 | 显示全部楼层
【解题思路】
第一步很简单想到用各种hash来去掉重复值。
follow up的就是在链表中一个一个对照的去掉重复值。
P.S. Test Case各种写不好。。直接参考一楼了  0 0

【时间复杂度】
O(N)
Follow up: O(N^2)

【空间复杂度】
O(N)
Follow up: O(1)

【gist link】
https://gist.github.com/UncleGarden/55470d66c3823ce9144e
回复 支持 反对

使用道具 举报

fang_wu 发表于 2014-6-23 19:20:59 | 显示全部楼层
【解题思路】
Hashmap
直接o(n2)的复杂度,循环比较

【时间复杂度】
O(N)
Follow up: O(N^2)

【空间复杂度】
O(N)
O(1)

【gist link】
https://gist.github.com/qiangusc/38a45fa1b39a0185b31a
回复 支持 反对

使用道具 举报

zhenzhenanan 发表于 2014-6-24 02:24:54 | 显示全部楼层
【解题思路】
1. 用hash set:建立一个hash set,并遍历链表。如果链表的点在hash set里面,则删除这个点;如果不在的话,插入到hash set里。
2. 不用hash set:两个指针,第一个current就正常遍历链表;第二个runner每一次都遍历current之前的,并查找重复的。如果有,则current所指向的。
3. 需要注意的是,删除current的时候并不能直接删除,因为需要让current之前的那一个的next指向current之后的那一个。所以我们让current永远指向当前node的前一个即可。
【时间复杂度】
用hash set: O(n)
不用hash set: O(n^2)
【空间复杂度】
用hash set: O(n)? (其实一直不知道时候hash table / hash set的时候,空间复杂度怎么算,求指点)
不用hash set: O(1)
【gist link】
https://gist.github.com/seemuch/af64b140e576b6ea73ad#file-2_1-cc
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】
回复 支持 反对

使用道具 举报

头像被屏蔽
serolins 发表于 2014-6-24 05:09:27 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

林微熙 发表于 2014-6-24 06:34:36 | 显示全部楼层
【解题思路】
不用hash set:两个指针,第一个current就正常遍历链表;第二个runner每一次都遍历current之前的,并查找重复的。如果有,则current所指向的。
需要注意的是,删除current的时候并不能直接删除,因为需要让current之前的那一个的next指向current之后的那一个。所以我们让current永远指向当前node的前一个即可。
基本上一样
【时间复杂度】
不用hash set: O(n^2)
【空间复杂度】
不用hash set: O(1)
【gist link】
https://gist.github.com/hilda8519/9d542359b602a1bb647c
回复 支持 反对

使用道具 举报

Greer728 发表于 2014-6-24 08:46:56 | 显示全部楼层
【解题思路】
1. HashSet: iterate through the linked list, if a node value is contained in HashSet, remove it; otherwise, ass the value to HashSet and move on.
2. No buffer: use two pointers, one for iterating through the linked list, the other as runner, which checks the subsequent list for duplicates.
【时间复杂度】
1. O(n)   2. O(n^2)
【空间复杂度】
1. O(n)  2. O(1)
【gist link】
https://gist.github.com/Julie728/204962f5bf5ff17026a9
回复 支持 反对

使用道具 举报

heycinderella 发表于 2014-6-24 09:26:22 | 显示全部楼层
【解题思路】
HashSet来存unique value,碰见一样的就删除
【时间复杂度】
O(n)  
【空间复杂度】
O(n)  

【解题思路】
不用extra buffer,用两个pointer,一个p1从前往后扫,另一个p2从p2下一个扫到结尾,如果碰见一样的就删除,如果到头就回p1下一个再重新往后扫,直到p1到达倒数第一个点。注意判断p1不能是null
【时间复杂度】
O(n^2)  
【空间复杂度】
O(1)  
【gist link】
https://gist.github.com/XiaoxiaoLi/8559f31eace496fc6fec
回复 支持 反对

使用道具 举报

wilbert 发表于 2014-6-24 10:42:47 | 显示全部楼层
【解题思路】
use hashtable to record the elements seem, if an element has seem before, remove it from the list
FOLLOW UP:
(1) If the order of the elements does not matter, sort the linked list first, then remove the duplicate elements
(2) If the order should be the same as original, brute-force solution
【时间复杂度】
O(N)
FOLLOW UP:
(1) O(N Log N)
(2) O(N^2)
【空间复杂度】
O(N)
FOLLOW UP:
(1) O(1)
(2) O(1)
【gist link】
https://gist.github.com/iwilbert/155842366920552262d7
回复 支持 反对

使用道具 举报

bitcpf 发表于 2014-6-24 10:52:43 | 显示全部楼层
【解题思路】Use hash table to determine if there is any duplicate item, if not, copy the item to a new list
Follow up: compare each member in the list, then delete the duplicated item
【时间复杂度】
1. O(n)   2. O(n^2)
【空间复杂度】
1. O(n)  2. O(1)
【gist link】
https://gist.github.com/bitcpf/7ce6a0976d775bd00724
回复 支持 反对

使用道具 举报

aloncgo 发表于 2014-6-24 20:27:19 | 显示全部楼层
【解题思路】用hashcode判断重复。 follow up: 没啥思路,挨个比较
【时间复杂度】O(n) follow up:O(n^2)
【空间复杂度】O(n) follow up:O(1)
【gist link】https://gist.github.com/weazord/179e61fee75273b29f8a
回复 支持 反对

使用道具 举报

guchang 发表于 2014-6-24 21:24:07 | 显示全部楼层
【解题思路】用hashcode判断重复, 有重复,删除结点。
【时间复杂度】O(n)
【空间复杂度】0~O(n)
【gist link】https://gist.github.com/guchang/c4b4c2ee2b7656b55d70
回复 支持 反对

使用道具 举报

heycinderella 发表于 2014-6-25 00:43:25 | 显示全部楼层
wilbert 发表于 2014-6-24 10:42
【解题思路】
use hashtable to record the elements seem, if an element has seem before, remove it fr ...

赞提出是否order matter
回复 支持 反对

使用道具 举报

Neal 发表于 2014-6-25 10:18:49 | 显示全部楼层
【解题思路】for each node, examine all its previous nodes and check if it's a duplicate.
【时间复杂度】O(n^2)
【空间复杂度】O(1)
【gist link】https://gist.github.com/nealhu/7047592e469cd42fdf1f
回复 支持 反对

使用道具 举报

RealityPC 发表于 2014-6-25 10:23:14 | 显示全部楼层
Method1
【解题思路】
Use hashtable to determine if a element is duplicate. If it is, delete it from the list.
【时间复杂度】O(N)
【空间复杂度】O(N)

Method2
【解题思路】
Two iterator compare element in list. Make sure elements before iterator i is unique. Any element after i that duplicated will be removed.
【时间复杂度】O(N^2)
【空间复杂度】O(1)

【gist link】https://gist.github.com/pchong90/ca41bc80780c2d1329ce
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 20:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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