栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

Leetcode-473. 火柴拼正方形:一个4X15的皇后问题(其实就是一个回溯法)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

Leetcode-473. 火柴拼正方形:一个4X15的皇后问题(其实就是一个回溯法)

题目链接

473. 火柴拼正方形

解题思路

第一,目标就是把数组里面的数,分到四个堆里面。

第二,就是把每个数分到不同的堆里面进行尝试,直到最后都分配完成了,此时判断能否满足要求,

第三,在回溯尝试的过程中,对于已经超出总数的25%的就直接停止,不用继续回溯了。

错误的解题代码

下面的代码将p函数执行4次,即每次从数组里面选择满足和为 sum/4 的一组,若4次都是true,则返回true。

这个解法的错误在于,第一次选虽然满足了第一租的要求,但是错误的把要分配给2 3 4租的数字给用了,导致2 3 4组没办法成功了 例如这组用例

[13,11,1,8,6,7,8,8,6,7,8,9,8]

class Solution {

   public boolean makesquare(int[] matchsticks) {
        int sum = 0;

        for (int i :matchsticks ){
            sum += i;
        }

        if (sum%4!=0){
            return false;
        }
        Arrays.sort(matchsticks);
        boolean[] b = new boolean[matchsticks.length];
        int l = sum/4;
        return p(matchsticks,b,l) && p(matchsticks,b,l) && p(matchsticks,b,l) &&p(matchsticks,b,l);

    }

    private boolean p(int[] matchsticks, boolean[] b, int l) {
        if (l==0){
            return true;
        } else if (l<0){
            return  false;
        } else{
            for (int i=matchsticks.length-1;i>=0;i--){
                if (!b[i]){
                    b[i] = true;
                    if (p(matchsticks,b,l-matchsticks[i])){
                        return true;
                    }
                    b[i] = false;
                }

            }
            return false;
        }
    }

}

 正确的解题代码

第一,先求和,并判断能够平分4份,

第二,通过回溯的方式,得到答案。

第三,进行大优化,先给数组排序,处理的顺序按照从大到小。保证全部用例不超时

第四,进行小优化,把回溯的第一个数固定到第一组。

public class Solution473 {

    int[] matchsticks;
    int end;
    public static void main(String[] args) {
        boolean a = new Solution473().makesquare(new int[]{13, 11, 1, 8, 6, 7, 8, 8, 6, 7, 8, 9, 8});
        System.out.println(a);
    }

    public boolean makesquare(int[] matchsticks) {
        Arrays.sort(matchsticks);
        this.matchsticks = matchsticks;
        int sum = 0;
        for (int i : matchsticks) {
            sum += i;
        }
        this.end = sum / 4;
        if (sum % 4 != 0) {
            return false;
        }
        int[] s = new int[4];
        s[0] = matchsticks[matchsticks.length-1];
        return p1(matchsticks.length-2,s);

    }

    private boolean p1(int i ,int[] s){

        if (this.end == s[0] && this.end==s[1] && this.end==s[2]&& this.end==s[3]){
            return true;
        }else {
            if (i<0){
                return false;
            }
            if (s[0]>end || s[1]>end || s[2]>end || s[3]>end ){
                return false;
            }

            boolean res = false;
            for (int j =0;j<4;j++){
                s[j] += this.matchsticks[i];
                res = res ||p1(i-1,s);
                s[j] -= this.matchsticks[i];
            }
            return res;

        }
    }
   
}
 解题结果

一轮优化后,通过了全部用例。

二轮优化后,提升了性能。

 

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/946994.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号