K-Element-Muster in LeetCode verstehen: Die Grundlagen (Teil 1)

Endlich verstehe ich! Der beste Weg, LeetCode zu lernen, besteht nicht darin, ein Problem nach dem anderen durchzugehen und manchmal eine ganze Stunde in Anspruch zu nehmen, um es ineffizient zu lösen. Der Schlüssel zur Beherrschung von LeetCode liegt im Studium von Mustern. Lasst uns ein gemeinsames studieren!

Interviewer fragen gerne nach dem Finden, Verwalten oder Bearbeiten von K-Elementen in einem String oder Array. Zuerst dachte ich, jedes Problem sei völlig anders, aber dann erkannte ich die Zusammenhänge. Lassen Sie mich Ihnen zeigen, was ich mit zwei Problemen meine, die mir wirklich geholfen haben, dieses Muster zu verstehen.

Aufgabe 1: Finden Sie die Teilfolge der Länge K mit der größten Summe

Dies ist technisch gesehen eine „einfache“ Frage (die nur von einem Unternehmen gestellt wird), aber Sie lernen so viel darüber, wie Sie über diese K-Element-Probleme nachdenken sollten!

Was sie fragen

Sie erhalten ein Array von Zahlen und einen Wert k, und Sie müssen k Zahlen aus dem Array finden, die zusammen die größtmögliche Summe ergeben. ABER (und das ist der Teil, der mich zuerst gestolpert hat), man muss die Zahlen in ihrer ursprünglichen Reihenfolge behalten!

Beispiel:

Oh! Das hier ist schwieriger:

Ok, ich verstehe

Zuerst dachte ich: „Nimm einfach die k-größten Zahlen, fertig!“ Aber nein – diese Bestellanforderung ändert alles. Das hat endlich Klick gemacht:

1. Wir müssen uns merken, wo jede Zahl herkommt, oder? Also Ich dachte: „Ich sollte jede Zahl mit ihr verknüpfen.“ Position?"

1. Dann können wir diese Paare nach den Werten sortieren (das ist der erste Zahl in jedem Paar), aber wir behalten den Überblick woher sie kamen (das ist die zweite Zahl)!

1. Jetzt kommt der coole Teil – wir brauchen nur k davon, also schnapp dir die erste k Paare und behalte einfach ihre Positionen:

1. Gehen Sie abschließend durch das ursprüngliche Array und behalten Sie es bei Zahlen, deren Positionen in unserem Set liegen:

Hier ist der Code

2: K-tes größtes Element in einem Stream

Okay, dieses Problem wurde auch als „einfach“ bezeichnet (auf Nachfrage von fünf Unternehmen), aber dieses Problem war für mich verwirrender als alle schwierigeren K-ten-Elemente-Probleme.

Was sie fragen

Stellen Sie sich vor, Sie arbeiten an einer Universität und Studenten reichen ständig Testergebnisse ein. Ihre Aufgabe ist es, jederzeit die k-thöchste Punktzahl zu kennen. Es kommen ständig neue Ergebnisse hinzu, und Sie müssen den Überblick behalten.

Sie geben dir K und einige Anfangswerte, dann werfen sie dir immer wieder neue Punkte zu und wollen jedes Mal den k-höchsten Wert wissen. Schauen wir uns ein Beispiel an:

Ok, ich glaube, ich verstehe

Zuerst habe ich jedes Mal versucht, das gesamte Array zu sortieren, wenn eine neue Partitur einging, aber ich weiß, dass das Sortieren ineffizient sein kann. Dann dachte ich, warum behalte ich den Überblick über alle Ergebnisse, wenn es mir nur um die Top-K geht?

So habe ich es aufgeschlüsselt:

1. Sortieren Sie zunächst die Anfangswerte und behalten Sie nur das oberste k:

1. Wenn jetzt eine neue Partitur eintrifft:

Wenn es kleiner als unsere k-thöchste (erste Zahl) ist, ignorieren Sie es
Wenn es größer ist, gehört es irgendwo in unsere Liste

Das passiert bei jedem Hinzufügen:

Der Kodex

Warum diese beiden Probleme miteinander verbunden sind

Beide Probleme haben mir etwas sehr Wichtiges über den Umgang mit k-Elementen beigebracht:

• Erstes Problem: Manchmal muss man nachverfolgen, wo sich Elemente befinden kam von
• Zweites Problem: Manchmal müssen Sie nur k Elemente behalten herum

Bei diesen K-Element-Problemen geht es darum, geschickt mit den Informationen umzugehen, die man behält und was man wegwirft.
Das nächste Mal werden wir uns zwei weitere K-Element-Probleme ansehen, die auf dieser Idee aufbauen. Ich hoffe, dass Sie am Ende ein Muster erkennen und diese Art von Problemen weniger beängstigend erscheinen!

Das obige ist der detaillierte Inhalt vonK-Element-Muster in LeetCode verstehen: Die Grundlagen (Teil 1). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!