Problem
Die erste Zeile ist [1]. Jede weitere Zeile beginnt und endet mit 1. Jeder innere Eintrag ist die Summe der beiden direkt darüberliegenden Einträge. Gib die ersten rows Zeilen zurück, beginnend mit der einzelnen 1.
Implementiere pascals_triangle(rows).
Eingabe
rows: Wie viele Zeilen generiert werden sollen.
Ausgabe
Gib eine Liste von Zeilen zurück, beginnend oben; jede Zeile ist eine Liste von Ganzzahlen.
Einschränkungen
0 ≤ rows ≤ 60. Jeder Eintrag passt in einen vorzeichenbehafteten 64-Bit-Integer. Bei null Zeilen wird eine leere Liste zurückgegeben.
Beispiele
Eingabe:
rows = 4
Erwartete Ausgabe:
expected = [
[1],
[1, 1],
[1, 2, 1],
[1, 3, 3, 1]
]Eingabe:
long long rows = 4;
Erwartete Ausgabe:
std::vector<std::vector<long long>> expected = {
{1},
{1, 1},
{1, 2, 1},
{1, 3, 3, 1}
};Eingabe:
long rows = 4;
Erwartete Ausgabe:
long[][] expected = new long[][] {
new long[] {1},
new long[] {1, 1},
new long[] {1, 2, 1},
new long[] {1, 3, 3, 1}
};Erläuterung
Die 2 in Zeile 3 ist 1 + 1. Die beiden inneren 3en in Zeile 4 sind 1 + 2 und 2 + 1.
Eingabe:
rows = 0
Erwartete Ausgabe:
expected = []Eingabe:
long long rows = 0;
Erwartete Ausgabe:
std::vector<std::vector<long long>> expected = {};Eingabe:
long rows = 0;
Erwartete Ausgabe:
long[][] expected = new long[][] {};Erläuterung
Es werden keine Zeilen angefordert, daher wird eine leere Liste zurückgegeben.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Jede Zeile beginnt und endet mit 1, und innere Werte entstehen aus den beiden Werten darüber.
Hinweis 2
Baue die Zeilen nacheinander aus der vorherigen Zeile auf, statt alles neu zu berechnen.
Hinweis 3
Behandle den Fall 0 Zeilen, indem du sofort eine leere Liste zurückgibst.
Erwartete Komplexität
Zeit O(rows^2), zusätzlicher Speicher O(rows^2)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.