首页/新闻资讯/正文详情

DeepSeek LeetCode 473. 火柴拼正方形 Java实现

发布时间:2026/11/5 2:43:03 来源:云帆数科 栏目:资讯中心
DeepSeek    LeetCode 473. 火柴拼正方形 Java实现
思路回溯 剪枝基本判断所有火柴总长度必须能被 4 整除最长的那根火柴不能超过正方形边长 target total / 4。核心搜索把每根火柴依次尝试放进 4 条边中用 sides[4] 记录每条边当前已放置的长度。放满 4 条边即成功。关键剪枝否则会超时从大到小排序长火柴先放分支更少相同边跳过如果 sides[i] sides[i-1]说明这两条边当前状态一样尝试一条即可空边失败剪枝如果某根火柴放进一条空边后搜索失败直接返回 false。因为放在哪条空边都等价满边失败剪枝如果某根火柴放进后该边正好填满但后续搜索失败直接返回 false。因为填满这条边是必然的无需换其他边尝试。Java 实现importjava.util.Arrays;classSolution{publicbooleanmakesquare(int[]matchsticks){inttotal0;for(intm:matchsticks)totalm;if(total%4!0)returnfalse;inttargettotal/4;intnmatchsticks.length;// 从大到小排序Arrays.sort(matchsticks);for(inti0,jn-1;ij;i,j--){inttmpmatchsticks[i];matchsticks[i]matchsticks[j];matchsticks[j]tmp;}if(matchsticks[0]target)returnfalse;int[]sidesnewint[4];returnbacktrack(matchsticks,0,sides,target);}privatebooleanbacktrack(int[]nums,intidx,int[]sides,inttarget){if(idxnums.length){// 走到这里所有火柴都已放置且每根都满足 target// 只要总和 4 * target则四条边必然都等于 targetreturntrue;}for(inti0;i4;i){// 剪枝 1放不下if(sides[i]nums[idx]target)continue;// 剪枝 2跳过状态相同的边if(i0sides[i]sides[i-1])continue;sides[i]nums[idx];if(backtrack(nums,idx1,sides,target))returntrue;sides[i]-nums[idx];// 剪枝 3空边放入失败直接返回if(sides[i]0)returnfalse;// 剪枝 4正好填满边但失败直接返回if(sides[i]nums[idx]target)returnfalse;}returnfalse;}}代码说明· idx nums.length 时直接返回 true因为每根火柴放入时都保证 sides[i] nums[idx] target所有火柴放完后总长度恰好是 4 * target所以四条边必然都等于 target。· 剪枝 3 的判断sides[i] 已在上一行减回去所以此时 sides[i] 0 表示放入之前该边为空。空边都放不下其他空边也一样直接失败。· 剪枝 4 的判断sides[i] nums[idx] target 表示放入之后该边正好填满。如果这种情况失败说明这根火柴必须放在这条边上而不行换边也一样直接失败。复杂度· 时间复杂度最坏 O(4^n)但剪枝后实际远小于此。· 空间复杂度O(n)递归栈深度 排序开销 O(log n)。易错点忘记倒序排序从小到大排会大幅增加搜索分支容易 TLE剪枝 3 和剪枝 4 的判断时机必须在 sides[i] - nums[idx] 之后判断否则 sides[i] 还是放入后的值判断会出错matchsticks[0] target 的检查倒序排序后 matchsticks[0] 是最长火柴必须提前拦截idx nums.length 直接返回 true 即可不需要再逐个比较四条边因为中途的 target 约束已经保证总和分配正确。

相关推荐

从“太会顺着人“到“独立而不偏离“:一个 AI 的人格升级全过程
从“太会顺着人“到“独立而不偏离“:一个 AI 的人格升级全过程

原文链接:https://mp.weixin.qq.com/s/qfzlmKZ8GsGltnKc6xNiwA 免责声明:本文为月牙寂与月绡凝的个人 AI 工程化实践知识分享,仅供学习参考,不构成任何商业建议或技术承诺。读者使用文中任何方法、工具、配置时请自行评估风险并担… · 2026/11/5 3:02:35

于品:《数学分析之课程讲义一分析123》
于品:《数学分析之课程讲义一分析123》

于品《数学分析之课程讲义一分析123》是清华大学丘成桐数学英才班专属的实验性数学分析教材,由清华大学数学系及丘成桐数学科学中心出品,作者为清华数学科学系于品教授,是国内顶尖数学拔尖人才培养体系中的标志性讲义。 📚 核心内… · 2026/11/5 8:05:21

Linux FFmpeg深度解析之avcodec_flush_buffers调用流程与实战(十九)
Linux FFmpeg深度解析之avcodec_flush_buffers调用流程与实战(十九)

简介: CSDN博客专家、《Android系统多媒体进阶实战》作者 博主新书推荐:《Android系统多媒体进阶实战》🚀 Android Audio工程师专栏地址: Audio工程师进阶系列【原创干货持续更新中……】🚀 Android多媒体专栏地址&a… · 2026/11/5 7:55:48

金融行业智能运维(AIOps)架构设计与实战
金融行业智能运维(AIOps)架构设计与实战

1. 智能运维在金融数字化转型中的核心价值 金融行业作为数字化转型的先行者,面临着前所未有的系统稳定性与效能挑战。我曾在某头部券商负责智能运维体系建设,深刻体会到传统运维模式在应对高频交易、实时清算等场景时的力不从心。当系统日交易量突破百亿… · 2026/11/5 8:17:03

服务器安全防护:核心威胁分析与加固实战指南
服务器安全防护:核心威胁分析与加固实战指南

1. 服务器安全现状与核心威胁分析 服务器作为现代互联网基础设施的核心组件,每天面临着数以万计的安全威胁。根据我过去十年运维经验,即使是最基础的企业官网服务器,平均每天也会遭遇50-100次自动化扫描和试探性攻击。这些攻击行为呈现出明显… · 2026/11/5 8:17:03

卡尔曼滤波在多传感器融合定位中的工程实践
卡尔曼滤波在多传感器融合定位中的工程实践

## 1. 项目概述:多传感器融合定位的工程实践在移动机器人自主导航领域,位姿估计(Pose Estimation)的精度直接决定了建图质量与路径规划可靠性。传统单一传感器方案存在明显局限:轮式里程计(Wheel Odometry&… · 2026/11/5 8:17:03

Stuxnet恶意软件:工业控制系统安全实战分析
Stuxnet恶意软件:工业控制系统安全实战分析

1. Stuxnet恶意软件概述:工业控制系统的"实战样本" 2010年6月,白俄罗斯的一家安全公司VirusBlokAda接到伊朗客户的求助,发现了一种前所未见的恶意软件。这个后来被命名为Stuxnet的恶意程序,彻底改变了网络安全领域的游戏… · 2026/11/5 8:17:03

需求挖掘方法论:从技术实现到用户刚需
需求挖掘方法论:从技术实现到用户刚需

1. 为什么需求挖掘比技术实现更关键?三年前我参与开发过一个个人记账App,团队用了当时最先进的机器学习算法预测用户消费趋势,结果上线后发现日活还不到预期的十分之一。后来我们花了两个月深入访谈真实用户,才发现大家最需要的根… · 2026/11/5 8:17:03

MySQL COUNT函数深度解析与性能优化实践
MySQL COUNT函数深度解析与性能优化实践

1. 理解COUNT函数的基础概念 在数据库操作中,COUNT函数可能是最常用但也最容易被误解的聚合函数之一。作为MySQL中最基础的统计工具,它表面上看起来简单直接——就是计数嘛,但实际应用中却藏着不少门道。 我第一次真正意识到COUNT的复杂性是… · 2026/11/5 8:16:03

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 3:16:49

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 6:59:29

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 7:02:38

多智能体协作系统架构设计与实践优化
多智能体协作系统架构设计与实践优化

1. 多智能体协作系统的时代背景2017年Transformer架构的诞生彻底改变了人工智能的发展轨迹。当行业还沉浸在单一大模型带来的性能突破时,Anthropic的研究团队已经将目光投向了更前沿的领域——如何让多个智能体通过协作产生超越单体能力的系统智能。这就像交响乐团中… · 2026/11/5 0:00:39

大模型系统性入门实战指南:从原理到部署微调的全链路路线
大模型系统性入门实战指南:从原理到部署微调的全链路路线

提到大模型的系统性入门,我先说个结论:这事真不难,难的是资料太散、路线太多,今天这个框架明天那个工具,新人很容易在“收藏夹吃灰”和“教程看到一半放弃”之间反复横跳。市面上关于大模型的内容少说有几十万篇&#… · 2026/11/5 0:00:39

鸿蒙文件系统沙箱机制解析与开发实践
鸿蒙文件系统沙箱机制解析与开发实践

1. 鸿蒙文件系统沙箱机制深度解析作为一名从Android转向鸿蒙开发的工程师,我深刻体会到文件系统访问是迁移过程中最先遇到的"拦路虎"。在Android上运行良好的文件读写代码,在鸿蒙真机环境却频频出现文件写入后神秘消失或直接抛出权限拒绝错误的… · 2026/11/5 0:00:39

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 3:16:49

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 6:59:29

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/4 7:02:38

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码