當了一年的 Facebook Rotational Software Engineer 心得分享

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 1094|回复: 5
收起左侧

[CareerCup] 【第四轮】4.13 - 4.19 Career Cup 3.4

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

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

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

x
3.4 In the classic problem of the Towers of Hanoi, you have 3 towers and N disks of
different sizes which can slide onto any tower. The puzzle starts with disks sorted
in ascending order of size from top to bottom (i.e., each disk sits on top of an
even larger one). You have the following constraints:
(1) Only one disk can be moved at a time.
(2) A disk is slid off the top of one tower onto the next tower.
(3) A disk can only be placed on top of a larger disk.
Write a program to move the disks from the first tower to the last using stacks.

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

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


A30041839 发表于 2015-4-16 13:16:39 | 显示全部楼层
[solution]
use the standard recursive solution for Hanoi problem. First Move n - 1 plates from tower1 to tower2 using tower3 as an intermediate. then move the largest plate of tower1 to tower3. Finally move n - 1 plates from tower2 to tower3 using tower1 as an intermediate.
[time]
T(n)=2T(n-1)+1
O(2^n)
[space]
O(n)
[gist]
https://gist.github.com/A30041839/b66a5f6a4356f3fc1c10
回复 支持 反对

使用道具 举报

全球28万学生4.7分推荐
iker01 发表于 2015-4-16 21:46:40 | 显示全部楼层
【解题思路】
# solution
# use the traditional Hanoi recursive solution to move the disk
【时间复杂度】
O(2**n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/zhangjiang2013/11cd967e0c146eb13876
回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-4-18 21:34:26 | 显示全部楼层
【解题思路】
use basic solution for solving Towers of Hanoi, we define three towers as origin, destination and buffer, in the buffer tower, we can treat it as middle status and transfer it to other status.
Thus we can write a recursive solution
【时间复杂度】
T(n) = 2T(n-1) +n
【空间复杂度】
O(n)
【gist link]
https://gist.github.com/JamesJi9277/99caad2644c621a98407
【test case】
回复 支持 反对

使用道具 举报

alikewmk 发表于 2015-5-1 13:21:10 | 显示全部楼层
本帖最后由 alikewmk 于 2015-5-1 13:22 编辑

【解题思路】
递归:
移动前n-1个盘子到缓冲塔上
移动第n个盘子到目标塔
从缓冲塔移动前n-1个盘子到目标塔
【时间复杂度】
如果盘子的数量是n,那么时间复杂度是O(2^n-1)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/alikewmk ... 3-4-hanoitower-java


回复 支持 反对

使用道具 举报

Godbless 发表于 2015-6-5 10:49:11 | 显示全部楼层
【解题思路】Use base case and build approach to recursively complete complicate case based
        on easier case.
【时间复杂度】O(2^n)
【空间复杂度】O(n)
【gist link] https://github.com/StephenWeiXu/ ... aster/Chap3/3_4.cpp
【test case】(optional,如果觉得比较好,欢迎贴出来分享)
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-20 18:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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