Expression Expand Word Break II Partition Equal Subset Sum
#字串展開問題,依照[]前的數字展開字串,主要是維護兩個棧一個是展開個數棧一個是展開內容棧,內容棧添加[用來判斷是否把要展開的內容全部推出,然後要注意數字可能不止一位其他就無所謂了
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
單字切分問題,在陣列重從開頭的字串開始查找,找到了就加入棧,然後每次循環pop 判斷pop出的字串是否完整,完整加入結果,不完整找後續,能找到後續加入棧,沒有繼續下一次循環,這裡又一定歧義,wordDict裡邊的字符串是否可以重複使用的問題?
這玩意當字串很長後邊的字典數組很多的時候會很慢,暫時沒想到什麼優化的演算法,lintcode給的測試資料裡邊好像沒有這種情況只有一個特殊情況,所以前邊加了一個濾波算通過了,還有要注意python的startwith函數
如果參數是''總是回傳True略坑爹····
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
##
以上是lintcode 題目記錄3的詳細內容。更多資訊請關注PHP中文網其他相關文章!