狗家店面

倒序浏览 · 2021-5-14 07:50:09

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

店面的题目是：
给一个手机键盘：
1 2 3
4 5 6
7 8 9
0

从一个位置X出发，和象棋里面的马一样，只能走L型。例如1->6， 1->8。
给定初始点，和总共的步数N，问有几条可能的路径。

先转换成一个graph，列出所有

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

2）基于1），可以对10这个固定步数再做优化，例如选择2步，4步，8步和16步四组cache，这样就可以总是从cache里面读结果，不需要任何计算。

DerekDe

看起来是蠡口久伞坞如果不对麻烦纠正

dulacz

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

lld2019

我觉得这个题应该用矩阵来做，类似Floyd Warshall的做法，利用矩阵乘法(9x9)，矩阵只能有0/1, 这样可以在O(log N) 的时间内算出结果

qwseda123

这题很有意思啊已加米谢谢分享

datiantian

本帖最后由 datiantian 于 2021-5-14 12:22 编辑

谢谢分享好像0/5永远也走不到. 从5开始哪里也到不了。剩下的每个数字都可以走到另外两个数字。
所以N步的话可能的路径就是N层完全二叉树leaf的数量喽。除了从5开始的特殊情况
可以这样理解吗？

tonyele11

datiantian 发表于 2021-5-14 12:14
谢谢分享好像0/5永远也走不到. 从5开始哪里也到不了。剩下的每个数字都可以走到另外两个数字。
所以N步 ...

对的，就是要注意这个二叉树中一直在重复类似的pattern

tonyele11

DerekDe 发表于 2021-5-14 12:44
看起来是蠡口久伞坞如果不对麻烦纠正

看了一下题目上是基本上一样，但是follow up很有意思，并不是蠡口上能够测试出来的

forrestxu

感谢楼主！这里提供一个思路，可以尝试bottom-up，这样就不需要使用cache。

wantage3

forrestxu 发表于 2021-5-21 08:19
感谢楼主！这里提供一个思路，可以尝试bottom-up，这样就不需要使用cache。

bottom up 本身也是一种cache。cache了之前步数的结果。

hfpt2020

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式