Google面经题密码箱问题解法求问

我的是三位密码锁转动遇到特定的组合会爆炸，问怎么转。。。。。我也跪在这了

skye_luobopi 发表于 2016-1-23 18:44
我的是三位密码锁转动遇到特定的组合会爆炸，问怎么转。。。。。我也跪在这了

同学你现在知道这个怎么做了吗？求解答。。。我第一次看到这个面经就吓傻了。。

我的面经里貌似有人说会做了，你可以去看看，我现在也不会

skye_luobopi 发表于 2016-1-24 09:44
我的是三位密码锁转动遇到特定的组合会爆炸，问怎么转。。。。。我也跪在这了

我看了你的面经，关键问题在于“转动式”密码锁有两种：一种像老式电话的拨号盘那样，所有数字均匀刻在一个圆上，中间的旋柄上有一个指针，通过旋转旋柄来依次输入数字；另一种是行李箱上常用的那种，每一位数字单独有一个转盘，可以按任意顺序设置各位数字。

两种有一个关键区别：就是第一种必须顺序输入密码，每次试验的前2位必是上次试出结果的后2位；而第二种可以以任意顺序输入密码，每次试验结果的任意2位都可以和上次结果的对应2位相同。

面试官问的是哪一种？

看到这道题，人已炸。。。

aifer 发表于 2016-1-24 11:45
看到这道题，人已炸。。。

我已经不懂楼上的大神们在讨论什么了……

google bar太高。
我另一同学考的是leetcode hard里面的最短回文，用kmp解的那道。

xiaozhuxiaozhu 发表于 2016-1-24 12:55
google bar太高。
我另一同学考的是leetcode hard里面的最短回文，用kmp解的那道。

说实话现在kmp已经不算什么bar了。。

stellari 发表于 2016-1-24 11:25
我看了你的面经，关键问题在于“转动式”密码锁有两种：一种像老式电话的拨号盘那样，所有数字均匀刻在一 ...

第二种，旅行箱的密码锁，三位可以随意选择的转

skye_luobopi 发表于 2016-1-24 13:26
第二种，旅行箱的密码锁，三位可以随意选择的转

如果是这种就比较简单一些。就是把每一个三位数想象成一个图中的节点，每个节点和周围的8个节点相连。把会爆炸的组合从这个图中删去。最后实际上就是求“在一个3维图上找到从000节点开始到777节点的最短路径”。因为这个图是无权的，用BFS最合适。当然，实际的节点数只有1000，用DFS其实也可以。