Weekly Contest 239
Hello! đ
Pour la session de cette semaine, nous nous sommes attaquĂ©s au Weekly Contest 239 đ. Petit rappel du format:
4ïžâŁ problĂšmes - Un facile, deux mediums et un difficile.
đ ThĂšmes variĂ©s.
â° 1h30 au total.
Un contest permet de se tester sous pression, avec lâobjectif Ă©tant de complĂ©ter tous les exercices dans le temps imparti.
François & moi-mĂȘme avons eu le temps de complĂ©ter les 2 premiers exercices.
RĂ©sultats
ProblĂšme 1 - Distance minimale Ă lâĂ©lĂ©ment cible (Facile đą)
Ătant donnĂ© un tableau d'integers
nums
et deux integerstarget
etstart
, trouvez un indexi
tel quenums [i] == target
etabs (i - start
) soit minimisé. Retournezabs(i - start)
.
Intuition
Lâindex start
est notre point de dĂ©part. Plus on sâĂ©loigne de cet index, plus on maximise abs(i - start)
. Nous pouvons donc explorer notre tableau en prenant lâĂ©lĂ©ment Ă lâindex start
pour point de dĂ©part, et explorer les Ă©lĂ©ments voisins (Ă droite et Ă gauche), jusquâa que nous en trouvions un Ă©gal Ă target
.
Quelles sont les conditions dâarrĂȘt de notre algorithme? Lorsque nous arrivons aux extrĂ©mitĂ©s de notre tableau: index >= 0
et index < len(nums).
Voici une dĂ©monstration de lâalgorithme:
Et voilà une implémentation en Python:
def getMinDistance(nums: List[int], target: int, start: int) -> int:
n = len(nums)
left, right = start, start
while left >= 0 or right < n:
if left >= 0:
if nums[left] == target: return start - left
left -= 1
if right < n:
if nums[right] == target: return right - start
right += 1
Complexité: linéaire en temps et constante en mémoire.
ProblĂšme 2 - SĂ©parer une string en valeurs successives dĂ©croissantes (Medium đ )
François & moi-mĂȘme avons trouvĂ© ce problĂšme intĂ©ressant et challengeant. Nous avons passĂ© la majoritĂ© de notre temps dessus.
Ătant donnĂ© une string
s
composée uniquement de chiffres, retournezTrue
sis
peut ĂȘtre divisĂ©e en 2 ou plusieurs sub-strings (non vides) telles que:
Les valeurs numériques des sub-strings soient dans l'ordre décroissant et
La différence entre 2 valeurs numériques adjacentes soit égale à 1.
Retournez
False
dans le cas contraire.
Intuition
Ce problĂšme nous demande dâĂ©valuer si une certaine solution existe, Ă©tant donnĂ© les contraintes existantes. Nous devons donc explorer toutes les solutions, et si au-moins une respecte les contraintes du problĂšme, nous pouvons retourner True
. Plus précisément:
Si nous trouvons une solution valide, nous pouvons arrĂȘter lâalgorithme et retourner
True
. Sinon, nous devons continuer à explorer les solutions restantes, jusqu'à en trouver une valide ou toutes les vérifier, retournant alorsFalse
.Cependant, il nây a pas besoin de construire une solution entiĂšrement pour la vĂ©rifier. En effet, nous construisons ici une sĂ©quence, oĂč tous les Ă©lĂ©ments doivent respecter 2 contraintes. Si les premiers Ă©lĂ©ments de la sĂ©quence ne respectent pas une des 2 contraintes, nous pouvons arrĂȘter, car cette sĂ©quence ne sera pas valide, Ă©tant donnĂ© que les contraintes sâappliquent Ă tous les Ă©lĂ©ments. Cela sâappelle communĂ©ment âearly pruningâ.
Cela devrait faire sonner la cloche backtracking đ
Pour une explication plus en profondeur, je vous renvoie vers cet excellent article, expliquant clairement lâintuition derriĂšre le backtracking.
Le backtracking a aussi lâavantage dâĂȘtre trĂšs concis:
def splitString(s: str) -> bool:
n = len(s)
def backtrack(start: int, seq: List[int]) -> bool:
# early pruning
if len(seq) >= 2 and not isValid(seq): return False
if start == n:
if isValid(seq): return True
else:
for i in range(start + 1, n+1):
if backtrack(i, seq + [int(s[start:i])]):
return True
return False
return backtrack(0, [])
ComplexitĂ©: exponentielle en temps et mĂ©moire, O(2^N), avec N le nombre de chiffres dans notre string. Lâintuition derriĂšre cette complexitĂ© est que pour chacun des N chiffres, nous avons 2 choix: couper ou non. Explorer toutes les solutions prend ainsi O(2^N).
Attention, nous utilisons ici une rĂ©cursion, qui utilise la call stack de notre systĂšme pour placer les rĂ©sultats intermĂ©diaires. Comme nous explorons un nombre exponentiel de choix, nous utilisons la mĂȘme empreinte mĂ©moire.
Rejoignez-nous sur Youtube pour un walkthrough dĂ©taillĂ© de notre solution Ă ce problĂšme đ
Prochaine session
Ce samedi 15 mai, on commence un nouveau cycle de problĂšmes ciblant le backtracking. On attaquera le problĂšme 39. Combination Sum đ.
On se dit Ă samedi prochain, 09:30am sur notre Twitch LeetGrindFr đ
Mots-clés de la session
array, string, backtracking, recursion