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ß geschrieben, aber ich habe im Moment keine Pläne für ein solches Interview.
Als IT-Ingenieur wäre 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 Day 65 "560. Subarray-Summe gleich K" 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!
438. Find All Anagrams in a String
Der Schwierigkeitsgrad ist Mittel. Auszug aus den 100 beliebtesten Fragen.
Angesichts der Zeichenfolge "s" und der nicht leeren Zeichenfolge "p" besteht das Problem darin, alle Startindizes des Anagramms "p" in "s" zu finden.
Zeichenfolgen bestehen nur aus Kleinbuchstaben, und die Länge von "s" und "p" darf 20.100 nicht überschreiten.
Die Reihenfolge der Ausgabe spielt keine Rolle.
Example 1:
Input: s: "cbaebabacd" p: "abc"
Output: [0, 6]
Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:
Input: s: "abab" p: "ab"
Output: [0, 1, 2]
Explanation: The substring with start index = 0 is "ab", which is an anagram of "ab". The substring with start index = 1 is "ba", which is an anagram of "ab". The substring with start index = 2 is "ab", which is an anagram of "ab".
Sie müssen den Index des Starts des Anagramms bereinigen. Ein Algorithmus namens "Sliding Window" scheint als Lösung bekannt zu sein, und ich plane, einen separaten Artikel zu schreiben. Es ist ein Wort, das ich im Netzwerk gehört habe, aber ich habe es nie im Algorithmus gehört.
Was ich jedoch versucht habe, die Logik nachzuahmen, ist wie folgt
import collections
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
len_s,len_p,set_p,ans = len(s),len(p),Counter(p),[]
for i in range(len_s-len_p+1):
if Counter(s[i:i+len_p]) == set_p:
ans.append(i)
return ans
# Runtime: 7868 ms, faster than 7.31% of Python3 online submissions for Find All Anagrams in a String.
# Memory Usage: 14.8 MB, less than 69.94% of Python3 online submissions for Find All Anagrams in a String.
Es war so spät, dass ich mich fragte, was passiert war ...
Vorerst versuchte ich zu verstehen, indem ich mir die Diskussion ansah.
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
LS, LP, S, P, A = len(s), len(p), 0, 0, []
if LP > LS: return []
for i in range(LP): S, P = S + hash(s[i]), P + hash(p[i])
if S == P: A.append(0)
for i in range(LP, LS):
S += hash(s[i]) - hash(s[i-LP])
if S == P: A.append(i-LP+1)
return A
Dann ist die Antwort so. Wenn ich mir den Code anschaue, verwende ich eine Hashmap anstelle von "counter", und der Rest scheint sich nicht viel zu ändern.
Mit Blick auf die Geschwindigkeit vorerst ...
Runtime: 68 ms, faster than 99.89% of Python3 online submissions for Find All Anagrams in a String.
Memory Usage: 14.9 MB, less than 42.94% of Python3 online submissions for Find All Anagrams in a String.
！？
Es ist lächerlich schnell ...
Wenn Sie darüber nachdenken, ist es offensichtlich ineffizient, für jedes Element den Zähler zu drehen, nicht wahr?
Das jedes Mal alle Elemente mit einer for-Anweisung zu drehen und mit dic zurückzukehren, ist eine ziemlich schlechte Implementierungsmethode. Je mehr Elemente vorhanden sind, desto langsamer wird es dramatisch.
Wenn Sie sich die Diskussion ansehen, können Sie auf diese Art von Idee stoßen, daher ist es wichtig, genauer hinzuschauen.
Das war's für diese Zeit. Danke für deine harte Arbeit.
Recommended Posts