一亩三分地论坛

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

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

[算法题] 在careercup 网站上面看到一道amazon的面试题 但是题目看不懂 求大神解释一下

[复制链接] |试试Instant~ |关注本帖
jackjiang2 发表于 2014-8-20 01:59:43 | 显示全部楼层 |阅读模式

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

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

x
网址如下
http://www.careercup.com/question?id=5380513791475712
请大神解释一下 这道题到底是啥意思
跪谢
 楼主| jackjiang2 发表于 2014-8-20 02:24:40 | 显示全部楼层
看得我脑袋迷糊
0.0
回复 支持 反对

使用道具 举报

 楼主| jackjiang2 发表于 2014-8-20 04:34:14 | 显示全部楼层
有木有 大神呀
回复 支持 反对

使用道具 举报

Limos 发表于 2014-8-20 05:10:22 | 显示全部楼层
有8个雕像,0,1,2,3,4,5,6,7,每一个雕像指向“North, South, East or West.”中的某一个方向。
按照给的input,就是每一个雕像具体指的某个方向,通过如下规则:
每次只能选取ABCDEFGHZ中的一个,比如你选择A,就只能转动雕像0和1,选择B,只能转动雕像0,1,2.
顺时针转动90度,具体说来就是可行的是E->S, S->W, W->N, N->E.
Move
A: 0,1
B: 0,1,2
C: 1,4,5,6
D: 2,5
E: 3,5
F: 3,7
G: 5,7
H: 6,7
使得全部雕像指向同一方向的最少步数。
Test Case 3:
input: NNSEWSWN
Output: 6
Exp: John uses Move A twice, B once, F twice, G once. This will result in all statues facing W.
首先选择A两次,将0和1由N转到S的位置,
然后选择B一次,将0,1,2转到W的位置。
再选择F两次,将3 E->W,7 N->S
G一次,5 S->W, 7 S->W
由此,全部的雕像都指向W。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| jackjiang2 发表于 2014-8-20 05:33:34 | 显示全部楼层
Limos 发表于 2014-8-19 16:10
有8个雕像,0,1,2,3,4,5,6,7,每一个雕像指向“North, South, East or West.”中的某一个方向。
按照给的i ...

灰常感谢
回复 支持 反对

使用道具 举报

ryancooper 发表于 2014-8-21 04:45:05 | 显示全部楼层
这题就是直接的BFS,使用位运算来对状态进行编码,特别的,我对N,E,S,W以编码成对应3位二进制位的四个数0,1,2,3。之所以选择用3位而不是2位是因为在3位的情况下,我们可以很容易的通过下列式子转到新的状态:newState = (state + moves) & MASK。moves会在对应受第i+1号操作(因为是zero-based)影响的statues位置上置1。由我们的编码可知要转到新方向就只是简单的做加法就可以了。唯一需要注意的是位置状态值是3的情况,这时候+1的结果需变回0,所以只要在与上设计好的掩码就可以了。

python代码在: https://gist.github.com/ryancooper/c385cdb4650cecd6ec1c
回复 支持 反对

使用道具 举报

ryancooper 发表于 2014-8-21 04:48:02 | 显示全部楼层
其实这题还有个更快的方法,就是构造模4的同余方程组,然后通过结合辗转相除法的高斯消元解出来(我们可以预先算出逆矩阵)。如果把逆矩阵hard code进程序,那么基本只要常数时间就能求出任意输入的解。
回复 支持 反对

使用道具 举报

 楼主| jackjiang2 发表于 2014-8-29 01:28:15 | 显示全部楼层
ryancooper 发表于 2014-8-20 15:45
这题就是直接的BFS,使用位运算来对状态进行编码,特别的,我对N,E,S,W以编码成对应3位二进制位的四个数 ...

0.0 我用bfs来做吧 你说的方法太高端
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 20:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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