题目分析

LeetCode 2543 判断一个点是否可以到达
规则：起点  (1, 1) ，可执行三种操作：

1.  (x, y) → (x + y, y) 
2.  (x, y) → (x, x + y) 
3. 若  x、y  均为偶数： (x, y) → (x/2, y/2) 
给定  (tx, ty) ，判断能否从  (1,1)  到达。

核心思路（逆向推导）
正向枚举范围爆炸，从终点倒推回起点：

1. 若  tx > ty ：只能由  (tx-ty, ty)  而来（或先除2）
2. 若  ty > tx ：只能由  (tx, ty-tx)  而来（或先除2）
3. 两数都为偶数时，优先除以2缩小范围
4. 终止条件：其中一个数变为 1，再校验另一个数

Java 实现（递归+剪枝 / 迭代版）

迭代版（推荐，无栈溢出，效率高）

java

class Solution {
public boolean isReachable(int tx, int ty) {
while (tx > 1 && ty > 1) {
// 都为偶数，直接减半
if (tx % 2 == 0 && ty % 2 == 0) {
tx /= 2;
ty /= 2;
}
// tx 更大
else if (tx > ty) {
// 快速取模，避免多次减法超时
tx %= ty;
}
// ty 更大
else {
ty %= tx;
}
}
// 最终有一个为1，另一个必须是正整数
return tx == 1 || ty == 1;
}
}

递归版（简洁，数据量大可能栈溢出）

java

class Solution {
public boolean isReachable(int tx, int ty) {
if (tx == 1 && ty == 1) return true;
if (tx < 1 || ty < 1) return false;

    if (tx % 2 == 0 && ty % 2 == 0) {
        return isReachable(tx / 2, ty / 2);
    }
    if (tx > ty) {
        return isReachable(tx - ty, ty);
    } else {
        return isReachable(tx, ty - tx);
    }
}

}

关键点说明

1. 取模优化：不用循环减法， a % b  等价于连续减  b ，大幅提速，适配大数用例。
2. 偶数优先除2：对应题目第三种操作，是缩小坐标的核心。
3. 终止条件：只要其中一个坐标降到  1 ，剩余坐标一定可通过累加得到，直接返回  true 。

复杂度：时间 O(\log(\max(tx,ty)))，空间 O(1)（迭代版）。