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ß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 Day89 "62. Eindeutige Pfade" ab Null
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!
1011. Capacity To Ship Packages Within D Days Der Schwierigkeitsgrad ist Mittel. Dies ist ein Auszug aus Leet Code 60-Fragen, die ich zur Vorbereitung von Codierungsinterviews lösen möchte.
Das Problem ist, dass das Förderband Gepäck hat, das innerhalb von D Tagen von einem Hafen zum anderen transportiert werden muss. Die i-te Last auf dem Förderband hat ein Gewicht [i]. Das tägliche Laden von Gepäck auf ein Förderband auf ein Schiff (in der angegebenen Gewichtsreihenfolge) darf die maximale Gewichtskapazität des Schiffes nicht überschreiten. Gibt die Mindestgewichtskapazität des Schiffes zurück, mit der das gesamte Gepäck auf dem Förderband innerhalb von D Tagen versendet wird.
Example 1:
Input: weights = [1,2,3,4,5,6,7,8,9,10], D = 5 Output: 15 Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this: 1st day: 1, 2, 3, 4, 5 2nd day: 6, 7 3rd day: 8 4th day: 9 5th day: 10
Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.
Example 2:
Input: weights = [3,2,2,4,1,4], D = 3 Output: 6 Explanation: A ship capacity of 6 is the minimum to ship all the packages in 3 days like this: 1st day: 3, 2 2nd day: 2, 4 3rd day: 1, 4
Example 3:
Input: weights = [1,2,3,1,1], D = 4 Output: 3 Explanation: 1st day: 1 2nd day: 2 3rd day: 3 4th day: 1, 1
class Solution:
def shipWithinDays(self, weights: List[int], D: int) -> int:
min_num = max_num = 0
min_num = max(weights)
max_num = sum(weights)
while min_num < max_num:
mid = (min_num + max_num)//2
days = temp_weight = 0
for i in weights:
temp_weight += i
if temp_weight > mid:
days += 1
temp_weight = i
if days + 1 <= D:
max_num = mid
else:
min_num = mid+1
return min_num
# Runtime: 508 ms, faster than 92.24% of Python3 online submissions for Capacity To Ship Packages Within D Days.
# Memory Usage: 17.1 MB, less than 7.21% of Python3 online submissions for Capacity To Ship Packages Within D Days.
Ich dachte in einer zweiminütigen Suche darüber nach.
Der minimale Wert ist hier der maximale Wert in der Liste, und der maximale Wert ist der Gesamtwert in der Liste. Dies ist die Bedingung, da dies zu einer minimalen Belastbarkeit führt, indem jeder Wert erfasst, gespeichert und durch eine Dichotomie mit dem Zeitplan verglichen wird. Der Grund für diese beiden Werte ist, dass unabhängig davon, wie sich die Werte ändern, die Untergrenze der Tragfähigkeit der niedrigste Wert in der Liste ist und der Maximalwert der Tragfähigkeit die Summe der Liste ist. Umgekehrt denke ich, dass es viel einfacher sein wird, wenn Sie die unteren und oberen Grenzen festlegen können.
Für den Testfall in Beispiel 1 enthalten "min_num" und "max_num" 10 bzw. 55. Und während diese Beziehung "min_num <max_num" bleibt, wird der Zwischenwert "mid" in der bekannten Dichotomie verarbeitet.
Danach wird die Verarbeitung basierend auf der Beziehung zwischen "Tagen" und "D" angewendet, der Bereich wird stetig eingeengt und schließlich wird die minimale Belastbarkeit abgeleitet.
Ich fand es schwierig zu erklären und suchte nach einem leicht verständlichen Beispiel Video in Java erklären hätten. Die Sprache selbst ist Java, aber die Grundidee ist dieselbe. Wenn es in meiner Erklärung schwer zu verstehen ist, sollten Sie hier einen Blick darauf werfen.
Das war's für diese Zeit. Danke für deine harte Arbeit.
Recommended Posts