class Solution {
public:
bool isReachable(int targetX, int targetY) {
}
};
2543. 判断一个点是否可以到达
给你一个无穷大的网格图。一开始你在 (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 <= 109原站题解
cpp 解法, 执行用时: 0 ms, 内存消耗: 5.8 MB, 提交时间: 2023-01-23 10:37:02
class Solution {
public:
bool isReachable(int targetX, int targetY) {
int g = gcd(targetX, targetY);
return (g & (g - 1)) == 0;
}
};
java 解法, 执行用时: 0 ms, 内存消耗: 38.1 MB, 提交时间: 2023-01-23 10:36:48
class Solution {
public boolean isReachable(int targetX, int targetY) {
int g = gcd(targetX, targetY);
return (g & (g - 1)) == 0;
}
private int gcd(int a, int b) {
while (a != 0) {
int tmp = a;
a = b % a;
b = tmp;
}
return b;
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-01-23 10:36:18
func isReachable(targetX, targetY int) bool {
g := gcd(targetX, targetY)
return g&(g-1) == 0
}
func gcd(a, b int) int {
for a != 0 {
a, b = b%a, a
}
return b
}
python3 解法, 执行用时: 36 ms, 内存消耗: 14.9 MB, 提交时间: 2023-01-23 10:36:04
class Solution:
def isReachable(self, targetX: int, targetY: int) -> bool:
g = gcd(targetX, targetY)
return (g & (g - 1)) == 0