解算almostIncreasingSequence（代码战）

Question

给定一个整数序列作为数组，通过从数组中删除不超过一个元素来确定是否可能获得严格递增的序列。

示例

对于序列[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

Answer 1

您的适度算法在这里失败的原因（除了缺少的“=”作为回报）是，它只是计算大于下一个的元素，如果该计数大于1，则返回结果。

其中重要的是在每次从列表中删除一个元素后查看列表，并确认它仍然是一个排序的列表。

我在这方面的尝试非常短暂，适用于所有场景。它不满足练习中单独设置的最后一个隐藏测试集的时间限制。

正如问题名称所暗示的，我直接想将列表与其排序版本进行比较，并在稍后处理“几乎”的情况—从而拥有almostIncreasingSequence。i、 e.：

if sequence==sorted(sequence):
   .
   .

但正如问题所说：

determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array (at a time).

在迭代过程中，我一次删除一个元素，开始可视化列表，并检查列表的其余部分是否是其自身的排序版本。因此我想到：

for i in range(len(sequence)):
    temp=sequence.copy()
    del temp[i]
    if temp==sorted(temp):
        .
        .

在这里，我可以看到，如果这个条件对完整的列表是真的，那么我们有什么是必需的-一个almostIncreasingSequence！所以我用这种方式完成了我的代码：

def almostIncreasingSequence(sequence):
    t=0
    for i in range(len(sequence)):
        temp=sequence.copy()
        del temp[i]
        if temp==sorted(temp):
            t+=1
    return(True if t>0 else False)

这个解决方案在[1，1，1，2，3]这样的列表中仍然失败。 正如@rory daulton在他的评论中指出的，在这个问题中，我们需要区分“排序”和“递增序列”。当测试[1，1，1，2，3]被排序时，它按照问题中的要求处于递增序列上。为了处理这个问题，下面是最后一个代码，添加了一行条件来检查连续的相同数字：

def almostIncreasingSequence(sequence):
    t=0
    for i in range(len(sequence)):
        temp=sequence.copy()
        del temp[i]
        if temp==sorted(temp) and not(any(i==j for i,j in zip(sorted(temp), sorted(temp)[1:]))):
            t+=1
    return t>0

---

由于这仍然没有通过最后一个测试的执行时间限制（列表必须很大），我仍然在寻找是否有办法优化我的解决方案。

Answer 2

这是我的。希望你觉得这有帮助：

def almostIncreasingSequence(sequence):

    #Take out the edge cases
    if len(sequence) <= 2:
        return True

    #Set up a new function to see if it's increasing sequence
    def IncreasingSequence(test_sequence):
        if len(test_sequence) == 2:
            if test_sequence[0] < test_sequence[1]:
                return True
        else:
            for i in range(0, len(test_sequence)-1):
                if test_sequence[i] >= test_sequence[i+1]:
                    return False
                else:
                    pass
            return True

    for i in range (0, len(sequence) - 1):
        if sequence[i] >= sequence [i+1]:
            #Either remove the current one or the next one
            test_seq1 = sequence[:i] + sequence[i+1:]
            test_seq2 = sequence[:i+1] + sequence[i+2:]
            if IncreasingSequence(test_seq1) == True:
                return True
            elif IncreasingSequence(test_seq2) == True:
                return True
            else:
                return False

Answer 3

你的算法太简单了。您有一个正确的想法，检查前一个元素小于后一个元素但需要更多元素的连续元素对。

制作一个例程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]))