leetcode473. 火柴拼正方形(回溯算法-java)

这篇具有很好参考价值的文章主要介绍了leetcode473. 火柴拼正方形(回溯算法-java)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

leetcode473 火柴拼正方形

难度 - 中等
原题链接 - leetcode473 火柴拼正方形

题目描述

你将得到一个整数数组 matchsticks ,其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒,但你可以把它们连在一起,而且每根火柴棒必须 使用一次 。
如果你能使这个正方形,则返回 true ,否则返回 false 。

示例1:
leetcode473. 火柴拼正方形(回溯算法-java),数据结构,java,算法,算法,java,python,leetcode,开发语言,数据结构,动态规划输入: matchsticks = [1,1,2,2,2]
输出: true
解释: 能拼成一个边长为2的正方形,每边两根火柴。

示例 2:
输入: matchsticks = [3,3,3,3,4]
输出: false
解释: 不能用所有火柴拼成一个正方形。

提示:
1 <= matchsticks.length <= 15
1 <= matchsticks[i] <= 1e8

leetcode473. 火柴拼正方形(回溯算法-java),数据结构,java,算法,算法,java,python,leetcode,开发语言,数据结构,动态规划

回溯算法

这个题的意思可以转换为,将数组分为四个相等的数组。
用回溯算法,进行选择。先看下回溯算法的基本流程。

废话不多说,直接上回溯算法框架,解决一个回溯问题,实际上就是一个决策树的遍历过程,站在回溯树的一个节点上,你只需要思考 3 个问题:
1.路径:也就是已经做出的选择。
2.选择列表:也就是你当前可以做的选择。
3.结束条件:也就是到达决策树底层,无法再做选择的条件。

代码框架

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

代码:

  int n ,t;
    int[]_nums;
    public boolean makesquare(int[] nums) {
        if(nums.length < 4){
            return false;
        }
        int sum = 0;
        for(int i = 0; i < nums.length;i++){
            sum += nums[i];
        }
        if(sum % 4 != 0){
            return false;
        }
        Arrays.sort(nums);
        _nums = nums;
        n = nums.length;
        t = sum / 4;
        return dfs(n - 1,0,0,new boolean[n]);
    }

    /**
     *
     * @param index
     * @param cur 当前元素和
     * @param cnt 已经凑够几个和为t的集合。
     * @param vis 标记哪些元素被使用过了。
     * @return
     */
    boolean dfs(int index,int cur,int cnt,boolean[]vis){
        if (cnt == 4){
            return true;
        }
        if (cur == t){
            return dfs(n - 1,0,cnt + 1,vis);
        }
        for (int i = index;i >= 0;i--){
            if (vis[i] || cur + _nums[i] > t){
                continue;
            }
            vis[i] = true;
            if (dfs(i - 1,cur + _nums[i],cnt,vis)){
                return true;
            }
            vis[i] = false;
            if (cur == 0){
                return false;
            }
        }
        return false;
    }

上期经典算法

leetcode292. Nim 游戏文章来源地址https://www.toymoban.com/news/detail-655969.html

到了这里,关于leetcode473. 火柴拼正方形(回溯算法-java)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode221.Maximal-Square<最大正方形>

        这题是动态规划,但是不会写。想着判断dp的 上,左,左上  去了。发现只能这样最大只能判断面积为4的正方形因为只会判断另外三个方格。而要想判断更大的正方形那就需要递归操作了。那肯定会超时了。 好吧,只能看答案了。 正方形的面积的长乘宽。在例子中我们

    2024年02月15日
    浏览(36)
  • LeetCode 1277. 统计全为 1 的正方形子矩阵【动态规划】1613

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2024年02月07日
    浏览(33)
  • 【LeetCode热题100】打卡第39天:数组中第K个最大元素&最大正方形

    大家好,我是知识汲取者,欢迎来到我的LeetCode热题100刷题专栏! 精选 100 道力扣(LeetCode)上最热门的题目,适合初识算法与数据结构的新手和想要在短时间内高效提升的人,熟练掌握这 100 道题,你就已经具备了在代码世界通行的基本能力。在此专栏中,我们将会涵盖各种

    2024年02月16日
    浏览(42)
  • 最大正方形(力扣)暴力 + 动态规划 JAVA

    在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内,找到只包含 ‘1’ 的最大正方形,并返回其面积。 示例 1: 输入:matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]] 输出:4 示例 2: 输入:m

    2024年02月15日
    浏览(61)
  • 【算法思考记录】【前缀和,C++】力扣1277. 统计全为 1 的正方形子矩阵

    原题链接 题目要求我们统计在一个由0和1构成的矩阵中,所有完全由1组成的正方形子矩阵的数量。这是一道中等难度的算法题目,其关键在于高效地计算出不同大小的正方形子矩阵是否完全由1组成。 解决此问题的一个有效方法是使用 前缀和 算法。前缀和是一种预处理技术

    2024年02月03日
    浏览(37)
  • Python-彩色正方形

    核心代码 核心代码 核心代码

    2024年02月19日
    浏览(35)
  • CSS 3D旋转正方形

    2024年01月23日
    浏览(39)
  • python绘制螺旋正方形

    1.首先导入画图功能库turtle 2.设置画笔大小,颜色  turtle.pensize()  turtle.pencolor() 3.如何绘制:螺旋正方形一开始外边有3条长度相同的边,先勾勒出一条边循环3次将外边构出,里边每勾勒一条循环两次,再进行循环,即需要一个双循环,边每次比前一次缩短。 画笔前进  turt

    2024年04月15日
    浏览(44)
  • P1387 最大正方形 题解

    通过二维前缀和判定矩形内是否全为1,计算和等于长度的平方就判断为是 复杂度 (Theta (n^2log{n})) 设状态 (f_{i,j}) 为以第 (i) 行 (j) 列为右下角的最大正方形的边长, (a_{i,j}) 表示输入矩阵中的数值,有转移方程: [f_{i,j} = (min(f_{i-1,j},f_{i,j-1},f_{i-1,j-1}) + 1) * a_{i,j}] 解释:

    2024年02月16日
    浏览(41)
  • 力扣221.最大正方形(动态规划)

    思路: 思路:从[0,0]元素开始,计算每个元素对应其与[0,0]之间矩阵块中最大正方形边长 情况:1)matrix [ i , j ] = ‘0’ -- 元素对应的最大正方形为0。 情况:2)matrix [ i , j ] = ‘1’ -- max ( matrix [ i-1 , j ] , matrix [ i - 1 , j - 1 ) ,matrix [ i , j - 1 ] ) + 1 具体实现:1)先找出第一行和第

    2024年02月13日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包