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 algorithmische Leistung 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ßartig geschrieben, aber ich habe im Moment keine Pläne für ein solches Interview.
Als IT-Ingenieur ist 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 Day69 "279. Perfect Squares" ab Null
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.
** Technischer Blog Gestartet! !! ** ** ** Ich denke, die Technologie wird über LetCode, Django, Nuxt usw. schreiben. ** Dies ist schneller zu aktualisieren **, vielen Dank für Ihre Mitarbeit!
295. Find Median from Data Stream
Der Schwierigkeitsgrad ist Schwer. Auszug aus den 100 beliebtesten Fragen.
Das Problem ist die Implementierung der Klasse.
Der Medianwert ist der Mittelwert der geordneten Liste von Ganzzahlen. Wenn die Listengröße gerade ist, gibt es keine Zwischenwerte. Daher ist der Medianwert der Durchschnitt der beiden Zwischenwerte.
Zum Beispiel
[2,3,4]
Median ist 3
[2,3]
Der Median ist (2 + 3) / 2 = 2,5
Entwerfen Sie eine Datenstruktur, die die folgenden zwei Vorgänge unterstützt:
void addNum (int num) - Fügt der Datenstruktur einen ganzzahligen Wert aus dem Datenstrom hinzu.
double findMedian () - Gibt den Medianwert aller vorherigen Elemente zurück.
Example:
addNum(1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2
Wenn man bedenkt, dass es sich um den Medianwert und nicht um den Durchschnittswert handelt, scheint die Implementierung dieses Teils ein sehr wichtiger Teil zu sein.
Der andere Teil scheint für jeden, der dieses Problem lösen möchte, nicht so schwer zu sein.
class MedianFinder:
def __init__(self):
"""
initialize your data structure here.
"""
self.sorted_list = []
self.length = 0
def addNum(self, num: int) -> None:
low,high = 0,self.length-1
while high >= low:
mid = (high+low)//2
if self.sorted_list[mid] > num:
high = mid-1
else:
low = mid+1
self.sorted_list.insert(low,num)
self.length += 1
def findMedian(self) -> float:
if self.length % 2 == 0:
median = self.length//2
return (self.sorted_list[median]+self.sorted_list[median-1])/2.0
else:
return self.sorted_list[self.length//2]
# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()
# Runtime: 296 ms, faster than 30.86% of Python3 online submissions for Find Median from Data Stream.
# Memory Usage: 25.2 MB, less than 18.26% of Python3 online submissions for Find Median from Data Stream.
Ich habe beschlossen, die Dichotomie im Teil "addNum" zu verwenden und die Länge der Liste zu speichern, damit ich mit dieser Länge in "findMedian" reibungslos schreiben kann. Rückblickend fühlt es sich wie eine Reihe grundlegender Dinge an.
Sie können es schreiben, wenn Sie sich genau an jedes Wissen erinnern, aber es ist ein Typ, der in das Dilemma gerät, dass Geschwindigkeit nicht so stark herauskommt. In Bezug auf die Verbesserung von hier aus können Sie dem folgenden Antwortbeispiel entnehmen, dass der Dichotomieteil etwas schwerer geworden ist.
from heapq import *
class MedianFinder:
def __init__(self):
self.heaps = [], []
def addNum(self, num):
small, large = self.heaps
heappush(small, -heappushpop(large, num))
if len(large) < len(small):
heappush(large, -heappop(small))
def findMedian(self):
small, large = self.heaps
if len(large) > len(small):
return float(large[0])
return (large[0] - small[0]) / 2.0
# Runtime: 200 ms, faster than 82.39% of Python3 online submissions for Find Median from Data Stream.
# Memory Usage: 24.6 MB, less than 98.20% of Python3 online submissions for Find Median from Data Stream.
https://leetcode.com/problems/find-median-from-data-stream/discuss/74044/Very-Short-O(log-n)-%2B-O(1)
Sie haben zwei Listen erstellt und jede als Haufen behandelt, um das Gewicht zu reduzieren.
Ich wünschte, ich hätte die Möglichkeit, die vorherige Antwort wie folgt zu konvertieren, aber diesmal habe ich sie aus der Diskussion gezogen, weil ich sie nicht verstanden habe.
Das war's für diese Zeit. Danke für deine harte Arbeit.
Recommended Posts