HackerRank Java的一維數組（第2部分）

我試圖解決以下問題HackerRank Java 1D Array HackerRank Java的一維數組（第2部分）

我想出了下面的回溯方法。

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; 
}

}

來源

2017-02-15 Learner

它可能會進入無限遞歸，因爲它在前進一步和後退一步之間保持交替。 –

在遞歸算法中則必須以避免相同的狀態的處理兩次

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

或可以重複使用ARR []爲同樣的目的的內容，如果可以修改它

來源

2017-02-15 07:55:32 rustot

謝謝。我修改了代碼。 – Learner

HackerRank Java的一維數組（第2部分）

回答

相關問題