LeetCode 题解工作台
到达终点
给定四个整数 sx , sy ， tx 和 ty ，如果通过一系列的 转换 可以从起点 (sx, sy) 到达终点 (tx, ty) ，则返回 true ，否则返回 false 。 从点 (x, y) 可以 转换 到 (x, x+y) 或者 (x+y, y) 。 示例 1: 输入: sx = 1, …
1
题型
4
代码语言
3
相关题
当前训练重点
困难 · 数学·driven
答案摘要
从 `(tx, ty)` 开始逆向计算，判断是否可以到达状态 `(sx, sy)`。由于逆向计算是将 tx, ty 中的较大值减少，因此当 `tx > ty` 时可以直接将 tx 的值更新为 `tx % ty`，当 `tx < ty` 时可以将 ty 的值更新为 `ty % tx`。逆向计算需要满足 `tx > sx && ty > sy && tx != ty`。 当条件不成立时，根据此时 tx…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数学·driven 题型思路
题目描述
给定四个整数 sx , sy ，tx 和 ty，如果通过一系列的转换可以从起点 (sx, sy) 到达终点 (tx, ty)，则返回 true，否则返回 false。
从点 (x, y) 可以转换到 (x, x+y) 或者 (x+y, y)。
示例 1:
输入: sx = 1, sy = 1, tx = 3, ty = 5 输出: true 解释: 可以通过以下一系列转换从起点转换到终点： (1, 1) -> (1, 2) (1, 2) -> (3, 2) (3, 2) -> (3, 5)
示例 2:
输入: sx = 1, sy = 1, tx = 2, ty = 2 输出: false
示例 3:
输入: sx = 1, sy = 1, tx = 1, ty = 1 输出: true
提示:
1 <= sx, sy, tx, ty <= 109
解题思路
方法一：逆向计算
从 (tx, ty) 开始逆向计算，判断是否可以到达状态 (sx, sy)。由于逆向计算是将 tx, ty 中的较大值减少，因此当 tx > ty 时可以直接将 tx 的值更新为 tx % ty，当 tx < ty 时可以将 ty 的值更新为 ty % tx。逆向计算需要满足 tx > sx && ty > sy && tx != ty。
当条件不成立时，根据此时 tx 和 ty 判断是否可以从起点转换到终点。
- 如果
tx == sx && ty == sy，说明此时已经到达起点状态，返回 true； - 如果
tx == sx，若ty > sy && (ty - sy) % tx == 0，返回 true，否则返回 false； - 如果
ty == sy，若tx > sx && (tx - sx) % ty == 0，返回 true，否则返回 false； - 如果
tx ≠ sx && ty ≠ sy，则不可以从起点转换到终点。
class Solution:
def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:
while tx > sx and ty > sy and tx != ty:
if tx > ty:
tx %= ty
else:
ty %= tx
if tx == sx and ty == sy:
return True
if tx == sx:
return ty > sy and (ty - sy) % tx == 0
if ty == sy:
return tx > sx and (tx - sx) % ty == 0
return False
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(log(max(tx,ty))) due to iterative reductions using modulo. Space complexity is O(1) for iterative approach or O(log(max(tx,ty))) for recursion stack. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate must identify the additive nature and consider reverse operations.
- question_mark
Look for recognition of modulo trick to avoid brute-force path enumeration.
- question_mark
Check if candidate correctly handles large numbers without simulating every move.
常见陷阱
外企场景- error
Attempting exhaustive forward recursion causes TLE for large tx or ty.
- error
Failing to check base cases when one coordinate equals the start leads to incorrect false returns.
- error
Misapplying modulo when the smaller coordinate is zero or already aligned with start coordinate.
进阶变体
外企场景- arrow_right_alt
Changing allowed operations to multiply instead of add requires a completely different strategy.
- arrow_right_alt
Restricting moves to one axis per turn tests understanding of additive paths.
- arrow_right_alt
Target coordinates with negative integers add edge cases for modulo reduction logic.