Python 解决几乎递增序列（Codefights）

Solve almostIncreasingSequence (Codefights)

提问by R N

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:

对于 sequence [1, 3, 2, 1]，输出应该是：

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:

对于 sequence [1, 3, 2]，输出应该是：

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].

您可以从数组中删除 3 以获得严格递增的序列 [1, 2]。或者，您可以删除 2 以获得严格递增的序列 [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

回答by Rory Daulton

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 0to 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.

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

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 ifstatements.

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

Here is Python code that passes all the tests you show.

这是通过您展示的所有测试的 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

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]))

回答by sukai

This is mine. Hope you find this helpful:

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

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

回答by Ashish Singh

The reason why your modest algorithm fails here (apart from the missing '=' in return) is, it's just counting the elements which are greater than the next one and returning a result if that count is more than 1.

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

What's important in this is to look at the list after removing one element at a time from it, and confirm that it is still a sortedlist.

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

My attempt at this is really short and works for all scenario. It fails the time constraint on the last hidden test set alone in the exercise.

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

As the problem name suggests, I directly wanted to compare the list to its sorted version, and handle the 'almost' case later - thus having the almostIncreasingSequence. i.e.:

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

if sequence==sorted(sequence):
   .
   .

But as the problem says:

但正如问题所说：

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

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

I started visualizing the list by removing an element at a time during iteration, and check if the rest of the list is a sorted version of itself. Thus bringing me to this:

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

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

It was here when I could see that if this condition is true for the full list, then we have what is required - an almostIncreasingSequence! So I completed my code this way:

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

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)

This solution still fails on lists such as [1, 1, 1, 2, 3]. As @rory-daulton noted in his comments, we need to differentiate between a 'sorted' and an 'increasingSequence' in this problem. While the test [1, 1, 1, 2, 3] is sorted, its on an increasingSequence as demanded in the problem. To handle this, following is the final code with a one line condition added to check for consecutive same numbers:

此解决方案在 [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

---

---

As this still fails the execution time limit on the last of the test (the list must be really big), I am still looking if there is a way to optimize this solution of mine.

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

回答by Amit Singh

There are two possibilities whenever you hit the condition of the sequence[i-1]>=sequence[i]

每当您遇到序列 [i-1]>=sequence[i] 的条件时，有两种可能性

• Delete index i-1
• Delete index i

• 删除索引 i-1
• 删除索引 i

So my idea was to create copy and delete the indexes and check if they are sorted and then at the end you can do the or and return if the ans is attainable. Complexity will be O(N2)[because of del] and space O(N)

所以我的想法是创建副本并删除索引并检查它们是否已排序，然后最后您可以执行 or 并返回是否可以实现。复杂度将是 O(N2)[因为 del] 和空间 O(N)

def almostIncreasingSequence(sequence):
    c0,c1=1,1
    n=len(sequence)
    l1=[]
    l2=[]
    for i in sequence:
        l1.append(i)
        l2.append(i)
    for i in range(1,n):
        if sequence[i-1]>=sequence[i]:
            del l1[i]
            del l2[i-1]
            break
    for i in range(1,n-1):
        if l1[i-1]>=l1[i]:
            c0=0
            break
    for i in range(1,n-1):
        if l2[i-1]>=l2[i]:
            c1=0
            break
    return bool(c0 or c1)

This is accepted solution.

这是公认的解决方案。

回答by SpiXel

Well, here's also my solution, I think it's a little bit cleaner than other solutions proposed here so I'll just bring it below.

嗯，这也是我的解决方案，我认为它比这里提出的其他解决方案更简洁一些，所以我将把它放在下面。

What it does is it basically checks for an index in which i-th value is larger than (i+1)-th value, if it finds such an index, checks whether removing any of those two makes the list into an increasing sequence.

它所做的基本上是检查第i个值大于第(i+1)个值的索引，如果找到这样的索引，则检查删除这两个中的任何一个是否使列表成为递增序列。

def almostIncreasingSequence(sequence):

    def is_increasing(lst):
        for idx in range(len(lst)-1):
            if lst[idx] >= lst[idx + 1]:
                return False
        return True

    for idx in range(len(sequence) - 1):
        if sequence[idx] >= sequence[idx + 1]:
            fixable = is_increasing([*sequence[:idx], *sequence[idx+1:]]) or is_increasing([*sequence[:idx+1], *sequence[idx+2:]])
            if not fixable:
                return False

    return True

回答by TImmuh

I'm still working on mine. Wrote it like this but I can't pass the last 3 hidden tests.

我还在做我的。像这样写，但我无法通过最后 3 个隐藏测试。

def almostIncreasingSequence(sequence):

boolMe = 0
checkRep = 0

for x in range(0, len(sequence)-1):

    if sequence[x]>sequence[x+1]:
        boolMe = boolMe + 1
        if (x!=0) & (x!=(len(sequence)-2)):
            if sequence[x-1]>sequence[x+2]:
                boolMe = boolMe + 1
    if sequence.count(sequence[x])>1:
        checkRep = checkRep + 1

    if (boolMe > 1) | (checkRep > 2):    
        return False
return True

回答by mTv

This was a pretty cool exercise.

这是一个非常酷的练习。

I did it like this:

我是这样做的：

def almostIncreasingSequence(list):
  removedIdx = []                   #Indexes that need to be removed

  for idx, item in enumerate(list):
    tmp = []                        #Indexes between current index and 0 that break the increasing order
    for i in range(idx-1, -1, -1):
      if list[idx]<=list[i]:        #Add index to tmp if number breaks order
        tmp.append(i)
    if len(tmp)>1:                  #If more than one of the former numbers breaks order  
      removedIdx.append(idx)        #Add current index to removedIdx
    else:
      if len(tmp)>0:                #If only one of the former numbers breaks order
        removedIdx.append(tmp[0])   #Add it to removedIdx
  return len(set(removedIdx))<=1

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]))
print(almostIncreasingSequence([1, 1, 1, 2, 3]))

回答by gingerroot

With Python3, I started with something like this...

使用 Python3，我从这样的事情开始......

def almostIncreasingSequence(sequence):
    for i, x in enumerate(sequence):
        ret = False
        s = sequence[:i]+sequence[i+1:]
        for j, y in enumerate(s[1:]):
            if s[j+1] <= s[j]:
                ret = True
                break
            if ret:
                break
        if not ret:
            return True
    return False

But kept timing out on Check #29.

但在检查 #29 上一直超时。

I kicked myself when I realized that this works, too, but still times out on #29. I have no idea how to speed it up.

当我意识到这也有效时，我踢了自己一脚，但仍然在 #29 超时。我不知道如何加快速度。

def almostIncreasingSequence(sequence):
    for i, x in enumerate(sequence):    
        s = sequence[:i]
        s.extend(sequence[i+1:])
        if s == sorted(set(s)):
            return True
    return False

回答by theannouncer

Here's my simple solution

这是我的简单解决方案

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

回答by Siva Karthikeyan

This works on most cases except has problems with performance.

这适用于大多数情况，除了性能问题。

def almostIncreasingSequence(sequence):
    if len(sequence)==2:
        return sequence==sorted(list(sequence))
    else:
        for i in range(0,len(sequence)):
            newsequence=sequence[:i]+sequence[i+1:]
            if (newsequence==sorted(list(newsequence))) and len(newsequence)==len(set(newsequence)):
                return True
                break
            else:
                result=False
    return result