ゼロから始めるLeetCode Day3 「1313. Decompress Run-Length Encoded List」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。
Twitterやってます。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day2 1108. Defanging an IP Address
次回
ゼロから始めるLeetCode Day4 「938. Range Sum of BST」

問題

1313. Decompress Run-Length Encoded List

We are given a list nums of integers representing a list compressed with run-length encoding.
Consider each adjacent pair of elements [freq, val] = [nums[2i], nums[2i+1]] (with i >= 0). For each such pair, there are freq elements with value val concatenated in a sublist. Concatenate all the sublists from left to right to generate the decompressed list.
Return the decompressed list.

前から順番に与えられたリストをなめていき、二つで一つのペアを作る。
そして前者を要素数としてのfreq、後者を値としてのvalueとして扱い、例えばfreq = 1,value = 2だった場合は[2]となる。

例として出されている nums = [1,2,3,4]の場合は、最初のペアが freq = 1,value = 2、
二つ目のペアがfreq = 3,value= 4であるため、[2] + [4,4,4]、そしてそれらをリストに追加すると[2,4,4,4]となる。

これらを返すような関数を作成せよ、というものが問題。

class Solution:
    def decompressRLElist(self, nums: List[int]) -> List[int]:
        ans = []
        for i in range(0,len(nums),2):
            ans += [nums[i+1]]*nums[i]
        return ans
# Runtime: 60 ms, faster than 95.75% of Python3 online submissions for Decompress Run-Length Encoded List.
# Memory Usage: 13.9 MB, less than 100.00% of Python3 online submissions for Decompress Run-Length Encoded List.

とりあえずfor文で回して要素数をとることが重要なのは問題を読めば分かる。

この問題で重要なのはiとi+1で、2つ刻みで要素を取得し、それらの前の数字とかけるという手法をどうやって実装するかという点だ。

幸いPythonはrange関数の引数に(start,stop,step)という順番で数値を当てはめるだけで良い。
startは始まりの数。私は今回の例で0からスタートした。
stopは最終的にどの数で終わらせるか。ここではnumsの数を超えて要素数をとるということはないため、numsの要素数、すなわちlen(nums)で良い。
stepは要素数の読み取り時にどれだけの要素数を飛ばすか、という数値である。

例えば、今回のテストケースでは[1,2,3,4]という引数が与えられるので、このrange関数ではiに1と3が代入される。

すごくありきたりな答えになってしまったがもしれないが、for文で0からfreqを2飛ばしで取得し、追加するときに一つ後の数字と掛けることで求めている数字を得ることができる。

なお、全く同じ考え方で、discussではこちらの考え方の方が優勢っぽいです。

class Solution:
    def decompressRLElist(self, nums: List[int]) -> List[int]:
        ans = []
        for i in range(1,len(nums),2):
            ans += [nums[i]]*nums[i-1]
        return ans
# Runtime: 60 ms, faster than 95.75% of Python3 online submissions for Decompress Run-Length Encoded List.
# Memory Usage: 14 MB, less than 100.00% of Python3 online submissions for Decompress Run-Length Encoded List.

速さやメモリの消費量など変わらないため、正直どちらでも良いとは思う。

なお、1行で回答するという猛者も世の中にはいる。
例えばこのような例だ。

def decompressRLElist(self, A):
        return [x for a, b in zip(A[0::2], A[1::2]) for x in [b] * a]
# Runtime: 88 ms, faster than 5.86% of Python3 online submissions for Decompress Run-Length Encoded List.
# Memory Usage: 14.1 MB, less than 100.00% of Python3 online submissions for Decompress Run-Length Encoded List.

for文で0から２飛ばしと1から2飛ばしをそれぞれaとbに入れ、最終的にそれらを掛け合わせたものをxに代入するというものだ。

なお、zip関数をこの回答では使用しているが、zip関数は以下のようなものである。
zip関数

それぞれのイテラブルから要素を集めたイテレータを作ります。
この関数はタプルのイテレータを返し、その i 番目のタプルは引数シーケンスまたはイテラブルそれぞれの i 番目の要素を含みます。このイテレータは、入力イテラブルの中で最短のものが尽きたときに止まります。単一のイテラブル引数が与えられたときは、1 要素のタプルからなるイテレータを返します。引数がなければ、空のイテレータを返します。

今回のこの問題は問題文が曖昧であまり良い問題ではないのではないか？という話もdiscussで上がっている。
現にbadの評価もgoodより遥かに多いみたいで、あまり参考にはならないかもしれない。