leetcode
leetcode 701 ~ 750
逃脱阻碍者

逃脱阻碍者

难度:

标签:

题目描述

代码结果

运行时间: 24 ms, 内存: 16.0 MB


/*
 * 题目思路:
 * 要确定是否可以逃脱成功,需要比较你和所有阻碍者到达目标的最短曼哈顿距离。
 * 计算你到目标的曼哈顿距离,然后比较每个阻碍者到目标的曼哈顿距离。
 * 如果所有阻碍者的距离都大于你的距离,则返回 true;否则返回 false。
 */

import java.util.Arrays;

public class EscapeGhostsStream {
    public boolean escapeGhosts(int[][] ghosts, int[] target) {
        // 计算你到目标的曼哈顿距离
        int playerDistance = Math.abs(target[0] - 0) + Math.abs(target[1] - 0);
        // 使用 Java Stream API 计算并判断
        return Arrays.stream(ghosts)
                     .mapToInt(ghost -> Math.abs(target[0] - ghost[0]) + Math.abs(target[1] - ghost[1]))
                     .allMatch(ghostDistance -> ghostDistance > playerDistance);
    }
}

解释

方法:

这个题解的思路是:如果阻碍者可以中途拦截玩家,即阻碍者比玩家先到达某个点,然后等玩家到达后一起走向终点,虽然不会改变结局,但阻碍者到达终点的时间会比玩家少。所以与其计算阻碍者是否可以中途拦截,不如直接计算所有阻碍者到达终点的最短时间,看是否比玩家快。具体做法是先计算玩家到达终点的曼哈顿距离,然后计算每个阻碍者到终点的曼哈顿距离,取其中的最小值。如果玩家的距离小于阻碍者的最小距离,说明玩家可以成功逃脱。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
题中提到如果玩家和阻碍者同时到达一个位置都不算是逃脱成功,那么在算法中如何确保处理了这种情况?
在算法实现中,通过确保玩家到达终点的曼哈顿距离严格小于任何阻碍者到终点的曼哈顿距离来处理这种情况。如果玩家的距离小于阻碍者的最小距离,玩家将在任何阻碍者到达之前成功到达终点。如果玩家的距离等于阻碍者的距离,即使他们同时到达,也不算玩家成功逃脱。因此,算法只在玩家的距离严格小于阻碍者的最小距离时返回真(true),这自然排除了同时到达的情况。
🦆
算法中使用曼哈顿距离来判断距离,这种方式在所有情况下都有效吗?特别是考虑到玩家和阻碍者可能采取不同的路径策略。
在此特定问题中,使用曼哈顿距离是有效的,因为题目假设允许玩家和阻碍者每次移动只能沿x轴或y轴移动一步。这正是曼哈顿距离计算方式,即水平和垂直距离之和。这种计算假设没有障碍阻挡直线路径。如果游戏地图引入了如墙壁或其他障碍物,阻挡直线路径,那么曼哈顿距离就不再适用,需要考虑实际可行路径或使用其他路径算法(如A*或Dijkstra算法)。
🦆
在计算阻碍者到目的地的曼哈顿距离时,为什么选择了取所有阻碍者中的最小距离而不是其他统计数据(如平均距离或最大距离)?
选择取所有阻碍者中的最小距离是因为在决定是否能成功逃脱时,最关键的是最快能达到终点的阻碍者。如果任何一个阻碍者可以在玩家之前到达终点,玩家的逃脱就可能会失败。因此,算法中只考虑最快的那个阻碍者对玩家的威胁。平均距离或最大距离虽然提供了其他信息,但对于决定玩家能否逃脱没有直接影响。
🦆
如果有多个阻碍者的曼哈顿距离相同,算法是否有处理或者考虑这种情况的策略?
算法中已经隐含处理了有多个阻碍者曼哈顿距离相同的情况。由于算法是取所有阻碍者到终点的最小曼哈顿距离,所以即使有多个阻碍者的距离相同,这不会影响算法的结果。算法只关心这个最小值,无论是由一个阻碍者还是多个阻碍者提供。因此,无需特别策略来处理多个相同距离的情况。

相关问题