火柴拼正方形(473)
一、题目描述
还记得童话《卖火柴的小女孩》吗?现在,你知道小女孩有多少根火柴,请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴,可以把火柴连接起来,并且每根火柴都要用到。
输入为小女孩拥有火柴的数目,每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。
示例 1:
输入: [1,1,2,2,2]
输出: true
解释: 能拼成一个边长为2的正方形,每边两根火柴
示例 2:
输入: [3,3,3,3,4]
输出: false
解释: 不能用所有火柴拼成一个正方形。
注意:
- 给定的火柴长度和在
0
到10^9
之间。 - 火柴数组的长度不超过15。
二、题目解析
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 火柴拼正方形(473) : https://leetcode-cn.com/problems/matchsticks-to-square/
class Solution {
public boolean makesquare(int[] matchsticks) {
// 火柴的数量小于了 4
if(matchsticks.length < 4) {
// 那必然无法拼凑成正方形
return false;
}
// 存储所有火柴的总长度
int sum = 0;
// 存储所有火柴的总长度
for(int i = 0 ; i < matchsticks.length ; i++){
sum += matchsticks[i];
}
// 如果发现总长度无法被 4 整除
if(sum % 4 != 0){
// 那必然无法拼凑成正方形
return false;
}
// 先将数组从小到大排序
Arrays.sort(matchsticks);
// 设置 4 个桶,每个桶的高度一开始都是 0
int[] bucket = new int[]{0,0,0,0};
// 接下来开始往桶里面放置火柴
// 注意:我们是从最大的火柴开始尝试的,所以是从 matchsticks.length - 1 开始尝试
return backtrack(matchsticks,matchsticks.length - 1,sum / 4 ,bucket);
}
// nums 存储火柴的长度
// index 表示正在放置的火柴下标
// target 表示能拼凑成功的正方形的边长
// bucket 存储 4 个桶的高度
private boolean backtrack(int[] nums, int index, int target, int[] bucket) {
// 如果全部的火柴都放到了 4 个桶中
if( index <= -1){
// 那么这 4 个桶中的火柴能拼凑成一个正方形
return true;
}
// 遍历这 4 个桶
for(int i = 0 ; i < 4 ; i++){
// 如果下标位置为 index 的这根火柴放入到第 i 个桶的时候高度超过了 target
// 这就代表无法把下标位置为 index 的这根火柴放入到第 i 个桶
if(bucket[i] + nums[index] > target ){
// 不执行下面的语句,而是去尝试放入到下一个桶
continue;
}
// 否则的话,把下标位置为 index 的这根火柴放入到第 i 个桶
// 此时,bucket[i] 的高度就需要加上 nums[index]
bucket[i] += nums[index];
// 接下来递归的放置下一根火柴
if(backtrack(nums, index - 1 ,target,bucket) ){
// 如果下一个根火柴放置成功,那么直接返回 true
return true;
}
// 否则的话,说明把下标位置为 index 的这根火柴放入到第 i 个桶后
// 后面的火柴无法放置成功,那么需要将 num[index] 从桶 i 中拿出
bucket[i] -= nums[index];
}
// 下标位置为 index 的这根火柴无法放入任何一个桶,那么返回 false
return false;
}
}