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

这道题的核心思路是从终点反向推导回起点并利用最大公约数GCD 的性质来判定。核心思路从 (1, 1) 正向推导到 (targetX, targetY) 路径太多不好下手。我们反过来想从 (targetX, targetY) 能否通过逆操作回到 (1, 1)原操作正向1. (x, y - x)2. (x - y, y)3. (2x, y)4. (x, 2y)对应的逆操作反向1. (x, y x)2. (x y, y)3. (x/2, y) — 要求 x 为偶数4. (x, y/2) — 要求 y 为偶数数学结论观察逆操作可以发现- 操作1和2加法不改变 x 和 y 的最大公约数GCD。- 操作3和4除以2可能让 GCD 除以2。因此从 (targetX, targetY) 出发无论怎么操作最终得到的 GCD 一定是原始 GCD 不断除以2的结果。要能到达 (1, 1)最终 GCD 必须为 1。结论(targetX, targetY) 能到达 (1, 1) 的充要条件是gcd(targetX, targetY) 是 2 的幂次方即形如 1, 2, 4, 8, 16...。判断方法一个数 g 是 2 的幂次方 ⇔ g (g - 1) 0且 g 0。Java 实现class Solution {public boolean isReachable(int targetX, int targetY) {// 1. 计算最大公约数int g gcd(targetX, targetY);// 2. 判断 g 是否为 2 的幂次方return (g (g - 1)) 0;}// 辗转相除法求最大公约数private int gcd(int a, int b) {while (b ! 0) {int temp b;b a % b;a temp;}return a;}}代码说明- gcd 方法标准的欧几里得算法辗转相除法时间复杂度 O(log min(a,b))。- g (g - 1) 0这是判断一个正整数是否为 2 的幂次方的经典位运算技巧。例如 8 的二进制是 10008-17 是 0111两者按位与结果为 0。- 时间复杂度O(log min(targetX, targetY))完全能处理 10^9 级别的数据。- 空间复杂度O(1)。示例验证输入 GCD 是否为2的幂 结果(6, 9) 3 否 (3不是2的幂) false(4, 7) 1 是 (1 2⁰) true(8, 12) 4 是 (4 2²) true(10, 15) 5 否 false这个解法简洁高效是这道题的标准最优解。