0473. 火柴拼正方形

题目地址(473. 火柴拼正方形)

https://leetcode-cn.com/problems/matchsticks-to-square/

题目描述

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

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

示例 1:

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

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


示例 2:

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

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


注意:

给定的火柴长度和在 0 到 10^9之间。
火柴数组的长度不超过15。

前置知识

  • 回溯

  • 剪枝

公司

  • 暂无

思路

题目规定了火柴数组的长度不超过 15,基本就可以锁定为回溯题目。

为什么?不清楚的可以看下我写的这篇文章

这道题我们可以使用长度为 4 的 sides 数组存储已经排好的火柴的边的情况。显然,如果能找到一个令任意 sides[i] 都等于 side 的组合就返回 True,否则返回 False。其中 side 为火柴长度总和的四分之一。

这提示我们使用回溯找到所有的 sides 的可行组合,从 sides[0] 开始枚举所有放置可能,接下来放置 sides[1] ...。

这里有两个剪枝:

  • 如果火柴长度之和不是四的倍数,直接可以返回 False。这是显然的。

  • 我们可以对火柴进行降序排序,并从头开始选择放置,这在火柴长度分布不均匀的时候极为有效。这算是带权值的放置型回溯的一个固定套路把。这是因为如果先放一个权值大的,那么选择就会少很多,因此递归树的规模就会小很多。

关键点

  • 如果火柴和不是 4 的倍数,需要剪枝。

  • 降序排序,优先选择权值大的可以介绍搜索树的规模。这是放置型回溯的常见的固定套路之一。

代码

  • 语言支持:Python3

Python3 Code:


class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        side = sum(matchsticks) // 4
        sides = [0] * 4
        # 剪枝处理
        if side * 4 != sum(matchsticks):
            return False

        matchsticks.sort(reverse=True)
        #  带权值的放置型回溯,有一个剪枝套路就是进行一次降序排序。
        # 由于:
        # 1. 性能瓶颈不在排序,并且先放大的可以有效减少极端情况下的执行次数,因此剪枝效果很棒。
        # 2. 既然都回溯了,那么顺序也是无所谓的,因此打乱顺序无所谓。 而如果真的顺序有所谓,我们也可以排序后记录下排序前的索引也帮不难。
        # 3. 优先选择大的,这样可选择变少了,可以有效减少递归树节点的个数,进而使得搜索时间大大降低。
        def backtrack(i):
            if i == len(matchsticks):
                return sides[0] == sides[1] == sides[2] == sides[3] == side
            for j in range(4):
                if sides[j] + matchsticks[i] <= side:
                    sides[j] += matchsticks[i]
                    if backtrack(i + 1):
                        return True
                    sides[j] -= matchsticks[i]
            return False

        return backtrack(0)

复杂度分析

令 n 为数组长度。

  • 时间复杂度:$O(2^n)$

  • 空间复杂度:$O(2^n)$

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。

最后更新于