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^9

解题思路

这道题目的关键是理解操作的逆向过程。由于正向模拟可能产生指数级的状态空间，我们采用逆向思维：从终点 (tx, ty) 回推到起点 (sx, sy)。

核心思路：

  1. 逆向操作：如果 (tx, ty) 可以从某点到达，那么该点必定是 (tx - ty, ty) 或 (tx, ty - tx) 中的一个
  2. 贪心策略：总是选择减去较小值的操作，这样能最快地缩小数值
  3. 优化处理：当两个值差距很大时，使用取模运算快速跳跃多步

算法步骤：

  • 当 tx > sx 且 ty > sy 时，继续回推
  • 如果 tx > ty，则上一步必定是 (tx - ty, ty)
  • 如果 ty > tx，则上一步必定是 (tx, ty - tx)
  • 当其中一个值等于目标值时，检查另一个值是否能通过连续加法到达

边界情况处理：

  • 当 tx == sx 时，检查 (ty - sy) % sx == 0 且 ty >= sy
  • 当 ty == sy 时，检查 (tx - sx) % sy == 0 且 tx >= sx

代码实现

class Solution {
public:
    bool reachingPoints(int sx, int sy, int tx, int ty) {
        while (tx >= sx && ty >= sy) {
            if (sx == tx && sy == ty) {
                return true;
            }
            
            if (tx > ty) {
                if (ty == sy) {
                    return (tx - sx) % sy == 0;
                }
                tx %= ty;
            } else {
                if (tx == sx) {
                    return (ty - sy) % sx == 0;
                }
                ty %= tx;
            }
        }
        return false;
    }
};

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

public class Solution {
    public bool ReachingPoints(int sx, int sy, int tx, int ty) {
        while (tx >= sx && ty >= sy) {
            if (sx == tx && sy == ty) {
                return true;
            }
            
            if (tx > ty) {
                if (ty == sy) {
                    return (tx - sx) % sy == 0;
                }
                tx %= ty;
            } else {
                if (tx == sx) {
                    return (ty - sy) % sx == 0;
                }
                ty %= tx;
            }
        }
        return false;
    }
}

/**
 * @param {number} sx
 * @param {number} sy
 * @param {number} tx
 * @param {number} ty
 * @return {boolean}
 */
var reachingPoints = function(sx, sy, tx, ty) {
    while (tx >= sx && ty >= sy) {
        if (tx === sx && ty === sy) {
            return true;
        }
        
        if (tx > ty) {
            if (ty === sy) {
                return (tx - sx) % ty === 0;
            }
            tx %= ty;
        } else {
            if (tx === sx) {
                return (ty - sy) % tx === 0;
            }
            ty %= tx;
        }
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度分析
时间复杂度O(log(max(tx, ty)))
空间复杂度O(1)

时间复杂度说明： 每次取模操作都会显著减小较大的数值，类似于欧几里得算法求最大公约数的过程，因此时间复杂度为对数级别。

空间复杂度说明： 只使用了常数额外空间。

相关题目