リストの要素をリバースする問題

問題

今日はWrite a program to reverse an array or stringの問題にチャレンジする。この問題は、リストの要素をリバースする問題。

Input : [1, 2, 3]
Output: [3, 2, 1]

Input : [4, 5, 1, 2]
Output: [2, 1, 5, 4]

実装

基本的な方針は、start, endの2つのインデックスを用意し、startは左から右に、endは右から左にインデックスを操作し、挟み撃ちしながら、各位置の要素をスワップしていけば、リバースすることができる。インデックスが交わる部分は、リストが[4, 5, 1, 2]のように偶数であれば、[start=0, end=3]→swap→[start=1, end=2]→swap→[start=2, end=1]→falseとなり、不要な要素の入れ替えが発生しない。一方でリストが[1, 2, 3, 4, 5]のように奇数の場合は、[start=0, end=4]→swap→[start=1, end=3]→swap→[start=2, end=2]→falseとなり、真ん中の要素の入れ替えが発生しない。

from typing import List

def swap(numbers: List[int]) -> List[int]:
    start = 0
    end = len(numbers) - 1

    while start < end:
        numbers[start], numbers[end] = numbers[end], numbers[start]
        start += 1
        end -= 1

if __name__ == '__main__':
    numbers = [4, 5, 1, 2]
    print(numbers)
    swap(numbers)
    print(numbers)

    numbers = [1, 2, 3]
    print(numbers)
    swap(numbers)
    print(numbers)

    numbers = [1,2,3,4,5,6,7,8,9]
    print(numbers)
    swap(numbers)
    print(numbers)

[4, 5, 1, 2]
[2, 1, 5, 4]
[1, 2, 3]
[3, 2, 1]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[9, 8, 7, 6, 5, 4, 3, 2, 1]

実装

このような繰り返すような処理は再帰を使っても書き直せる。

from typing import List

def swap2(numbers: List[int], start: int, end: int) -> List[int]:
    if start >= end:
        return
    numbers[start], numbers[end] = numbers[end], numbers[start]
    swap2(numbers, start+1, end-1)

if __name__ == '__main__':
    numbers = [4, 5, 1, 2]
    print(numbers)
    swap2(numbers, 0, len(numbers) - 1)
    print(numbers)

    numbers = [1, 2, 3]
    print(numbers)
    swap2(numbers, 0, len(numbers) - 1)
    print(numbers)

[4, 5, 1, 2]
[2, 1, 5, 4]
[1, 2, 3]
[3, 2, 1]