火柴拼正方形(473)

一、题目描述

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

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

示例 1:

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

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

示例 2:

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

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

注意:

  1. 给定的火柴长度和在 010^9之间。
  2. 火柴数组的长度不超过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;
    }

}

2、C++ 代码

3、Python 代码

四、动画理解(没有声音)

发表评论

邮箱地址不会被公开。 必填项已用*标注

评论(2)