lintcode 题目记录3

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 string

    def expressionExpand(self, s):

        # Write your code here

        nl=[]

        sl=[]

        sc=''

        res=''

        lstr=''

        for i in s:

            if i.isdigit():

                if not lstr.isdigit():

                    sl.append(sc)

                    sc=''

                sc = sc + i

            else:

                if i=='[':

                    nl.append(int(sc))

                    sc = ''

                    sl.append('[')

                elif i==']':

                    n=nl.pop()

                    while len(sl)>0:

                        k=sl.pop()

                        if k== '[':break

                        sc = k+ sc

                    ts=''

                    for j in range(n):ts= ts + sc

                    sc=''

                    if len(nl) > 0:sl.append(ts)

                    else:

                        res = res + ts

                else:

                    if len(nl)>0:

                        sc = sc + i

                    else:

                        res = res + i

            lstr=i

        return 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 words

    def wordBreak(self, s, wordDict):

        # Write your code here

        head=[]

        ss=''

        for i in s:

            if ss=='':

                ss=i

            else:

                if i not in ss:

                    ss = ss + i

        for i in ss:

            flag=False

            for di in wordDict:

                if i in di:

                    flag=True

                    break;

            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)

                continue

            for 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 false

    def canPartition(self, nums):

        # Write your code here

        sum=0

        for n in nums:

            sum = sum +n

        if sum%2!=0:return False

        k=sum//2

        a=[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 0

                else:

                    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 True

        return False

巴特西

lintcode 题目记录3

Partition Equal Subset Sum

最新文章

热门文章