. Zielsumme

494. Zielsumme

Schwierigkeit:Mittel

Themen:Array, Dynamische Programmierung, Backtracking

Sie erhalten ein Integer-Array nums und ein Integer-Ziel.

Sie möchten einen Ausdruck aus Zahlen erstellen, indem Sie vor jeder Ganzzahl in Zahlen eines der Symbole „ “ und „-“ hinzufügen und dann alle Ganzzahlen verketten.

• Wenn beispielsweise nums = [2, 1] ist, können Sie ein „ ' vor 2 und ein „-“ vor 1 hinzufügen und diese verketten, um den Ausdruck „ 2-1“ zu bilden.

Gibt die Anzahl der verschiedenen Ausdrücke zurück, die Sie erstellen können und die als Ziel ausgewertet werden.

Beispiel 1:

• Eingabe: nums = [1,1,1,1,1], Ziel = 3
• Ausgabe: 5
• Erklärung: Es gibt 5 Möglichkeiten, Symbole zuzuweisen, damit die Summe der Zahlen Ziel 3 ist.
  • -1 1 1 1 1 = 3
  • 1 - 1 1 1 1 = 3
  • 1 1 - 1 1 1 = 3
  • 1 1 1 - 1 1 = 3
  • 1 1 1 1 - 1 = 3

Beispiel 2:

• Eingabe: nums = [1], Ziel = 1
• Ausgabe: 1

Einschränkungen:

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= Ziel <= 1000

Lösung:

Das Problem „Zielsumme“ besteht darin, Ausdrücke mithilfe der Zahlen in einem Array zu erstellen, indem jeder Zahl ein Oder-Zeichen zugewiesen wird. Das Ziel besteht darin, zu berechnen, wie viele solcher Ausdrücke für das gegebene Ziel ausgewertet werden. Dieses Problem kann durch dynamische Programmierung oder Backtracking effizient gelöst werden.

Wichtige Punkte

1. Eingabebeschränkungen:
   • Array-Länge: 1 <= nums.length <= 20
   • Elementwerte: 0 <= nums[i] <= 1000
   • Zielbereich: -1000 <= Ziel <= 1000

2. Ausgabe:

   • Gibt die Anzahl der Ausdrücke zurück, die zum Ziel ausgewertet werden.

3. Herausforderungen:

   • Die Lösung muss sowohl kleine als auch große Zielwerte verarbeiten.
   • Effiziente Handhabung von bis zu 2²⁰ Kombinationen bei Verwendung von Backtracking.

Anfahrt

Wir können dieses Problem mithilfe von Dynamischer Programmierung (Subset Sum Transformation) oder Backtracking lösen. Im Folgenden verwenden wir Dynamic Programming (DP) für mehr Effizienz.

Wichtige Beobachtungen:

1. Wenn wir Zahlen in zwei Gruppen aufteilen: P (positive Teilmenge) und N (negative Teilmenge), dann gilt: Ziel = Summe(P) – Summe(N)

Begriffe neu anordnen: sum(P) sum(N) = sum(nums)

Es sei S die Summe der positiven Teilmenge. Dann: S = (sum(nums) target) / 2

1. Wenn (sum(nums) target) % 2 ≠ 0, geben Sie 0 zurück, da es unmöglich ist, die Summen zu partitionieren.

Planen

1. Berechnen Sie die Gesamtsumme der Zahlen.
2. Überprüfen Sie anhand der Formel für S, ob das Ziel erreichbar ist . Wenn ungültig, geben Sie 0 zurück.
3. Verwenden Sie einen DP-Ansatz, um die Anzahl der Teilmengen in Nums zu ermitteln, deren Summe gleich S ist .

Lassen Sie uns diese Lösung in PHP implementieren: 494. Zielsumme

<?php
/**
 * @param Integer[] $nums
 * @param Integer $target
 * @return Integer
 */
function findTargetSumWays($nums, $target) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$nums = [1, 1, 1, 1, 1];
$target = 3;
echo findTargetSumWays($nums, $target); // Output: 5
?>

Erläuterung:

1. Eingabevalidierung:

   • Wir berechnen S = (sum(nums) target) / 2.
   • Wenn S keine ganze Zahl ist, ist es unmöglich, Zahlen in zwei Teilmengen aufzuteilen.

2. Dynamische Programmierlogik:

   • dp[j] stellt die Anzahl der Möglichkeiten dar, mit den angegebenen Zahlen eine Summe j zu bilden.
   • Beginnend mit dp[0] = 1 aktualisieren wir für jede Zahl in nums dp[j], indem wir die Anzahl der Wege addieren, um j – num zu bilden.

3. Ergebnis:

   • Nach der Verarbeitung aller Zahlen enthält dp[S] die Anzahl der Wege, um die Zielsumme zu erreichen.

Beispiel-Anleitung

Eingabe: nums = [1, 1, 1, 1, 1], Ziel = 3

1. totalSum = 5, S = (5 3) / 2 = 4.
2. DP-Array initialisieren: dp = [1, 0, 0, 0, 0].
3. Verarbeiten Sie jede Zahl:
   • Für 1: dp aktualisieren: [1, 1, 0, 0, 0].
   • Für 1: dp aktualisieren: [1, 2, 1, 0, 0].
   • Für 1: dp aktualisieren: [1, 3, 3, 1, 0].
   • Für 1: dp aktualisieren: [1, 4, 6, 4, 1].
   • Für 1: dp aktualisieren: [1, 5, 10, 10, 5].
4. Ergebnis: dp[4] = 5.

Zeitkomplexität

• Zeit: O(n x S), wobei n die Länge der Zahlen und S die Zielsumme ist.
• Leerzeichen: O(S) für das DP-Array.

Ausgabe als Beispiel

Eingabe: nums = [1,1,1,1,1], Ziel = 3

Ausgabe: 5

Dieser Ansatz berechnet mithilfe dynamischer Programmierung effizient die Anzahl der Möglichkeiten zur Bildung der Zielsumme. Indem wir das Problem auf die Teilmengensumme reduzieren, nutzen wir die Struktur von DP für eine bessere Leistung.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub

Das obige ist der detaillierte Inhalt von. Zielsumme. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!