Il semble que des tests de codage soient menés à l'étranger lors d'entretiens d'ingénieurs, et dans de nombreux cas, l'essentiel est d'implémenter des fonctions et des classes spécifiques en fonction du thème.
En guise de contre-mesure, il semble qu'un site appelé Let Code prendra des mesures.
Un site qui forme une puissance algorithmique capable de résister aux tests de codage dont on parle très tôt.
Je pense qu'il vaut mieux avoir la puissance de l'algorithme d'un être humain, donc je vais résoudre le problème de manière irrégulière et écrire la méthode que j'ai pensé à ce moment-là sous forme de mémo.
Table de codes Leet commençant à zéro
Dernière fois Leet Code Day 42 "2. Add Two Numbers" commençant à zéro
En ce moment, je résous le support des 100 questions les plus appréciées Easy a été résolu, donc si vous êtes intéressé, veuillez vous rendre à la table.
Twitter Je le fais.
5. Longest Palindromic Substring
Le niveau de difficulté est moyen. Extrait des 100 questions les plus appréciées.
Étant donné la chaîne s, concevez un algorithme qui trouve la plus longue répétition dans cette chaîne (celle que vous lirez sera la même).
Input: "babad" Output: "bab" Note: "aba" is also a valid answer.
Input: "cbbd" Output: "bb"
Résolu avant Leet Code Day 30 à partir de zéro "234. Palindrome Linked List" C'est similaire à cela, mais la dernière fois, il n'a vérifié que si la liste concaténée donnée était une circulaire, mais cette fois, elle a changé pour en extraire la plus longue. C'est un peu compliqué.
Cependant, la manière orthodoxe de penser le problème de la récitation est de comparer l'élément d'origine avec celui qui lèche l'élément à l'envers comme la dernière fois, et s'il correspond, continuez la comparaison, sinon Ce serait de sauvegarder ces chaînes de caractères dans la chaîne de caractères préparée.
Par exemple, le "" babad "" donné à titre d'exemple
babad
Quand
dabab
Léchage par l'avant, laissant l'élément le plus long par rapport à la longueur de la chaîne enregistrée à l'origine du premier «a» au deuxième «a» qui correspondent, et enfin Il semble que cela puisse être résolu en renvoyant la chaîne de caractères à.
La question est de savoir comment définir comment lécher cet élément, mais l'inversion peut facilement être implémentée avec la tranche [:: -1].
Donc, ce sera O (N ^ 2), mais résolvons-le avec la technique approximative de tourner deux fois l'instruction for.
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.
C'est trop tard ...
Voici quelques exemples de réponses incroyablement rapides:
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
Sugge vite! !! !! !! !! Il n'y a pas de fin à ce que vous devez étudier. très bon.
Alors c'est tout pour cette fois. Je vous remercie pour votre travail acharné.
Recommended Posts