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 Day20 "134. Tankstelle" ab Null
Grundsätzlich möchte ich die einfache Akzeptanz in absteigender Reihenfolge lösen.
Twitter Ich mache es.
448. Find All Numbers Disappeared in an Array
Der Schwierigkeitsgrad ist einfach. Eine der 100 beliebtesten Fragen. Die einfachen Probleme in den Top 100 Liked Questions haben ebenfalls erheblich abgenommen.
Bei einem Array von ganzen Zahlen mit "1 ≤ a [i] ≤ n" (n ist die Größe des Arrays) erscheinen einige Elemente zweimal und andere einmal.
Suchen Sie alle Elemente, die in diesem Array nicht sichtbar sind.
Input: [4,3,2,7,8,2,3,1]
Output: [5,6]
Da die nicht vorhandenen Werte zwischen 1 und 8 5 und 6 sind, werden diese beiden zurückgegeben.
Das erste, was wir dieses Mal implementiert haben, ist, das Array zu sortieren, das sortierte Array mit dem ursprünglichen Array zu vergleichen und es dem Array hinzuzufügen, das einen nicht vorhandenen Wert zurückgibt.
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
num,ans = set(sorted(nums)),[]
for i in range(1,len(nums)+1):
if i not in num:
ans.append(i)
return ans
# Runtime: 464 ms, faster than 11.82% of Python3 online submissions for Find All Numbers Disappeared in an Array.
# Memory Usage: 23.7 MB, less than 7.14% of Python3 online submissions for Find All Numbers Disappeared in an Array.
Es ist jedoch nicht sehr schnell und spart nicht so viel Speicher. Also habe ich diesmal versucht, es woanders zu implementieren.
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
for num in nums:
ans = abs(num) - 1
if nums[ans] > 0:
nums[ans] *= -1
return [i+1 for i in range(len(nums)) if nums[i] > 0]
# Runtime: 380 ms, faster than 63.11% of Python3 online submissions for Find All Numbers Disappeared in an Array.
# Memory Usage: 21.5 MB, less than 17.86% of Python3 online submissions for Find All Numbers Disappeared in an Array.
Es hat sich ein wenig verbessert.
Letzterer erhält "abs", um den absoluten Wert zu erhalten, und wenn "nums [ans]" größer als Null ist, ersetzt "nums [ans]" den Wert, dem -1 in "nums [ans]" fehlt. ..
Schließlich schrieb ich es, indem ich die Länge der Zahlen in der Einschlussnotation abrief, i + 1 machte, wenn nums [i]> 0, und schließlich zurückkehrte.
Es ist interessant zu glauben, dass sich der Rechenaufwand aufgrund der einfachen Verarbeitung mit nur einer Schreibmethode stark ändert.
Wenn es eine gute Antwort gibt, werde ich sie hinzufügen.
Recommended Posts