Wie man rekursive Funktion verwaltet?

Question

Ich muss eine rekursive Funktion schreiben, die 4 Parameter erhält.

Die erste ist Array. der zweite - linke Index, der dritte ein rechter Index und "K" Index. Der "K" -Index ist eine Zelle im Array und der lrft-Index zeigt auf den Anfang und der rechte Index zeigt auf das Ende.

Ein Array kann solche Digitalis wie Nullen und Einsen enthalten. Die Methode gibt die maximale Länge einer Folge von Einsen zurück, die die Zelle k enthalten.

Hier ist das Beispiel für das Ergebnis, das ich bekommen müssen:

public static void main(String[] args) { 
    int[] A = {1,1,1,0,1,1,0,1,1,1,1,1,0,1,1}; 
    System.out.println(floodOnes(A,0, A.length-1, 9)); // 5 output 
    System.out.println(floodOnes(A,0, A.length-1, 3)); // 0 output 
    System.out.println(floodOnes(A,0, A.length-1, 0)); // 3 output 
    System.out.println(floodOnes(A,0, A.length-1, 14)); // 2 output 
} 

public static int floodOnes(int [] A,int left, int right, int k){ 
    //some logic 
} 

Hier ist meine Implementierung:

public class Program { 
    public static void main(String[] args) { 
     int[] A = {1,1,1,0,1,1,0,1,1,1,1,1,0,1,1}; 
     System.out.println(floodOnes(A,0,A.length-1, 9)); 
    } 

    public static int floodOnes(int [] A,int left, int right, int k){   
     if (left != k) left+=1; 
     if (right != k) right-=1; 

     if (left == k && right == k) return A[k]; //condition when the recursive call stops 

     int res = floodOnes(A, left, right, k); 

     if (A[left] == 1 && A[right] == 1) 
      return res = A[left] + A[right]; //count ones  

     else return res; 
    } 
} 

Aber meine Lösung nicht richtig funktioniert.

In diesen Zeilen:

if (A[left] == 1 && A[right] == 1) 
     return res = A[left] + A[right]; //count ones 

Wenn eine der Bedingungen einmal ausgeführt isn `t, sollten die folgenden Renditen nicht diejenigen hinzufügen Variable führen.

Und ich weiß nicht, wie es geht.

Answer 1

Da Sie suchen - the maximum length of a sequence of ones that contain the cell k. Ein einfacher und prägnanter Code, um dies zu erreichen, kann wie folgt sein.

public static void main(String[] args) { 
    int[] A = {1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1}; 
    System.out.println(floodOnes(A, 0, A.length - 1, 9)); // prints 5 
    System.out.println(floodOnes(A, 0, A.length - 1, 3)); // prints 0 
    System.out.println(floodOnes(A, 0, A.length - 1, 0)); // prints 3 
    System.out.println(floodOnes(A, 0, A.length - 1, 14)); // prints 2 
} 

public static int checkLeft(int[] A, int k) { 
    return (k < 0 || A[k] != 1) ? 0 : 1 + checkLeft(A, k - 1); 
} 

public static int checkRight(int[] A, int k) { 
    return (k > (A.length - 1) || A[k] != 1) ? 0 : 1 + checkRight(A, k + 1); 
} 

public static int floodOnes(int[] A, int left, int right, int k) { 
    return (A[k] != 1) ? 0 : checkLeft(A, k - 1) + 1 + checkRight(A, k + 1); 
} 

Es gibt das gewünschte Ergebnis aus.

5 
0 
3 
2 

Answer 2

Sie können dieses Problem in 2 Funktionen zerlegen. Der erste zählt Elemente auf der linken Seite, letztere auf der rechten Seite. Beide verwenden Rekursion.

public static int floodOnes(int[] A, int left, int right, int k) { 
    return checkLeft(A, left, k-1, A[k]) + 1 + checkRight(A, right, k+1, A[k]); 
} 

public static int checkLeft(int[] A, int leftBoundary, int k, int number) { 
    if (k < 0 || A[k] != number || k < leftBoundary) 
     return 0; 
    return 1 + checkLeft(A, leftBoundary, k-1, number); 
} 

public static int checkRight(int[] A, int rightBoundary, int k, int number) { 
    if(k >= A.length || A[k] != number || k > rightBoundary) 
     return 0; 
    return 1 + checkRight(A, rightBoundary, k+1, number); 
} 

Ich gehe davon aus:
dass 0 <= left <= k <= right < A.length;
, dass die Einzelzahl im Gegensatz zu Ihrem Beispiel als 1 (Sequenz der Länge 1) gezählt werden sollte. Wenn Sie möchten, dass es als 0 gezählt wird, fügen Sie if(A[k] != 1) return 0; oder eine ähnliche Bedingung in Ihrer floodOnes Methode hinzu.

Deshalb:

System.out.println(floodOnes(A, 0, A.length - 1, 9)); // prints 5 
System.out.println(floodOnes(A, 0, A.length - 1, 3)); // prints 1 
System.out.println(floodOnes(A, 0, A.length - 1, 0)); // prints 3 
System.out.println(floodOnes(A, 0, A.length - 1, 14)); // prints 2 

Neben left und right Parameter können für einige Eingangs Ausnahmen verwendet werden (z.B. k > A.length).

Answer 3

Ich bewies meinen Kommentar falsch. Hier ist eine rekursive Methode mit den 4 in der Frage genannten Parametern, die das Problem tatsächlich löst.

public static int floodOnes(int[] a, int left, int right, int k) { 
    if (0 <= left && left <= k && k <= right && right < a.length) { 
     // is there a 0 between left (inclusive) and k (exclusive)? 
     int i = left; 
     while (i < k && a[i] == 1) { 
      i++; 
     } 
     if (i < k) { 
      assert a[i] == 0; 
      return floodOnes(a, i + 1, right, k); 
     } 
     // is there a 0 between k (exclusive) and right (inclusive)? 
     i = right; 
     while (i > k && a[i] == 1) { 
      i--; 
     } 
     if (i > k) { 
      assert a[i] == 0; 
      return floodOnes(a, left, i - 1, k); 
     } 
     // no zero found, a[k] not checked, though 
     if (a[k] == 0) { 
      return 0; 
     } else { 
      return right - left + 1; 
     } 
    } else { 
     throw new IllegalArgumentException("Expected " + left + " <= " + k + " <= " + right + " < " + a.length); 
    } 
} 

Mit dieser Methode druckt das erste main Methode in Ihrer Frage die erwartete:

5 
0 
3 
2 

ich einen Punkt sehe nicht wirklich das Problem auf diese Weise bei der Lösung, so dass ich bin weit davon entfernt Sicher, das war was beabsichtigt war. Ich würde eine nicht-rekursive Lösung bevorzugen, oder wenn es nur irgendwie rekursiv sein muss, dann die Lösung in Grzegorz Górkiewicz’ answer.