Hard

题目描述

有一个无限大的网格。你当前在点 (1, 1)，需要使用有限步数到达点 (targetX, targetY)。

在一步中，你可以从点 (x, y) 移动到以下任一点：

  • (x, y - x)
  • (x - y, y)
  • (2 * x, y)
  • (x, 2 * y)

给定两个整数 targetX 和 targetY 分别表示最终位置的 X 坐标和 Y 坐标，如果可以从 (1, 1) 使用某些步骤到达该点，则返回 true，否则返回 false。

示例 1：

输入：targetX = 6, targetY = 9
输出：false
解释：不可能使用任何移动序列从 (1,1) 到达 (6,9)，因此返回 false。

示例 2：

输入：targetX = 4, targetY = 7
输出：true
解释：你可以按照路径 (1,1) -> (1,2) -> (1,4) -> (1,8) -> (1,7) -> (2,7) -> (4,7)。

约束条件：

  • 1 <= targetX, targetY <= 10^9

解题思路

这道题需要从逆向思考的角度来解决。我们从 (targetX, targetY) 开始，尝试回到 (1, 1)。

根据题目给出的四种移动方式，逆向操作为：

  • (x, y) → (x, y + x) 或 (x + y, y)
  • (x, y) → (x/2, y) 当 x 为偶数时
  • (x, y) → (x, y/2) 当 y 为偶数时

关键观察：前两种操作不会改变 gcd(x, y)，而后两种操作可能会改变 gcd。我们需要分析什么时候使用除法操作是最优的。

核心思路：

  1. 当 x 和 y 都大于 1 且其中一个是偶数时，优先使用除法操作
  2. 当两个数都是奇数时，使用减法操作（类似辗转相除法）
  3. 最终目标是到达 (1, 1)

算法步骤：

  1. 不断对较大的偶数除以 2
  2. 当两数都是奇数时，用大数减小数
  3. 重复直到其中一个数变为 1
  4. 检查剩余的数是否为 2 的幂次

这个问题本质上是判断能否通过 gcd 操作和 2 的幂次操作从目标点回到 (1, 1)。

代码实现

class Solution {
public:
    bool isReachable(int targetX, int targetY) {
        int gcd_val = gcd(targetX, targetY);
        
        // 检查 gcd 是否只包含因子 2
        while (gcd_val % 2 == 0) {
            gcd_val /= 2;
        }
        
        return gcd_val == 1;
    }
    
private:
    int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
};

class Solution:
    def isReachable(self, targetX: int, targetY: int) -> bool:
        import math
        
        gcd_val = math.gcd(targetX, targetY)
        
        # 检查 gcd 是否只包含因子 2
        while gcd_val % 2 == 0:
            gcd_val //= 2
        
        return gcd_val == 1

public class Solution {
    public bool IsReachable(int targetX, int targetY) {
        int gcdVal = GCD(targetX, targetY);
        
        // 检查 gcd 是否只包含因子 2
        while (gcdVal % 2 == 0) {
            gcdVal /= 2;
        }
        
        return gcdVal == 1;
    }
    
    private int GCD(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

var isReachable = function(targetX, targetY) {
    while (targetX % 2 === 0) {
        targetX /= 2;
    }
    while (targetY % 2 === 0) {
        targetY /= 2;
    }
    
    while (targetX !== targetY) {
        if (targetX > targetY) {
            targetX -= targetY;
        } else {
            targetY -= targetX;
        }
    }
    
    return targetX === 1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(log(min(targetX, targetY)))
空间复杂度O(1)

时间复杂度主要来自计算 GCD 的过程，以及对 GCD 进行因子 2 的除法操作。空间复杂度为常数级别。

相关题目