どーも！
たかぽんです！
今回もやっていこうと思います！
344. Reverse String
本日の問題は以下。
やることとしては、単純に配列の要素として文字をもつリストが渡されるので、その値を逆順にしたリストを返せ...といったものです。
いつも通り、例をお借りすると...
Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]上記のように、Inputでhelloという文字が要素として保持されていて、それをひっくり返したOutputを出せ。
といった問題ですね。
ただし...
一つだけ大切な条件があります。
Do not allocate extra space for another array,
you must do this by modifying the input array in-place with O(1) extra memory.つまり、別の配列を作ってなんかしたりしちゃだめですよ〜！と。
与えられたinputの配列そのものを編集して、Outputの形にする必要があります。
筆者の得意分野が潰されました...w
というわけで、問題はなんとなくわかったかと思います。それでは、アルゴリズムを検討していきましょう。
アルゴリズム
筆者が思いついた方法だと、まず最初に配列の要素数分ループを回すのですが、その際に末尾から順番に値を取得していきます。
そして、順番に取得する値をそれぞれ都度末尾に追加していきます。
そうすることで...
['h', 'e', 'l', 'l', 'o'] // オリジナル
['h', 'e', 'l', 'l', 'o'] // oを取り出して末尾につける
['h', 'e', 'l', 'o', 'l'] // 後ろのlを取り出して末尾につける
['h', 'e', 'o', 'l', 'l'] // 手前のlを取り出して末尾につける
['h', 'o', 'l', 'l', 'e'] // eを取り出して末尾につける
['o', 'l', 'l', 'e', 'h'] // 完成！のようになるイメージです。
初回に関しては末尾を取得して、末尾に追加するという不毛なことをやってしまっていますが、いったん目を瞑ります...w
手元で取ったメモだとこんな感じです。
都度sのオリジナルのリストを書き換えていくのですが、ちゃんとデクリメントさせることによって、後ろに追加し多分が逆順に整列されているイメージですね。
気をつけないといけないのが、s自体を編集しているため、下手にpopしてしまうと、編集後のpopになります。
そのため、初期のhelloのpop(2)はeですが、例えば上記の4段階目にあるsのappend後"holle"の場合は、sの中身がholle"なので、pop(2)はoになります。
そこに気をつけて処理をかければうまくできるかと思います。
提出したコード
最後に提出したコードを以下に載せておきます。
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
for i, char in enumerate(s):
popped = s.pop(len(s) -1 - i)
s.append(popped)
return s
# 結果
Runtime: 424 ms, faster than 5.16% of Python3 online submissions for Reverse String.
Memory Usage: 18.5 MB, less than 81.19% of Python3 online submissions for Reverse String.