Python|火柴拼正方形-回溯法

原创
09/08 00:00
阅读数 25

本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列文章。

问题描述

还记得童话《卖火柴的小女孩》吗?现在,你知道小女孩有多少根火柴,请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴,可以把火柴连接起来,并且每根火柴都要用到。

输入为小女孩拥有火柴的数目,每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。

示例 1:

输入: [1,1,2,2,2]

输出: true

解释: 能拼成一个边长为2的正方形,每边两根火柴。

示例 2:

输入: [3,3,3,3,4]

输出: false

解释: 不能用所有火柴拼成一个正方形。


解决方案

新建立一个长为4的列表存储火柴,因为这里使用的是回溯,所以火柴按由大到小的顺序存储,这样可以减少回溯可能。在火柴全部存储后,就可以判断列表中四个小列表之和是否相等,如果都相等,证明可以拼成正方形。

在写代码的时候,先判断输入数组中火柴的总和%4是否为0,这是数组里火柴能否拼成正方形的先决条件。其次,在运行代码时,新建列表中的小列表之和不可超过总和长度的1/4。利用这些条件可以使代码的时间和空间复杂度很大程度的优化。

完整代码:

def makequre(nums):

    nums_sum = sum(nums)

    # 数组长度小于4或者数组总和对4取余不为0

    if len(nums) < 4 or nums_sum % 4 != 0:

        return False

    # 从大到小排序

    nums = sorted(nums, reverse=True)

    # 储存火柴

    nums2 = [[] for i in range(4)]

return helper(0, nums, nums_sum//4, nums2)

def helper(i, nums, result, nums2):

    if i >= len(nums):

        return [[result] for i in range(4)]

    for j in range(4):

        # 每条边上存储的火柴不超过数组总和的1/4

        if sum(nums2[j]) + nums[i] > result:

            continue

        nums2[j].append(nums[i])

        if helper(i+1, nums, result, nums2):

            return True

        nums2[j].pop()

    return False


结语

这道题虽然可以使用回溯法做出来,但这样做出来的代码的时间和空间复杂度还是比较高,特别是时间复杂度。但是回溯法的优势在于能适时“回头”,若再往前走不可能得到解,就回溯,退一步另找其他可能,这样可省去大量的无效操作。



主编:  王文星

稿件来源:深度学习与文旅应用实验室(DLETA)

本文分享自微信公众号 - 算法与编程之美(algo_coding)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部