水木社区手机版
- 主题:一道面试题，没做出来, 求指教
- 可以近似看做只往右、上两个方向移动，2 ** 24 不至于算不出来，不过 1s 肯定不够。
按照最远可以走多远的话，走 N 步，相当于从 (1,0) 往右侧一个等腰直角三角形内所有的点，再加上 x=0 线上全部的点，没算错的话，应该是
25 * 13 + 24 = 349
(0,0) 到这 349 - 26 - 2 个点（边缘上的点不用求肯定能到，(0,0) 和 (1,0) 两个点可以排除肯定不能到）。按照优先队列的话 O(N * log(N)) * 321，理论上40k以内应该能求出解来。做点儿优化的话，1s 应该问题不大。
另外感觉这道题很可能一个函数式直接常数求解，因为 O(2 * N) 等于以 O(N) 的解为原点，再求一个 O(N)。如果能证明 O(N) 的解为边缘以内除 (0,0) 和 (1,0) 所有的点，那就不难证明 O(2*N) 也能覆盖所有的点
【 在 stub 的大作中提到: 】
: 25普通机器可能算不出来
--
FROM 203.184.25.* - 我的将近10年前的笔记本算2到25的所有结果用了不到70s的时间。
【 在 stub 的大作中提到: 】
: 25普通机器可能算不出来
--
FROM 103.90.178.* - 这不就是DFS+visited数组
【 在 stub 的大作中提到: 】
: dfs很简单, 但是有 1s限制, dfs会超时
--
FROM 1.203.166.* - 【 在 orbpig 的大作中提到: 】
: 这不就是DFS+visited数组
visited的key是什么呢，点不能复用。你在该点之前记录的数据，由于这一次跟上一次路过的痕迹已经不同。所以记录的是否有用么
--
FROM 39.144.44.* - 什么面试会出这么难的题呢？
膨胀速度接近2.57，按规则逐条路径模拟，时间和空间增长很快
通项公式或者递推公式貌似也不太容易看出来
--
FROM 221.222.172.* - 【 在 z16166 的大作中提到: 】
: 什么面试会出这么难的题呢？
: 膨胀速度接近2.57，按规则逐条路径模拟，时间和空间增长很快
: 通项公式或者递推公式貌似也不太容易看出来
量化投资
--
FROM 183.195.11.* - 你啥代码这么快，我手机算到N:15 Path:311259下一个就爆栈了
【 在 ArchLinux 的大作中提到: 】
: 我的将近10年前的笔记本算2到25的所有结果用了不到70s的时间。
:
--
FROM 115.193.175.* - 写了一点想法，居然卡审核了。我换成截图发在下面~~
【 在 stub 的大作中提到: 】
: dfs很简单, 但是有 1s限制, dfs会超时
--
FROM 101.88.39.* - 我只算了数量，没记录是什么路径。1s可以算完2到20的结果。
https://paste.debian.net/1240403
【 在 webhost 的大作中提到: 】
: 你啥代码这么快，我手机算到N:15 Path:311259下一个就爆栈了
--
修改:ArchLinux FROM 103.90.178.*
FROM 103.90.178.* - 没太深入考虑，第一反应是 考虑25*25的情况，先不考虑被排除掉的路径，每次出发都有4个方向可选，总共25步，整个空间也就4^25 aka 2^50大小，因此设计一种规则去映射从第0步到第25步所有的中间路径到一个uint64上去，用这个映射值做dp的中间结果
【 在 stub 的大作中提到: 】
: 节点不能复用，所以每次遇到该点时路过的痕迹已经不同，所以只是这样记录应该不行
--
FROM 61.149.18.*