0473. 火柴拼正方形

0473. 火柴拼正方形 #

  • 标签:位运算、数组、动态规划、回溯、状态压缩
  • 难度:中等

题目大意 #

给定一个表示火柴长度的数组 matchsticks,其中 matchsticks[i] 表示第 i 根火柴的长度。

要求:找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴,可以将火柴连接起来,并且每根火柴都要用到。如果能拼成正方形,则返回 True,否则返回 False

解题思路 #

  • 先排除数组为空和火柴总长度不是 4 的倍数的情况,直接返回 False
  • 然后将火柴按照从大到小排序。用数组 sums 记录四个边长分组情况。
  • 将火柴分为四组,把每一根火柴依次向 4 条边上放。直到放置最后一根,判断能否构成正方形,若能构成正方形,则返回 True,否则返回 False

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def dfs(self, index, sums, matchsticks, size, side_len):
        if index == size:
            return sums[0] == sums[1] == sums[2] == side_len

        for i in range(4):
            if sums[i] + matchsticks[index] <= side_len:
                sums[i] += matchsticks[index]
                if self.dfs(index + 1, sums, matchsticks, size, side_len):
                    return True
                sums[i] -= matchsticks[index]
        return False

    def makesquare(self, matchsticks: List[int]) -> bool:
        if not matchsticks:
            return False
        size = len(matchsticks)
        sum_len = sum(matchsticks)
        if sum_len % 4 != 0:
            return False

        side_len = sum_len // 4
        matchsticks.sort(reverse=True)

        sums = [0 for _ in range(4)]
        return self.dfs(0, sums, matchsticks, size, side_len)
本站总访问量  次  |  您是本站第  位访问者