はじめに
どんな問題を解決するか
リストの回転は、当番表(次は誰の番か)、循環バッファー、画像の処理、面接問題などに出てきます。1ステップずつ要素を動かすと遅いですが、スライスなら1回でできます。
身近なたとえ
リストの回転は、全員が右に2席ずつずれる円卓のようなものです。最後の2人が回って最初の席に着き、ほかの人は順番を保ちます。席の数ちょうどだけ回転しても何も変わりません。
円卓からコードへ
steps %= len(values)🔁 5席のテーブルで7席動くのは2席と同じvalues[-steps:]🚶 最後の2人が前へ移るvalues[:-steps]🪑 ほかの人は順番を保つ+🔗 一緒に座らせる:[4, 5, 1, 2, 3]ひと言でいうと
リストを右に k だけ回転すると、最後の k 個の要素が前に移り、すべての要素の順番は保たれます。
重要なポイント
if not values: return []は空のリストを処理します。そうしないと% len(values)が0で割ることになります。steps %= len(values)は大きな回転数を折り返します。values[-steps:]は前に移る末尾で[4, 5]です。values[:-steps]は残りの[1, 2, 3]で、+が2つをつなぎます。
どんな場面で使う?
- 順番に回る当番やスケジュール。
- 循環バッファーやずれていくデータの窓。
- スライスと剰余に関する面接問題。
使わなくてよいとき
- 1ステップずつ何度も回転する場合:
collections.deque.rotateがその場で効率よく行います。 - 余分なメモリが問題になる巨大なリスト:その場で反転する方法ならコピーを避けられます。
動きで理解する
箱をクリックするかスライダーでインデックスを選びます。挿入や削除をすると、後ろの要素がすべてずれる理由がわかります。
サンプルコード
main.py
def rotate_right(values, steps):
if not values:
return []
steps %= len(values)
return values[-steps:] + values[:-steps]
print(rotate_right([1, 2, 3, 4, 5], 2))
実行結果
[4, 5, 1, 2, 3]
コードの解説
steps %= len(values)という余りの計算は、回転数がリストの長さより大きい場合に対応するためのものです。5個の要素のリストを7回回転させるのは、2回回転させるのと同じだからです。スライスvalues[-steps:]とvalues[:-steps]で末尾のk個と残りを取り出し、新しい順番でつなげます。時間とメモリの計算量はどちらもO(n)です。
値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。
発展問題
下のヒントにしたがってコードを書き換えてみましょう。自分で変えて結果を確かめると、コードを読むだけよりずっと深く理解できます。
- 空のリスト、要素が1つだけのリスト、重複した値を含むリストで試す。
- 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
- 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
よくある間違い
回転数0を忘れる
values[-0:] はリスト全体なので、% がないと結果が2倍になります。
問題
return values[-steps:] + values[:-steps] # steps = 5 gives a list of 10
修正
steps %= len(values)
return values[-steps:] + values[:-steps]
このレッスンを終えましたか?
学習済みにすると進み具合を記録できます。
進み具合はこのブラウザーに保存されています ログインすると、どのデバイスでも引き継げます。
チャレンジで練習する
このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。
すべてのチャレンジ