ゼロから始めるLeetCode Day10 「1431. Kids With the Greatest Number of Candies」

概要

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

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

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

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

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

Leetcode

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

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day9「701. Insert into a Binary Search Tree」
次回
ゼロから始めるLeetCode Day11 「1315. Sum of Nodes with Even-Valued Grandparent」

問題

1431. Kids With the Greatest Number of Candies

配列candiesと数値のextraCandiesが与えられます。candies[i]はi番目の子供が持っているキャンディの数です。
それぞれの子供に子供たちの中で最大数のキャンディーを持つことができるように子供たちにextraCandyを配布する方法があるかどうかを確認します。

問題だけだと少しわかりにくいですね・・・
実際の例を見た方が良さそうです。

Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true] 

一番最初の子の場合は元から持っているキャンディー2個にextraCandiesの3個を与えた場合、2+3で5になり、candiesの中で最大値である5に並ぶため、trueとなります。
二番目、三番目、五番目の子についても同様のことがいえます。

唯一Falseなのは仮に3個のextraCandiesを与えられても4個にしかならず、配列の中の最大値である5に届かない四番目の子です。

それぞれの配列の数字にextraCandiesの値を足した後に配列の中の最大値と比較し、最大値以上であればTrueを、未満であればFalseをcandiesに代入し、その流れを一通り回した後にcandiesを返すような関数であれば条件を満たしそうです。

まずは再帰と分岐だけで書いてみた例

class Solution:
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
        num = max(candies)
        for i in range(len(candies)):
            if candies[i] + extraCandies >= num:
                candies[i] = True
            else:
                candies[i] = False
        return candies
# Runtime: 64 ms, faster than 33.33% of Python3 online submissions for Kids With the Greatest Number of Candies.
# Memory Usage: 13.6 MB, less than 100.00% of Python3 online submissions for Kids With the Greatest Number of Candies.

超シンプルです。ただこれだとあまり速くないですし、もっと簡略化したいですね。
ここでの省略できる部分を考えてみると、for文以降のif分岐が少し冗長かなと思います。

class Solution:
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
        num = max(candies)
        return [candy + extraCandies >= num for candy in candies]
# Runtime: 48 ms, faster than 33.33% of Python3 online submissions for Kids With the Greatest Number of Candies.
# Memory Usage: 14 MB, less than 100.00% of Python3 online submissions for Kids With the Greatest Number of Candies.

こう書き換えてみます。少し速くなりましたね。
returnの後に続いているのはリスト内包表記というもので、
[ 式 for 変数 in オブジェクト ]
という書き方をすることができるというものです。

内包表記には他にも、
セット { 式 for 変数 in オブジェクト }
辞書 { キー式: 値式 for k,v in オブジェクト }
ジェネレーター　( 式 for 変数 in オブジェクト )
といった物もあるので、興味がある場合は以下のドキュメントを参考にすると良いです。

6. 式 (expression)

なお、内包表記の速度に関する興味深い記事として以下のような物がありました。
時間があるときにチェックするといいかもしれません。

Pythonのリスト内包表記の速度