[PYTHON] Lassen Sie Code Day 39 "494. Target Sum" von vorne beginnen

Überblick

Es scheint, dass Codierungstests in Ingenieurinterviews im Ausland durchgeführt werden, und in vielen Fällen besteht die Hauptsache darin, bestimmte Funktionen und Klassen entsprechend dem Thema zu implementieren.

Als Gegenmaßnahme scheint eine Website namens Let Code Maßnahmen zu ergreifen.

Eine Site, die algorithmische Leistung trainiert, die Codierungstests standhält, über die früh gesprochen wird.

Ich denke, es ist besser, die Algorithmuskraft eines Menschen zu haben, also werde ich das Problem unregelmäßig lösen und die Methode, die ich damals dachte, als Memo aufschreiben.

Leetcode

Leet Code-Tabelle ab Null

Letztes Mal Leet Code Day 38 ab Null "208. Implementieren Sie Trie (Präfixbaum)"

Im Moment löse ich das Medium mit den 100 beliebtesten Fragen. Easy wurde gelöst. Wenn Sie interessiert sind, gehen Sie bitte zum Tisch.

Twitter Ich mache es.

Problem

494. Target Sum

Gegeben das natürliche Zahlenarray "nums" und die natürliche Zahl "S". Addieren oder subtrahieren Sie bei + und- alle Arrays, um die Anzahl der Kombinationen zurückzugeben, die dem Wert von S entsprechen.

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.

Es ist so. Sie können anhand des Beispiels sehen, was ich sagen möchte.

Lösung

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

Zuerst habe ich es mit der Absicht geschrieben, es mit Bruteforce zu lösen, aber die Zeit ist abgelaufen.

Also habe ich es umgeschrieben.

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.

Leet Code Tag 25 "70. Klettertreppen" ab Null Mit dem angezeigten "@ lru_cache" habe ich jedoch "calc" als Hilfsfunktion vorbereitet und implementiert.

Ich konnte es mit einem guten Gefühl umsetzen, daher ist es wichtig, weiter zu lernen und es in Form zu lassen.

Diesmal hier. Danke für Ihre Unterstützung.