How do I calculate the distance in Escape The Ghosts?

Use the Manhattan distance formula: $|x_1 - x_2| + |y_1 - y_2|$ to determine how long it takes for the player and ghosts to reach the target.

What happens if I reach the target at the same time as a ghost?

If you reach the target at the same time as any ghost, you do not escape, and the output should be false.

What is the time complexity of solving Escape The Ghosts?

The time complexity is O(n) where n is the number of ghosts because we calculate the distance for each ghost to the target.

What is the significance of early exit in Escape The Ghosts?

Early exit improves efficiency by stopping the computation as soon as a ghost reaches the target faster than or at the same time as the player.

How does Escape The Ghosts relate to array-based algorithms?

Escape The Ghosts involves manipulating arrays for ghost positions and using mathematical comparisons, combining array handling with distance calculations.

#789

Medium

auto_awesome数组·数学

LeetCode 题解工作台

逃脱阻碍者

你在进行一个简化版的吃豆人游戏。你从 [0, 0] 点开始出发，你的目的地是 target = [x target , y target ] 。地图上有一些阻碍者，以数组 ghosts 给出，第 i 个阻碍者从 ghosts[i] = [x i , y i ] 出发。所有输入均为整数坐标。每一…

数组数学

题目描述

你在进行一个简化版的吃豆人游戏。你从 [0, 0] 点开始出发，你的目的地是 target = [x_target, y_target] 。地图上有一些阻碍者，以数组 ghosts 给出，第 i 个阻碍者从 ghosts[i] = [x_i, y_i] 出发。所有输入均为 整数坐标 。

每一回合，你和阻碍者们可以同时向东，西，南，北四个方向移动，每次可以移动到距离原位置 1 个单位 的新位置。当然，也可以选择不动。所有动作同时发生。

如果你可以在任何阻碍者抓住你之前到达目的地（阻碍者可以采取任意行动方式），则被视为逃脱成功。如果你和阻碍者同时到达了一个位置（包括目的地） 都不算 是逃脱成功。

如果不管阻碍者怎么移动都可以成功逃脱时，输出 true ；否则，输出 false 。

示例 1：

输入：ghosts = [[1,0],[0,3]], target = [0,1]
输出：true
解释：你可以直接一步到达目的地 (0,1) ，在 (1, 0) 或者 (0, 3) 位置的阻碍者都不可能抓住你。

示例 2：

输入：ghosts = [[1,0]], target = [2,0]
输出：false
解释：你需要走到位于 (2, 0) 的目的地，但是在 (1, 0) 的阻碍者位于你和目的地之间。

示例 3：

输入：ghosts = [[2,0]], target = [1,0]
输出：false
解释：阻碍者可以和你同时达到目的地。

提示：

1 <= ghosts.length <= 100
ghosts[i].length == 2
-10⁴ <= x_i, y_i <= 10⁴
同一位置可能有 多个阻碍者 。
target.length == 2
-10⁴ <= x_target, y_target <= 10⁴

lightbulb

解题思路

方法一：曼哈顿距离

对于任意一个阻碍者，如果它到目的地的曼哈顿距离小于等于你到目的地的曼哈顿距离，那么它就可以在你到达目的地之前抓住你。因此，我们只需要判断所有阻碍者到目的地的曼哈顿距离是否都大于你到目的地的曼哈顿距离即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。其中 $n$ 为阻碍者的数量。

1

2

3

4

5

class Solution:
    def escapeGhosts(self, ghosts: List[List[int]], target: List[int]) -> bool:
        tx, ty = target
        return all(abs(tx - x) + abs(ty - y) > abs(tx) + abs(ty) for x, y in ghosts)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for efficient handling of the distance calculation.
question_mark
Check the approach to early exits and minimal computation.
question_mark
Assess how the solution scales when more ghosts are added.

warning

常见陷阱

外企场景

error
Misunderstanding the simultaneous movement of ghosts and the player.
error
Incorrectly comparing distances by neglecting the Manhattan distance formula.
error
Failing to optimize for early exits, potentially leading to slower solutions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Incorporate dynamic grid changes where some obstacles appear along the path.
arrow_right_alt
Introduce ghosts with different speeds and behavior patterns.
arrow_right_alt
Adjust the problem to allow ghosts to react differently, such as following you.

help

常见问题

外企场景

继续练习

#782 变为棋盘 #781 森林中的兔子 #775 全局倒置与局部倒置