Maison >développement back-end >Tutoriel Python >enregistrement de questions lintcode 3
Expression Expand Word Break II Partition Equal Subset Sum
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
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!