LeetCode473-火柴拼正方形

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/matchsticks-to-square/

中文链接：https://leetcode-cn.com/problems/matchsticks-to-square/

题目详述

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

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

示例 1:

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

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

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

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

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

题目详解

  • 先判断火柴长度总和是否能被 4 整除，如果不能直接返回 false。
  • 对每一根火柴进行递归调用，枚举火柴分别放在 1、2、3、4 条边上的情况。每次枚举的时候，判断当前长度和加上火柴长度是否大于正方形边长，如果大于就不用往下递归了。并且可以先对火柴按照长度进行排序，从大到小遍历，缩短递归深度。
  • 当 3 条边的边长都满足条件时，说明第四条边也满足条件，返回 true。
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
27
28
29
30
31
public class LeetCode_00473 {

    public boolean makesquare(int[] nums) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int sum = Arrays.stream(nums).sum();
        if (sum % 4 != 0) {
            return false;
        }
        Arrays.sort(nums);
        int[] lens = new int[4];
        return dfs(nums, nums.length - 1, lens, sum / 4);
    }

    private boolean dfs(int[] nums, int index, int[] lens, int len) {
        if (lens[0] == len && lens[1] == len && lens[2] == len) {
            return true;
        }
        for (int i = 0; i < 4; ++i) {
            if (lens[i] + nums[index] <= len) {
                lens[i] += nums[index];
                if (dfs(nums, index - 1, lens, len)) {
                    return true;
                }
                lens[i] -= nums[index];
            }
        }
        return false;
    }
}