LeetCode473. Matchsticks to Squa

1、题目链接

https://leetcode.com/problems/matchsticks-to-square/

2、解题思路

这道题的意思是说有个卖火柴的小女孩，她有一些火柴（火柴的根数小于15），让你将她的火柴拼接成一个正方形，边可以用火柴叠加，但是火柴不能够折断，每一根火柴的长度都小于10的9次方（小女孩也是够厉害的，这么长的火柴），还有一个条件，火柴必须用完；首先可以肯定的是这些火柴的总长度一定是4的倍数，而且我们还能知道最终正方形的边长是多少，不要问我为什么知道>_<，其次，我们可以定义一个长度为4的数组来表示每个边的长度，然后递归遍历每一根火柴并将其加入到定义的边长数组中，然后和边长进行比较，递归结束的条件就是当四条边都相等，并且等于最先计算出来的边长，那么就返回true

3、代码

class Solution {
    public boolean makesquare(int[] nums) {
        if (null == nums || nums.length < 4) {
            return false;
        }

        Integer[] matchsticks = Arrays.stream(nums).boxed().toArray(Integer[]::new);
        int len = matchsticks.length;
        int[] eachSides = new int[4];
        /**
         * 因为要求每一根火柴都必须用到，所以火柴的总长度一定要是4的倍数，这里去除火柴总和不为4的倍数的情况
         */
        int total = 0;
        int eachSide;
        for (int i = 0; i < len; i++) {
            total += matchsticks[i];
        }
        if (total % 4 != 0) {
            return false;
        }
        eachSide = total / 4;
        
        //从大到小排序，过滤部分过长的火柴，以及我们优先用大的火柴，这样能避免做重复的操作
        Arrays.sort(matchsticks, (o1, o2) -> o2 - o1);

        return dfs(0, matchsticks, eachSide, eachSides);
    }
    
    public boolean dfs(int pos, Integer[] nums, int eachSide, int[] eachSides) {
        if (pos == nums.length) {
            return eachSides[0] == eachSides[1] && eachSides[1] == eachSides[2] && eachSides[2] == eachSides[3] && eachSides[0] == eachSide;
        }
        if (nums[pos] > eachSide) {
            return false;
        }
        //循环遍历每一一根火柴，将火柴放入长度为4的数组中
        for (int i = 0; i < 4; i++) {
            if (nums[pos] + eachSides[i] <= eachSide) {
                eachSides[i] += nums[pos];
                if (dfs(pos + 1, nums, eachSide, eachSides)) {
                    return true;
                }
                //不成立就减去上一步加的值
                eachSides[i] -= nums[pos];
            }
        }
        return false;
    }
}

4、结果

WX20190731-211335@2x.png