J'ai commencé Let Code pour améliorer mes compétences en programmation. Je vais vous expliquer le problème de base TwoSum dans Ruby.
Two Sum
Donne un tableau d'entiers et renvoie un tableau de combinaisons d'index où la somme des deux éléments est la valeur cible.
nums = [2,7,11,15]
target = 9
Est donnée.
nums[0] + nums[1] = 2+7 = 9
Alors
[0, 1]
Retour.
** Le but est d'écrire une méthode en Ruby qui répond aux exigences ci-dessus. ** **
Brute Force signifie «forcé» en japonais. En d'autres termes, résolvez sans réfléchir.
# @param {Integer[]}nums tableau d'entiers
# @param {Integer}entier cible
# @return {Integer[]}Tableau d'entiers
def two_sum(nums, target)
(0..nums.length-1).each do |i|
(i+1..nums.length-1).each do |j|
return [i, j] if nums[i] + nums[j] == target #Vérifiez s'il atteint la valeur cible
end
end
end
Sur la base d'un certain élément, nous rechercherons les éléments après cela pour voir si la somme devient la valeur cible.
La soumission de ce code entraînera les résultats suivants:
Runtime : 4656 ms(moyenne)
Memory : 9.6 MB(moyenne)
La moyenne est à peu près supérieure, mais parfois c'est une limite de temps. (Out comme une soumission)
Ceci est calculé par ʻchaque` une moyenne de n fois x n-1 fois, donc l'ordre de calcul est indiqué par * O * ($ n ^ 2 $). Autrement dit, plus le nombre d'éléments est grand, plus le temps requis en tant que fonction quadratique est long.
Il est plus efficace de rechercher un complément qui est «élément de valeur cible 1» que de rechercher un élément dont la somme est la valeur cible. Le hachage y est utilisé.
# @param {Integer[]}nums tableau d'entiers
# @param {Integer}entier cible
# @return {Integer[]}Tableau d'entiers
def two_sum(nums, target)
hash = {}
(0..nums.length-1).each do |i|
hash.store(nums[i], i) #Initialiser le hachage
end
(0..nums.length-1).each do |i|
complement = target - nums[i] #Préparez un complément
return [i, hash.fetch(complement)] if hash.has_key?(complement) && hash.fetch(complement) != i #Contrôle complémentaire
end
end
Préparez un hachage à l'avance et recherchez une valeur qui sera un complément.
En faisant cela, n fois x n-1 fois le calcul par ʻchaque` ne sera que n fois. Par conséquent, l'ordre du montant du calcul est * O * ($ n $). Et si vous soumettez ce code, le résultat sera:
Runtime : 43 ms(moyenne)
Memory : 10.2 MB(moyenne)
Il a utilisé un peu plus de mémoire, mais c'était horriblement plus rapide.
Cette fois, il existe également une technique utilisant le même hachage. Il est terminé en une seule analyse.
# @param {Integer[]}nums tableau d'entiers
# @param {Integer}entier cible
# @return {Integer[]}Tableau d'entiers
def two_sum(nums, target)
hash = {}
(0..nums.length-1).each do |i|
complement = target - nums[i]
return [hash.fetch(complement), i] if hash.has_key?(complement) #Contrôle complémentaire
hash.store(nums[i], i) #Ajouté car le complément n'existait pas
end
La quantité de code a été réduite, mais il est devenu plus difficile à lire. Il s'agit d'une méthode pour ajouter des éléments lorsque les éléments qui satisfont aux conditions ne sont pas trouvés. La quantité de mémoire peut être un peu réduite car les éléments sont ajoutés et recherchés en une seule analyse. De même, l'ordre de montant calculé est * O * ($ n $) et le résultat soumis est le suivant.
Runtime : 48 ms(moyenne)
Memory : 9.9 MB(moyenne)
C'est un peu plus lent, mais cela utilise moins de mémoire. Quelle méthode est meilleure que ** Solution 2 ** dépend de la situation, Je pense que la qualité de la méthode de hachage est claire par rapport à la ** Solution 1 **! De plus, comme le nombre d'essais est de 7 chacun, la précision de la valeur moyenne n'est pas élevée, mais cela ressort clairement de ce résultat.
J'ai expliqué Two Sum, qui est le problème de base de Leet Code. Nous avons également constaté que le temps d'exécution peut être considérablement réduit en prenant une solution appropriée. Je pense que j'ai beaucoup appris en résolvant correctement ce problème. Je veux continuer Let Code ...
Recommended Posts