概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。
と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。
ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
Python3で解いています。
前回
ゼロから始めるLeetCode Day97 「349. Intersection of Two Arrays」
Twitterやってます。
技術ブログ始めました！！
技術はLeetCode、Django、Nuxt、あたりについて書くと思います。こちらの方が更新は早いので、よければブクマよろしくお願いいたします！
お知らせ
Day 100でQiitaでの投稿はひとまず区切りを付けようかと思います。
タグの記事が僕の記事ばかりになってしまうのもいかがなものかと思いましたし、他に有益な情報を提供している方の邪魔になってしまうこともあると考えたので、こうすることにしました。
至らない部分は多々ありましたが、今までお付き合い頂きありがとうございました。
問題を解いて記事を書く、というのは上記の個人ブログで続けるつもりですし、興味ある方はたまにそちらを覗いていただけると嬉しいです。
Twitterの方のアカウントはほとんど更新通知用と化しているので、Leetcodeを解く記事について気になる方はそちらも合わせてフォローいただくと良いかもしれません。
問題
39. Combination Sum
難易度はMedium。
コーディング面接対策のために解きたいLeetCode 60問からの抜粋です。
問題としては、候補番号（候補）（重複なし）と目標番号（目標）の集合が与えられたとき、候補番号の和が目標になるような、候補の中のすべてのユニークな組み合わせを求めなさい、というものです。
なお、同じ繰り返し数は何度でもいいとします。
Example 1:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]Example 2:
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
解法
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
ans = []
def dfs(cur,left,num):
if left == 0:
ans.append(cur+[])
return
for i in range(num,len(candidates)):
if left-candidates[i] >= 0:
cur.append(candidates[i])
dfs(cur,left-candidates[i],i)
cur.pop()
dfs([],target,0)
return ans
# Runtime: 84 ms, faster than 63.61% of Python3 online submissions for Combination Sum.
# Memory Usage: 14.1 MB, less than 11.55% of Python3 online submissions for Combination Sum.
ゼロから始めるLeetCode Day96 「78. Subsets」と似た内容になっています。
dfsを実装し、長さ分リストを回す、というものです。
こちらも再帰的な書き方ではなくdfsを実装し、それを呼び出すだけでansに値が代入されるようになっています。
では今回はここまで。お疲れ様でした。