問題
今回はQuickly find multiple left rotations of an arrayにあるリストの並びを指定した回数 k回ローテーションさせる問題を勉強する。具体的には下記のようなリストがあったときに、kで指定した数値分リストを回転させることが目的。
k = 3 Input : [1, 3, 5, 7, 9] Output : 7 9 1 3 5
実装
回答に記載されている実装のイメージはこんな感じ。リストを拡張し、適切な位置からスタートすることで、ローテーションさせなくともローテーションさせたように扱うことができる方法。
小さな問題に分解して考えると、「リストを拡張する関数」と「スタート位置を決めて出力する関数」で構成されていることがわかるので、これらの関数を作成していく。
from typing import List
def preprocess(numbers: List[int], n: int) -> List[int]:
tmp = [None] * (2 * n)
for i in range(n):
tmp[i] = tmp[i + n] = numbers[i]
return tmp
def leftRotate(numbers: List[int], k: int) -> int:
len_numbers = len(numbers)
expand_list = preprocess(numbers, len_numbers)
start = k % len_numbers
# expand_list[start:start + len_numbers]
for i in range(start, start + len_numbers):
print(expand_list[i], end=" ")
print('')
if __name__ == '__main__':
numbers = [1, 3, 5, 7, 9]
print(numbers)
print('-'*10)
leftRotate(numbers, k=1)
print('-'*10)
leftRotate(numbers, k=2)
print('-'*10)
leftRotate(numbers, k=3)
print('-'*10)
leftRotate(numbers, k=4)
print('-'*10)
leftRotate(numbers, k=5)
[1, 3, 5, 7, 9]
----------
3 5 7 9 1
----------
5 7 9 1 3
----------
7 9 1 3 5
----------
9 1 3 5 7
----------
1 3 5 7 9
実装2
ローテーションと聞くと、私のような初心者は「リスト自体を回転」させようとするが、考え方を変えると、「インデックスをローテーション」させれば、つまるところ、やっていることは同じといえる・・・。なるほど。ということで、繰り返しといえば剰余をうまく使えば、インデックスもうまく動かせるので、それで実装してみる。剰余で計算されるインデックスを表示するための行があるが、実際は不要。
from typing import List
def leftRotate(numbers: List[int], k: int) -> int:
len_numbers = len(numbers)
# index for display
[print(i % len_numbers, end=' ') for i in range(k, k + len_numbers)]
print('')
for i in range(k, k + len_numbers):
print(str(numbers[i % len_numbers]), end=' ')
print('')
if __name__ == '__main__':
numbers = [1, 3, 5, 7, 9]
print(numbers)
print('-'*10)
leftRotate(numbers, k=1)
print('-'*10)
leftRotate(numbers, k=2)
print('-'*10)
leftRotate(numbers, k=3)
print('-'*10)
leftRotate(numbers, k=4)
print('-'*10)
leftRotate(numbers, k=5)
[1, 3, 5, 7, 9]
----------
1 2 3 4 0
3 5 7 9 1
----------
2 3 4 0 1
5 7 9 1 3
----------
3 4 0 1 2
7 9 1 3 5
----------
4 0 1 2 3
9 1 3 5 7
----------
0 1 2 3 4
1 3 5 7 9
