当前位置:Gxlcms > Python > lintcode题目记录3

lintcode题目记录3

时间:2021-07-01 10:21:17 帮助过:43人阅读

Expression Expand Word Break II Partition Equal Subset Sum

Expression Expand

字符串展开问题,按照[]前的数字展开字符串,主要是维护两个栈一个是展开个数栈一个是展开内容栈,内容栈添加[用来判断是否把要展开的内容全部推出,然后要注意数字可能不止一位其他就无所谓了

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

Partition Equal Subset Sum

数组分组求和问题,题目说条件很多 数字都是整数不超过100 数组长度不超过200,就是让用动态规划来做,就是背包问题的简化版,先求所有数字的和,为偶数才能分成两组,否则直接返回false,然后除以2求最终要分组的和,这个值就类似背包问题的容量,数组中的数字就类似要装进背包的东西,不同于背包问题的是背包问题要遍历到最后一个格子,这里只有又格子值与这个和相等就行了,不一定要遍历到最后一个格子

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的详细内容,更多请关注Gxl网其它相关文章!

人气教程排行