难度: Medium
Submission
运行时间: 44 ms
内存: 16.8 MB
class Solution:
def minDistance(self, height: int, width: int, tree: List[int], squirrel: List[int], nuts: List[List[int]]) -> int:
n=len(nuts)
sum_TtoNuts=0
maxmize=-math.inf
for i in range(n):
TtoNuts = abs(tree[0]-nuts[i][0])+abs(tree[1]-nuts[i][1])
sum_TtoNuts += TtoNuts
StoNuts = abs(squirrel[0]-nuts[i][0])+abs(squirrel[1]-nuts[i][1])#松鼠到坚果i并返回树的距离
maxmize = max(maxmize, TtoNuts - StoNuts)
return 2*sum_TtoNuts - maxmize
Explain
该题解的思路是先计算树到所有坚果的总距离 sum_TtoNuts。然后遍历每个坚果，计算松鼠到该坚果并返回树的距离 StoNuts，并更新 maxmize 为 TtoNuts - StoNuts 的最大值。最后返回两倍的 sum_TtoNuts 减去 maxmize。这相当于先让松鼠到离树最远的那个坚果，然后回到树，接着树去剩下的坚果。这样可以最小化松鼠的移动距离。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def minDistance(self, height: int, width: int, tree: List[int], squirrel: List[int], nuts: List[List[int]]) -> int:
n = len(nuts)
sum_TtoNuts = 0
maxmize = -math.inf
for i in range(n):
TtoNuts = abs(tree[0]-nuts[i][0]) + abs(tree[1]-nuts[i][1]) # 计算树到坚果i的距离
sum_TtoNuts += TtoNuts
StoNuts = abs(squirrel[0]-nuts[i][0]) + abs(squirrel[1]-nuts[i][1]) # 计算松鼠到坚果i并返回树的距离
maxmize = max(maxmize, TtoNuts - StoNuts) # 更新最大值
return 2*sum_TtoNuts - maxmize # 总距离为两倍的树到坚果距离减去最大值
Explore
如果不考虑松鼠的初始位置，最短的路径是松鼠从树出发，收集所有坚果，并返回树，这个距离是`2*sum_TtoNuts`。然而，松鼠最初不在树上，而是在一个特定的位置。因此，我们要找一个坚果，使得从松鼠的起始位置到这个坚果，再到树的总距离最小化，这种情况下，我们只需调整第一次行走的坚果选择。具体来说，我们计算每个坚果到树的距离与松鼠到这个坚果的距离之差的最大值（maxmize），这个最大值代表了松鼠从其初始位置到第一个坚果，再到树所节省的最大额外距离。因此，`2*sum_TtoNuts - maxmize` 表示考虑松鼠初始位置后的最短总距离。
`TtoNuts - StoNuts` 表示从树到某个坚果的距离与从松鼠当前位置到这个坚果的距离之差。这个差值越大，意味着松鼠从当前位置到这个坚果，然后再到树，相比于直接从树出发来回走这个坚果节省的距离就越多。因此，我们寻找这个差值的最大值（maxmize），这样可以使得松鼠的第一次行走尽可能省距离，从而整体上减少松鼠的移动距离。
首先，松鼠的总移动距离包括它从其起始位置到第一个坚果的距离，然后是从这个坚果回到树，后续再从树到其他坚果的往返距离。如果首次选择离树最远的那个坚果，这通常意味着这个坚果到树的距离（TtoNuts）很大。如果TtoNuts远大于StoNuts，松鼠到这个坚果的距离，那么`TtoNuts - StoNuts`的值会很大，这表明选择这个坚果作为第一个目标，可以最大化节省的距离。因此，选择离树最远的那个坚果做为第一个访问的目标，可以在松鼠的初始旅程中节省最多的距离，从而帮助减少总的移动距离。