Ich habe Let Code gestartet, um meine Programmierkenntnisse zu verbessern. Ich werde das Grundproblem TwoSum in Ruby erklären.
Two Sum
Gibt ein Array von Ganzzahlen an und gibt ein Array von Indexkombinationen zurück, wobei die Summe der beiden Elemente der Zielwert ist.
nums = [2,7,11,15]
target = 9
Ist gegeben.
nums[0] + nums[1] = 2+7 = 9
Damit
[0, 1]
Kehrt zurück.
** Ziel ist es, eine Methode in Ruby zu schreiben, die die oben genannten Anforderungen erfüllt. ** ** **
Brute Force bedeutet auf Japanisch "gezwungen". Mit anderen Worten, lösen Sie ohne nachzudenken.
# @param {Integer[]}nums Array von ganzen Zahlen
# @param {Integer}Ziel-Ganzzahl
# @return {Integer[]}Array von ganzen Zahlen
def two_sum(nums, target)
(0..nums.length-1).each do |i|
(i+1..nums.length-1).each do |j|
return [i, j] if nums[i] + nums[j] == target #Überprüfen Sie, ob der Zielwert erreicht ist
end
end
end
Basierend auf einem bestimmten Element werden wir danach nach den Elementen suchen, um zu sehen, ob die Summe zum Zielwert wird.
Das Senden dieses Codes führt zu folgenden Ergebnissen:
Runtime : 4656 ms(durchschnittlich)
Memory : 9.6 MB(durchschnittlich)
Der Durchschnitt liegt ungefähr darüber, aber gelegentlich ist es ein Zeitlimit. (Als Vorlage heraus)
Dies wird im Durchschnitt durch "jeweils" n-mal x n-1-mal berechnet, sodass die Berechnungsreihenfolge durch * O * ($ n ^ 2 $) angegeben wird. Das heißt, je größer die Anzahl der Elemente ist, desto mehr Zeit wird als quadratische Funktion benötigt.
Es ist effizienter, nach einem Komplement zu suchen, das "Zielwertelement 1" ist, als nach einem Element zu suchen, dessen Summe der Zielwert ist. Dort wird Hash verwendet.
# @param {Integer[]}nums Array von ganzen Zahlen
# @param {Integer}Ziel-Ganzzahl
# @return {Integer[]}Array von ganzen Zahlen
def two_sum(nums, target)
hash = {}
(0..nums.length-1).each do |i|
hash.store(nums[i], i) #Hash initialisieren
end
(0..nums.length-1).each do |i|
complement = target - nums[i] #Bereiten Sie eine Ergänzung vor
return [i, hash.fetch(complement)] if hash.has_key?(complement) && hash.fetch(complement) != i #Ergänzende Prüfung
end
end
Bereiten Sie einen Hash im Voraus vor und suchen Sie nach einem Wert, der eine Ergänzung darstellt.
Auf diese Weise wird die Berechnung von n mal x n-1 mal durch "jeder" nur n mal. Daher lautet die Reihenfolge der Berechnungsbeträge * O * ($ n $). Und wenn Sie diesen Code einreichen, lautet das Ergebnis:
Runtime : 43 ms(durchschnittlich)
Memory : 10.2 MB(durchschnittlich)
Es verbrauchte etwas mehr Speicher, war aber schrecklich schneller.
Dieses Mal gibt es auch eine Technik, die denselben Hash verwendet. Es wird in einem Scan abgeschlossen.
# @param {Integer[]}nums Array von ganzen Zahlen
# @param {Integer}Ziel-Ganzzahl
# @return {Integer[]}Array von ganzen Zahlen
def two_sum(nums, target)
hash = {}
(0..nums.length-1).each do |i|
complement = target - nums[i]
return [hash.fetch(complement), i] if hash.has_key?(complement) #Ergänzende Prüfung
hash.store(nums[i], i) #Hinzugefügt, da das Komplement nicht vorhanden war
end
Die Menge an Code wurde reduziert, aber das Lesen ist schwieriger geworden. Dies ist eine Methode zum Hinzufügen von Elementen, wenn die Elemente, die die Bedingungen erfüllen, nicht gefunden werden. Der Speicherplatz kann ein wenig reduziert werden, da Elemente in einem Scan hinzugefügt und durchsucht werden. In ähnlicher Weise lautet die berechnete Betragsreihenfolge * O * ($ n $) und das übermittelte Ergebnis lautet wie folgt.
Runtime : 48 ms(durchschnittlich)
Memory : 9.9 MB(durchschnittlich)
Es ist etwas langsamer, benötigt aber weniger Speicher. Welche Methode besser ist als ** Lösung 2 **, hängt von der Situation ab. Ich denke, es ist klar, wie gut die Hash-Methode im Vergleich zu ** Lösung 1 ** ist! Da die Anzahl der Versuche jeweils 7 beträgt, ist die Genauigkeit des Durchschnittswerts nicht hoch, aber dies geht aus diesem Ergebnis hervor.
Ich erklärte Two Sum, das ist das Grundproblem von Leet Code. Wir haben auch festgestellt, dass die Ausführungszeit durch eine geeignete Lösung erheblich verkürzt werden kann. Ich glaube, ich habe viel gelernt, indem ich dieses eine Problem richtig gelöst habe. Ich möchte fortfahren Let Code ...
Recommended Posts