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 Day 42 "2. Addiere zwei Zahlen" ab Null
Im Moment löse ich das Medium mit den 100 beliebtesten Fragen. Easy wurde gelöst. Wenn Sie interessiert sind, gehen Sie bitte zum Tisch.
Twitter Ich mache es.
5. Longest Palindromic Substring
Der Schwierigkeitsgrad ist Mittel. Auszug aus den 100 beliebtesten Fragen.
Entwerfen Sie anhand der Zeichenfolge s einen Algorithmus, der die längste Wiederholung in dieser Zeichenfolge findet (je nachdem, aus welcher Sie lesen).
Input: "babad" Output: "bab" Note: "aba" is also a valid answer.
Input: "cbbd" Output: "bb"
Vorher gelöst Leet Code Tag 30 ab Null "234. Palindrome Linked List" Es ist ähnlich, aber beim letzten Mal wurde nur überprüft, ob die angegebene verkettete Liste ein Zirkular war, aber diesmal wurde die längste als Zeichenfolge daraus extrahiert. Es ist ein bisschen kompliziert.
Die orthodoxe Art, über das Problem der Rezitation nachzudenken, besteht jedoch darin, das ursprüngliche Element mit dem zu vergleichen, das das Element wie beim letzten Mal verkehrt herum leckt, und wenn es übereinstimmt, den Vergleich fortzusetzen, andernfalls Es wäre, diese Zeichenketten in der vorbereiteten Zeichenkette zu speichern.
Zum Beispiel das "babad" als Beispiel
babad
Wann
dabab
Von vorne zusammen lecken und das längere Element im Vergleich zur Länge der ursprünglich gespeicherten Zeichenfolge vom ersten "a" bis zum zweiten "a", das übereinstimmt, und schließlich belassen Es scheint, dass es gelöst werden kann, indem die Zeichenfolge an zurückgegeben wird.
Die Frage ist, wie man festlegt, wie dieses Element geleckt wird, aber die Inversion kann einfach mit dem Slice [:: -1] implementiert werden.
Es wird also O (N ^ 2) sein, aber lösen wir es mit der groben Technik, die for-Anweisung zweimal zu drehen.
class Solution:
def longestPalindrome(self, s: str) -> str:
if not s:
return ""
for i in range(len(s),0,-1):
for j in range(len(s)-i+1):
if s[j:i+j] == s[j:i+j][::-1]:
return s[j:i+j]
# Runtime: 4884 ms, faster than 25.37% of Python3 online submissions for Longest Palindromic Substring.
# Memory Usage: 13.7 MB, less than 22.69% of Python3 online submissions for Longest Palindromic Substring.
Es ist zu spät ...
Einige Beispiele für wahnsinnig schnelle Antworten waren:
class Solution(object):
def longestPalindrome(self, s: str) -> str:
if len(s) < 2:
return s
start = 0
maxLen = 1
i = 0
while i < len(s):
l = i
r = i
while r < len(s) - 1 and s[r] == s[r+1]:
r += 1
i = r + 1
while r < len(s)-1 and l > 0 and s[r+1] == s[l-1]:
l -= 1
r += 1
if maxLen < r - l + 1:
start = l
maxLen = r - l + 1
return s[start: start + maxLen]
# Runtime: 116 ms, faster than 95.05% of Python3 online submissions for Longest Palindromic Substring.
# Memory Usage: 13.8 MB, less than 22.69% of Python3 online submissions for Longest Palindromic Substring.
https://leetcode.com/problems/longest-palindromic-substring/discuss/410963/Python-beats-93-solution-with-illustrations
Schlagen Sie schnell vor! !! !! !! !! Es gibt kein Ende für das, was Sie lernen müssen. sehr gut.
Das war's für diese Zeit. Danke für deine harte Arbeit.
Recommended Posts