ゼロから始めるLeetCode Day39「494. Target Sum」
概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。
と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。
ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
Python3で解いています。
Twitterやってます。
前回
ゼロから始めるLeetCode Day38「208. Implement Trie (Prefix Tree)」
次回
ゼロから始めるLeetCode Day40「114. Flatten Binary Tree to Linked List」
Twitterやってます。
問題
自然数の配列numsと自然数Sが与えられます。
+と-が与えられるので、配列を全て足すか引いてSの値と一致させるような組み合わせの数を返してください。
Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
There are 5 ways to assign symbols to make the sum of nums be target 3.
こんな感じです。
言いたいことは例から分かると思います。
解法
class Solution:
def calc(self,nums,index,sums,S):
if index == len(nums):
if sums == S:
self.count += 1
else:
self.calc(nums,index+1,sums+nums[index],S)
self.calc(nums,index+1,sums-nums[index],S)
def findTargetSumWays(self, nums: List[int], S: int) -> int:
self.count = 0
self.calc(nums,0,0,S)
return self.count
# Time Limit Exceeded
最初Bruteforceで解こうと思って書いたのですが時間切れになっちゃいました。
なので書き換えました。
from functools import lru_cache
class Solution:
def findTargetSumWays(self, nums: List[int], S: int) -> int:
@lru_cache(None)
def calc(index,S):
if index == 0:
return int(nums[0] == S) + int(-nums[0] == S)
return calc(index-1, S - nums[index]) + calc(index-1, S + nums[index])
return calc(len(nums)-1, S)
# Runtime: 240 ms, faster than 74.28% of Python3 online submissions for Target Sum.
# Memory Usage: 31.5 MB, less than 50.00% of Python3 online submissions for Target Sum.
ゼロから始めるLeetCode Day25「70. Climbing Stairs」
でも登場した@lru_cacheを使ってヘルパー関数としてcalcを用意して実装しました。
良い感じで実装できたので、学習を続けて形に残しておくのは大事ですね。
今回はこのあたりで。おつかれさまでした。
コメント
コメントを投稿