楼主: 匿名
跳转到指定楼层
上一主题 下一主题
收起左侧

骨骼onsite

地里匿名用户
🔗
匿名用户-L8B7M  2019-12-22 20:51:46
wtcupup 发表于 2019-12-22 18:06
第三轮不用set怎么做?

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

使用道具 举报

地里匿名用户
🔗
匿名用户-L8B7M  2019-12-22 20:53:03
本帖最后由 匿名 于 2019-12-22 20:57 编辑
windpuppy 发表于 2019-12-22 16:51
我12/10面的,hr说的和你hr说的一模一样。。祝/求好运。

HR名字首字母是B吗?
回复

使用道具 举报

🔗
xuqicx23 2019-12-22 21:50:06 | 只看该作者
全局:

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

使用道具 举报

🔗
duduhaha 2019-12-23 05:00:48 | 只看该作者
全局:
xuqicx23 发表于 2019-12-22 21:50
感觉也可以dp来做吧。很像dp题。dp[j][n] 代表走了n步到达i j的次数。transition function 等于周围四个 ...

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

使用道具 举报

🔗
xuqicx23 2019-12-23 08:44:41 | 只看该作者
全局:
本帖最后由 xuqicx23 于 2019-12-23 08:49 编辑
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:46:43 | 只看该作者
全局:
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
回复

使用道具 举报

🔗
aviva 2019-12-23 09:18:10 | 只看该作者
全局:
第一道题优化time是指的记忆化吗?
random那道题,不用set或者map,时间要求O(1),具体要怎么做呢?
回复

使用道具 举报

🔗
aviva 2019-12-23 09:18:16 | 只看该作者
全局:
第一道题优化time是指的记忆化吗?
random那道题,不用set或者map,时间要求O(1),具体要怎么做呢?
回复

使用道具 举报

🔗
drool 2019-12-24 12:52:27 | 只看该作者
全局:
xuqicx23 发表于 2019-12-22 21:50
感觉也可以dp来做吧。很像dp题。dp[j][n] 代表走了n步到达i j的次数。transition function 等于周围四个 ...

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

使用道具 举报

🔗
spirit_room 2019-12-27 07:38:00 | 只看该作者
全局:
第一题怎么优化时间?

第三题的题目没看懂,能否重新表述一下?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表