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

火柴拼正方形

  • leetcode473 火柴拼正方形
    • 题目描述
    • 回溯算法
  • 上期经典算法

leetcode473 火柴拼正方形

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

题目描述

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

示例1:
在这里插入图片描述输入: matchsticks = [1,1,2,2,2]
输出: true
解释: 能拼成一个边长为2的正方形,每边两根火柴。

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

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

在这里插入图片描述

回溯算法

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

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

代码框架

result = []
def backtrack(路径, 选择列表):if 满足结束条件:result.add(路径)returnfor 选择 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 游戏

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/95103.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

索引下推介绍

索引下推 介绍作用MySQL5.6之前MySQL5.6及以上版本举例说明 该语句的具体执行 MySQL 5.6之前MySQL 5.6之后判断方法总结 介绍 索引条件下推&#xff0c;也叫索引下推&#xff0c;英文全称‘Index Condition Pushdown’, 简称ICP。 作用 索引下推是MySQL5.6新添加的特性&#xf…

Spring Clould 消息队列 - RabbitMQ

视频地址&#xff1a;微服务&#xff08;SpringCloudRabbitMQDockerRedis搜索分布式&#xff09; 初识MQ-同步通讯的优缺点&#xff08;P61&#xff0c;P62&#xff09; 同步和异步通讯 微服务间通讯有同步和异步两种方式&#xff1a; 同步通讯&#xff1a;就像打电话&…

grafana中利用变量来添加dashboard详情页地址实现点击跳转

背景 最近弄grafana的dashboard,突然想到各个dashboard之前可以直接跳转到不同详细页面的面板,于是找了找实现方法 实现 以stat 格式的面板为例,显示出各个pod的对应状态, PromQL是(avg(kube_pod_status_phase{phase"Running", namespace!"kube-system"…

C#语音播报问题之 无法嵌入互操作类型SpVoiceClass,请改用适用的窗口

C#语音播报问题之 无法嵌入互操作类型SpVoiceClass&#xff0c;请改用适用的窗口 解决办法如下&#xff1a; 只需要将引入的Interop.SpeechLib的属性嵌入互操作类型改为false 改为false 即可解决&#xff01;

Docker Compose安装

官网地址&#xff1a;Install the Compose plugin | Docker Documentation 安装前先更新docker&#xff0c;避免版本不匹配问题。最新版或者自定版本 sudo yum install docker-ce docker-ce-cli containerd.io docker-buildx-plugin docker-compose-plugin 安装&#xff1a; …

生信豆芽菜-差异基因富集分析的圈图

网址&#xff1a;http://www.sxdyc.com/visualsEnrichCirplot 1、数据准备 准备一个基因集的文件 2、选择富集分析的数据库&#xff0c;同时输入展示top几的条目&#xff0c;选择颜色&#xff0c;如果是GO的话选择三个颜色&#xff0c;如果是KEGG选择一个&#xff0c;如果是G…

使用wxPython和PyMuPDF在Python中显示PDF目录的实现

展示如何使用wxPython和PyMuPDF库在Python中选择PDF文件并将目录显示在列表框中。 简介&#xff1a; 在本篇教程中&#xff0c;我们将学习如何使用wxPython和PyMuPDF库在Python中选择PDF文件&#xff0c;并将其目录显示在一个列表框中。这将使用户能够方便地浏览PDF文档的目录…

双指针算法

文章目录 双指针算法leetcode题目 双指针算法 双指针算法可以实现对于时间复杂度降一维度&#xff0c;使得O(n2)的算法时间复杂度变为O(n) 指针类型 对撞指针快慢指针 对撞指针 一般是用于顺序结构中的&#xff0c;也可以称为左右指针&#xff0c;从两端向中间移动&#xff0c…

【Mysql 连接报错】

文章目录 遇到问题查看用户信息修改加密规则成功连入mysql 遇到问题 socket: auth failed …/…/lualib/skynet/socketchannel.lua:482: errno:1251, msg:Client does not support authentication protocol requested by server; consider upgrading MySQL client,sqlstate:080…

MS Word表格宽度自适应

x.1 问题&#xff1a; 你的表格可能并没有占满整行&#xff0c;且右对齐&#xff0c;例如如下&#xff0c; x.2 解决方式 这个时候你想右对齐&#xff0c;你可以这么操作&#xff0c;点左上角的十字全选表格&#xff0c; 在布局里选择自动对齐&#xff0c; 对齐方式选择居中右…

信息与通信工程面试准备——数学知识|正态分布|中心极限定理

目录 正态分布 正态分布的参数 正态分布的第一个参数是均值 正态分布的第二个参数是标准差SD 所有正态分布的共同特征 标准正态分布&#xff1a;正态分布的特例 中心极限定理 理解定义 示例# 1 示例# 2 知道样本均值总是正态分布的实际含义是什么&#xff1f; 正态分…

设计HTML5列表和超链接

在网页中&#xff0c;大部分信息都是列表结构&#xff0c;如菜单栏、图文列表、分类导航、新闻列表、栏目列表等。HTML5定义了一套列表标签&#xff0c;通过列表结构实现对网页信息的合理排版。另外&#xff0c;网页中还包含大量超链接&#xff0c;通过它实现网页、位置的跳转&…

使用Python批量将Word文件转为PDF文件

说明&#xff1a;在使用Minio服务器时&#xff0c;无法对word文件预览&#xff0c;如果有需要的话&#xff0c;可以将word文件转为pdf文件&#xff0c;再存储到Minio中&#xff0c;本文介绍如何批量将word文件&#xff0c;转为pdf格式的文件&#xff1b; 安装库 首先&#xff…

DaVinci Resolve Studio 18 for Mac 达芬奇调色

DaVinci Resolve Studio 18是一款专业的视频编辑和调色软件&#xff0c;适用于电影、电视节目、广告等各种视觉媒体的制作。它具有完整的后期制作功能&#xff0c;包括剪辑、调色、特效、音频处理等。 以下是DaVinci Resolve Studio 18的主要特点&#xff1a; - 提供了全面的视…

一次Linux中的木马病毒解决经历(6379端口---newinit.sh)

病毒入侵解决方案 情景 最近几天一直CPU100%,也没有注意看到了以为正常的服务调用,直到腾讯给发了邮件警告说我的服务器正在入侵其他服务器的6379端口,我就是正常的使用不可能去入侵别人的系统的,这是违法的. 排查 既然入侵6379端口,就怀疑是通过我的Redis服务进入的我的系统…

Maven官网下载配置新仓库

1.Maven的下载 Maven的官网地址&#xff1a;Maven – Download Apache Maven 点击Download&#xff0c;查找 Files下的版本并下载如下图&#xff1a; 2.Maven的配置 自己在D盘或者E盘创建一个文件夹&#xff0c;作为本地仓库&#xff0c;存放项目依赖。 将下载好的zip文件进行解…

初识Redis

目录 认识Redis分布式系统Redis的特性Redis的应用场景Redis客户端Redis命令 认识Redis 上面一段话是官网给出的对Redis的介绍&#xff0c;in-memory data store表明Redis是在内存中存储数据的&#xff0c;这和我们接触的其他数据库就有很大的不同&#xff0c;比如MySQL&#xf…

02-前端基础第二天-HTML5

01-HTML标签&#xff08;下&#xff09;导读 目标&#xff1a; 能够书写表格能够写出无序列表能够写出3~4个常用input表单类型能够写出下拉列表表单能够使用表单元素实现注册页面能够独立查阅W3C文档 目录&#xff1a; 表格标签列表标签表单标签综合案例查阅文档 02-表格标…

OptaPlanner笔记1

1.1 什么是OptaPlanner 每个组织都面临规划问题&#xff1a;为产品或服务提供有限的受约束的资源&#xff08;员工、资产、时间和金钱&#xff09;。OptaPlanner用来优化这种规划&#xff0c;以实现用更少的资源来做更多的业务。 这被称为Constraint Satisfaction Programming…

【Java】Spring——Bean对象的作用域和生命周期

文章目录 前言一、引出Bean对象的作用域1.普通变量的作用域2.Bean对象的作用域 二、Bean对象的作用域1.Bean对象的6种作用域2.设置Bean对象的作用域 三、Bean对象的生命周期总结 前言 本人是一个普通程序猿!分享一点自己的见解,如果有错误的地方欢迎各位大佬莅临指导,如果你也…