1D Array Spiel auf HackerRank

Question

Ich versuche, dieses Problem auf HackerRank für Stunden zu lösen. Die grundlegende Problembeschreibung lautet wie folgt:

Sie haben ein 1D-Array, das nur aus 0s und 1s besteht. Sie beginnen mit dem 0. Index. Nehmen wir an, die Größe des Arrays sei n. Sie gewinnen, wenn Sie über den Rahmen des Arrays (d. H. Zu einem Index> n-1) hinausreichen können. Aber Sie können nur auf zwei Arten bewegen:

• Gehen Sie einen Schritt vorwärts oder rückwärts.
• Machen Sie einen Sprung von genau 'm' Länge vorwärts.

Sie können aber auch nur STEP auf ein Element mit dem Wert 0 Der Wert bei 0. Index ist bekannt 0 zu sein (so starten Sie eine gültige Position)

‚m‘ vorgesehen ist, wie eine Eingabe und es kann ein beliebiger Wert zwischen 0 und 100 einschließlich sein. Die Array-Größe kann einen Wert zwischen 2 und 100 einschließlich haben.

Das Programm sollte "YES" drucken, wenn ein Gewinn möglich ist. sonst "NEIN".

Ich versuchte es mit einem Backtracking-Algorithmus in Java zu lösen. Aber es wird für die meisten Testfälle abgelehnt.

Bitte helfen Sie mir. Danke im Voraus.

public class Solution { 

public static void main(String[] args) { 
     Scanner sc = new Scanner(System.in); 

     int n=sc.nextInt(); 
     int m=sc.nextInt(); 
     int[] array = new int[n]; 

     for(int i=0;i<n;i++){ 
      array[i]=sc.nextInt(); 
     } 

     if(m<2){ 
      for(int i=0;i<n;i++){ 
        if(array[i] == 1){ 
         System.out.println("NO"); 
         break; 
        } 
       } 
       System.out.println("YES"); 
      } 

      else{ 
     if(isSolvable(array,0,m,n)) 
     {System.out.println("YES");} 
     else 
     {System.out.println("NO");} 

     } 

    } 

    static boolean isSolvable(int[] array,int x,int m,int n){ 
     if(x>n-1){ 
      //System.out.print(x + " "); 
      return true; 
     } 
     if(array[x] == 1) return false; 
     if(isSolvable(array,x+m,m,n)){ 
      //System.out.print(x + " "); 
      return true; 
     } 
     if(isSolvable(array,x+1,m,n)){ 
      //System.out.print(x + " "); 
      return true; 
     } 
     return false; 
    } 
} 

Answer 1

Ich tat dies nicht mit Rückzieher, aber nur Rekursion, und ich war in der Lage, das Problem zu lösen und alle bekommen Testfälle korrekt. Der Code, den Sie gepostet haben, führt auch kein Backtracking durch. Ich sehe auch, dass du unter deinen Bedingungen die Bedingung verpasst, sich um 1 zurück zu bewegen, was dazu führen würde, dass du in einigen Fällen versagt.

ZB: 0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1 mit m = 5.

Mit dem obigen Beispiel springen Sie zuerst zu x + m, dann versuchen Sie erneut x + m, dann versuchen Sie x + 1, sonst kommen Sie raus.

diesen Testfall zu brechen:

0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1 

     ^x+m True 
0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1 

        ^x+m False 
0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1 

      ^x+1 False 
0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1 

^x+1 False 

mit Ihrem Code, würden Sie falsch zurück, wo anstatt diese zu lösen, müßten Sie Folgendes tun:

0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1 

     ^x+m 

0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1 

     ^x-1 
0 1 1 1 0 0 1 1 1 0 1 1 1 1 0 1 

       ^x+m 

Dann zwei weitere x + m, um es zu vervollständigen, um wahr zurückzukehren.

Um dies mit Ihrem Code zu vervollständigen, müssen Sie die Bedingung hinzufügen, um ein Leerzeichen zurück zu verschieben, ABER wenn Sie dies tun, könnten Sie eine endlose rekursive Schleife einbauen. Beispiel: (-1 + 1-1 + 1-1 + 1) was zu einem Stackoverflow führen wird. Eine der Sachen, die ich vorschlagen würde, würde ein boolean Array sein, zum des Gedächtnisses der Punkte zu halten, die du vorher gesehen hast.

Answer 2

dieses Spiel Coding ist ein bisschen schwer für einen Amateur, aber die algorytm erklären, dass ich denke, das Problem zu lösen.

Zunächst einmal denke ich, dass die Punkte, die Sie sowohl eins als auch "m" Schritte weiter gehen können, die Schlüsselpunkte dieses Problems sind. Ich meine, du kannst einen anderen Weg von ihnen wählen. Wenn du sie 3 mal erreichst, sind sie nutzlos usw. Es ist wichtig, sie in einem Array zu halten, denke ich.

• definieren ein Array als WellPoints

• prüfen ersten Punkt des Array, in dem Sie einen Schritt gehen und „m“ Stufen beide weiter. Speichern Sie es unter firstWellPoint oder WellPoints[0].

• Versuchen Sie, diesen Punkt mit einem einfachen Backtracking-Algorithmus um einen oder mehrere Schritte zu erreichen. Wenn Sie nicht können, ist es einfach "NEIN".

• Wenn Sie firstWellPoint erreichen kann, definieren eine counter, wie oft Sie WellPoints besucht zu zählen.

• Während Sie die nächsten Schritte für jeden Punkt überprüfen, überprüfen Sie auch, ob der Punkt für einen Schritt und m Schritte geeignet ist. Wenn eins und m weiter "0" für beide ist, plaziere es auf WellPoints Array. Jetzt

• , wenn nächste Prüfung nicht wahr sein wird, wieder an die letzte Element WellPoints Array und erhöhen auch Ihre counter von 1.

• Wenn Sie einen neuen WellPoint finden, setzen Sie Ihre counter 1.

• Wenn counter = 3, dann löschen Sie diese WellPoint und starten Sie von einem vorher durch andere Weise überprüft, die neue letzte Element WellPoint Array bedeutet. Es kann den Weg durch die Überprüfung counter wie counter = 1 versuchen, eine Schritte zu entscheiden, und wenn Sie wieder hierher kommen, bedeutet es, wenn counter = 2 m Schritte versuchen.

• wenn WellPoint Arrays erstes Element oder firstWellPoint, wie ich wieder WellPoint Array 3 mal durch Rückzieher auf Erreichen erklärt, können Sie Ihren Array löschen werden diese WellPoint auch so wird am Ende auf ihn gehen nicht in der Lage sein.

• Wenn Sie erreichen von Array zu beenden, so dass Sie wissen, dass ...