LeetCode daily #2094. Finding 3-Digit Even Numbers

【LeetCode #2094】Finding 3-Digit Even Numbers

はじめに

平日の daily が easy 問題だと安心しますね．
今日も easy 問題でした．なので 2 つほど解き方をご紹介します．

問題概要

与えられた配列の要素を用いて下記の条件を満たす 3 桁の数値を昇順で返す問題です．

• 数値は配列内の要素から 3 つの値を連結して作る
• 0 が先頭に来ない
• 偶数

例

入力： digits = [2, 1, 3, 0]
出力： [102, 120, 130, 132, 210, 230, 302, 310, 312, 320]

カテゴリ

問題難易度：easy
タグ：Array, Hash Table, Sorting, Enumeration

解法①：全候補から条件を満たすもののみ抽出

こちらは，与えられた digits から作成できる 3 桁の組み合わせを全パターン作成し，条件を満たすものを抽出していく手法です．つまり，

• 先頭が 0 の数字
• 末尾が 2 で割り切れない数字

を除去したものを答えとします．

組み合わせパターン列挙には permutations を使用します．

class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]:
        results = set()
        
        for p in permutations(digits, 3):
            if p[0] == 0:
                continue
            if p[2] % 2 != 0:
                continue
            num = p[0]*100 + p[1]*10 + p[2]
            results.add(num)
        
        return sorted(results)

digits の中から 3 つの数字を選び，「先頭が 0 でない」かつ「末尾が 2 で割り切れる」数値を set() に格納していきます．set() なのでユニークに格納でき，最後に sorted() をして返します．

ご想像の通り，列挙の数も多いですし，sort もするのでとっても遅いです．

解法②：100 ~ 999 までの数値を作れるかチェックする方法

先ほどは与えられた配列の要素で作成できるパターンを全列挙し，条件を満たすかチェックしました．
こちらの方法では，100 ~ 999 の値を順に走査し，配列内の要素で作成できるかをチェックします．

予め，digits 内の値の出現回数を記録しておき，その後 100 ~ 999 の値を生成できるかチェックします．

class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]:
        count = Counter()
        for d in digits:
            count[str(d)] += 1
        ans = []
        for n in range(100, 999, 2):
            tmp = [i for i in str(n)]
            tmpc = Counter(tmp)
            if all(count[k] >= v for k, v in tmpc.items()):
                ans.append(n)
        return ans

range(100, 999, 2) により，偶数のみを作成できます．
また，100 開始なので，先頭 0 も回避することができます．
解法①と比較すると，圧倒的にこちらの方が高速です．

まとめ

本日も easy 問題をご紹介しました．
解き方によって速度もかなり変わってくるので，1 つの解き方だけでなく複数の解法を書けるようにしておくと，実務でも役立つかもしれませんね．
ではまた別の問題で〜．