enregistrement de questions lintcode 3

Expression Expand Word Break II Partition Equal Subset Sum

Expression Expand

Problème d'expansion de chaîne, développez en fonction du nombre avant [] Les chaînes maintiennent principalement deux piles, l'une consiste à étendre la pile de nombres et l'autre à étendre la pile de contenu. La pile de contenu est ajoutée [pour déterminer s'il faut extraire tout le contenu à développer, puis notez que le nombre peut être. plus d'un chiffre, et le reste n'a pas d'importance

class Solution:# @param {string} s  an expression includes numbers, letters and brackets# @return {string} a stringdef expressionExpand(self, s):# Write your code herenl=[]
        sl=[]
        sc=''res=''lstr=''for i in s:if i.isdigit():if not lstr.isdigit():
                    sl.append(sc)
                    sc=''sc = sc + ielse:if i=='[':
                    nl.append(int(sc))
                    sc = ''sl.append('[')elif i==']':
                    n=nl.pop()while len(sl)>0:
                        k=sl.pop()if k== '[':breaksc = k+ sc
                    ts=''for j in range(n):ts= ts + sc
                    sc=''if len(nl) > 0:sl.append(ts)else:
                        res = res + tselse:if len(nl)>0:
                        sc = sc + ielse:
                        res = res + i
            lstr=ireturn res

Word Break II

Problème de saut de mot, recherche à partir du début de la chaîne dans le tableau, ajoutez-le à la pile une fois trouvé, puis faites une boucle à chaque fois. Déterminez si la chaîne sautée est complète, ajoutez le résultat si elle est complète et recherchez le suivi si elle est incomplète. Si vous pouvez trouver le suivi, ajoutez-le à la pile sans passer au cycle suivant. Il doit y avoir une ambiguïté ici. La chaîne dans wordDict peut-elle être réutilisée ?

Cette chose sera très lente lorsque la chaîne est très longue et qu'il y a de nombreux tableaux de dictionnaires derrière elle. Je n'ai pensé à aucun algorithme optimisé pour le moment. Il ne semble pas y avoir de telle situation dans le cas. données de test fournies par lintcode. Il n'y a qu'un seul cas particulier, donc le précédent Après avoir ajouté un filtre, il a réussi. Veuillez également noter que la fonction startwith de python

renvoie toujours True si le paramètre est '', ce qui est. un peu ennuyeux...

class Solution:# @param {string} s a string# @param {set[str]} wordDict a set of wordsdef wordBreak(self, s, wordDict):# Write your code herehead=[]
        ss=''for i in s:if ss=='':
                ss=ielse:if i not in ss:
                    ss = ss + ifor i in ss:
            flag=Falsefor di in wordDict:if i in di:
                    flag=Truebreak;if not flag:return []for di in wordDict:if di !='' and  s.startswith(di):
                head.append(di)if len(head)<1:return []
        cur=s
        res=[]while len(head)>0:
            h=head.pop()
            le=len(h.replace(' ',''))
            cur=s[le:]if cur == '': 
                res.append(h)continuefor di in wordDict:if cur.startswith(di):
                    head.append(h+' '+di)                    return res

Partition Equal Subset Sum

Problème de sommation de groupe de tableaux , la question dit que les conditions sont que de nombreux nombres soient des entiers et ne dépassent pas 100 et que la longueur du tableau ne dépasse pas 200. Utilisez simplement la programmation dynamique pour le faire, qui est une version simplifiée du problème du sac à dos. Trouvez d'abord la somme de. tous les nombres. S'il s'agit d'un nombre pair, il peut être divisé en deux groupes. Sinon, il renvoie directement false, puis divise par 2 pour trouver la somme finale des groupes. le problème, les nombres dans le tableau sont similaires aux éléments qui doivent être mis dans le sac à dos. Différent du problème du sac à dos, le problème du sac à dos nécessite de passer à la dernière grille. Ici, il suffit que la valeur de la grille soit égale à. cette somme, et il n'est pas nécessaire de la parcourir jusqu'au bout. Une grille

class Solution:# @param {int[]} nums a non-empty array only positive integers# @return {boolean} return true if can partition or falsedef canPartition(self, nums):# Write your code heresum=0for n in nums:
            sum = sum +nif sum%2!=0:return False
        k=sum//2a=[None]*len(nums)for i in range(len(nums)):
            a[i]=[0]*k            for i in range(len(nums)):for j in range(k):if i == 0:
                    a[i][j] = nums[i] if nums[i] < j+1 else 0else:if nums[i]> j+1:
                        a[i][j]=a[i-1][j]else:
                        a[i][j]=max(nums[i]+a[i-1][j+1-nums[i]],a[i-1][j])                        if a[i][j] ==k:return Truereturn False

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!