松鼠模拟
难度:
标签:
题目描述
代码结果
运行时间: 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`而不是其他可能的计算方式?
▷🦆
在更新`maxmize`的过程中,`TtoNuts - StoNuts`的计算意味着什么?为什么选择这种方式表示松鼠的额外行走距离?
▷🦆
能否详细解释为什么首次让松鼠直接去到离树最远的那个坚果,而不是最近的或其他坚果,能够最小化总移动距离?
▷