米乐M6 M6米乐20210129 每日一题 最小体力消耗路径

2022-11-07 14:05:08
浏览次数:
返回列表

  LeetCode上最小体力消耗路径,思路参考了官方题解,记录下自己的理解过程吧

  要从编号0点走到编号39点,求之间消耗的最小体力。根据题意,最小体力的消耗应该是路径上相邻格子之间高度差绝对值的最大值决定的,就是连通路径上最高点和最低点的差值。

  这里看这张图可以知道,假设每个点只能向右和向下连接,比如0点就可以和1/8点连接,连接的时候需要的体力是1/6,那么可以遍历整张图,生成一个每个点到另外点的一个数组。还要注意最后一行以及最后一列只能向右或者只能向下,这种情况应该过滤掉。

  会写出这样一个双重循环,从[0,0]点开始循环,当前点的编号就是id = i*col + j,每个数组中保存的数据是[当前点序号,连接点序号,两者之间体力消耗的绝对值]

  这里需要求得一个最小值,可以理解为一个贪心算法,每次都连接体力消耗最小的,直到两点连接上了,那么此时消耗的体力就是最小体力

  那么在最后通过并查集连接的时候从这个数组的第一个开始连接,直到判断到find(nodes[0]) === find(nodes[row*col - 1])即0点和最后一点的parent属性相等就是表示连接了

米乐M6 M6米乐20210129 每日一题 最小体力消耗路径(图1)

  连接体力消耗为1的数据,可以发现此时star已经进入路径了,但是还没有和end连接

米乐M6 M6米乐20210129 每日一题 最小体力消耗路径(图2)

  这样不断的循环整个数组直到把39连入的时候,那个时候消耗的体力就是最小体力米乐M6 M6米乐米乐M6 M6米乐米乐M6 M6米乐

搜索