0780：到达终点（1897 分）

力扣第 780 题

题目

给定四个整数 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

相似问题：

• 2400：恰好移动 k 步到达某一位置的方法数目（1751 分）
• 2543：判断一个点是否可以到达（2220 分）
• 2849：判断能否在给定时间到达单元格（1515 分）

分析

• 从起点递推情况很多，但注意到从终点反推状态很少
  • 若 tx=ty，没有上一状态
  • 若 tx>ty，上一状态必然是 [tx-ty,ty]
  • 若 tx<ty，上一状态必然是 [tx,ty-tx]
• 若 tx<sx 或 ty<sy，直接 false
• 若 tx=sx，判断 ty 能否减成 sy；ty=sy 同理
• 若 tx>sx 且 ty>sy
  • 若 tx=ty，直接 false
  • 若 tx>ty，tx 要一直减到小于 ty，才有可能让 ty 减小，因此直接更新 tx%=ty
  • 若 ty>tx，同理

解答

1
2
3
4
5
6
7

class Solution:
    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:
        while tx>sx and ty>sy and tx!=ty:
            tx,ty = (tx,ty%tx) if tx<ty else (tx%ty,ty)
        if tx==sx and ty>=sy and (ty-sy)%tx==0:
            return True
        return ty==sy and tx>=sx and (tx-sx)%ty==0

0 ms