侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【DFS, 回溯】火柴拼正方形

GabrielxD
2022-09-20 / 0 评论 / 0 点赞 / 32 阅读 / 1,186 字 / 正在检测是否收录...

题目

473. 火柴拼正方形


你将得到一个整数数组 matchsticks ,其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒,但你可以把它们连在一起,而且每根火柴棒必须 使用一次

如果你能使这个正方形,则返回 true ,否则返回 false

示例 1:

输入: matchsticks = [1,1,2,2,2]
输出: true
解释: 能拼成一个边长为2的正方形,每边两根火柴。

示例 2:

输入: matchsticks = [3,3,3,3,4]
输出: false
解释: 不能用所有火柴拼成一个正方形。

提示:

  • 1 <= matchsticks.length <= 15
  • 1 <= matchsticks[i] <= 10^8

解题

方法一:DFS 回溯 排序 剪枝

思路

先求出所有火柴的长度总和(sum),如果 sum 不是 44 的倍数那么一定不能拼成正方形,直接返回 false,否则记录每条边的长度(edgeLen=sum4edgeLen = \frac{sum}{4})。

然后就可以爆搜+回溯:对于每一根(idx)火柴,尝试放入每一条边(edges[i]),如果放入之后边的长度大于 edgeLen 就需要进行剪枝,否则继续枚举下一个火柴,如果之后的某根火柴无法被正确放置就需要回溯,退回到前一根火柴尝试下一条边,否则所有火柴都被放好就说明可以拼成正方形。

动画

参考:https://leetcode.cn/problems/matchsticks-to-square/solution/hui-su-suan-fa-jie-jue-ji-you-hua-chao-g-9iyl/

代码

DFS + 回溯 + 剪枝(超时)

class Solution {
    int n, edgeLen;
    int[] msArr, edges = new int[4];

    public boolean makesquare(int[] matchsticks) {
        int sum = 0;
        for (int len : matchsticks) sum += len;
        if (sum % 4 != 0) return false;
        edgeLen = sum / 4; 
        msArr = matchsticks;
        n = msArr.length;
        return dfs(0);
    }

    public boolean dfs(int idx) {
        if (idx == n && edges[0] == edgeLen && edges[1] == edgeLen &&
            edges[2] == edgeLen && edges[3] == edgeLen) return true;
        int curr = msArr[idx];
        for (int i = 0; i < 4; ++i) {
            if (edges[i] + curr > edgeLen) continue; 
            edges[i] += curr;
            if (edges[i] <= edgeLen && dfs(idx + 1)) return true;
            edges[i] -= curr;
        }
        return false;
    }
}

把火柴(matchsticks)降序排序可以有效的减少搜索量,因为如果火柴数组中前面有很多短火柴的话每次尝试都很难超过 edgeLen 造成多了很多错误的尝试,把较长的火柴放在前面可以提高剪枝率(通过)。

class Solution { 
    int edge_len, n;
    vector<int> ms_lens;
    vector<int> edges;

public:
    bool makesquare(vector<int>& matchsticks) {
        int sum = accumulate(matchsticks.begin(), matchsticks.end(), 0);
        if (sum % 4 != 0) return false;
        edge_len = sum / 4;
        n = matchsticks.size();
        ms_lens = matchsticks;
        sort(ms_lens.begin(), ms_lens.end(), greater<int>());
        edges.resize(4);
        return dfs(0);
    }

    bool dfs(int idx) {
        if (idx == n) return true;
        int& curr = ms_lens[idx];
        for (int i = 0; i < 4; ++i) {
            if (edges[i] + curr > edge_len) continue;
            edges[i] += curr;
            if (dfs(idx + 1)) return true;
            edges[i] -= curr;
        }
        return false;
    }
};

(Java int 数组不能方便的降序排序,于是升序排序反着搜索)。

class Solution {
    int edgeLen;
    int[] msArr, edges = new int[4];

    public boolean makesquare(int[] matchsticks) {
        int sum = 0;
        for (int len : matchsticks) sum += len;
        if (sum % 4 != 0) return false;
        edgeLen = sum / 4;
        msArr = matchsticks;
        Arrays.sort(msArr);
        return dfs(msArr.length - 1);
    }

    public boolean dfs(int idx) {
        if (idx == -1) return true;
        int curr = msArr[idx];
        for (int i = 0; i < 4; ++i) {
            if (edges[i] + curr > edgeLen) continue; 
            edges[i] += curr;
            if (dfs(idx - 1)) return true;
            edges[i] -= curr;
        }
        return false;
    }
}

剪枝:

if (i > 0 && edges[i] == edges[i - 1]) continue;

表示如果当前边与上一个边的长度相同,则跳过。
原因:如果边长相等,那么把当前火柴加入 edges[i] 加入 edges[i - 1] 递归的结果是一致的。

这个剪枝直接把运行时间从上百毫秒减少到了个位数:

image-20220920114131247

参考:https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/solution/by-lfool-d9o7/ 中的第二次尝试剪枝

class Solution {
    int edgeLen;
    int[] msArr, edges = new int[4];

    public boolean makesquare(int[] matchsticks) {
        int sum = 0;
        for (int len : matchsticks) sum += len;
        if (sum % 4 != 0) return false;
        edgeLen = sum / 4;
        msArr = matchsticks;
        Arrays.sort(msArr);
        return dfs(msArr.length - 1);
    }

    public boolean dfs(int idx) {
        if (idx == -1) return true;
        int curr = msArr[idx];
        for (int i = 0; i < 4; ++i) {
            if (edges[i] + curr > edgeLen ||
                i > 0 && edges[i] == edges[i - 1]) continue; 
            edges[i] += curr;
            if (edges[i] <= edgeLen && dfs(idx - 1)) return true;
            edges[i] -= curr;
        }
        return false;
    }
}
class Solution { 
    int edge_len, n;
    vector<int> ms_lens;
    vector<int> edges;

public:
    bool makesquare(vector<int>& matchsticks) {
        int sum = accumulate(matchsticks.begin(), matchsticks.end(), 0);
        if (sum % 4 != 0) return false;
        edge_len = sum / 4;
        n = matchsticks.size();
        ms_lens = matchsticks;
        sort(ms_lens.begin(), ms_lens.end(), greater<int>());
        edges.resize(4);
        return dfs(0);
    }

    bool dfs(int idx) {
        if (idx == n) return true;
        int& curr = ms_lens[idx];
        for (int i = 0; i < 4; ++i) {
            if (edges[i] + curr > edge_len ||
                i > 0 && edges[i] == edges[i - 1]) continue;
            edges[i] += curr;
            if (dfs(idx + 1)) return true;
            edges[i] -= curr;
        }
        return false;
    }
};
0

评论区