豆包 LeetCode 2543. 判断一个点是否可以到达 Java实现

题目分析

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)（迭代版）。