当前位置：网站首页>LeetCode 473. 火柴拼正方形

LeetCode 473. 火柴拼正方形

2022-06-23 18:37:00 【51CTO】

截止到目前我已经写了 500多道算法题，其中部分已经整理成了pdf文档，目前总共有1000多页（并且还会不断的增加），大家可以免费下载

LeetCode 473. 火柴拼正方形_LeetCode

这就是回溯算法，他不断的尝试，一旦成功也就成功了。如果不成功，在回到上一步继续尝试，其实他有一个经典的模板

       
       private 
       
       void 
       
       backtrack(
       
       "原始参数") {
       
       //终止条件(递归必须要有终止条件)
       
       if (
       
       "终止条件") {
       
       //一些逻辑操作（可有可无，视情况而定）
       
       return;
       
    }
       
       for (
       
       int 
       
       i 
       
       = 
       
       "for循环开始的参数"; 
       
       i 
       
       < 
       
       "for循环结束的参数"; 
       
       i
       
       ++) {
       
       //一些逻辑操作（可有可无，视情况而定）
       
       //做出选择
       
       //递归
       
       backtrack(
       
       "新的参数");
       
       //一些逻辑操作（可有可无，视情况而定）
       
       //撤销选择
       
    }
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.

我们来看下最终代码

       
       public 
       
       boolean 
       
       makesquare(
       
       int[] 
       
       nums) {
       
       int 
       
       total 
       
       = 
       
       0;
       
       //统计所有火柴的长度
       
       for (
       
       int 
       
       num : 
       
       nums) {
       
       total 
       
       += 
       
       num;
       
    }
       
       //如果所有火柴的长度不是4的倍数，直接返回false
       
       if (
       
       total 
       
       == 
       
       0 
       
       || (
       
       total 
       
       & 
       
       3) 
       
       != 
       
       0)
       
       return 
       
       false;
       
       //回溯
       
       return 
       
       backtrack(
       
       nums, 
       
       0, 
       
       total 
       
       >> 
       
       2, 
       
       new 
       
       int[
       
       4]);
       
}
       
       //index表示访问到当前火柴的位置，target表示正方形的边长，size是长度为4的数组，
       
       //分别保存正方形4个边的长度
       
       private 
       
       boolean 
       
       backtrack(
       
       int[] 
       
       nums, 
       
       int 
       
       index, 
       
       int 
       
       target, 
       
       int[] 
       
       size) {
       
       if (
       
       index 
       
       == 
       
       nums.
       
       length) {
       
       //如果火柴都访问完了，并且size的4个边的长度都相等，说明是正方形，直接返回true，
       
       //否则返回false
       
       if (
       
       size[
       
       0] 
       
       == 
       
       size[
       
       1] 
       
       && 
       
       size[
       
       1] 
       
       == 
       
       size[
       
       2] 
       
       && 
       
       size[
       
       2] 
       
       == 
       
       size[
       
       3])
       
       return 
       
       true;
       
       return 
       
       false;
       
    }
       
       //到这一步说明火柴还没访问完
       
       for (
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       size.
       
       length; 
       
       i
       
       ++) {
       
       //如果把当前火柴放到size[i]这个边上，他的长度大于target，我们直接跳过
       
       if (
       
       size[
       
       i] 
       
       + 
       
       nums[
       
       index] 
       
       > 
       
       target)
       
       continue;
       
       //如果当前火柴放到size[i]这个边上，长度不大于target，我们就放上面
       
       size[
       
       i] 
       
       += 
       
       nums[
       
       index];
       
       //然后在放下一个火柴，如果最终能变成正方形，直接返回true
       
       if (
       
       backtrack(
       
       nums, 
       
       index 
       
       + 
       
       1, 
       
       target, 
       
       size))
       
       return 
       
       true;
       
       //如果当前火柴放到size[i]这个边上，最终不能构成正方形，我们就把他从
       
       //size[i]这个边上给移除，然后在试其他的边
       
       size[
       
       i] 
       
       -= 
       
       nums[
       
       index];
       
    }
       
       //如果不能构成正方形，直接返回false
       
       return 
       
       false;
       
}
      
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.

LeetCode 473. 火柴拼正方形_LeetCode_03

       
       public 
       
       boolean 
       
       makesquare(
       
       int[] 
       
       nums) {
       
       int 
       
       total 
       
       = 
       
       0;
       
       //统计所有火柴的长度
       
       for (
       
       int 
       
       num : 
       
       nums) {
       
       total 
       
       += 
       
       num;
       
    }
       
       //如果所有火柴的长度不是4的倍数，直接返回false
       
       if (
       
       total 
       
       == 
       
       0 
       
       || (
       
       total 
       
       & 
       
       3) 
       
       != 
       
       0)
       
       return 
       
       false;
       
       //先排序
       
       Arrays.
       
       sort(
       
       nums);
       
       //回溯，从最长的火柴开始
       
       return 
       
       backtrack(
       
       nums, 
       
       nums.
       
       length 
       
       - 
       
       1, 
       
       total 
       
       >> 
       
       2, 
       
       new 
       
       int[
       
       4]);
       
}
       
       //index表示访问到当前火柴的位置，target表示正方形的边长，size是长度为4的数组，
       
       //分别保存正方形4个边的长度
       
       private 
       
       boolean 
       
       backtrack(
       
       int[] 
       
       nums, 
       
       int 
       
       index, 
       
       int 
       
       target, 
       
       int[] 
       
       size) {
       
       if (
       
       index 
       
       == 
       
       -
       
       1) {
       
       //如果火柴都访问完了，并且size的4个边的长度都相等，说明是正方形，直接返回true，
       
       //否则返回false
       
       if (
       
       size[
       
       0] 
       
       == 
       
       size[
       
       1] 
       
       && 
       
       size[
       
       1] 
       
       == 
       
       size[
       
       2] 
       
       && 
       
       size[
       
       2] 
       
       == 
       
       size[
       
       3])
       
       return 
       
       true;
       
       return 
       
       false;
       
    }
       
       //到这一步说明火柴还没访问完
       
       for (
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       size.
       
       length; 
       
       i
       
       ++) {
       
       //如果把当前火柴放到size[i]这个边上，他的长度大于target，我们直接跳过。或者
       
       // size[i] == size[i - 1]即上一个分支的值和当前分支的一样，上一个分支没有成功，
       
       //说明这个分支也不会成功，直接跳过即可。
       
       if (
       
       size[
       
       i] 
       
       + 
       
       nums[
       
       index] 
       
       > 
       
       target 
       
       || (
       
       i 
       
       > 
       
       0 
       
       && 
       
       size[
       
       i] 
       
       == 
       
       size[
       
       i 
       
       - 
       
       1]))
       
       continue;
       
       //如果当前火柴放到size[i]这个边上，长度不大于target，我们就放上面
       
       size[
       
       i] 
       
       += 
       
       nums[
       
       index];
       
       //然后在放下一个火柴，如果最终能变成正方形，直接返回true
       
       if (
       
       backtrack(
       
       nums, 
       
       index 
       
       - 
       
       1, 
       
       target, 
       
       size))
       
       return 
       
       true;
       
       //如果当前火柴放到size[i]这个边上，最终不能构成正方形，我们就把他从
       
       //size[i]这个边上给移除，然后在试其他的边
       
       size[
       
       i] 
       
       -= 
       
       nums[
       
       index];
       
    }
       
       //如果不能构成正方形，直接返回false
       
       return 
       
       false;
       
}
      
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.

LeetCode 473. 火柴拼正方形_数组_04

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_4774266/5412485

当前位置：网站首页>LeetCode 473. 火柴拼正方形

LeetCode 473. 火柴拼正方形

边栏推荐

猜你喜欢

随机推荐