解决几乎递增序列(Codefights) [英] Solve almostIncreasingSequence (Codefights)

问题描述

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

示例

对于序列[1, 3, 2, 1]，输出应该是:

almostIncreasingSequence(sequence) = false;

这个数组中没有一个元素可以被移除以获得严格递增的序列.

对于序列[1, 3, 2]，输出应该是:

almostIncreasingSequence(sequence) = true.

可以从数组中去掉3，得到严格递增的序列[1, 2].或者，您可以删除 2 以获得严格递增的序列 [1, 3].

我的代码:

def几乎递增序列(序列):c = 0对于范围内的 i(len(sequence)-1):如果序列[i]>=序列[i+1]:c +=1返回 c<1

但它无法通过所有测试.

输入:[1, 3, 2]输出:假预期输出:真输入:[10, 1, 2, 3, 4, 5]输出:假预期输出:true输入:[0, -2, 5, 6]输出:假预期输出:true输入:[1, 1]输出:假预期输出:true输入:[1, 2, 3, 4, 3, 6]输出:假预期输出:true输入:[1, 2, 3, 4, 99, 5, 6]输出:假预期输出:true

解决方案

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

制作一个例程first_bad_pair(sequence)，检查所有元素对是否有序的列表.如果是，则返回值 -1.否则，返回先前元素的索引:这将是一个从 0 到 n-2 的值.然后一种可行的算法是检查原始列表.如果有效，那很好，但如果无效，请尝试删除较早或较晚的违规元素.如果其中任何一个有效，则很好，否则无效.

我可以想到其他算法，但这个算法似乎最简单.如果您不喜欢通过将原始列表的两个切片组合而成的最多两个临时列表，则可以使用更多 if 语句在原始列表中进行比较来完成等效的操作.>

这是通过您展示的所有测试的 Python 代码.

def first_bad_pair(sequence):"""返回一对元素的第一个索引，其中较早的元素不小于后面的元素.如果没有这样的一对存在，返回-1."""对于范围内的 i(len(sequence)-1):如果序列[i] >=序列[i+1]:返回我返回-1定义几乎递增序列(序列):"""返回是否可以得到严格递增的通过从数组中删除不超过一个元素来排序."""j = first_bad_pair(序列)如果 j == -1:return True # 列表在增加如果 first_bad_pair(sequence[j-1:j] + sequence[j+1:]) == -1:return True # 删除前面的元素会增加如果 first_bad_pair(sequence[j:j+1] + sequence[j+2:]) == -1:return True # 删除后面的元素会增加return False # 删除要么不增加

如果您确实想避免使用这些临时列表，这里是其他具有更复杂配对检查例程的代码.

def first_bad_pair(sequence, k):"""返回序列中一对元素的第一个索引[]对于索引 k-1, k+1, k+2, k+3, ... 其中较早的元素是不小于后面的元素.如果不存在这样的对，则返回 -1."""如果 0 

这是我使用的测试.

print('\n这些应该是真的.')打印(几乎递增序列([]))打印(几乎递增序列([1]))打印(几乎递增序列([1, 2]))打印(几乎递增序列([1, 2, 3]))打印(几乎递增序列([1, 3, 2]))打印(almostIncreasingSequence([10, 1, 2, 3, 4, 5]))打印(几乎递增序列([0、-2、5、6]))打印(几乎递增序列([1, 1]))打印(几乎递增序列([1、2、3、4、3、6]))打印(almostIncreasingSequence([1, 2, 3, 4, 99, 5, 6]))打印(几乎递增序列([1、2、2、3]))print('\n这些应该是假的.')打印(几乎递增序列([1、3、2、1]))打印(几乎递增序列([3, 2, 1]))打印(几乎递增序列([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]))

这篇关于解决几乎递增序列(Codefights)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！