[PYTHON] Let Code Day 39 "494. Target Sum" à partir de zéro

Aperçu

Il semble que des tests de codage soient menés à l'étranger lors d'entretiens d'ingénieurs, et dans de nombreux cas, l'essentiel est d'implémenter des fonctions et des classes spécifiques en fonction du thème.

En guise de contre-mesure, il semble qu'un site appelé Let Code prendra des mesures.

Un site qui forme une puissance algorithmique capable de résister aux tests de codage dont on parle très tôt.

Je pense qu'il vaut mieux avoir la puissance de l'algorithme d'un être humain, donc je vais résoudre le problème de manière irrégulière et écrire la méthode que j'ai pensé à ce moment-là sous forme de mémo.

Leetcode

Table de codes Leet commençant à zéro

Dernière fois Leet Code Day 38 commençant à zéro "208. Implement Trie (Prefix Tree)"

En ce moment, je résous le support des 100 questions les plus appréciées Easy a été résolu, donc si vous êtes intéressé, veuillez vous rendre à la table.

Twitter Je le fais.

problème

494. Target Sum

Étant donné le tableau de nombres naturels «nums» et le nombre naturel «S». Étant donné + et-, ajoutez ou soustrayez tous les tableaux pour renvoyer le nombre de combinaisons qui correspondent à la valeur de 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.

C'est comme ça. Vous pouvez voir ce que je veux dire à partir de l'exemple.

Solution

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

Au début, je l'ai écrit avec l'intention de le résoudre avec Bruteforce, mais le temps est écoulé.

Alors je l'ai réécrit.

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 Day 25 "70. Climbing Stairs" à partir de zéro Cependant, en utilisant le @ lru_cache qui est apparu, j'ai préparé et implémenté calc comme fonction d'assistance.

J'ai pu le mettre en œuvre avec un bon feeling, il est donc important de continuer à apprendre et de le laisser en forme.

Cette fois par ici. Merci pour votre soutien.