Mit Objekten können Sie verschlüsselte Wertesammlungen speichern. Das ist in Ordnung.
Aber ziemlich oft stellen wir fest, dass wir eine geordnete Sammlung benötigen, in der wir ein 1., ein 2., ein 3. Element usw. haben. Wir brauchen das zum Beispiel, um eine Liste von etwas zu speichern: Benutzer, Waren, HTML-Elemente usw.
Es ist nicht praktisch, hier ein Objekt zu verwenden, da es keine Methoden zum Verwalten der Reihenfolge von Elementen bereitstellt. Wir können keine neue Eigenschaft „zwischen“ den vorhandenen einfügen. Objekte sind einfach nicht für diesen Zweck bestimmt.
Es gibt eine spezielle Datenstruktur namens Array zum Speichern geordneter Sammlungen.
Es gibt zwei Syntaxen zum Erstellen eines leeren Arrays:
let arr = new Array(); sei arr = [];
Fast immer wird die zweite Syntax verwendet. Wir können Anfangselemente in den Klammern angeben:
let Fruits = [„Apfel“, „Orange“, „Pflaume“];
Array-Elemente sind nummeriert, beginnend mit Null.
Wir können ein Element anhand seiner Nummer in eckigen Klammern ermitteln:
let Fruits = [„Apfel“, „Orange“, „Pflaume“]; Alert( Früchte[0] ); // Apfel Alert( Früchte[1] ); // Orange Alert( Früchte[2] ); // Pflaume
Wir können ein Element ersetzen:
Früchte[2] = 'Birne'; // now ["Apple", "Orange", "Birne"]
…Oder fügen Sie dem Array ein neues hinzu:
Früchte[3] = 'Zitrone'; // now ["Apple", "Orange", "Birne", "Lemon"]
Die Gesamtzahl der Elemente im Array ist seine length :
let Fruits = [„Apfel“, „Orange“, „Pflaume“]; Alert(fruits.length); // 3
Wir können alert auch verwenden, um das gesamte Array anzuzeigen.
let Fruits = [„Apfel“, „Orange“, „Pflaume“]; Warnung (Früchte); // Apfel, Orange, Pflaume
Ein Array kann Elemente jeden Typs speichern.
Zum Beispiel:
// Wertemix
let arr = [ 'Apple', { name: 'John' }, true, function() { Alert('hello'); } ];
// Holen Sie sich das Objekt bei Index 1 und zeigen Sie dann seinen Namen an
alarm( arr[1].name ); // John
// Holen Sie sich die Funktion bei Index 3 und führen Sie sie aus
arr[3](); // HalloNachgestelltes Komma
Ein Array kann, genau wie ein Objekt, mit einem Komma enden:
lass Früchte = [ "Apfel", "Orange", "Pflaume", ];
Der Stil „nachgestelltes Komma“ erleichtert das Einfügen/Entfernen von Elementen, da alle Zeilen gleich werden.
Eine neue Ergänzung
Dies ist eine neue Ergänzung der Sprache. Alte Browser benötigen möglicherweise Polyfills.
Nehmen wir an, wir wollen das letzte Element des Arrays.
Einige Programmiersprachen erlauben die Verwendung negativer Indizes für denselben Zweck, wie beispielsweise fruits[-1] .
Allerdings funktioniert es in JavaScript nicht. Das Ergebnis wird undefined sein, da der Index in eckigen Klammern wörtlich behandelt wird.
Wir können den Index des letzten Elements explizit berechnen und dann darauf zugreifen: fruits[fruits.length - 1] .
let Fruits = [„Apfel“, „Orange“, „Pflaume“]; Alert( Früchte[Früchte.Länge-1] ); // Pflaume
Etwas umständlich, nicht wahr? Wir müssen den Variablennamen zweimal schreiben.
Glücklicherweise gibt es eine kürzere Syntax: fruits.at(-1) :
let Fruits = [„Apfel“, „Orange“, „Pflaume“]; // das Gleiche wie Fruits[fruits.length-1] Alert( Fruits.at(-1) ); // Pflaume
Mit anderen Worten, arr.at(i) :
ist genau das Gleiche wie arr[i] , wenn i >= 0 .
Bei negativen Werten von i wird vom Ende des Arrays zurückgegangen.
Eine Warteschlange ist eine der häufigsten Verwendungsmöglichkeiten eines Arrays. In der Informatik bedeutet dies eine geordnete Sammlung von Elementen, die zwei Operationen unterstützt:
push hängt ein Element an das Ende an.
shift holt ein Element von Anfang an und rückt die Warteschlange vor, sodass das 2. Element zum 1. wird.
Arrays unterstützen beide Operationen.
In der Praxis brauchen wir es sehr oft. Beispielsweise eine Warteschlange mit Nachrichten, die auf dem Bildschirm angezeigt werden müssen.
Es gibt noch einen weiteren Anwendungsfall für Arrays – die Datenstruktur namens Stack.
Es unterstützt zwei Operationen:
push fügt am Ende ein Element hinzu.
pop übernimmt ein Element vom Ende.
Neue Elemente werden also immer vom „Ende“ hinzugefügt oder übernommen.
Ein Stapel wird normalerweise als Kartenstapel dargestellt: Neue Karten werden oben hinzugefügt oder von oben entnommen:
Bei Stapeln wird das zuletzt gepushte Element zuerst empfangen. Dies wird auch als LIFO-Prinzip (Last-In-First-Out) bezeichnet. Für Warteschlangen haben wir FIFO (First-In-First-Out).
Arrays in JavaScript können sowohl als Warteschlange als auch als Stapel funktionieren. Sie ermöglichen das Hinzufügen/Entfernen von Elementen, sowohl am Anfang als auch am Ende.
In der Informatik wird die Datenstruktur, die dies ermöglicht, Deque genannt.
Methoden, die mit dem Ende des Arrays arbeiten:
pop
Extrahiert das letzte Element des Arrays und gibt es zurück:
let Fruits = [„Apfel“, „Orange“, „Birne“]; alarm(fruits.pop() ); // „Pear“ entfernen und alarmieren Warnung (Früchte); // Apfel, Orange
Sowohl fruits.pop() als auch fruits.at(-1) geben das letzte Element des Arrays zurück, aber fruits.pop() verändert das Array auch, indem es es entfernt.
push
Hängen Sie das Element an das Ende des Arrays an:
let Fruits = ["Apfel", "Orange"];
Früchte.push("Birne");
Warnung (Früchte); // Apfel, Orange, Birne Der Aufruf fruits.push(...) ist gleich fruits[fruits.length] = ... .
Methoden, die mit dem Anfang des Arrays arbeiten:
shift
Extrahiert das erste Element des Arrays und gibt es zurück:
let Fruits = [„Apfel“, „Orange“, „Birne“]; alarm( Fruits.shift() ); // Apple entfernen und benachrichtigen Warnung (Früchte); // Orange, Birne
unshift
Fügen Sie das Element am Anfang des Arrays hinzu:
let Fruits = ["Orange", "Birne"];
Früchte.unshift('Apple');
Warnung (Früchte); // Apfel, Orange, Birne Die Methoden push und unshift können mehrere Elemente gleichzeitig hinzufügen:
let Fruits = ["Apfel"];
Früchte.push("Orange", "Pfirsich");
Fruits.unshift("Ananas", "Zitrone");
// ["Ananas", "Zitrone", "Apfel", "Orange", "Pfirsich"]
Warnung (Früchte); Ein Array ist eine besondere Art von Objekt. Die eckigen Klammern, die für den Zugriff auf eine Eigenschaft arr[0] verwendet werden, stammen eigentlich aus der Objektsyntax. Das ist im Wesentlichen dasselbe wie obj[key] , wobei arr das Objekt ist, während Zahlen als Schlüssel verwendet werden.
Sie erweitern Objekte und stellen spezielle Methoden für die Arbeit mit geordneten Datensammlungen und auch der length bereit. Aber im Kern ist es immer noch ein Objekt.
Denken Sie daran, dass es in JavaScript nur acht grundlegende Datentypen gibt (weitere Informationen finden Sie im Kapitel „Datentypen“). Array ist ein Objekt und verhält sich daher wie ein Objekt.
Es wird beispielsweise per Referenz kopiert:
let Fruits = ["Banane"]
sei arr = Früchte; // Nach Referenz kopieren (zwei Variablen verweisen auf dasselbe Array)
Alert( arr === Früchte ); // WAHR
arr.push("Pear"); // das Array per Referenz ändern
Warnung (Früchte); // Banane, Birne – jetzt 2 Artikel…Aber das Besondere an Arrays ist ihre interne Darstellung. Die Engine versucht, ihre Elemente nacheinander im zusammenhängenden Speicherbereich zu speichern, wie in den Abbildungen in diesem Kapitel dargestellt, und es gibt auch andere Optimierungen, damit Arrays wirklich schnell arbeiten.
Aber sie alle gehen kaputt, wenn wir aufhören, mit einem Array wie mit einer „geordneten Sammlung“ zu arbeiten, und anfangen, damit zu arbeiten, als wäre es ein normales Objekt.
Technisch gesehen können wir beispielsweise Folgendes tun:
lass Früchte = []; // ein Array erstellen Früchte[99999] = 5; // Eine Eigenschaft zuweisen, deren Index weitaus größer als ihre Länge ist Früchte. Alter = 25; // eine Eigenschaft mit einem beliebigen Namen erstellen
Das ist möglich, weil Arrays an ihrer Basis Objekte sind. Wir können ihnen beliebige Eigenschaften hinzufügen.
Aber die Engine erkennt, dass wir mit dem Array wie mit einem normalen Objekt arbeiten. Array-spezifische Optimierungen sind für solche Fälle nicht geeignet und werden deaktiviert, ihre Vorteile verschwinden.
Die Möglichkeiten, ein Array zu missbrauchen:
Fügen Sie eine nicht numerische Eigenschaft wie arr.test = 5 hinzu.
Machen Sie Löcher, etwa: Fügen Sie arr[0] und dann arr[1000] hinzu (und nichts dazwischen).
Füllen Sie das Array in umgekehrter Reihenfolge, z. B. arr[1000] , arr[999] usw.
Stellen Sie sich Arrays bitte als spezielle Strukturen für die Arbeit mit den geordneten Daten vor. Dafür stellen sie spezielle Methoden zur Verfügung. Arrays werden in JavaScript-Engines sorgfältig darauf abgestimmt, mit zusammenhängenden geordneten Daten zu arbeiten. Bitte verwenden Sie sie auf diese Weise. Und wenn Sie beliebige Schlüssel benötigen, ist die Wahrscheinlichkeit hoch, dass Sie tatsächlich ein reguläres Objekt {} benötigen.
Die Methoden push/pop laufen schnell, während shift/unshift langsam ist.
Warum ist es schneller, mit dem Ende eines Arrays zu arbeiten als mit seinem Anfang? Mal sehen, was während der Ausführung passiert:
Früchte.shift(); // 1 Element vom Anfang nehmen
Es reicht nicht aus, das Element mit dem Index 0 zu übernehmen und zu entfernen. Auch andere Elemente müssen neu nummeriert werden.
Der shift muss drei Dinge tun:
Entfernen Sie das Element mit dem Index 0 .
Verschieben Sie alle Elemente nach links, nummerieren Sie sie vom Index 1 auf 0 , von 2 auf 1 usw. um.
Aktualisieren Sie die length .
Je mehr Elemente im Array vorhanden sind, desto mehr Zeit wird zum Verschieben benötigt und desto mehr Vorgänge im Speicher werden ausgeführt.
Ähnliches passiert mit unshift : Um ein Element am Anfang des Arrays hinzuzufügen, müssen wir zunächst vorhandene Elemente nach rechts verschieben und ihre Indizes erhöhen.
Und was ist mit push/pop ? Sie müssen nichts bewegen. Um ein Element vom Ende zu extrahieren, bereinigt die pop -Methode den Index und verkürzt length .
Die Aktionen für den pop -Vorgang:
Früchte.pop(); // 1 Element vom Ende nehmen
Die pop -Methode muss nichts verschieben, da andere Elemente ihre Indizes behalten. Deshalb ist es rasend schnell.
Ähnliches gilt für die push -Methode.
Eine der ältesten Methoden zum Durchlaufen von Array-Elementen ist die for -Schleife über Indizes:
let arr = ["Apple", "Orange", "Birne"];
for (let i = 0; i < arr.length; i++) {
alarm( arr[i] );
} Aber für Arrays gibt es eine andere Form der Schleife, for..of :
let Fruits = [„Apfel“, „Orange“, „Pflaume“];
// iteriert über Array-Elemente
für (Frucht von Früchten lassen) {
Warnung (Frucht);
} Das for..of gibt keinen Zugriff auf die Nummer des aktuellen Elements, sondern nur auf seinen Wert, aber in den meisten Fällen reicht das aus. Und es ist kürzer.
Da es sich bei Arrays um Objekte handelt, ist es technisch gesehen auch möglich, for..in zu verwenden:
let arr = ["Apple", "Orange", "Birne"];
for (arr eingeben lassen) {
alarm( arr[key] ); // Apfel, Orange, Birne
}Aber das ist eigentlich eine schlechte Idee. Es gibt potenzielle Probleme damit:
Die Schleife for..in durchläuft alle Eigenschaften , nicht nur die numerischen.
Im Browser und in anderen Umgebungen gibt es sogenannte „Array-ähnliche“ Objekte, die wie Arrays aussehen . Das heißt, sie verfügen über length und Indexeigenschaften, können aber auch über andere nicht numerische Eigenschaften und Methoden verfügen, die wir normalerweise nicht benötigen. Die for..in Schleife listet sie jedoch auf. Wenn wir also mit Array-ähnlichen Objekten arbeiten müssen, können diese „zusätzlichen“ Eigenschaften zu einem Problem werden.
Die for..in Schleife ist für generische Objekte und nicht für Arrays optimiert und daher 10-100-mal langsamer. Natürlich ist es immer noch sehr schnell. Die Beschleunigung kann nur bei Engpässen von Bedeutung sein. Dennoch sollten wir uns des Unterschieds bewusst sein.
Im Allgemeinen sollten wir for..in nicht für Arrays verwenden.
Die length wird automatisch aktualisiert, wenn wir das Array ändern. Genauer gesagt handelt es sich dabei nicht um die Anzahl der Werte im Array, sondern um den größten numerischen Index plus eins.
Beispielsweise ergibt ein einzelnes Element mit einem großen Index eine große Länge:
lass Früchte = []; Früchte[123] = „Apfel“; Alert(fruits.length); // 124
Beachten Sie, dass wir solche Arrays normalerweise nicht verwenden.
Ein weiterer interessanter Aspekt der length ist, dass sie beschreibbar ist.
Wenn wir es manuell erhöhen, passiert nichts Interessantes. Wenn wir ihn jedoch verringern, wird das Array abgeschnitten. Der Vorgang ist irreversibel, hier das Beispiel:
sei arr = [1, 2, 3, 4, 5]; arr.length = 2; // Auf 2 Elemente kürzen alarm( arr ); // [1, 2] arr.length = 5; // Länge zurückgeben alarm( arr[3] ); // undefiniert: Die Werte werden nicht zurückgegeben
Der einfachste Weg, das Array zu löschen, ist also: arr.length = 0; .
Es gibt noch eine weitere Syntax zum Erstellen eines Arrays:
let arr = new Array("Apple", "Pear", "etc"); Es wird selten verwendet, da eckige Klammern [] kürzer sind. Außerdem gibt es eine knifflige Funktion.
Wenn new Array mit einem einzelnen Argument aufgerufen wird, das eine Zahl ist, wird ein Array ohne Elemente, aber mit der angegebenen Länge erstellt.
Mal sehen, wie man sich selbst ins Bein schießen kann:
let arr = new Array(2); // wird ein Array von [2] erstellt? alarm( arr[0] ); // undefiniert! keine Elemente. alarm( arr.length ); // Länge 2
Um solche Überraschungen zu vermeiden, verwenden wir normalerweise eckige Klammern, es sei denn, wir wissen wirklich, was wir tun.
Arrays können Elemente enthalten, die auch Arrays sind. Wir können es für mehrdimensionale Arrays verwenden, zum Beispiel zum Speichern von Matrizen:
sei Matrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]; alarm( Matrix[0][1] ); // 2, der zweite Wert des ersten inneren Arrays
Arrays verfügen über eine eigene Implementierung der toString -Methode, die eine durch Kommas getrennte Liste von Elementen zurückgibt.
Zum Beispiel:
sei arr = [1, 2, 3]; alarm( arr ); // 1,2,3 alarm( String(arr) === '1,2,3' ); // WAHR
Versuchen wir außerdem Folgendes:
alarm( [] + 1 ); // "1" alarm( [1] + 1 ); // „11“ alarm( [1,2] + 1 ); // "1,21"
Arrays verfügen weder über Symbol.toPrimitive noch über einen brauchbaren valueOf . Sie implementieren nur die toString Konvertierung, daher wird hier [] zu einer leeren Zeichenfolge, [1] zu "1" und [1,2] zu "1,2" .
Wenn der binäre Plus-Operator "+" etwas zu einer Zeichenfolge hinzufügt, wandelt er es ebenfalls in eine Zeichenfolge um, sodass der nächste Schritt wie folgt aussieht:
alarm( "" + 1 ); // "1" alarm( "1" + 1 ); // „11“ alarm( "1,2" + 1 ); // "1,21"
Arrays in JavaScript sollten im Gegensatz zu einigen anderen Programmiersprachen nicht mit dem Operator == verglichen werden.
Dieser Operator hat keine spezielle Behandlung für Arrays, er funktioniert mit ihnen wie mit allen anderen Objekten.
Erinnern wir uns an die Regeln:
Zwei Objekte sind nur dann gleich == wenn sie auf dasselbe Objekt verweisen.
Wenn eines der Argumente von == ein Objekt und das andere ein Primitiv ist, wird das Objekt in ein Primitiv konvertiert, wie im Kapitel Konvertierung von Objekten in Primitive erläutert.
…Mit Ausnahme von null und undefined , die einander gleich == sind und sonst nichts.
Der strikte Vergleich === ist noch einfacher, da er keine Typen konvertiert.
Wenn wir also Arrays mit == vergleichen, sind sie niemals gleich, es sei denn, wir vergleichen zwei Variablen, die genau auf dasselbe Array verweisen.
Zum Beispiel:
alarm( [] == [] ); // FALSCH alarm( [0] == [0] ); // FALSCH
Diese Arrays sind technisch gesehen unterschiedliche Objekte. Sie sind also nicht gleich. Der == Operator führt keinen Element-für-Element-Vergleich durch.
Der Vergleich mit Grundelementen kann ebenfalls zu scheinbar seltsamen Ergebnissen führen:
alarm( 0 == [] ); // WAHR
alarm('0' == [] ); // FALSCH Hier vergleichen wir in beiden Fällen ein Grundelement mit einem Array-Objekt. Daher wird das Array [] zu Vergleichszwecken in ein Primitiv konvertiert und zu einer leeren Zeichenfolge '' .
Anschließend geht der Vergleichsprozess mit den Grundelementen weiter, wie im Kapitel Typkonvertierungen beschrieben:
// nachdem [] in '' konvertiert wurde
alarm( 0 == '' ); // wahr, da '' in die Zahl 0 umgewandelt wird
alarm('0' == '' ); // false, keine Typkonvertierung, andere StringsWie vergleicht man also Arrays?
Das ist ganz einfach: Verwenden Sie nicht den == Operator. Vergleichen Sie sie stattdessen Element für Element in einer Schleife oder verwenden Sie Iterationsmethoden, die im nächsten Kapitel erläutert werden.
Ein Array ist eine besondere Art von Objekt, das zum Speichern und Verwalten geordneter Datenelemente geeignet ist.
Die Erklärung:
// eckige Klammern (üblich) let arr = [item1, item2...]; // neues Array (außergewöhnlich selten) let arr = new Array(item1, item2...);
Der Aufruf von new Array(number) erstellt ein Array mit der angegebenen Länge, jedoch ohne Elemente.
Die length ist die Länge des Arrays, genauer gesagt sein letzter numerischer Index plus eins. Es wird durch Array-Methoden automatisch angepasst.
Wenn wir length manuell verkürzen, wird das Array abgeschnitten.
Die Elemente abrufen:
Wir können ein Element anhand seines Index ermitteln, z. B. arr[0]
Wir können auch die Methode at(i) verwenden, die negative Indizes zulässt. Bei negativen Werten von i wird vom Ende des Arrays zurückgegangen. Wenn i >= 0 , funktioniert es genauso wie arr[i] .
Wir können ein Array als Deque mit den folgenden Operationen verwenden:
push(...items) fügt am Ende items hinzu.
pop() entfernt das Element vom Ende und gibt es zurück.
shift() entfernt das Element vom Anfang und gibt es zurück.
unshift(...items) fügt items am Anfang hinzu.
So durchlaufen Sie die Elemente des Arrays:
for (let i=0; i<arr.length; i++) – funktioniert am schnellsten, kompatibel mit alten Browsern.
for (let item of arr) – die moderne Syntax nur für Elemente,
for (let i in arr) – niemals verwenden.
Verwenden Sie zum Vergleichen von Arrays nicht den == Operator (sowie > , < und andere), da diese keine spezielle Behandlung für Arrays haben. Sie behandeln sie wie beliebige Objekte, und das ist nicht das, was wir normalerweise wollen.
Stattdessen können Sie for..of Schleife verwenden, um Arrays Element für Element zu vergleichen.
Wir werden mit Arrays fortfahren und im nächsten Kapitel Array-Methoden weitere Methoden zum Hinzufügen, Entfernen, Extrahieren von Elementen und Sortieren von Arrays untersuchen.
Wichtigkeit: 3
Was wird dieser Code zeigen?
let Fruits = [„Äpfel“, „Birne“, „Orange“];
// einen neuen Wert in die „Kopie“ schieben
let shoppingCart = Früchte;
einkaufenCart.push("Banana");
// Was steckt in Früchten?
Alert(fruits.length); // ?
Das Ergebnis ist 4 :
let Fruits = [„Äpfel“, „Birne“, „Orange“];
let shoppingCart = Früchte;
einkaufenCart.push("Banana");
Alert(fruits.length); // 4 Das liegt daran, dass Arrays Objekte sind. Daher sind sowohl shoppingCart als auch fruits Verweise auf dasselbe Array.
Wichtigkeit: 5
Probieren wir 5 Array-Operationen aus.
Erstellen Sie eine Reihe styles mit den Elementen „Jazz“ und „Blues“.
Hängen Sie am Ende „Rock-n-Roll“ an.
Ersetzen Sie den Wert in der Mitte durch „Classics“. Ihr Code zum Ermitteln des Mittelwerts sollte für alle Arrays mit ungerader Länge funktionieren.
Entfernen Sie den ersten Wert des Arrays und zeigen Sie ihn an.
Stellen Sie dem Array Rap und Reggae voran.
Das Array im Prozess:
Jazz, Blues Jazz, Blues, Rock'n'Roll Jazz, Klassik, Rock'n'Roll Klassiker, Rock'n'Roll Rap, Reggae, Klassiker, Rock'n'Roll
let Styles = ["Jazz", "Blues"];
styles.push("Rock-n-Roll");
styles[Math.floor((styles.length - 1) / 2)] = "Classics";
alarm(styles.shift());
styles.unshift("Rap", "Reggae");Wichtigkeit: 5
Was ist das Ergebnis? Warum?
let arr = ["a", "b"];
arr.push(function() {
alarm( this );
});
arr[2](); // ?
Der Aufruf arr[2]() ist syntaktisch die gute alte obj[method]() , in der Rolle von obj haben wir arr und in der Rolle von method haben wir 2 .
Wir haben also einen Aufruf der Funktion arr[2] als Objektmethode. Natürlich empfängt es this Referenzierung auf das Objekt arr und gibt das Array aus:
let arr = ["a", "b"];
arr.push(function() {
alarm( this );
})
arr[2](); // a,b,function(){...}Das Array hat drei Werte: Ursprünglich hatte es zwei plus die Funktion.
Wichtigkeit: 4
Schreiben Sie die Funktion sumInput() die:
Fragt den Benutzer mithilfe prompt nach Werten und speichert die Werte im Array.
Beendet die Abfrage, wenn der Benutzer einen nicht numerischen Wert oder eine leere Zeichenfolge eingibt oder auf „Abbrechen“ drückt.
Berechnet die Summe der Array-Elemente und gibt sie zurück.
PS Eine Null 0 ist eine gültige Zahl, bitte stoppen Sie die Eingabe nicht bei Null.
Führen Sie die Demo aus
Bitte beachten Sie das subtile, aber wichtige Detail der Lösung. Wir wandeln value nicht sofort nach prompt in eine Zahl um, da wir nach value = +value nicht in der Lage wären, eine leere Zeichenfolge (Stoppzeichen) von der Null (gültige Zahl) zu unterscheiden. Wir machen es stattdessen später.
Funktion sumInput() {
let zahlen = [];
while (wahr) {
let value = prompt("Eine Zahl bitte?", 0);
// Sollen wir absagen?
if (value === "" || value === null || !isFinite(value)) break;
zahlen.push(+value);
}
sei Summe = 0;
für (sei es eine Anzahl von Zahlen) {
Summe += Zahl;
}
Rückgabesumme;
}
alarm( sumInput() );Wichtigkeit: 2
Die Eingabe ist ein Array von Zahlen, z. B. arr = [1, -2, 3, 4, -9, 6] .
Die Aufgabe besteht darin, das zusammenhängende Unterarray von arr mit der maximalen Summe an Elementen zu finden.
Schreiben Sie die Funktion getMaxSubSum(arr) die diese Summe zurückgibt.
Zum Beispiel:
getMaxSubSum([-1, 2, 3, -9]) == 5 (die Summe der hervorgehobenen Elemente) getMaxSubSum([2, -1, 2, 3, -9]) == 6 getMaxSubSum([-1, 2, 3, -9, 11]) == 11 getMaxSubSum([-2, -1, 1, 2]) == 3 getMaxSubSum([100, -9, 2, -3, 5]) == 100 getMaxSubSum([1, 2, 3]) == 6 (alle nehmen)
Wenn alle Elemente negativ sind, bedeutet das, dass wir keines nehmen (das Unterarray ist leer), sodass die Summe Null ist:
getMaxSubSum([-1, -2, -3]) = 0
Versuchen Sie bitte, sich eine schnelle Lösung auszudenken: O(n 2 ) oder sogar O(n), wenn Sie können.
Öffnen Sie eine Sandbox mit Tests.
Wir können alle möglichen Teilsummen berechnen.
Der einfachste Weg besteht darin, jedes Element zu nehmen und ausgehend von ihm die Summen aller Subarrays zu berechnen.
Zum Beispiel für [-1, 2, 3, -9, 11] :
// Beginnend bei -1: -1 -1 + 2 -1 + 2 + 3 -1 + 2 + 3 + (-9) -1 + 2 + 3 + (-9) + 11 // Ab 2: 2 2 + 3 2 + 3 + (-9) 2 + 3 + (-9) + 11 // Ab 3: 3 3 + (-9) 3 + (-9) + 11 // Ab -9 -9 -9 + 11 // Ab 11 11
Der Code ist eigentlich eine verschachtelte Schleife: Die externe Schleife über Array-Elemente und die internen Zählungen beginnen mit dem aktuellen Element.
Funktion getMaxSubSum(arr) {
sei maxSum = 0; // wenn wir keine Elemente nehmen, wird Null zurückgegeben
for (let i = 0; i < arr.length; i++) {
sei sumFixedStart = 0;
for (let j = i; j < arr.length; j++) {
sumFixedStart += arr[j];
maxSum = Math.max(maxSum, sumFixedStart);
}
}
return maxSum;
}
alarm( getMaxSubSum([-1, 2, 3, -9]) ); // 5
alarm( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
alarm( getMaxSubSum([-2, -1, 1, 2]) ); // 3
alarm( getMaxSubSum([1, 2, 3]) ); // 6
alarm( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100Die Lösung hat eine zeitliche Komplexität von O(n 2 ). Mit anderen Worten: Wenn wir die Array-Größe verdoppeln, arbeitet der Algorithmus viermal länger.
Bei großen Arrays (1000, 10000 oder mehr Elemente) können solche Algorithmen zu erheblicher Trägheit führen.
Gehen wir das Array durch und behalten die aktuelle Teilsumme der Elemente in der Variablen s bei. Wenn s irgendwann negativ wird, dann weisen Sie s=0 zu. Das Maximum aller solcher s wird die Antwort sein.
Wenn die Beschreibung zu vage ist, sehen Sie sich bitte den Code an. Er ist kurz genug:
Funktion getMaxSubSum(arr) {
sei maxSum = 0;
sei partielle Summe = 0;
for (let item of arr) { // für jedes Element von arr
partielle Summe += Element; // füge es zu partialSum hinzu
maxSum = Math.max(maxSum, partielleSum); // Merke dir das Maximum
if (PartialSum < 0) PartialSum = 0; // Null, wenn negativ
}
return maxSum;
}
alarm( getMaxSubSum([-1, 2, 3, -9]) ); // 5
alarm( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
alarm( getMaxSubSum([-2, -1, 1, 2]) ); // 3
alarm( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100
alarm( getMaxSubSum([1, 2, 3]) ); // 6
alarm( getMaxSubSum([-1, -2, -3]) ); // 0Der Algorithmus erfordert genau einen Array-Durchlauf, daher beträgt die Zeitkomplexität O(n).
Nähere Informationen zum Algorithmus finden Sie hier: Maximum-Subarray-Problem. Wenn immer noch nicht klar ist, warum das funktioniert, dann verfolgen Sie bitte den Algorithmus anhand der Beispiele oben und sehen Sie, wie er funktioniert, das ist besser als alle Worte.
Öffnen Sie die Lösung mit Tests in einer Sandbox.