Es scheint, dass Codierungstests in Ingenieurinterviews im Ausland durchgeführt werden, und in vielen Fällen besteht die Hauptsache darin, bestimmte Funktionen und Klassen entsprechend dem Thema zu implementieren.
Anscheinend ergreifen viele Ingenieure Maßnahmen auf der Website namens LetCode.
Es ist eine Site, die die Algorithmusleistung trainiert, die dem Codierungstest standhält, der in der frühen Geschichte durchgeführt wird, und es ist ein unvermeidlicher Weg für diejenigen, die eine Karriere bei einem ausländischen Technologieunternehmen aufbauen möchten.
Ich habe es groß geschrieben, aber ich habe im Moment keine Pläne für ein solches Interview.
Als IT-Ingenieur wäre es jedoch besser, die gleiche Algorithmusleistung wie eine Person zu haben. Daher möchte ich das Problem unregelmäßig lösen und die Methode, die ich damals dachte, als Memo aufschreiben.
Ich löse es mit Python3.
Letztes Mal Leet Code Day59 ab Null "1221. Teilen Sie einen String in ausgeglichene Strings"
Im Moment priorisiere ich das Medium der 100 beliebtesten Fragen. Easy wurde gelöst. Wenn Sie interessiert sind, gehen Sie bitte zum Tisch.
Twitter Ich mache es.
Artikel für ca. 2 Monate wurden gesammelt. Ich bin überrascht, dass es bisher so weitergegangen ist.
1481. Least Number of Unique Integers after K Removals
Der Schwierigkeitsgrad ist Mittel. Es ist ein ziemlich neues Problem, das kürzlich hinzugefügt wurde.
Das Problem ist das Array "arr" und die ganze Zahl "k" gegeben. Das Problem besteht darin, einen Algorithmus zu entwerfen, der die minimale Anzahl eindeutiger Ganzzahlen findet, nachdem Elemente im Wert von "k" aus dem Array entfernt wurden.
Es ist ein wenig verwirrend, also schauen wir uns ein Beispiel an.
Input: arr = [5,5,4], k = 1 Output: 1 Explanation: Remove the single 4, only 5 is left.
In diesem Beispiel ist ein Element nur "4" im Array. Also 4 löschen. Da das einzige verbleibende Element "5" ist, wird "5" so zurückgegeben, wie es ist.
Input: arr = [4,3,1,1,3,3,2], k = 3 Output: 2 Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.
Es wird beschlossen, "4" und "2" zu löschen, aber der verbleibende löscht entweder "1" oder "3". "1" oder "3" bleibt bestehen, aber die Länge der eindeutigen Nummer selbst beträgt "2", sodass sie zurückgegeben wird.
Dieses Mal geben wir eine Ganzzahl zurück, und egal wie wir mit dem Array umgehen, es hat keinen Einfluss auf die Antwort. Ich dachte, es wäre einfacher zu verstehen, wenn wir es früh sortieren würden. Wenn das Beispiel "arr = [4,3,1,1,3,3,2]", was würden Sie dann tun, wenn Sie wie "arr = [1,1,2,3,3,4]" sortieren? Es ist auf einen Blick klar, ob Sie es löschen sollten.
Nun, wenn ich es schnell schreibe, besteht das Problem dieses Mal darin, das gegebene "k" mit der Anzahl der Elemente zu vergleichen, und wenn "k" mehr als die Anzahl der Elemente ist, von "k" bis "k" + Subtrahieren Sie die Anzahl der Elemente und zählen Sie die Anzahl der Subtraktionen. Und schließlich können Sie die Anzahl der Subtraktionen von der Länge des ursprünglich sortierten Arrays subtrahieren.
Ich glaube jedoch nicht, dass ich ehrlich verstehen kann, selbst wenn dies geschrieben ist. Schauen wir uns also den tatsächlichen Code an.
import collections
class Solution:
def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
sorted_counts,removed_counts = sorted(Counter(arr).items(),key=lambda x: x[1]),0
for keys,values in sorted_counts:
if k >= values:
k -= values
removed_counts += 1
return len(sorted_counts) - removed_counts
# Runtime: 496 ms, faster than 92.08% of Python3 online submissions for Least Number of Unique Integers after K Removals.
# Memory Usage: 32.9 MB, less than 33.33% of Python3 online submissions for Least Number of Unique Integers after K Removals.
In Python gibt es eine praktische Bibliothek namens Counter of Collections. Daher ist es eine gute Idee, vorerst jede Zahl zu zählen.
Im Fall von Beispiel 1 wird es wie folgt sein.
Counter({5: 2, 4: 1})
Und wenn Sie dies nach dem Wert von "Schlüssel" sortieren, wird es wie folgt sein.
[(4, 1), (5, 2)]
Übrigens, wenn Sie nicht viel Python schreiben, werfen Sie einen kurzen Blick auf den Sortierteil.
sorted_counts = sorted(Counter(arr))
# [4,5]
Sie möchten vielleicht schreiben, aber in diesem Fall ist die Ausgabe "[4,5]" und die Anzahl ist erschöpft, also ist es NG.
Obwohl der Lambda-Ausdruck von Python herausgekommen ist,
Name=Lambda-Argument,Streit, ...:Formel
Sie können in Form von schreiben. In PEP8 wird jedoch empfohlen, den Lambda-Ausdruck als anonyme Funktion in Python zu schreiben. Diesmal folgt daraus.
Darüber hinaus wird diese Verwendung als Argument für "sortiert ()" verwendet. Sie kann jedoch basierend auf dem Ergebnis sortiert werden, indem auf jedes Element eine beliebige Funktion angewendet wird, indem ein Lambda-Ausdruck in "sortiert ()" verwendet wird. Dies dient dazu, diese Eigenschaft zu nutzen.
Natürlich können Sie eine Funktion mit def definieren und als key angeben, aber wenn Sie sie wie dieses Mal nur einmal verwenden, ist es einfacher, wie dieses Mal zu schreiben Kann schreiben.
Dieses Mal war das Problem neu, und wahrscheinlich, weil es nicht viele Befragte gab, hätten wir etwas schaffen können, das in Bezug auf die Geschwindigkeit nicht schlecht war.
Bis hierher für diese Zeit. Danke für deine harte Arbeit.
Recommended Posts