当前位置：网站首页>LeetCode 473. 火柴拼正方形
LeetCode 473. 火柴拼正方形
2022-06-23 18:37:00 【51CTO】
截止到目前我已经写了 500多道算法题，其中部分已经整理成了pdf文档，目前总共有1000多页（并且还会不断的增加），大家可以免费下载
视频链接
这就是回溯算法，他不断的尝试，一旦成功也就成功了。如果不成功，在回到上一步继续尝试，其实他有一个经典的模板
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.
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.
边栏推荐
- Advanced network planning notes (IX)
- NAACL 2022 Findings | 字节提出MTG：多语言文本生成数据集
- Jerry's broadcast MP3 prompt sound function [chapter]
- Docker搭建redis集群
- LeetCode 1079. 活字印刷
- 准备好迁移上云了？请收下这份迁移步骤清单
- SAVE: 软件分析验证和测试平台
- Chaos engineering, learn about it
- Advanced network accounting notes (IV)
- sed replace \tPrintf to \t//Printf
猜你喜欢
Learn the basic principles of BLDC in Simulink during a meal
Basic knowledge of assembly language (1)
SAVE: 软件分析验证和测试平台
Docker builds redis cluster
基于 ShardingSphere 的得物数据库中间件平台“彩虹桥”演进之路
火线沙龙第26期-多云安全专场
Nanxin semiconductor rushes to the scientific innovation board: its annual revenue is RMB 980 million. Sequoia Xiaomi oppo is the shareholder
How can enterprises do business monitoring well?
混沌工程，了解一下
【NOI2014】15.起床困难综合症【二进制】
随机推荐
20set introduction and API
【NOI2014】15. Difficult to get up syndrome [binary]
[one by one series] identityserver4 (III) user name and password
Docker搭建redis集群
Robust extraction of specific signals with time structure (Part 2)
IDEA控制台显示中文乱码
如何通过7个步骤编写出色的在线用户手册
Function definition and function parameters
Live broadcast review | detailed explanation of koordinator architecture of cloud native hybrid system (complete ppt attached)
golang set type implementation
NLP 论文领读｜改善意图识别的语义表示：有监督预训练中的各向同性正则化方法
【One by One系列】IdentityServer4（三）使用用户名和密码
Tutorial on installing SSL certificates in Microsoft Exchange Server 2007
Idea console displays Chinese garbled code
【NOI2014】15.起床困難綜合症【二進制】
How can enterprises do business monitoring well?
[one by one series] identityserver4 (II) using client credentials to protect API resources
LeetCode 每日一题——30. 串联所有单词的子串
[one by one series] spa of identityserver4 (VI) authorization code process principle
Docker builds redis cluster