尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
DeepSeek    LeetCode 526. 优美的排列 Java实现
LeetCode 526. 优美的排列Java题目要点用 1 ~ n 构造排列 perm下标从 1 开始要求对每个位置 iperm[i] % i 0 或 i % perm[i] 0返回满足条件的排列数量。方法一回溯 剪枝从位置 1 到 n 依次填数字用一个 used 数组标记数字是否已使用。当前位置 pos 只能放满足整除关系的未使用数字。classSolution{privateintcount0;publicintcountArrangement(intn){boolean[]usednewboolean[n1];backtrack(1,n,used);returncount;}privatevoidbacktrack(intpos,intn,boolean[]used){// 所有位置都填完了说明找到一个合法排列if(posn){count;return;}for(intnum1;numn;num){if(used[num])continue;// 满足优美排列条件if(num%pos0||pos%num0){used[num]true;backtrack(pos1,n,used);used[num]false;}}}}复杂度· 时间复杂度最坏 O(n!)但剪枝后远小于全排列。· 空间复杂度O(n)递归栈和 used 数组。方法二状态压缩 DP用二进制 mask 表示哪些数字已经被使用。dp[mask] 表示使用 mask 中数字填充前 popcount(mask) 个位置的方法数。当前要填的位置pos Integer.bitCount(mask) 1尝试把未使用的数字 num 放到 pos如果满足整除条件则转移。classSolution{publicintcountArrangement(intn){inttotalMask1n;int[]dpnewint[totalMask];dp[0]1;for(intmask0;masktotalMask;mask){if(dp[mask]0)continue;intposInteger.bitCount(mask)1;for(intnum1;numn;num){intbit1(num-1);// 数字 num 还没被使用if((maskbit)0){// 满足优美排列条件if(num%pos0||pos%num0){dp[mask|bit]dp[mask];}}}}returndp[totalMask-1];}}复杂度· 时间复杂度O(n * 2^n)· 空间复杂度O(2^n)示例输入n2输出2解释 排列[1,2]1%102%20合法 排列[2,1]2%101%2!0但2%10合法输入n3输出3推荐· n ≤ 15 时回溯法代码简单、实际运行很快面试中更常写。· 状态压缩 DP 思路更系统适合展示动态规划能力。· 两者都可以通过 LeetCode 526。
RELATED

相关推荐

AI 眼镜 PCBA 代工怎么选:从 BOM 到首件的工艺核查清单

AI 眼镜 PCBA 代工怎么选:从 BOM 到首件的工艺核查清单

一句话结论:AI 眼镜的贴片不是"消费电子代工"的常规活,它更靠近高密度封装工艺。选厂比的不是报价,是工艺窗口和过程数据能不能摊开给你看。#mermaid-svg-YaPSQB8cLY1QmzlT{font-family:"trebuchet ms",verdana,arial,sa…

📅 2026/11/6 8:48:47
基于SpringBoot Vue公司财务管理系统

基于SpringBoot Vue公司财务管理系统

系统介绍: 基于SpringBoot和Vue实现的公司财务管理系统采用前后端分离的架构方式。系统设计了三种角色,分别是管理员、财务人员、员工。 管理员可以在系统后台中进行登录、首页、用户管理、部门与费用科目管理、报销管理、借款管理、记账凭证管理、工资管…

📅 2026/11/6 8:48:47
广东尘埃粒子计数器选型指南

广东尘埃粒子计数器选型指南

在广东选尘埃粒子计数器,最先要定的不是品牌,也不是“通道数越多越好”的配置清单,而是一个更根本的问题:**这台仪器测出的数据,要拿去做什么**。在深圳的芯片封装车间,它要能看见0.1 μm级别的纳米颗粒&am…

📅 2026/11/6 8:48:47
MORE NEWS

更多资讯

📰

Cline CLI完全指南:在终端运行AI编程代理,实现CI/CD自动化代码审查

人工智能大模型AI Agent代码智能体AI 应用开发工具 【免费下载链接】cline-chinese Cline中文汉化版,Cline是一款在您的 IDE 中运行的自主编程助手,经您许可后可以创建/编辑文件、运行命令、使用浏览器等功能。 项目地址: https://gitcode.co…

📰

Windows域控 设置全域的密码策略 【全域策略生效】

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

📰

Spring+SpringMVC+MyBatis 整合(+拦截器) 详:

SpringSpringMVCMyBatis 整合(拦截器) 详: 目前为止博客基本已将掌握SpringMVC 相关的知识点; 终于来到了最终时刻 SSM 三大框架整合; 搭建SSM 框架的程序架构 SSM 框架整合其实就是:Mybatis Spring SpringMVC 的整合; 前面学习我们知道 &#xff1a…

📰

Oracle数据库基础学习

Oracle数据库基础学习 个人之前就学习过 mysql sqlserver 但笔记没有在CSDN上可能会有些跳跃~ 不明确地方可以看这位大佬的笔记~不是我的. Oracle 简介 OracleDatabase 又名Oracle RDBMS , 是甲骨文公司的一款关系数据库管理系统。(世界上最好的数据库系统;(历史悠…

📰

Java 面试

Java 面试宝典 不定时更新 Java的面试题, 有什么好的 感谢评论告知! 小提示 可以看旁边的文章目录, 自问自带看看自己会不会! 奉上本人Java学习笔记! Java 线程 泛型 集合 SSM Mybatis mybatis中namespace的作用 Namespace是命名空间…

📰

PowerShell监控——监控共享打印机 获取打印记录、打印人员、打印文件等详细信息

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

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬