【JAVA】【刷题子】473. 火柴拼正方形_南方者

theme: smartblue highlight: monokai

持续创作，加速成长！这是我参与「掘金日新计划 · 6 月更文挑战」的第9天，点击查看活动详情

一、题目与题目分析

题目

你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用所有的火柴棍拼成一个正方形。你不能折断任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须使用一次。
　　如果你能使这个正方形，则返回 true ，否则返回 false 。
（题目来源：力扣：473. 火柴拼正方形）

题目分析

就是给一些固定长度的线段，判断这些线段是否能组成正方形。
　　问题简单化，先把干扰的排除掉。
　　首先，要清楚的是，形成正方形的条件：4条长度一样的边。
　　因此，就演变成两个条件：① 边长4条. ② 每条边长都相等。

二、整体逻辑与主要代码

题目分析已经比较清楚了，接下来我们进入代码设计。

整体逻辑

首先，整体逻辑先把干扰的排除掉。① 把达不到4条线段的排除。 ② 把所有的线段长加起来，加起来的和不能被4整除的（也就是和对4求余不等于0的）也排除。 ③ 检查组成的正方形，前提是否基于在限制固定长度下的线段。

主要代码

整体逻辑也清晰了，也有较清楚的注释。直接来看代码吧！（如有不懂的或者更好的建议，欢迎评论区分享友友的看法哈~） ```java class Solution { public boolean makesquare(int[] matchsticks) { int len = matchsticks.length; // 达不到4条线段的排除 if (len < 4) { return false; } int sum = 0; for (int m : matchsticks) { sum += m; } // 所有的线段长加起来，加起来的和不能被4整除的排除 if (sum % 4 != 0) { return false; } // 检查组成的正方形，前提是否基于在限制固定长度下的线段 int avg = sum / 4; // 平均值 // 排序（升序） Arrays.sort(matchsticks); // 迭代的方法会从排序后的数，最后一个开始回溯（形成倒序，也就是会从最大的开始判断） int[] newNums = new int[4]; // 定义对应的四条边 int back = len - 1; // 从最后一个开始回溯 return checkSquare(matchsticks, back, newNums, avg); }

// 迭代进行判断
public boolean checkSquare(int[] nums, int back, int[] newNums, int avg) {
    if (back == -1) { // 最底层出口
        // 已经到底部了，判断前三条边是否等于平均值；（一共四条边，前三条等于平均值，第四条也等于平均值了。）
        return newNums[0] == avg && newNums[1] == avg && newNums[2] == avg;
    }
    for (int i = 0; i < 4; i++) { // 计算四条边
        if (newNums[i] + nums[back] > avg) { // 组合的边是否超出平均值
            continue;
        }
        // 组合边长
        newNums[i] += nums[back];
        // 迭代追溯到最低
        if (checkSquare(nums, back - 1, newNums, avg)) {
            return true;
        }
        // 不符合的不要
        newNums[i] -= nums[back];
    }
    return false;
}

} ```

三、结果展示

四、总结

问题很难，解决问题可能更难；别怕，大不了难上加难！

题目数据库

Gitee：传送门

文章小尾巴

文章写作、模板、文章小尾巴可参考：《写作“小心思”》
　　感谢你看到最后，最后再说两点~
　　①如果你持有不同的看法，欢迎你在文章下方进行留言、评论。
　　②如果对你有帮助，或者你认可的话，欢迎给个小点赞，支持一下~
　　我是南方者，一个热爱计算机更热爱祖国的南方人。

　　（文章内容仅供学习参考，如有侵权，非常抱歉，请立即联系作者删除。）