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 Day74 à partir de zéro "12. Integer to Roman"
À 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!
15. 3Sum Le niveau de difficulté est moyen.
Le problème est que si vous avez un tableau de n entiers «nums», alors vous avez un algorithme pour vérifier si «nums» contient des éléments «a, b, c» tels que «a + b + c = 0». Concevez et trouvez tous les termes triples uniques dans un tableau qui donne la somme de 0.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
Vous pouvez choisir 3 et choisir la combinaison qui sera 0. On peut dire que c'est une règle de combinaison de fer, mais je pense qu'il vaut mieux décider ce qu'il faut corriger en premier.
Cette fois, j'ai écrit comme suit.
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
ans = []
for i in range(len(nums)-2):
if i > 0 and nums[i] == nums[i-1]:
continue
left = i+1
right = len(nums)-1
while left < right:
sums = nums[i]+nums[left]+nums[right]
if sums < 0:
left += 1
elif sums > 0:
right -= 1
else:
ans.append([nums[i],nums[left],nums[right]])
while left < right and nums[left]==nums[left+1]:
left += 1
while left > right and nums[right]==nums[right-1]:
right -= 1
left += 1
right -= 1
return ans
# Runtime: 1092 ms, faster than 45.79% of Python3 online submissions for 3Sum.
# Memory Usage: 17.1 MB, less than 76.15% of Python3 online submissions for 3Sum.
Triez par ordre croissant en triant d'abord. Cela facilite la spécification de la taille de l'élément lors de la rotation de l'élément avec l'instruction for d'avant.
Pour donner un exemple concret,
[-1,0,1,2,-1,-4]
Une fois triés,
[-4,-1,-1,0,1,2]
Ce sera comme ça.
Le cœur de ce problème est de savoir comment sélectionner les deux éléments restants de 3sum en léchant les éléments de celui-ci depuis le début.
Comme je l'ai écrit dans le code, j'ai mis «i + 1» à «gauche», «len (nums) -1» à «droite», et s'ils étaient ajoutés, leur valeur totale, «sommes», était de 0. La solution consistait à définir l'élément de gauche sur +1 s'il était plus petit et -1 à droite s'il était supérieur à 0. Ceci est possible grâce au tri mentionné ci-dessus.
réellement
-4+(-1)+2=-3<0
Alors déplacez l'élément gauche et
-4+(-1)+2=-3<0
C'est toujours le même, alors déplacez à nouveau l'élément de gauche
-4+0+2=-2<0
C'est un flux comme ça.
Et si autre que ceux-là, c'est-à-dire les sommes == 0, l'élément est ajouté aux «an» préparés.
Je pense qu'il est facile de résoudre un tel système de combinaison de sommes dans un format comme celui-ci, je voudrais donc m'en souvenir comme un problème typique.
Alors c'est tout pour cette fois. Je vous remercie pour votre travail acharné.
Recommended Posts