【leetcode】473. Matchsticks to Square

题目如下：

解题思路：居然把卖火柴的小女孩都搬出来了。题目的意思是输入一个数组，判断能否把数组分成四个子数组，使得每个子数组的和相等。首先我们可以很容易的求出每个子数组的和应该是avg = sum(nums)/4，接下来我的思路是求出nums中所有和等于avg的子数组，子数组中保存元素下标，然后找出四个不存在相同下标的子数组求并集，如果并集长度刚好等于len(nums),那么就是符合条件的，返回true。如果在子数组列表中找到四个符合条件的子数组，我用的是DFS，为什么不用BFS？因为题目要求是找到一组符合条件的子数组即可，DFS显然要比BFS快。

代码如下：

class Solution(object):

    def makesquare(self, nums):

        """

        :type nums: List[int]

        :rtype: bool

        """

        nums.sort()

        border = 4

        if sum(nums)%border != 0 :

            return False

        avg = sum(nums)/border

        queue = [[x] for x in xrange(len(nums))]

        res = []

        visit = [0 for x in xrange(len(nums))]

        while len(queue) > 0:

            nl = queue.pop(0)

            amount = 0

            for i in nl:

                amount += nums[i]

            if amount == avg:

                res.append(nl)

                for i in nl:

                    visit[i] = 1

                continue

            tl = []

            for i in xrange(nl[-1]+1,len(nums)):

                if amount + nums[i] <= avg:

                    tl = nl[:]

                    tl.append(i)

                    queue.append(tl)

        if len(res) < border:

            return False

        if sum(visit) != len(visit):

            return False

        queue = []

        for i in res:

            queue.append((set(i),1))

        #print queue

        while len(queue) > 0:

            ns,count = queue.pop(0)

            if count == border and len(ns) == len(nums):

                #print ns

                return True

            for i in res:

                #print ns | set(i)

                if len(ns | set(i)) == len(ns) + len(i):

                    queue.insert(0,(ns|set(i),count+1))

        return False

巴特西

【leetcode】473. Matchsticks to Square

最新文章

热门文章