题目分析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) 而来或先除22. 若 ty tx 只能由 (tx, ty-tx) 而来或先除23. 两数都为偶数时优先除以2缩小范围4. 终止条件其中一个数变为 1再校验另一个数Java 实现递归剪枝 / 迭代版迭代版推荐无栈溢出效率高javaclass 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;}}递归版简洁数据量大可能栈溢出javaclass 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)迭代版。
