leetcode
leetcode 501 ~ 550
松鼠模拟

松鼠模拟

难度:

标签:

题目描述

代码结果

运行时间: 44 ms, 内存: 16.8 MB


// LeetCode 573: Squirrel Simulation
// 思路:
// 1. 使用Java Stream API来计算坚果和树的距离总和。
// 2. 使用Stream来找到松鼠到所有坚果的最小距离。
 
import java.util.stream.IntStream;
 
public class SquirrelSimulation {
    public int minDistance(int height, int width, int[] tree, int[] squirrel, int[][] nuts) {
        int totalDistance = IntStream.range(0, nuts.length)
                .map(i -> 2 * (Math.abs(nuts[i][0] - tree[0]) + Math.abs(nuts[i][1] - tree[1])))
                .sum();
 
        int minDistanceToNut = IntStream.range(0, nuts.length)
                .map(i -> Math.abs(nuts[i][0] - squirrel[0]) + Math.abs(nuts[i][1] - squirrel[1]) - (Math.abs(nuts[i][0] - tree[0]) + Math.abs(nuts[i][1] - tree[1])))
                .min()
                .orElse(0);
 
        return totalDistance + minDistanceToNut;
    }
}

解释

方法:

该题解的思路是先计算树到所有坚果的总距离 sum_TtoNuts。然后遍历每个坚果,计算松鼠到该坚果并返回树的距离 StoNuts,并更新 maxmize 为 TtoNuts - StoNuts 的最大值。最后返回两倍的 sum_TtoNuts 减去 maxmize。这相当于先让松鼠到离树最远的那个坚果,然后回到树,接着树去剩下的坚果。这样可以最小化松鼠的移动距离。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在计算最小化移动距离时,考虑的是`2*sum_TtoNuts - maxmize`而不是其他可能的计算方式?
如果不考虑松鼠的初始位置,最短的路径是松鼠从树出发,收集所有坚果,并返回树,这个距离是`2*sum_TtoNuts`。然而,松鼠最初不在树上,而是在一个特定的位置。因此,我们要找一个坚果,使得从松鼠的起始位置到这个坚果,再到树的总距离最小化,这种情况下,我们只需调整第一次行走的坚果选择。具体来说,我们计算每个坚果到树的距离与松鼠到这个坚果的距离之差的最大值(maxmize),这个最大值代表了松鼠从其初始位置到第一个坚果,再到树所节省的最大额外距离。因此,`2*sum_TtoNuts - maxmize` 表示考虑松鼠初始位置后的最短总距离。
🦆
在更新`maxmize`的过程中,`TtoNuts - StoNuts`的计算意味着什么?为什么选择这种方式表示松鼠的额外行走距离?
`TtoNuts - StoNuts` 表示从树到某个坚果的距离与从松鼠当前位置到这个坚果的距离之差。这个差值越大,意味着松鼠从当前位置到这个坚果,然后再到树,相比于直接从树出发来回走这个坚果节省的距离就越多。因此,我们寻找这个差值的最大值(maxmize),这样可以使得松鼠的第一次行走尽可能省距离,从而整体上减少松鼠的移动距离。
🦆
能否详细解释为什么首次让松鼠直接去到离树最远的那个坚果,而不是最近的或其他坚果,能够最小化总移动距离?
首先,松鼠的总移动距离包括它从其起始位置到第一个坚果的距离,然后是从这个坚果回到树,后续再从树到其他坚果的往返距离。如果首次选择离树最远的那个坚果,这通常意味着这个坚果到树的距离(TtoNuts)很大。如果TtoNuts远大于StoNuts,松鼠到这个坚果的距离,那么`TtoNuts - StoNuts`的值会很大,这表明选择这个坚果作为第一个目标,可以最大化节省的距离。因此,选择离树最远的那个坚果做为第一个访问的目标,可以在松鼠的初始旅程中节省最多的距离,从而帮助减少总的移动距离。

相关问题