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.
Als Gegenmaßnahme scheint eine Website namens Let Code Maßnahmen zu ergreifen.
Eine Site, die algorithmische Leistung trainiert, die Codierungstests standhält, über die früh gesprochen wird.
Ich denke, es ist besser, die Algorithmuskraft eines Menschen zu haben, also werde ich das Problem unregelmäßig lösen und die Methode, die ich damals dachte, als Memo aufschreiben.
Letztes Mal Leet Code Day12 ab Null "617. Zwei binäre Bäume zusammenführen"
Grundsätzlich möchte ich die einfache Akzeptanz in absteigender Reihenfolge lösen.
Der Schwierigkeitsgrad ist Mittel. In letzter Zeit scheint es viele gute Fragen zu geben, da ich bevorzugt aus den Top 100 Liked Questions auswähle. Natürlich ist es vorteilhaft, mathematische Kenntnisse zu haben, aber es ist sehr interessant, weil es viele Probleme gibt, die zur richtigen Antwort führen, wenn Sie sorgfältig überlegen, auch wenn Sie sie nicht haben.
Eine natürliche Zahl "num" wird angegeben. Berechnet die Anzahl der Einsen in der binären Darstellung aller Zahlen i im Bereich "0 ≤ i ≤ num" und gibt sie als Array zurück.
Denken Sie, dass dieses Problem nur eine Problemstellung ist? Es wird sein. Schauen wir uns ein Beispiel an.
Example 1:
Input: 2 Output: [0,1,1]
In diesem Fall wird 2 als "num" angegeben. Das Konvertieren von [0,1,2] in eine Binärzahl ergibt [0,1,10], das Zählen der Anzahl von Einsen in jedem dieser Werte ergibt "011" und das Konvertieren in ein Array ergibt [0,1,10]. 1]. Gibt schließlich dieses Array zurück.
Example 2:
Input: 5 Output: [0,1,1,2,1,2]
In diesem Fall wird 5 als "num" angegeben. Das Konvertieren von [0,1,2,3,4,5] in Binärzahlen ergibt [0,1,10,11,100,101], und das Zählen der in diesen Werten enthaltenen Einsen ergibt "011212", [0, 1,1,2,1,2].
Bereiten Sie zunächst eine Liste für die Rückgabe ans vor und erwägen Sie die Verwendung einer for-Anweisung, die Werte von 1 bis num + 1 wiederholt.
Es führt eine binäre Konvertierung für jede Zahl durch, fügt der Liste eine Anzahl von 1 hinzu und gibt schließlich das erste vorbereitete "ans" zurück. Das vielleicht wichtigste dieser Probleme ist ein Algorithmus, der auch eine binäre Konvertierung durchführt und die Zahl 1 zählt.
Wenn Sie das i-te von "ans" durch 2 teilen und diesen Wert zum Rest addieren, wenn i durch 2 geteilt wird, wird es gut konvertiert. Der Grund ist, dass wenn der Wert von "num" ungerade ist, die letzte Ziffer 1 ist und 1 durch Rechtsverschiebung gelöscht wird. Weil es eines von wird.
Betrachten wir dieses Beispiel zum Beispiel, wenn num 4 ist,
ans[4/2]+(4%2)
Es wird sein. In diesem Fall ist es die Sekunde von "ans [0,1,1,2]", dh 1. Die 1 und 0, der Rest von (4% 2), werden hinzugefügt, und 1, die die Anzahl der Einsen von '100' ist, wenn 4 in Binär konvertiert wird, wird der Liste hinzugefügt.
Ich schrieb wie folgt.
class Solution:
def countBits(self, num: int) -> List[int]:
ans = [0]
for i in range(1,num+1):
ans.append(ans[i//2] + (i%2))
return ans
# Runtime: 84 ms, faster than 72.90% of Python3 online submissions for Counting Bits.
# Memory Usage: 20.7 MB, less than 5.00% of Python3 online submissions for Counting Bits.
Ich habe lange über dieses Problem nachgedacht. Ich möchte schneller eine Lösung finden.
Recommended Posts