到达终点

难度: Hard

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

Submission

运行时间: 24 ms

内存: 16.1 MB

class Solution:
    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:
        # 关键点1：倒着思考，那么 （tx，ty） 到 （sx，sy） 的序列就是唯一的。比如小叶秋叶游乘车的题目就是这样
        # 关键点2：线性模拟会超时，而取模则直接跳到线性模拟的关键步骤，避免超时

        while sx < tx and sy < ty: # 由于 x 和 y 是非严格递增的，且每次操作至少要增加其中一个。因此其中一个变成 target 后，那么后面只能操作另外一个了，且操作是确定的
            if tx < ty:
                # 大的一定是上一步经过相加得到的、预期线性模拟，倒不如直接取模，否则会超时。因为如果上一步还是 ty 大的话，又要执行一次同样操作。同样操作执行若干次后 ty 第一次变成比 tx 小的时候，不在继续这一操作。而第一次比 tx 小的时候 ty 就等于 ty % tx
                ty %= tx
            else:
                tx %= ty
        # 如果 sx == tx，那么接下来看 sy 都不能变成 ty， 如果 sy <= ty，那么每次 sy 增加 sx 能增加到 ty 就返回 true。否则其他情况都是 false
        # 如果 sy == ty 也是同理
        return sx == tx and sy <= ty and (ty - sy) % sx == 0 or sy == ty and sx <= tx and (tx - sx) % sy == 0

Explain

题解采用的是从终点(tx, ty)向起点(sx, sy)反向推理的方式。考虑到每次变换操作是唯一的，可以逆向单步回溯，从(tx, ty)减少到(sx, sy)。如果在过程中tx>ty，则意味着tx是通过(tx - ty, ty)转换而来；反之，则ty是通过(tx, ty - tx)转换而来。由于直接递减可能导致复杂度过高，因此代码使用取模操作以优化性能，跳过多次直接递减的过程。当其中一个值与起点对应值相等时，只需验证另一个值能否通过若干次指定增加操作变为目标值。

时间复杂度: O(log(min(tx, ty)))

空间复杂度: O(1)

class Solution:
    def reachingPoints(self, sx: int, sy: int, tx: int, ty: int) -> bool:
        while sx < tx and sy < ty: # 当sx, sy其中一个数小于tx, ty时继续
            if tx < ty:
                ty %= tx # ty减去多个tx直到小于tx，等同于取模
            else:
                tx %= ty # 同上，tx减去多个ty直到小于ty
        return sx == tx and sy <= ty and (ty - sy) % sx == 0 or sy == ty and sx <= tx and (tx - sx) % sy == 0 # 最终检查能否由(sx, sy)经过若干次变换达到(tx, ty)

Explore

从终点到起点逆向推理的主要优势在于简化问题的复杂度。在正向推理中，从(sx, sy)到(tx, ty)的每一步都有两种可能性（增加sx或增加sy），这会导致状态空间的指数级增长，使得问题变得难以处理。而逆向推理则明确每一步的选择，因为每个(tx, ty)点只能通过一种方式从一个更大的点转换而来（要么是(tx - ty, ty)，要么是(tx, ty - tx)），从而减少了可能的路径数量，并能更直观地通过减法和模运算来逐步逼近起始点。

取模操作通过减少无效的重复步骤来优化算法性能。在每一步操作中，如果tx > ty，则进行tx %= ty操作，这实际上是将tx减少到小于ty的值，等价于去掉了多个ty，确保了不会跳过任何可能的状态，因为这个过程只是快速实现了多次(tx - ty)操作。同理，ty的处理也是类似的。这种方法确保了我们每一步都是有效地接近目标点(sx, sy)，而不是错过它。

这个终止条件是基于逆向推理逻辑的结果。当tx和ty中的一个与起点的sx或sy相等时，我们需检查另一个坐标是否能够通过多次相同的增加操作回达到另一个起点坐标。例如，如果tx等于sx，并且ty大于sy，那么我们需要检查从sy到ty是否可以通过多次添加sx得到。这可以通过`(ty - sy) % sx == 0`来验证，确保ty可以通过减去若干个sx准确达到sy。同理适用于另一个条件。

如果tx和ty远大于sx和sy，递减方法的效率极低，因为它需要逐步一个一个地减去ty或tx，而这可能需要进行数百万次操作。取模方法可以显著减少所需的操作次数，因为它一次性减去了多个ty或tx，直接跳到一个与另一坐标相近的值。这种方法在处理大数时尤其有效，可以将时间复杂度从线性降低到对数级别，显著提高算法的执行速度。