一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
Offer多多
Salarytics
交友
Learn
Who's Hiring?
疫情动态
指尖新闻
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 1275|回复: 18
收起左侧

[树/链表/图] 一道和LC-1368很像的Google面试题目

[复制链接] |只看干货 |刷题, 树/链表/图
我的人缘0

升级   17.71%


分享帖子到朋友圈
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (112)
 
 
0% (0)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
在蠡口上看到有人讨论的一个题目, 想搬运过来和大家讨论一下

Q: Given a m-by-n matrix containing positive numbers, you start from top left and travel towards bottom right. You can move in either up, down, left, or right directions. When moving from a higher number to lower or equal number, the cost is 0. When moving from a lower number to a higher number, the cost is the absolute difference. Find and return the minimum cost from top left to bottom right of the matrix.

Follow-up: Given the same m-by-n matrix, however, this time you can only move from a higher number to lower number. You can increase any number so that you can move to the next number. Find and return the minimum amount to increase in order to move from top left to bottom right of the matrix.

第一问Dijkastra应该可以轻松handle,但是看到讨论有说DP可以做,我没太想明白DP怎么处理四个方向都可以走的情况,难道是做一次从左上到右下的DP,然后再做一次右下到左上的DP,一直重复这个过程直到DP的table稳定不变了?
紧接这第二问有点像LC 174. Dungeon Game,但是需要DP才好做,依然是同样的问题,怎么处理四个方向都可以走的情况?

评分

参与人数 2大米 +11 收起 理由
14417335 + 10
resco + 1 给你点个赞!

查看全部评分


上一篇:272. Closest Binary Search Tree Value II 的 优于O(n)解法
下一篇:leetcode执行出错是什么情况
我的人缘0

升级   56.5%

beyondR 2020-7-8 02:22:14 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (166)
 
 
4% (7)    👎
能不能把lc讨论的原链接贴一下?
回复

使用道具 举报

我的人缘0

升级   54.14%

PocketOffer 2020-7-8 02:51:01 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   92% (236)
 
 
7% (18)    👎
第二题,如果是用DP的话,虽然是四个方向都可以走,但是因为规定了只能从大走到小,所以其实也是个不会产生循环的图-》所以也是也能用DP的吧?对于每一个点来说,先不改自己的值,通过往本来就比自己小的邻居得到一个解, 然后再改了自己的值(直接在GRID里改??),通过本来比自己大的邻居得到另一个解,两个解比较一下,取小的。至于怎么利用DP,就拿横纵坐标当做MEM参数????
回复

使用道具 举报

我的人缘0

升级   17.71%

 楼主| 旧未来 2020-7-8 03:04:39 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (112)
 
 
0% (0)    👎
beyondR 发表于 2020-7-8 02:22
能不能把lc讨论的原链接贴一下?

https://leetcode.com/discuss/int ... e-june-2020-pending

这个的round 4
回复

使用道具 举报

我的人缘0

升级   17.71%

 楼主| 旧未来 2020-7-8 03:16:01 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (112)
 
 
0% (0)    👎
PocketOffer 发表于 2020-7-8 02:51
第二题,如果是用DP的话,虽然是四个方向都可以走,但是因为规定了只能从大走到小,所以其实也是个不会产生 ...

没太能够follow你的思路,你的意思是对于任何图中的(i,j)点,到达这点需要的cost是min(四周比它低的点cost + 高度差, 四周比它高的点的cost)?
回复

使用道具 举报

我的人缘0

升级   56.5%

beyondR 2020-7-8 03:26:05 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (166)
 
 
4% (7)    👎
thanks for the link。这道题纯dp应该是做不了的。需要nxm的DP array和graph search相结合。我个人是觉得用diksja做就可以。followup和lc1368完全一样,稍微改一下cost改变的条件就行,我个人会用heap+bfs做啦,复杂度稍微高一些。DP+graph search应该可以达到nm的复杂度。
回复

使用道具 举报

我的人缘0

升级   17.71%

 楼主| 旧未来 2020-7-8 03:52:40 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (112)
 
 
0% (0)    👎
beyondR 发表于 2020-7-8 03:26
thanks for the link。这道题纯dp应该是做不了的。需要nxm的DP array和graph search相结合。我个人是觉得用 ...

其实这题第一问和第二问有什么本质区别吗?没太想明白这个地方
我的理解是第一问从高到低 ,edge weight  = 0, 从低到高,edge weight = diff
第二问,从高到低 ,edge weight  = 0,  从低到高,只需要把低的增到和高的一致就行,weight也是diff
回复

使用道具 举报

我的人缘0

升级   56.5%

beyondR 2020-7-8 04:33:19 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (166)
 
 
4% (7)    👎
旧未来 发表于 2020-7-8 03:52
其实这题第一问和第二问有什么本质区别吗?没太想明白这个地方
我的理解是第一问从高到低 ,edge weight ...

我后来想了想,我一开始说的不对。纯DP也可以,根据cost的定义,可以greedy的证明,我们只会向下走和向右走,不会向上和向左。所以直接dp做就可以
回复

使用道具 举报

我的人缘0

升级   0%

DZgeralt 2020-7-8 04:48:29 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   0% (0)
 
 
0% (0)    👎
got this one last November ... didn't solve it
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

Some icons made by Freepik from flaticon.com

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