水木社区手机版
- 主题:一道面试题，没做出来, 求指教
- dfs很简单, 但是有 1s限制, dfs会超时
--
修改:stub FROM 39.144.43.*
FROM 183.195.11.* - 【 在 iRoNcOoL 的大作中提到: 】
: dfs + cache, a top-down DP solution
我觉得应该也是cache，关键是这个cache该怎么做呢
--
FROM 223.104.211.* - 【 在 iRoNcOoL 的大作中提到: 】
: 坐标加步数做key，可能数当 value
:
: #发自zSMTH@MATE 20 pro
节点不能复用，所以每次遇到该点时路过的痕迹已经不同，所以只是这样记录应该不行
--
FROM 223.104.211.* - @z16166
--
FROM 112.64.119.* - 【 在 ArchLinux 的大作中提到: 】
: 如果上机考试的话，那就先用DFS算出所有答案（算出2到25的答案时间不太长），然后打表。
:
25普通机器可能算不出来
--
FROM 112.64.119.* - 【 在 orbpig 的大作中提到: 】
: 这不就是DFS+visited数组
visited的key是什么呢，点不能复用。你在该点之前记录的数据，由于这一次跟上一次路过的痕迹已经不同。所以记录的是否有用么
--
FROM 39.144.44.* - 【 在 z16166 的大作中提到: 】
: 什么面试会出这么难的题呢？
: 膨胀速度接近2.57，按规则逐条路径模拟，时间和空间增长很快
: 通项公式或者递推公式貌似也不太容易看出来
量化投资
--
FROM 183.195.11.* - 【 在 lby20180710 的大作中提到: 】
: 国内前5？最少前10的量化公司，我也做过，也跪了。。。。。
哈哈
--
FROM 183.195.13.* - 【 在 webhost 的大作中提到: 】
: 跟你时间差不多了，手机计算起来性能不比电脑差啊
: [upload=1][/upload]
:
贴下代码？
--
FROM 183.195.13.* - 【 在 z16166 的大作中提到: 】
: 当前正在枚举的path的最大长度是N，所以visited数组只需要尺寸是[N]就行，搞成二维的[N][N]也行。
: 每个点的下一个邻接点最多只有3个，因为不能回到来时的路。
: N = 1, path count: 1 (1.00), time: 0.000 seconds
: ...................
思路基本一样 但是超时
--
FROM 183.195.13.*