Lintcode-Fragedatensatz 3

Ausdruck erweitern Wortumbruch II Partition Equal Subset Sum

Ausdruck erweitern

String-Erweiterungsproblem, entsprechend der Zahl vor [] erweitern Zeichenfolgen verwalten hauptsächlich zwei Stapel, einer dient zum Erweitern des Zahlenstapels und der andere zum Erweitern des Inhaltsstapels mehr als eine Ziffer, und der Rest spielt keine Rolle

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

Wortumbruch II

Wortumbruchproblem, Suche vom Anfang der Zeichenfolge im Array an, Fügen Sie es dem Stapel hinzu, wenn es gefunden wird, und führen Sie dann jedes Mal eine Schleife aus. Bestimmen Sie, ob die gepoppte Zeichenfolge vollständig ist, fügen Sie das Ergebnis hinzu, wenn es vollständig ist, und suchen Sie nach dem Follow-up, wenn es unvollständig ist. Fügen Sie es dem Stapel hinzu, ohne mit dem nächsten Zyklus fortzufahren. Hier muss eine Mehrdeutigkeit bestehen. Kann die Zeichenfolge in WordDict wiederverwendet werden?

Dieses Ding wird sehr langsam sein, wenn die Zeichenfolge sehr lang ist und sich viele Wörterbucharrays dahinter befinden. Derzeit scheint es keine solche Situation zu geben Von Lintcode bereitgestellte Testdaten gibt es nur in einem Sonderfall. Nach dem Hinzufügen eines Filters ist zu beachten, dass die Startwith-Funktion

immer True zurückgibt, was der Fall ist ein bisschen nervig...

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

Array-Gruppen-Summationsproblem In der Frage heißt es, dass die Bedingungen darin bestehen, dass viele Zahlen ganze Zahlen sind und 100 nicht überschreiten und die Array-Länge 200 nicht überschreitet. Verwenden Sie dazu einfach dynamische Programmierung, was eine vereinfachte Version des Rucksackproblems ist. Finden Sie zuerst die Summe von Wenn es sich um eine gerade Zahl handelt, kann sie in zwei Gruppen unterteilt werden. Andernfalls wird die endgültige Summe der Gruppen durch 2 ermittelt Das Problem besteht darin, dass die Zahlen im Array den Dingen ähneln, die in den Rucksack gesteckt werden müssen. Anders als beim Rucksackproblem ist es erforderlich, dass der Rasterwert gleich ist Diese Summe muss nicht bis zum Ende durchlaufen werden. Ein Gitter

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

Das obige ist der detaillierte Inhalt vonLintcode-Fragedatensatz 3. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!