LeetCode Matchsticks to Square

· 624 words · 2 minute read
2017年7月
LeetCode

473. Matchsticks to Square

Remember the story of Little Match Girl? By now, you know exactly what matchsticks the little match girl has, please find out a way you can make one square by using up all those matchsticks. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Your input will be several matchsticks the girl has, represented with their stick length. Your output will either be true or false, to represent whether you could make one square using all the matchsticks the little match girl has.

Example 1:

Input: [1,1,2,2,2]
Output: true

Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.

Example 2:

Input: [3,3,3,3,4]
Output: false

Explanation: You cannot find a way to form a square with all the matchsticks.

Note：

  1. The length sum of the given matchsticks is in the range of 0 to 10^9.
  2. The length of the given matchstick array will not exceed 15.

方法

由于给定的数组长度不会超过15，所以暗示可以进行递归和dfs遍历操作。

对于实际上有两个数组的dfs，需要转换一下思考角度，不能再像一个数组的dfs那样进行解题，谨记： 两个数组变化也可以用dfs解题。

dfs操作

声明一个一维数组，其大小为4，分别存放矩阵的四条边，当四条边都与目标值相等时，说明能生成正方形矩阵。

说明: 如下代码在LeetCode上能AC，但是很奇怪，对原数组排序并加上sum[3] == target后却报超时，sum[3] == target省略可以理解为剪枝，能接受，但是排序后就超时了？不理解，求大神们赐教。

public class Solution {
    public boolean makesquare(int[] nums) {
        if(nums.length < 4){
            return false;
        }
        int sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum = sum + nums[i];
        }
        if(sum % 4 != 0){
            return false;
        }
        //Arrays.sort(nums);
        return find(nums,new int[4],0,sum/4);
    }
    public boolean find(int[] nums, int[] sum, int index, int target){
        if(index == nums.length){
            if(sum[0] == target && sum[1] == target && sum[2] == target){
                return true;
            }else{
                return false;
            }
        }

        for(int i = 0; i < 4; i++){
            if(sum[i] + nums[index] > target){
                continue;
            }
            sum[i] = sum[i] + nums[index];
            if(find(nums,sum,index + 1,target)){
                return true;
            }
            sum[i] = sum[i] - nums[index];
        }
        return false;
    }
}

递归

总的思路实际上差不多，主要是在方法的声明中将数组拆分为4个数，然后分别递归判断。

    public boolean helper(int[] a, int i,long sum1,long sum2,long sum3,long sum4, long width){
        if(sum1>width||sum2>width||sum3>width||sum4>width) return false;
        if(i==-1){
            if(sum1==width&&sum2==width&&sum3==width&&sum4==width) return true;
            else return false;
        }
//check a[i]  belonging to side1,side2,side3,side4
        return helper(a,i-1,sum1+a[i],sum2,sum3,sum4,width)||
        helper(a,i-1,sum1,sum2+a[i],sum3,sum4,width)||
        helper(a,i-1,sum1,sum2,sum3+a[i],sum4,width)||
        helper(a,i-1,sum1,sum2,sum3,sum4+a[i],width);
    }
Share