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.
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 à l'époque sous forme de mémo.
Je le résolve avec Python3.
Table de codes Leet commençant à zéro
Dernière fois Leet Code Day68 à partir de zéro "709. En minuscules"
À 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!
279. Perfect Squares Le niveau de difficulté est moyen. Extrait des 100 questions les plus appréciées.
Étant donné un entier positif n, le problème est de trouver le nombre minimum de carrés parfaits qui s'additionnent à n (par exemple 1, 4, 9, 16, ...).
Example 1:
Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4.
Example 2:
Input: n = 13 Output: 2 Explanation: 13 = 4 + 9.
class Solution:
def numSquares(self, n: int) -> int:
dp = [i for i in range(n+1)]
for i in range(2,n+1):
for j in range(1,int(i ** 0.5)+1):
dp[i] = min(dp[i],dp[i-j*j]+1)
return dp[n]
# Runtime: 4608 ms, faster than 39.65% of Python3 online submissions for Perfect Squares.
# Memory Usage: 14 MB, less than 60.54% of Python3 online submissions for Perfect Squares.
Mis en œuvre à l'aide de la planification dynamique. Quand j'ai vu le problème, il s'est avéré être DP. Si la valeur est petite, vous pouvez faire une recherche complète, mais elle est inefficace par tous les moyens, alors je l'ai écrite comme ci-dessus.
En tant que recommandation de la méthode de planification dynamique de mon article personnel sur Qiita Super introduction à la planification dynamique! Explications des problèmes A à E du concours DP éducatif et problèmes similaires Et dans l'implémentation en Python Mémo d'apprentissage de la programmation dynamique (DP) ~ par Python ~ Partie 1
N'est-ce pas un bon exemple? Je pense qu'il vaut mieux saisir le concept dans le premier et en apprendre davantage sur l'implémentation en Python dans le second.
En parlant de cela, c'est une méthode de programmation dynamique en japonais, mais c'est de la programmation dynamique en anglais, n'est-ce pas?
Alors c'est tout pour cette fois. Je vous remercie pour votre travail acharné.
Recommended Posts