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 Day89 "62. Unique Paths" à partir de zéro
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!
1011. Capacity To Ship Packages Within D Days Le niveau de difficulté est moyen. Ceci est un extrait de Leet Code 60 Questions que je veux résoudre pour la préparation des entrevues de codage.
Le problème est que le tapis roulant contient des bagages qui doivent être expédiés d'un port à un autre dans les D jours. La «i» charge sur la bande transporteuse a un poids «[i]». Le chargement quotidien des bagages sur un tapis roulant à bord d'un navire (dans l'ordre indiqué en poids) ne peut excéder la capacité de poids maximale du navire. Renvoie la capacité de poids minimum du navire que tous les bagages sur le tapis roulant seront expédiés dans les jours D.
Example 1:
Input: weights = [1,2,3,4,5,6,7,8,9,10], D = 5 Output: 15 Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this: 1st day: 1, 2, 3, 4, 5 2nd day: 6, 7 3rd day: 8 4th day: 9 5th day: 10
Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.
Example 2:
Input: weights = [3,2,2,4,1,4], D = 3 Output: 6 Explanation: A ship capacity of 6 is the minimum to ship all the packages in 3 days like this: 1st day: 3, 2 2nd day: 2, 4 3rd day: 1, 4
Example 3:
Input: weights = [1,2,3,1,1], D = 4 Output: 3 Explanation: 1st day: 1 2nd day: 2 3rd day: 3 4th day: 1, 1
class Solution:
def shipWithinDays(self, weights: List[int], D: int) -> int:
min_num = max_num = 0
min_num = max(weights)
max_num = sum(weights)
while min_num < max_num:
mid = (min_num + max_num)//2
days = temp_weight = 0
for i in weights:
temp_weight += i
if temp_weight > mid:
days += 1
temp_weight = i
if days + 1 <= D:
max_num = mid
else:
min_num = mid+1
return min_num
# Runtime: 508 ms, faster than 92.24% of Python3 online submissions for Capacity To Ship Packages Within D Days.
# Memory Usage: 17.1 MB, less than 7.21% of Python3 online submissions for Capacity To Ship Packages Within D Days.
J'y ai réfléchi dans une recherche de deux minutes.
La valeur minimale ici est la valeur maximale de la liste et la valeur maximale est la valeur totale de la liste. Telle est la condition car elle conduit à la capacité de charge minimale en acquérant chaque valeur, en la stockant et en la comparant à la planification par une dichotomie. La raison de ces deux valeurs est que quelle que soit la manière dont les valeurs changent, la limite inférieure de la capacité de charge est la valeur la plus basse de la liste et la valeur maximale de la capacité de charge est la somme de la liste. Inversement, je pense que ce sera beaucoup plus facile si vous pouvez définir les limites inférieure et supérieure.
Pour le cas de test de l'exemple 1, «min_num» et «max_num» contiennent respectivement 10 et 55. Et tandis que cette relation reste «min_num <max_num», la valeur intermédiaire «mid» est traitée dans la dichotomie familière.
Après cela, le traitement est appliqué sur la base de la relation entre «jours» et «D», la plage est rétrécie régulièrement et finalement la capacité de charge minimale est dérivée.
Je pensais que c'était difficile à expliquer et je cherchais un exemple facile à comprendre vidéo expliquant en Java eu. Le langage lui-même est Java, mais l'idée de base est la même, donc s'il est difficile à comprendre dans mon explication, vous voudrez peut-être jeter un coup d'œil ici.
Alors c'est tout pour cette fois. Je vous remercie pour votre travail acharné.
Recommended Posts