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 de mettre en œuvre 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 à des 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 Day24 à partir de zéro "21. Fusionner deux listes triées"
En gros, je voudrais résoudre l'acceptation facile par ordre décroissant.
Twitter Je le fais.
70. Climbing Stairs Le niveau de difficulté est facile. Extrait des 100 questions les plus appréciées.
Je pense que c'est un problème familier pour ceux qui ont passé l'examen du premier cycle du secondaire. En fait, il existe une solution très simple, mais je l'expliquerai dans la méthode de la solution.
Lorsque vous montez les escaliers, vous pouvez monter une ou deux marches.
Étant donné le nombre naturel n, veuillez répondre de combien de façons vous pouvez atteindre le sommet.
Example 1:
Input: 2 output: 2
Dans le cas de 2, il existe une méthode de montée de 2 marches d'affilée et une méthode de montée d'1 pas deux fois, donc 2 est retourné.
Example 2:
Input: 3 Output: 3
Dans le cas de 3, 3 est renvoyé car il existe trois méthodes: répéter un pas à la fois, monter un pas et monter deux marches, et monter deux marches et monter un pas.
En fait, c'est un problème avec la séquence de Fibonacci. Vous l'avez peut-être vu en étudiant le nombre de cas.
À propos, la séquence de nombres de Fibonacci est １,１,２,３,５,８,１３,２１,３４,５５, Et ainsi de suite, c'est une séquence de nombres dans laquelle la somme des deux nombres précédents devient le nombre suivant.
Considérons le cas où il y a 3 étapes comme dans l'exemple. Dans ce cas, cela dépend du cas à la première étape. Il y a une tendance à monter une ou deux marches. Si vous montez deux marches, vous aurez forcément une option car il ne reste plus qu'une marche. En revanche, si vous sélectionnez 1, il reste 2 étapes, c'est-à-dire 2 voies comme indiqué dans l'exemple. La somme de ces ajouts est la réponse pour chaque cas, et ceci est un exemple typique de la séquence de Fibonacci telle que décrite ci-dessus.
Essayez également d'autres numéros. Disons qu'il comporte 4 étapes.
Sélectionnez ensuite la première étape et la deuxième étape en premier. Le premier est le cas d'une étape, mais le reste est de 3 étapes. En d'autres termes, vous pouvez utiliser les 3 méthodes des 3 étapes précédentes telles quelles. Et dans le cas de 2 étapes, le reste est de 2 étapes. En d'autres termes, il y a deux manières. Il y a 3 façons + 2 façons, donc il y a 5 façons.
Si un pas est ajouté, il passera à 8, et s'il est augmenté d'un autre pas, il passera à 13 ... et ainsi de suite.
Une fois que vous avez compris la structure de cet ajout, tout ce que vous avez à faire est de coder la loi.
À titre d'exemple simple
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 1:
return n
num1, num2 = 0, 1
for i in range(n):
num1, num2 = num2, num1+num2
return num2
# Runtime: 32 ms, faster than 39.40% of Python3 online submissions for Climbing Stairs.
# Memory Usage: 13.7 MB, less than 5.97% of Python3 online submissions for Climbing Stairs.
C'est la solution générale. Cependant, quand j'ai regardé la discussion, il y avait un moyen plus rapide de l'écrire.
from functools import lru_cache
class Solution:
@lru_cache(None)
def climbStairs(self, n):
if n == 1:
return 1
elif n == 2:
return 2
else:
return self.climbStairs(n-1) + self.climbStairs(n-2)
# Runtime: 24 ms, faster than 91.08% of Python3 online submissions for Climbing Stairs.
# Memory Usage: 13.9 MB, less than 5.97% of Python3 online submissions for Climbing Stairs.
C'est vraiment rapide ...
Au fait, qu'est-ce que lru_cache?
Alors je l'ai tranquillement recherché dans le Document officiel.
@functools.lru_cache(user_function) @functools.lru_cache(maxsize=128, typed=False) Un décorateur qui enveloppe une fonction dans un objet appelable pour mémorandum et enregistre jusqu'à la taille maximale des appels récents. Vous pouvez gagner du temps lorsque vous appelez régulièrement des fonctions coûteuses ou des fonctions liées aux E / S avec les mêmes arguments.
Puisqu'un dictionnaire est utilisé pour mettre en cache les résultats, la position de la fonction et les arguments des mots clés doivent être hachables.
Si les modèles d'argument sont différents, ils sont considérés comme des appels différents et seront des entrées de cache distinctes. Par exemple, f (a = 1, b = 2) et f (b = 2, a = 1) ont un ordre différent d'arguments de mot-clé, ce qui donne deux entrées de cache distinctes. .....
Le cache LRU (utilisé le moins récemment) est le plus efficace lorsque le dernier appel est le plus susceptible d'être rappelé (par exemple, les articles les plus populaires sur le serveur de news ont tendance à changer quotidiennement). .. La limite de taille du cache garantit que le cache ne dépasse pas les limites des processus à long terme tels que les serveurs Web.
En général, le cache LRU ne doit être utilisé que lorsque vous souhaitez réutiliser la valeur précédemment calculée. Cela n'a donc pas de sens de mettre en cache les fonctions qui ont des effets secondaires, les fonctions qui vous obligent à créer un objet mutable séparé pour chaque appel et des fonctions impures comme time () et random ().
En d'autres termes, il semble que le résultat de la fonction appelée soit mis en cache à l'aide d'un dictionnaire, donc si le résultat en cache est appelé même avec le dernier appel, l'efficacité au moment de l'exécution augmentera.
Je ne le savais pas, donc j'ai beaucoup appris, mais il est important de voir la discussion.
Recommended Posts