[解決済み] 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]))
関連
-
Python Decorator 練習問題
-
Python カメの描画コマンドとその例
-
Python 可視化 big_screen ライブラリ サンプル 詳細
-
[解決済み】RuntimeWarning: invalid value encountered in double_scalars で numpy の除算ができない。
-
[解決済み】ilocが「IndexError: single positional indexer is out-of-bounds」を出す。
-
[解決済み】 NameError: グローバル名 'xrange' は Python 3 で定義されていません。
-
[解決済み】Django: ImproperlyConfigured: SECRET_KEY 設定は空であってはならない
-
[解決済み】TypeErrorを取得しました。エントリを持つ子テーブルの後に親テーブルを追加しようとすると、 __init__() missing 1 required positional argument: 'on_delete'
-
[解決済み】"No JSON object could be decoded "よりも良いエラーメッセージを表示する。
-
[解決済み】Python Error: "ValueError: need more than 1 value to unpack" (バリューエラー:解凍に1つ以上の値が必要です
最新
-
nginxです。[emerg] 0.0.0.0:80 への bind() に失敗しました (98: アドレスは既に使用中です)
-
htmlページでギリシャ文字を使うには
-
ピュアhtml+cssでの要素読み込み効果
-
純粋なhtml + cssで五輪を実現するサンプルコード
-
ナビゲーションバー・ドロップダウンメニューのHTML+CSSサンプルコード
-
タイピング効果を実現するピュアhtml+css
-
htmlの選択ボックスのプレースホルダー作成に関する質問
-
html css3 伸縮しない 画像表示効果
-
トップナビゲーションバーメニュー作成用HTML+CSS
-
html+css 実装 サイバーパンク風ボタン
おすすめ
-
PythonはWordの読み書きの変更操作を実装している
-
Pythonの学習とデータマイニングのために知っておくべきターミナルコマンドのトップ10
-
Python Pillow Image.save jpg画像圧縮問題
-
[解決済み】DataFrameのコンストラクタが正しく呼び出されない!エラー
-
[解決済み】RuntimeWarning: 割り算で無効な値が発生しました。
-
[解決済み】なぜ「LinAlgError: Grangercausalitytestsから「Singular matrix」と表示されるのはなぜですか?
-
[解決済み】LogisticRegression: Pythonでsklearnを使用して、未知のラベルタイプ: '連続'を使用しています。
-
[解決済み】NameError: 名前 'self' が定義されていません。
-
[解決済み】Flaskのテンプレートが見つからない【重複あり
-
[解決済み】 'numpy.float64' オブジェクトは反復可能ではない