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.
Apparemment, de nombreux ingénieurs prennent des mesures sur le site appelé LetCode.
C'est un site qui forme la puissance de l'algorithme qui peut résister au test de codage effectué au début, et c'est un chemin inévitable pour ceux qui veulent faire carrière dans une entreprise de technologie à l'étranger.
Je l'ai écrit en grand, mais je n'ai pas l'intention d'avoir une telle interview pour le moment.
Cependant, en tant qu'ingénieur informatique, il serait préférable d'avoir le même niveau de puissance d'algorithme qu'une personne, alors j'aimerais résoudre le problème de manière irrégulière et écrire la méthode que je pensais à ce moment-là sous forme de mémo.
Je le résolve avec Python3.
Table de codes Leet commençant à zéro
Dernière fois Leet Code Day 65 "560. Subarray Sum Equals K" à partir de zéro
À l'heure actuelle, je donne la priorité au moyen 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.
** Blog technique Commencé! !! ** ** Je pense que la technologie écrira sur LetCode, Django, Nuxt, etc. ** C'est plus rapide à mettre à jour **, merci pour votre coopération!
438. Find All Anagrams in a String
Le niveau de difficulté est moyen. Extrait des 100 questions les plus appréciées.
Étant donné la chaîne «s» et la chaîne non vide «p», le problème est de trouver tous les index de début de l'anagramme du «p» dans le «s».
Les chaînes se composent uniquement de lettres minuscules et les longueurs «s» et «p» ne doivent pas dépasser 20 100.
L'ordre de sortie n'a pas d'importance.
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".
Vous devez nettoyer l'index du début de l'anagramme. Un algorithme appelé «Sliding Window» semble être une solution réputée, et je prévois d'écrire un article séparé. C'est un mot que j'ai entendu sur le réseau, mais je ne l'ai jamais entendu sur l'algorithme.
Cependant, ce que j'ai essayé d'imiter la logique est la suivante
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.
Il était si tard que je me suis demandé ce qui s'était passé ...
Pour le moment, j'ai essayé de comprendre en regardant la discussion.
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
Alors la réponse est comme ça.
En regardant le code, j'utilise un hashmap au lieu de counter, et le reste ne semble pas beaucoup changer.
En regardant la vitesse pour le moment ...
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.
！？
C'est ridiculement rapide ...
Si vous y réfléchissez, tourner Counter pour chaque élément est évidemment inefficace, n'est-ce pas?
Tourner tous les éléments à chaque fois avec une instruction for et retourner avec dic est une méthode d'implémentation plutôt mauvaise car plus il y a d'éléments, plus elle devient dramatiquement lente.
Cependant, je n'ai pas eu l'idée de le mettre dans HashMap ... Si vous regardez la discussion, vous pouvez rencontrer ce genre d'idée, il est donc important de regarder de plus près.
Alors c'est tout pour cette fois. Je vous remercie pour votre travail acharné.
Recommended Posts