Java递归实现坐标可达性验证遇问题，求高效解法及代码排查

Problem Overview #

You're trying to verify if you can reach coordinate (x,y) starting from (1,1), where each move is either (a+b, b) or (a, a+b). Your recursive brute-force approach works for small inputs but fails for larger ones due to stack overflow and redundant calculations. Let's break down the issues and fix them with an efficient reverse simulation approach.

Issues with Your Recursive Code #

Your code has two main problems that cause test case failures:

• Stack Overflow: For large values of x/y (e.g., 10^5 or higher), the recursion depth becomes too deep, exceeding Java's default stack limit. This crashes the program instead of returning a valid result.
• Redundant Computations: The same (a,b) pair is checked multiple times through different paths, leading to exponential time complexity and slow performance for even moderately sized inputs.
• Edge Case Gap: While your base cases handle most scenarios, inputs where x or y is less than 1 aren't explicitly validated (though the base case a > x || b > y will return false, it's cleaner to handle this upfront).

Efficient Approach: Reverse Simulation #

Instead of starting from (1,1) and moving forward, we can work backwards from (x,y). This is far more efficient because each step has only one valid choice (the larger number must have been formed by adding the smaller number in the forward direction):

1. Input Validation: If x or y is less than 1, return "No" immediately (we can't reach a coordinate smaller than our starting point).
2. Reverse Steps:
   • While x and y are not equal:
     • If x > y: Use modulo to skip repeated subtractions (instead of subtracting y from x multiple times, compute x = x % y). If x becomes 0 (meaning x was a multiple of y), set x = y (since the only valid multiple is when y=1).
     • If y > x: Do the same for y: y = y % x, and handle exact division similarly.
3. Final Check: After x and y are equal, check if they're both 1 (since our starting point is (1,1); any other equal pair can't be reached).

Java Code for Efficient Solution #

import java.util.Scanner;

class Solution {
    static String ans(int x, int y) {
        // Handle invalid inputs
        if (x < 1 || y < 1) {
            return "No";
        }
        
        while (x != y) {
            if (x > y) {
                if (y == 0) {
                    return "No";
                }
                // If x is exactly divisible by y, the previous step would be (y,y) which is only valid if y=1
                if (x % y == 0) {
                    x = y;
                } else {
                    x = x % y;
                }
            } else {
                if (x == 0) {
                    return "No";
                }
                if (y % x == 0) {
                    y = x;
                } else {
                    y = y % x;
                }
            }
        }
        
        // Only (1,1) is a valid equal starting point
        return x == 1 ? "Yes" : "No";
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        System.out.println(ans(x, y));
        sc.close();
    }
}

Optional: Fixing Your Recursive Code (With Memoization) #

If you want to keep a recursive approach (only recommended for small inputs), add memoization to cache results of already computed (a,b) pairs. This avoids redundant calculations:

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

class Solution {
    static Map<String, Boolean> memo = new HashMap<>();
    
    static boolean sol(int a, int b, int x, int y) {
        String key = a + "," + b;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        if (a == x && b == y) {
            memo.put(key, true);
            return true;
        }
        if (a > x || b > y) {
            memo.put(key, false);
            return false;
        }
        boolean result = sol(a + b, b, x, y) || sol(a, a + b, x, y);
        memo.put(key, result);
        return result;
    }
    
    static String ans(int x, int y) {
        memo.clear(); // Reset memo for each test case
        if (x < 1 || y < 1) {
            return "No";
        }
        return sol(1, 1, x, y) ? "Yes" : "No";
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        System.out.println(ans(x, y));
        sc.close();
    }
}

Note: This memoized recursive approach still won't handle very large inputs due to stack overflow, so the reverse simulation method is the better choice for all cases.

内容的提问来源于stack exchange，提问作者Keerthi Nandigam