力扣：473 火柴拼正方形 - 的思考过程

发表于

473. 火柴拼正方形 - 力扣（LeetCode） (leetcode-cn.com)

题目：

是否能利用给定数组中的所有数拼出一个正方形。

思考过程：

看题目的数据范围就知道是用状态压缩。当然，这类题目很多时候都可以用dfs + 剪枝技巧 来做。包括我自己以前都是喜欢一股脑地上dfs，但是这次专门挑战下就用状态压缩dp。原因有两个：1）处于锻炼自身技能的目的 2）dfs经常要搭配一些剪枝技巧，有时候并不是很容易找出来剪枝技巧的思路。

这道题属于十分经典的状态压缩类的（分组）问题。典型的套路就是：将原问题拆解为子问题的解。还有一道比较类似的可以参考：1681. 最小不兼容性 - 力扣（LeetCode） (leetcode-cn.com)

在这里的情况就是将数组中所有数分到4组，看是否每一组的和都相等。所以我们可以提前计算出数组总和，然后除以4就能求出边长，也即每个分组的和

递推公式如下：

f[k][mask]∣=f[k−1][mask⊕subset],其中valid[subset]=true,表示数组中的某个子集subset代表的数之和是否等于正方形的边长f[k][mask] \quad |= f[k-1][mask \oplus subset],其中valid[subset] = true,表示数组中的某个
\子集subset代表的数之和是否等于正方形的边长f[k][mask]∣=f[k−1][mask⊕subset],其中valid[subset]=true,表示数组中的某个子集subset代表的数之和是否等于正方形的边长
顺便说一下两个位运算的经典作用：

1.求所有子集

1
2
3
4
5
6
7
8
9
ini复制代码int subset = mask;
while (subset > 0) {
	subset = (subset - 1) & mask;
}

也可以：
for (int subset = mask; subset > 0; subset = (subset - 1) & mask) {

}

2.将选定的数置0

1
2
css复制代码mask = mask ^ subset;
将二进制表示的mask 中的subset 位置 置为0

我们可以先预处理valid数组，看哪些数字组合可以放到一组中，然后再利用上面的递推式枚举所有状态，最后答案是:

f[k][(1<<nums.length)−1]f[k][(1 << nums.length) - 1]f[k][(1<<nums.length)−1]
一开始的代码如下：

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
java复制代码   public boolean makesquare(int[] matchsticks) {
        long sum = 0;
        for (int i = 0; i < matchsticks.length; i++) {
            sum += matchsticks[i];
        }
        if (sum % 4 != 0) {
            return false;
        }
        int sidelen = (int) (sum / 4);
        boolean[][] valid = new boolean[4][1 << matchsticks.length];
        for (int i = 0; i < (1 << matchsticks.length); i++) {
            long tmpSum = 0L;
            for (int j = 0; j < matchsticks.length; j++) {
                if (((1 << j) & i) != 0) {
                    tmpSum += matchsticks[j];
                }
            }
            if (tmpSum == sidelen) {
                valid[0][i] = true;
            }

        for (int i = 1; i < 4; i++) {
            for (int j = 0; j < (1 << matchsticks.length); j++) {
                for (int subset = j; subset > 0; subset = (subset - 1) & j) {

                    if (valid[0][subset]) {
                        valid[i][j] |= valid[i - 1][j ^ subset];
                    }
                }
            }
        }

        return valid[3][(1 << matchsticks.length) - 1];
    }

image-20211129224342302.png

2300多ms通过你敢信。。。？

当然本着学习的态度，这显然是无法接受的。

于是我在原来的代码上加了很多输出，帮助自己寻找“重复”的计算，类似于：

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
ini复制代码   public boolean makesquare(int[] matchsticks) {
        long sum = 0;
        for (int i = 0; i < matchsticks.length; i++) {
            sum += matchsticks[i];
        }
        if (sum % 4 != 0) {
            return false;
        }
        int sidelen = (int) (sum / 4);
        boolean[][] valid = new boolean[4][1 << matchsticks.length];
        for (int i = 0; i < (1 << matchsticks.length); i++) {
            long tmpSum = 0L;
            for (int j = 0; j < matchsticks.length; j++) {
                if (((1 << j) & i) != 0) {
                    tmpSum += matchsticks[j];
                }
            }
            if (tmpSum == sidelen) {
                valid[0][i] = true;
            }
        }

        for (int i = 1; i < 4; i++) {
            for (int j = 0; j < (1 << matchsticks.length); j++) {
                for (int subset = j; subset > 0; subset = (subset - 1) & j) {

                    if (valid[0][subset]) {
                        valid[i][j] |= valid[i - 1][j ^ subset]

                    }
                }
            }
        }

//        for (int i = 0; i < 4; i++) {
//            for (int j = 0; j < (1 << matchsticks.length); j++) {
////                StringJoiner stringJoiner = new StringJoiner(",");
////                for (int k = 0; k < matchsticks.length; k++) {
////                    if (((1 << k) & j) != 0) {
////                        stringJoiner.add(matchsticks[k] + "");
////                    }
////                }
////                System.out.println(stringJoiner.toString() + " " + valid[i][j]);
//                System.out.println(translate(matchsticks, j) + " " + valid[i][j]);
//            }
//            System.out.println("***************");
//        }
        return valid[3][(1 << matchsticks.length) - 1];
    }
    
        private String translate(int[] matchsticks, int chosen) {

        StringJoiner stringJoiner = new StringJoiner(",");
        for (int k = 0; k < matchsticks.length; k++) {
            if (((1 << k) & chosen) != 0) {
                stringJoiner.add(matchsticks[k] + "");
            }
        }
        //System.out.println(stringJoiner.toString() + " ");
        return stringJoiner.toString() + " ";
    }

终于，在观察了半天打印出来的输出之后，我发现：其实我一直迷惑了自己，双层for循环其实是“不重不漏”的，没有地方重复计算了，每一步都是“合理”的，比如，当要求f[3][mask]的时候，就需要知道f[2][mask ^ subset]的各种情况。

真正耗时的是由很多计算其实是不需要的，所以只需要加上判断：

1
2
3
css复制代码if (sidesum[j] != (i + 1) * sidelen) {
    continue;
}

就能够提减少运算。

它的含义是在当前k=i的情况下，只有那些sidesum[j] == (i + 1) * sidelen才有可能 为true

完整代码如下：

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
42
43
44
45
46
java复制代码public boolean makesquare(int[] matchsticks) {
    long sum = 0;
    for (int i = 0; i < matchsticks.length; i++) {
        sum += matchsticks[i];
    }
    if (sum % 4 != 0) {
        return false;
    }
    int sidelen = (int) (sum / 4);
    boolean[][] valid = new boolean[4][1 << matchsticks.length];
    long[] sidesum = new long[1 << matchsticks.length];

    for (int i = 0; i < (1 << matchsticks.length); i++) {
        long tmpSum = 0L;
        for (int j = 0; j < matchsticks.length; j++) {
            if (((1 << j) & i) != 0) {
                tmpSum += matchsticks[j];
            }
        }
        sidesum[i] = tmpSum;
        if (tmpSum == sidelen) {
            valid[0][i] = true;
        }
    }

    //int count = 0;
    for (int i = 1; i < 4; i++) {
        for (int j = 0; j < (1 << matchsticks.length); j++) {
            if (sidesum[j] != (i + 1) * sidelen) {
                continue;
            }
            //count++;
            for (int subset = j; subset > 0; subset = (subset - 1) & j) {
                if (valid[0][subset]) {
                    valid[i][j] = valid[i - 1][j ^ subset];
                }
                if (valid[i][j]) {
                    break;
                }
            }
        }
    }

    //System.out.println(count);
    return valid[3][(1 << matchsticks.length) - 1];
}

另外，其实可以把双层循环改成一层就够了，如下：

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
42
43
44
45
46
47
java复制代码public boolean makesquare(int[] matchsticks) {
    long sum = 0;
    for (int i = 0; i < matchsticks.length; i++) {
        sum += matchsticks[i];
    }
    if (sum % 4 != 0) {
        return false;
    }
    int sidelen = (int) (sum / 4);
    boolean[] valid = new boolean[1 << matchsticks.length];
    long[] sidesum = new long[1 << matchsticks.length];

    for (int i = 0; i < (1 << matchsticks.length); i++) {
        long tmpSum = 0L;
        for (int j = 0; j < matchsticks.length; j++) {
            if (((1 << j) & i) != 0) {
                tmpSum += matchsticks[j];
            }
        }
        sidesum[i] = tmpSum;
        if (tmpSum == sidelen) {
            valid[i] = true;
        }
    }


    //int count = 0;
    for (int j = 0; j < (1 << matchsticks.length); j++) {
        if (sidesum[j] % sidelen == 0) {
           // if (sidesum[j] / sidelen > 1) {
             //   count++;
          //  }

            for (int subset = j; subset > 0; subset = (subset - 1) & j) {

                if (valid[subset]) {
                    valid[j] |= valid[j ^ subset];
                }
                if (valid[j]) {
                    break;
                }
            }
        }
    }
    //System.out.println(count);
    return valid[(1 << matchsticks.length) - 1];
}

上面的两个代码我加了count来对比是否计算量一致，最后发现是一致的。

最终提交的时间：

image-20211129225933699.png

其实跟dfs+剪枝比还是不快的，但是这种套路应用性好一点，毕竟有些剪枝技巧实在是不容易看出来。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%