ゼロから始めるLeetCode Day39「494. Target Sum」

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

その対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。

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

Leetcode

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day38「208. Implement Trie (Prefix Tree)」

今はTop 100 Liked QuestionsのMediumを解いています。
Easyは全て解いたので気になる方は目次の方へどうぞ。

Twitterやってます。

問題

494. Target Sum

自然数の配列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を用意して実装しました。

良い感じで実装できたので、学習を続けて形に残しておくのは大事ですね。

今回はこのあたりで。おつかれさまでした。