leetcode-matchsticks-to-square

发表于   |   分类于 ，   |  

题目大意

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

　　给你一个数组，无重复地选出4组数，每组数之和相等。

题目分析

　　自己写了个dfs解法，没有写对，参考了讨论区的dfs的一个优雅做法：https://discuss.leetcode.com/topic/72107/java-dfs-solution-with-explanation　用了四个数字保存四条边的累计和，每次拓展最多有四个方向。但是这样做可以AC，但是不够优化，注意可以先将数组倒序，这样从先往后搜索时先遇到大的数可以进行剪枝掉了，如果从小的开始，可能需要很久才能“凑够”一个边长。经过排序优化后程序运行时间有1000多降到40几。这个题目理论上可以动态规划解，但实际不好设计保存状态的数据结构。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class Solution {
    
    private boolean[] v;
    
    private boolean search(int[] nums, int [] sums, int a, int idx) { // a是边长，idx代表要搜索的位置    
        int len = nums.length;
        if (idx == len) {
            if (sums[0] == a && sums[1] == a && sums[2] == a) {
                return true;
            }
            return false;
        }
        for (int i = 0; i < 4; i++) {
            if (sums[i] + nums[idx] <= a) {
                sums[i] += nums[idx];
                if (search(nums, sums, a, idx + 1)) {
                    return true;
                }
                sums[i] -= nums[idx];
            }
        }
        return false;
    }
    
    public boolean makesquare(int[] nums) {
        if (nums == null || nums.length < 4) {
            return false;
        }
        int len = nums.length;
        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum += nums[i];
        }
        if (sum % 4 != 0) {
            return false;
        }
        int a = sum / 4;
        v = new boolean[len];
        return search(nums, new int[4], a, 0);
    }
}

复杂度:O(4^15)