新鲜Google intern 电面 大概率挂经

第二题有点像离寇药姚凌饵？不过最大值变成了最小值。

四个方向走，是不是用不了DP啊，因为无法根据之前的状态确定之后的状态。好像DP必须限定往右，往下方向才行（总归只能往一个方向走，右下方向，有时候可以三个方向加对角线，但是不能四个方向）。不知道有没有大牛解释一下。这题目没有限定一定有解吗？如果一定有解BFS吧，如果不一定可能真的要楼上的兄弟的解法二分再BFS了。最短的话，应该是典型BFS吧。。。DFS是不是不太好？

huorili 发表于 2019-12-13 03:10
四个方向走，是不是用不了DP啊，因为无法根据之前的状态确定之后的状态。好像DP必须限定往右，往下方向才行 ...

我也跟面试官说了因为有四个方向，可能再回到之前的点，不知道DP怎么做；BFS应该咋做啊。。我感觉是类似Backtracking的做法，不知道对不对

草草草群 发表于 2019-12-13 02:27
第二题有点像离寇药姚凌饵？不过最大值变成了最小值。

也不是，第二题要找的是题里面定义的effort，不是路径的长短。

Zbeeee 发表于 2019-12-13 04:39
也不是，第二题要找的是题里面定义的effort，不是路径的长短。

有道理 我之前理解错了。
是不是可以把每个cell到相邻的的effort存到第三维里然后对三维的matrix进行dijkstra，每个坐标存的就是从起点到这个坐标的minimum effort.

谢谢楼主分享。新人积分少看不到，评论攒积分

谢谢楼主分享。新人积分少看不到，评论攒积分

第二题题目大意是给一个n*n 非负数的整型矩阵，要求找到从右上到左下所有路径中最小的EFFORT(可能有多条路径符合，所以只要返回EFFORT), EFORT的定义是在这个路径中所有2个相连的cell的差值的绝对值的最大值（这个要理解清楚）。
解法：
类似dijkstra的贪心。就是BFS 从右上开始直到找到右下那个cell，把所有相邻的cell 加到 一个min heap里(最小优先队列)，heap用当前cell和前一个cell差值的绝对值（diff）作为排序条件。这样在BFS处理的是所有路径中当前effort最小的那条，如果到达了右下点就可以停止了。
如果有受益 请加大米

第一题暂时没想到比BFS/DFS更优的解法，第二题记忆化搜索有点问题是需要记录来的路径，这里可能会爆栈。迪杰斯特拉可解，但是还有个骚操作用对差值二分去做。对于输入数取值范围较小的情况时间复杂度近似于n^2。

请问第一题可以用 dikstra解吗  感觉可以把这个二维数组当成一个图