判断一个点是否可以到达

There exists an infinitely large grid. You are currently at point (1, 1), and you need to reach the point (targetX, targetY) using a finite number of steps.

In one step, you can move from point (x, y) to any one of the following points:

• (x, y - x)
• (x - y, y)
• (2 * x, y)
• (x, 2 * y)

Given two integers targetX and targetY representing the X-coordinate and Y-coordinate of your final position, return true if you can reach the point from (1, 1) using some number of steps, and false otherwise.

 

Example 1:

Input: targetX = 6, targetY = 9
Output: false
Explanation: It is impossible to reach (6,9) from (1,1) using any sequence of moves, so false is returned.

Example 2:

Input: targetX = 4, targetY = 7
Output: true
Explanation: You can follow the path (1,1) -> (1,2) -> (1,4) -> (1,8) -> (1,7) -> (2,7) -> (4,7).

 

Constraints:

• 1 <= targetX, targetY <= 109

/*
 * 题目思路：
 * 与Java解法相同，利用Java Stream来进行操作
 * 虽然Stream在此题目中不是最优的解决方案，但它展示了一种使用lambda表达式和流的方式
 */
import java.util.stream.Stream;
public class Solution {
    public boolean canReach(int targetX, int targetY) {
        return Stream.iterate(new int[]{targetX, targetY}, p -> p[0] > 1 && p[1] > 1,
                p -> p[0] > p[1] ? new int[]{p[0] % p[1], p[1]} : new int[]{p[0], p[1] % p[0]})
                .anyMatch(p -> (p[0] == 1 && p[1] > 0) || (p[1] == 1 && p[0] > 0));
    }
}

该题解使用了逆向思维的深度优先搜索（DFS）方法。从目标点 (targetX, targetY) 开始，尝试反向追溯到起点 (1, 1)。反向操作包括：如果当前坐标的 x 或 y 是偶数，则将其除以 2；如果坐标 x 和 y 不相等，则尝试通过减法操作逆向推回。这里的思路是从目标点反推到初始点，而非正向从起点搜索到终点，因为反向操作可以更直接地缩小搜索空间。递归中，如果 x 和 y 相等而且都是奇数，则无法继续操作，因为不可能通过以上操作生成两个相等的奇数。最终，如果能反向递归到 (1, 1)，说明目标点可达，返回 true；否则返回 false。通过使用 @cache 装饰器，优化了重复子问题的求解过程，提高了效率。

O(log(max(targetX, targetY)))

O(log(max(targetX, targetY)))