Ausdruck erweitern Wortumbruch II Partition Equal Subset Sum
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 resWortumbruch 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
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!
