骨骼onsite

wtcupup 发表于 2019-12-22 18:06
第三轮不用set怎么做？

六角形用相对坐标就好不用set是因为想让用蓄水池抽样

windpuppy 发表于 2019-12-22 16:51
我12/10面的，hr说的和你hr说的一模一样。。祝/求好运。

HR名字首字母是B吗？

匿名者 发表于 2019-12-22 11:07
dfs+memo

感觉也可以dp来做吧。很像dp题。dp[i][j][n] 代表走了n步到达i j的次数。transition function 等于周围四个点n-1步的和。

xuqicx23 发表于 2019-12-22 21:50
感觉也可以dp来做吧。很像dp题。dp[j][n] 代表走了n步到达i j的次数。transition function 等于周围四个 ...

你能写个dp的代码吗？ 没看出来动态规划该怎么做

duduhaha 发表于 2019-12-23 05:00
你能写个dp的代码吗？ 没看出来动态规划该怎么做

3d DP. 我没有写，读了下题大概脑海中sudo code是
DP[i][j][n] represents # of ways to get to i, j with N steps taken.
初始条件为dp[i][i][j][0] = 1. 做三层for loop
dp[i][i][j][n] = sum of (dp[i-1][j][n-1], dp[i][j-1][n-1], dp[i+1][j][n-1] and dp[i][j+1][n-1])。最后return一下dp[i][j][n]的值就可以了。
由上面的转换方程也能看出来，可以优化成2d dp。[/i][/i][/i][/i][/i][/i][/i][/i]

xuqicx23 发表于 2019-12-23 08:44
3d DP. 我没有写，读了下题大概脑海中sudo code是
DP[j][n] represents # of ways to get to i, j with  ...

不知道为什么我打的3d dp  i, j,n 保存之后就变成了[j][n]了。希望避免误会，是个3d的array

第一道题优化time是指的记忆化吗？
random那道题，不用set或者map，时间要求O（1），具体要怎么做呢？

第一道题优化time是指的记忆化吗？
random那道题，不用set或者map，时间要求O（1），具体要怎么做呢？

xuqicx23 发表于 2019-12-22 21:50
感觉也可以dp来做吧。很像dp题。dp[j][n] 代表走了n步到达i j的次数。transition function 等于周围四个 ...

我想这个题应该有个数学解吧？n是奇数不可能回到原点，偶数的话x,y方向成对出现的组合数即是解

第一题怎么优化时间？

第三题的题目没看懂，能否重新表述一下？