Luobuyu's Blog

0%

473.火柴拼正方形

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 2.2k 阅读时长 ≈ 2 分钟
排序，从大到小可以剪枝。

473.火柴拼正方形

题目描述：

一个整数数组 nums，表示火柴的长度。将所有的火柴拼成一个正方形。不能折断任何一根火柴，并且每根火柴都必须使用一次。

数据范围：
$ 1\le n \le 15,1\le nums[i]\le 10^8 $

题解：

可以对每一根火柴枚举边。也可以对边枚举火柴。

需要先进行排序剪枝，排序限制了分支的数量，可以大大减少分支数量。

对火柴枚举边：

需要创建一个长度为 $ 4 $ 的边数组，然后对每个火柴选择一个格子放进去，如果放入失败，那么长度相同的边则跳过，再次剪枝。

对边枚举火柴：

需要使用 mask 标记哪些火柴使用过。

剪枝操作：

  • 从大到小排序
  • 每条边内部，编号递增
  • 如果当前火柴放置失败
    • 跳过长度相同的火柴
    • 如果是第一个，则直接返回，剪掉该分支
    • 如果是最后一根，也剪掉该分支（如果最后一根用更短的火柴可以成功，那么之后用到这根火柴的地方与当前互换也会成功）

代码：

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const static int INF = 0x3f3f3f3f;
    bool dfs(int step, int len, vector<int> &nums, vector<int> &cur)
    {
        if (step == nums.size())
        {
            return true;
        }
        for (int i = 0; i < 4; ++i)
        {
            if (i > 0 && cur[i] == cur[i - 1])
                continue;

            if (cur[i] + nums[step] <= len)
            {
                cur[i] += nums[step];
                if (dfs(step + 1, len, nums, cur))
                    return true;
                else
                    cur[i] -= nums[step];
            }
        }
        return false;
    }
    bool makesquare(vector<int> &matchsticks)
    {
        int sum = 0;
        vector<int> cur(4);
        for (int i = 0; i < matchsticks.size(); ++i)
        {
            sum += matchsticks[i];
        }
        if (sum % 4)
            return false;
        int len = sum / 4;
        for (int i = 0; i < matchsticks.size(); ++i)
        {
            if (matchsticks[i] > len)
                return false;
        }
        sort(matchsticks.begin(), matchsticks.end(), greater<int>());
        return dfs(0, len, matchsticks, cur);
    }
};
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
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const static int INF = 0x3f3f3f3f;
    bool dfs(int step, int cur, int& len, vector<int> &nums, int mask, int cnt)
    {
        if (cnt == 3)
            return true;
        if (cur == len) return dfs(0, 0, len, nums, mask, cnt + 1);
        for (int i = step; i < nums.size(); ++i)
        {
            if (mask & (1 << i))
                continue;
            if (cur + nums[i] <= len)
            {
                if (dfs(i + 1, cur + nums[i], len, nums, mask | (1 << i), cnt))
                {
                    return true;
                }
                // 放置失败
                if (cur == 0 || cur + nums[i] == len)
                    return false;
            }
            while (i + 1 < nums.size() && nums[i + 1] == nums[i])
                i++;
        }
        return false;
    }
    bool makesquare(vector<int> &matchsticks)
    {
        int sum = 0;
        for (int i = 0; i < matchsticks.size(); ++i)
        {
            sum += matchsticks[i];
        }
        if (sum % 4)
            return false;
        int len = sum / 4;
        sort(matchsticks.begin(), matchsticks.end(), greater<int>());
        return dfs(0, 0, len, matchsticks, 0, 0);
    }
};

image-20230321115257497