一亩三分地论坛

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

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

[CareerCup] 【第四轮】4.6 - 4.12 Career Cup 2.2

[复制链接] |试试Instant~ |关注本帖
pure0909 发表于 2015-4-7 01:40:38 | 显示全部楼层 |阅读模式

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

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

x
2.2 Implement an algorithm to find the kth to last element of a singly linked list.

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

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

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


laonong15 发表于 2015-4-7 05:35:13 | 显示全部楼层
【解题思路】
use two pointers  first pointer  move k times  then  move first and second  pointer  together   until first reach  the end
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link]
https://gist.github.com/michaelniu/d81729783fdeff6ee48c
【test case】
https://gist.github.com/michaelniu/d81729783fdeff6ee48c  (main)
回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-4-7 21:26:53 | 显示全部楼层
【解题思路】
这个题思路大家应该都比较一致,就是用快慢指针来做
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link]
https://github.com/JamesJi9277/C ... inkedLists/2.2.java
【test case】
回复 支持 反对

使用道具 举报

slaink 发表于 2015-4-8 07:17:51 | 显示全部楼层
【解题思路】
* First we need to know if there are k elements in the list,
* if not return nothing.
*
* After we find the kth element from the beginning, we create
* a new pointer pointing at the head, so the distance between
* old pointer and new pointer is `k`. Then we move them
* simultaneously until the old pointer reaches the end of the list.
* Then we get the last k elements in the list.
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link] https://github.com/bxshi/intervi ... to_last_element.cpp
【test case】(optional,如果觉得比较好,欢迎贴出来分享)https://github.com/bxshi/intervi ... c/test/2_2_test.cpp
回复 支持 反对

使用道具 举报

chongtianzs 发表于 2015-4-8 13:35:03 | 显示全部楼层
解题思路】
用快慢指针,如果快指针并检查k是否大于list的长度。
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link]
https://github.com/chongtianzs/CC150/blob/master/2.2-cc150.cpp
回复 支持 反对

使用道具 举报

alikewmk 发表于 2015-4-10 13:09:26 | 显示全部楼层
【解题思路】
快慢指针
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/alikewmk ... -2-findktolast-java
回复 支持 反对

使用道具 举报

coperdli 发表于 2015-4-10 13:47:39 | 显示全部楼层
思路:遍历链表,得出总的元素个数,由此可计算得到所求元素距离链表头部的距离,然后从头部开始搜索特定距离便可得
时间复杂度:O(n)
空间复杂度:O(1)
code snippet & test: https://gist.github.com/coperd/4ac2f0573b55e4210667

补充内容 (2015-5-4 20:30):
考虑了各位所说的哈希方法,但是在本题中不知道数据特征的情况下,如何用hash?例如,数据全是整形,那选取hash函数: f(i) = i(就是直接将链表数据映射为下标); 则哈希表的大小为max(num in list).
回复 支持 反对

使用道具 举报

芒果舞 发表于 2015-4-13 05:49:51 | 显示全部楼层
【解题思路】
1.使用static variable存count, 然后recursive调用函数。

【时间复杂度】
1.O(n)

【空间复杂度】
1.O(n)

【gist link】        Java
https://gist.github.com/LinyinWu/1013d20adbcd1ac39cbd
【test case】
"FOLLOWuuP" k=4        --->        "W"
回复 支持 反对

使用道具 举报

干.什么 发表于 2015-4-13 07:12:18 | 显示全部楼层
本帖最后由 干.什么 于 2015-4-13 07:14 编辑

【解题思路】快慢指針,基於這個數學推導過程,kth-to-last = len - k,先向前走k,然後兩個同時走,當快指針走到底的時候,慢指針就是目標元素
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link]  https://github.com/noisedispatch/CC150/blob/master/src/main/java/chap2/FindKth2Last.java
【test case】
https://github.com/noisedispatch/CC150/blob/master/src/test/java/chap2/TestFindKth2Last.java

看了上面同學的代碼,想到一個測試用例是如果輸入的 k 是一個非法的數字,比如說鏈表長度為10,而 k 是20,那麽這個時候一定要處理,否則會有異常。

此外是我自己的一個錯誤,就是在移動指針之前,一定要保證當前指針不為空才行,這個錯誤是在測試返回 head 元素時發現的。

回复 支持 反对

使用道具 举报

干.什么 发表于 2015-4-13 07:13:22 | 显示全部楼层
干.什么 发表于 2015-4-13 07:12
【解题思路】快慢指針,基於這個數學推導過程,kth-to-last = len - k,先向前走k,然後兩個同時走,當快指 ...

這裏是鏈接地址:

Source Code: https://github.com/noisedispatch/CC150/blob/master/src/main/java/chap2/FindKth2Last.java

Test Case: https://github.com/noisedispatch/CC150/blob/master/src/test/java/chap2/TestFindKth2Last.java

誰能教教我怎麼插入超級鏈接,每次都失敗
回复 支持 反对

使用道具 举报

daphne_ying 发表于 2015-4-13 21:39:35 | 显示全部楼层
【solution】
use two pointers, firstly move fast runner k-1 steps forward, and then move two pointers both one step everytime until the fast runner hit the end, return the slow runner
【time】
O(n)
【space】
O(1)
【gist link 】
https://gist.github.com/kelly-us/69c2c202a0a85ae378b2
回复 支持 反对

使用道具 举报

iker01 发表于 2015-4-14 09:47:50 | 显示全部楼层
【解题思路】
# use two pointers, one move first for k - 1 step
# then move first and second pointer at the same time
# return the second value until the first node reaches the final spot
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/zhangjiang2013/17431cb8a347cc104562
回复 支持 反对

使用道具 举报

A30041839 发表于 2015-4-14 14:38:51 | 显示全部楼层
[solution]
use two pointers, make the fast pointer go k steps than the slow pointer
[time]
O(n)
[space]
O(1)
[gist]
https://gist.github.com/A30041839/0862e9279c7c14874e22
回复 支持 反对

使用道具 举报

sevenwonder 发表于 2015-4-19 01:24:52 | 显示全部楼层
[solution]
1. slow and faster ptr. 2. recursion
[time]
1. O(n), 2. O(n)
[space]
1. O(1), 2.O(n)
[gist]
https://gist.github.com/songpu2015617/8ac85fd5ecb6b3cc3119/edit()
回复 支持 反对

使用道具 举报

Godbless 发表于 2015-5-27 09:37:18 | 显示全部楼层
【解题思路】Iterative methods - use two pointers, one is kth ahead of the other one. Then forward these
        two pointers with the same pace. When the first pointer reach the end, the second pointer
        will point to the kth element to the last element
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link] https://github.com/StephenWeiXu/ ... aster/Chap2/2_2.cpp
【test case】(optional,如果觉得比较好,欢迎贴出来分享)
回复 支持 反对

使用道具 举报

voiding 发表于 2015-5-31 02:28:48 | 显示全部楼层
【解题思路】
use two pointers. Move runner pointer K steps. and then move walker and runner pointer simultaneously. When the runner hit the end of the linked list, return walker.
【时间复杂度】
O(n)
【空间复杂度】
O(1)

GistLink including test cases
https://gist.github.com/mogutou1214/8c3d5871ea1a7da4d234
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 22:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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