解决几乎增加的序列(代码战) [英] Solve almostIncreasingSequence (Codefights)
问题描述
给出一个整数序列作为数组，确定是否可以通过从数组中删除不超过一个元素来获得严格递增的序列.
示例
对于序列[1, 3, 2, 1]，输出应为:
almostIncreasingSequence(sequence) = false;
此数组中没有一个元素可以删除以得到严格递增的序列.
对于序列[1, 3, 2]，输出应为:
almostIncreasingSequence(sequence) = true.
您可以从数组中删除3以获得严格递增的序列[1、2].或者，您可以删除2以获得严格递增的顺序[1，3].
我的代码:
def almostIncreasingSequence(sequence):
c= 0
for i in range(len(sequence)-1):
if sequence[i]>=sequence[i+1]:
c +=1
return c<1
但是它不能通过所有测试.
input: [1, 3, 2]
Output:false
Expected Output:true
Input: [10, 1, 2, 3, 4, 5]
Output: false
Expected Output: true
Input: [0, -2, 5, 6]
Output: false
Expected Output: true
input: [1, 1]
Output: false
Expected Output: true
Input: [1, 2, 3, 4, 3, 6]
Output: false
Expected Output: true
Input: [1, 2, 3, 4, 99, 5, 6]
Output: false
Expected Output: true
您的算法过于简单.您有一个正确的主意，请检查连续的元素对，确认前一个元素小于后一个元素，但需要更多.
执行例程first_bad_pair(sequence)，该例程检查所有成对元素的顺序.如果是这样，则返回值-1.否则，返回先前元素的索引:这将是从0到n-2的值.然后一种可行的算法是检查原始列表.如果可行，则很好，但如果不能，请尝试删除较早或之后的有问题的元素.如果这些方法中的任何一个都可以，那么可以，否则就不可以了.
我可以想到其他算法，但这似乎是最简单的算法.如果您不喜欢通过合并原始列表的两个部分而形成的最多两个临时列表，则可以使用更多的if语句对原始列表进行比较，从而完成等效操作.
这是通过您显示的所有测试的Python代码.
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
如果您确实想避免使用这些临时列表，那么以下是其他代码，其中包含更复杂的成对检查例程.
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
这是我使用的测试.
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]))
Given a sequence of integers as an array, determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.
Example
For sequence [1, 3, 2, 1], the output should be:
almostIncreasingSequence(sequence) = false;
There is no one element in this array that can be removed in order to get a strictly increasing sequence.
For sequence [1, 3, 2], the output should be:
almostIncreasingSequence(sequence) = true.
You can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, you can remove 2 to get the strictly increasing sequence [1, 3].
My code:
def almostIncreasingSequence(sequence):
c= 0
for i in range(len(sequence)-1):
if sequence[i]>=sequence[i+1]:
c +=1
return c<1
But it can't pass all tests.
input: [1, 3, 2]
Output:false
Expected Output:true
Input: [10, 1, 2, 3, 4, 5]
Output: false
Expected Output: true
Input: [0, -2, 5, 6]
Output: false
Expected Output: true
input: [1, 1]
Output: false
Expected Output: true
Input: [1, 2, 3, 4, 3, 6]
Output: false
Expected Output: true
Input: [1, 2, 3, 4, 99, 5, 6]
Output: false
Expected Output: true
Your algorithm is much too simplistic. You have a right idea, checking consecutive pairs of elements that the earlier element is less than the later element, but more is required.
Make a routine first_bad_pair(sequence) that checks the list that all pairs of elements are in order. If so, return the value -1. Otherwise, return the index of the earlier element: this will be a value from 0 to n-2. Then one algorithm that would work is to check the original list. If it works, fine, but if not try deleting the earlier or later offending elements. If either of those work, fine, otherwise not fine.
I can think of other algorithms but this one seems the most straightforward. If you do not like the up-to-two temporary lists that are made by combining two slices of the original list, the equivalent could be done with comparisons in the original list using more if statements.
Here is Python code that passes all the tests you show.
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
If you do want to avoid those temporary lists, here is other code that has a more complicated pair-checking routine.
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
And here are the tests I used.
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]))
这篇关于解决几乎增加的序列(代码战)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
