问题:求解几乎递增的序列(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]))