HackerRank Java 一维数组（第 2 部分）

Question

我想出了以下回溯方法。

import java.util.Scanner;

public class Solution {
static int arr[];

public static void main(String[] args) {    
    Scanner sc= new Scanner(System.in);
    int T = sc.nextInt();
    for (int j= 0; j < T; j++) {
        int n = sc.nextInt();
        arr = new int[n];
        int m = sc.nextInt();
        for (int k = 0; k< n; k++) {
            arr[k]= sc.nextInt();
        }
       if(canReach(0,arr.length,m))
           System.out.println("YES");
       else 
          System.out.println("NO");
    }
}
public static boolean canReach(int src,int dest,int m)
{
    if(src>=(dest-1)||(src+m)>=dest)
        return true;
    if(isValidDest(src+1)&&canReach(src+1, dest, m))
        return true;
    if(isValidDest(src-1)&&canReach(src-1, dest, m))
        return true;
    if(isValidDest(src+m)&&canReach(src+m, dest, m))
        return true;
    return false;
}
private static boolean isValidDest(int dest) {
    if(((dest>=0&&dest<arr.length)&&(arr[dest]==0)))
        return true;
    return false;
}

}

但我收到以下测试用例的堆栈溢出错误 0 0 1 1 1 0。

谁能帮我解决如何避免这种堆栈溢出错误，同时保持回溯方法的完整性。

Modified code (solution)

import java.util.Scanner;

public class Solution {
static int arr[];
static boolean isDestVisited[];

public static void main(String[] args) {    
    Scanner sc= new Scanner(System.in);
    int T = sc.nextInt();
    for (int j= 0; j < T; j++) {
        int n = sc.nextInt();
        arr = new int[n];
        isDestVisited = new boolean[n];
        int m = sc.nextInt();
        for (int k = 0; k< n; k++) {
            arr[k]= sc.nextInt();
        }
       if(canReach(0,arr.length,m))
           System.out.println("YES");
       else 
          System.out.println("NO");
    }
}
public static boolean canReach(int src,int dest,int m)
{
    if(src>=(dest-1)||(src+m)>=dest)
        return true;
    if(isDestVisited[src]==true)
        return false;
    isDestVisited[src]=true;
    if(isValidDest(src+1)&&canReach(src+1, dest, m))
        return true;
    if(isValidDest(src-1)&&canReach(src-1, dest, m))
        return true;
    if(isValidDest(src+m)&&canReach(src+m, dest, m))
        return true;
    isDestVisited[src]=false;
    return false;
}
private static boolean isValidDest(int dest) {
    if(((dest>=0&&dest<arr.length)&&(arr[dest]==0)))
        return true;
    return false;
}

}

Answer 1

在递归算法中，你必须避免两次处理相同的状态

if (src >= dest)
    return true;
if (thisPositionAlreadyTested[src])
  return false;
thisPositionAlreadyTested[src] = true;
if ( ...

或者如果您可以修改 arr[] 内容，您可以将其重复用于同一目的

HackerRank Java 一维数组（第 2 部分）

HackerRank Java 1D Array (Part 2)

java

algorithm

recursion

backtracking