[解決済み] almostIncreasingSequenceを解く (コードファイト)

質問

整数の列が配列として与えられたとき、配列から要素を1つ以上取り除かないことによって厳密に増加する列を得ることが可能かどうかを判定しなさい。

例

シーケンスの場合 [1, 3, 2, 1] と出力されるはずです。

almostIncreasingSequence(sequence) = false;

この配列には、厳密に増加する配列を得るために削除できる要素は1つもありません。

配列の場合 [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 . そうすると、1つのアルゴリズムとして、元のリストをチェックすることができます。うまくいくなら問題ありませんが、そうでないなら、前または後の問題のある要素を削除してみてください。どちらかがうまくいけば問題ありませんが、そうでない場合はうまくいきません。

他のアルゴリズムも考えられますが、これが一番わかりやすいと思います。もし、元のリストの2つのスライスを組み合わせて作られる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]))