解决几乎增加的序列(Codefights)

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

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

创建一个例程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]))

Answer 2

该解决方案接近直观的解决方案，您检查序列中的当前项是否大于当前最大值（根据定义，它是严格递增序列中的前一项）。

问题是，在某些情况下，您应该删除违反上述规定的当前项目，而在其他情况下，您应该删除以前的较大项目。

例如，考虑以下内容：

[1, 2, 5, 4, 6]

您检查具有 value 的 item 的序列4，发现它破坏了递增序列规则。在此示例中，很明显您应该删除前一项5，并且考虑原因很重要。原因是该值4大于“先前”最大值（ 之前的最大值5，在本例中为2），因此5是异常值，应将其删除。

接下来考虑以下事项：

[1, 4, 5, 2, 6]

您检查具有 value 的 item 的序列2，发现它破坏了递增序列规则。在此示例中，2不大于“先前”最大值，4因此2是异常值，应将其删除。

现在您可能会争辩说，上述每个场景的净效果是相同的 - 从序列中删除一项，我们可以使用计数器进行跟踪。
然而，重要的区别在于更新maximum和previous_maximum值的方式：

• 对于[1, 2, 5, 4, 6]，因为5是异常值，4所以应该成为新的maximum。

• 对于[1, 4, 5, 2, 6]，因为2是异常值，5因此应保留为maximum。

这种区别对于评估序列中的其他项目至关重要，确保我们正确忽略先前的异常值。

这是基于上述描述（O(n)复杂性和O(1)空间）的解决方案：

def almostIncreasingSequence(sequence):
    removed = 0
    previous_maximum = maximum = float('-infinity')
    for s in sequence:
        if s > maximum:
            # All good
            previous_maximum = maximum
            maximum = s
        elif s > previous_maximum:
            # Violation - remove current maximum outlier
            removed += 1
            maximum = s
        else:
            # Violation - remove current item outlier
            removed += 1
        if removed > 1:
            return False
    return True

我们最初设置maximum和previous_maximum并定义一个值为 的-infinity计数器。removed0

第一个测试用例是“通过”用例，仅更新maximum和previous_maximum值。

第二个测试用例在s <= maximum检查是否触发时触发s > previous_maximum- 如果为真，则先前的maximum值是异常值并被删除，同时s更新为新值maximum并且removed计数器递增。

s <= maximum当和是异常值时，第三个测试用例被触发s <= previous_maximum- 在这种情况下，s是异常值，因此被删除（和s没有变化）并且计数器递增。maximumprevious_maximumremoved

需要考虑的一种边缘情况如下：

[10, 1, 2, 3, 4]

对于这种情况，第一项是异常值，但只有在检查第二项 ( 1) 时我们才知道这一点。此时，maximumis 10while previous_maximumis -infinity，so 10（或第一项大于第二项的任何序列）将被正确识别为异常值。

Answer 3

这是我的简单解决方案

def almostIncreasingSequence(sequence):
    removed_one = False
    prev_maxval = None
    maxval = None
    for s in sequence:
        if not maxval or s > maxval:
            prev_maxval = maxval
            maxval = s
        elif not prev_maxval or s > prev_maxval:
            if removed_one:
                return False
            removed_one = True
            maxval = s
        else:
            if removed_one:
                return False
            removed_one = True
    return True

Answer 4

这是我的.希望您觉得这有用:

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 5

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

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

我在这方面的尝试非常短，适用于所有场景。它在练习中仅通过最后一个隐藏测试集的时间限制就失败了。

正如问题名称所暗示的那样，我直接想将列表与其排序版本进行比较，并在稍后处理“几乎”的情况 - 因此具有几乎IncreasingSequence。IE：

if sequence==sorted(sequence):
   .
   .

但正如问题所说：

确定是否可以通过从数组中删除不超过一个元素来获得严格递增的序列（一次）。

我通过在迭代期间一次删除一个元素来开始可视化列表，并检查列表的其余部分是否是其自身的排序版本。从而使我想到这一点：

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

正是在这里，我可以看到如果完整列表的条件为真，那么我们就有了所需的东西 - 一个几乎递增的序列！所以我以这种方式完成了我的代码：

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

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