Votre algorithme est beaucoup trop simpliste. Vous avez une bonne idée, en vérifiant des paires consécutives d'éléments que l'élément précédent est inférieur à l'élément suivant, mais il faut aller plus loin.
Instaurer une routine first_bad_pair(sequence) qui vérifie que toutes les paires d'éléments sont dans l'ordre. Si c'est le cas, il renvoie la valeur -1 . Sinon, il renvoie l'indice de l'élément précédent : il s'agit d'une valeur de 0 a n-2 . L'algorithme qui fonctionnerait alors consisterait à vérifier la liste originale. Si elle fonctionne, c'est parfait, mais si ce n'est pas le cas, il faut essayer de supprimer les éléments incriminés antérieurs ou postérieurs. Si l'un ou l'autre fonctionne, c'est bon, sinon ce n'est pas bon.
Je peux penser à d'autres algorithmes, mais celui-ci semble le plus simple. Si vous n'aimez pas les listes temporaires jusqu'à deux qui sont faites en combinant deux tranches de la liste originale, l'équivalent pourrait être fait avec des comparaisons dans la liste originale en utilisant plus de if déclarations.
Voici un code Python qui passe tous les tests que vous avez indiqués.
def first_bad_pair(sequence):
"""Return the first index of a pair of elements where the earlier
element is not less than the later elements. If no such pair
exists, return -1."""
for i in range(len(sequence)-1):
if sequence[i] >= sequence[i+1]:
return i
return -1
def almostIncreasingSequence(sequence):
"""Return whether it is possible to obtain a strictly increasing
sequence by removing no more than one element from the array."""
j = first_bad_pair(sequence)
if j == -1:
return True # List is increasing
if first_bad_pair(sequence[j-1:j] + sequence[j+1:]) == -1:
return True # Deleting earlier element makes increasing
if first_bad_pair(sequence[j:j+1] + sequence[j+2:]) == -1:
return True # Deleting later element makes increasing
return False # Deleting either does not make increasing
Si vous souhaitez éviter ces listes temporaires, voici un autre code qui présente une routine de vérification des paires plus compliquée.
def first_bad_pair(sequence, k):
"""Return the first index of a pair of elements in sequence[]
for indices k-1, k+1, k+2, k+3, ... where the earlier element is
not less than the later element. If no such pair exists, return -1."""
if 0 < k < len(sequence) - 1:
if sequence[k-1] >= sequence[k+1]:
return k-1
for i in range(k+1, len(sequence)-1):
if sequence[i] >= sequence[i+1]:
return i
return -1
def almostIncreasingSequence(sequence):
"""Return whether it is possible to obtain a strictly increasing
sequence by removing no more than one element from the array."""
j = first_bad_pair(sequence, -1)
if j == -1:
return True # List is increasing
if first_bad_pair(sequence, j) == -1:
return True # Deleting earlier element makes increasing
if first_bad_pair(sequence, j+1) == -1:
return True # Deleting later element makes increasing
return False # Deleting either does not make increasing
Et voici les tests que j'ai utilisés.
print('\nThese should be True.')
print(almostIncreasingSequence([]))
print(almostIncreasingSequence([1]))
print(almostIncreasingSequence([1, 2]))
print(almostIncreasingSequence([1, 2, 3]))
print(almostIncreasingSequence([1, 3, 2]))
print(almostIncreasingSequence([10, 1, 2, 3, 4, 5]))
print(almostIncreasingSequence([0, -2, 5, 6]))
print(almostIncreasingSequence([1, 1]))
print(almostIncreasingSequence([1, 2, 3, 4, 3, 6]))
print(almostIncreasingSequence([1, 2, 3, 4, 99, 5, 6]))
print(almostIncreasingSequence([1, 2, 2, 3]))
print('\nThese should be False.')
print(almostIncreasingSequence([1, 3, 2, 1]))
print(almostIncreasingSequence([3, 2, 1]))
print(almostIncreasingSequence([1, 1, 1]))
