当前位置: 首页 > news >正文

LeetCode刷题--- 优美的排列

个人主页:元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客

个人专栏

力扣递归算法题

 http://t.csdnimg.cn/yUl2I   

【C++】    

 http://t.csdnimg.cn/6AbpV 

数据结构与算法

 ​​​​​​http://t.csdnimg.cn/hKh2l


前言:这个专栏主要讲述递归递归、搜索与回溯算法,所以下面题目主要也是这些算法做的  

我讲述题目会把讲解部分分为3个部分:
1、题目解析

2、算法原理思路讲解

3、代码实现


优美的排列

题目链接:

题目

假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm下标从 1 开始),只要满足下述条件 之一 ,该数组就是一个 优美的排列 :

  • perm[i] 能够被 i 整除
  • i 能够被 perm[i] 整除

给你一个整数 n ,返回可以构造的 优美排列 的 数量 。

示例 1:

输入:n = 2
输出:2
解释:
第 1 个优美的排列是 [1,2]:- perm[1] = 1 能被 i = 1 整除- perm[2] = 2 能被 i = 2 整除
第 2 个优美的排列是 [2,1]:- perm[1] = 2 能被 i = 1 整除- i = 2 能被 perm[2] = 1 整除

示例 2:

输入:n = 1
输出:1

提示:

  • 1 <= n <= 15

解法

题目解析

题目的意思非常简单

假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm下标从 1 开始),只要满足下述条件 之一 ,该数组就是一个 优美的排列 :

  • perm[i] 能够被 i 整除
  • i 能够被 perm[i] 整除

给你一个整数 n ,返回可以构造的 优美排列 的 数量 。

示例 1:

输入:n = 2
输出:2
解释:
第 1 个优美的排列是 [1,2]:- perm[1] = 1 能被 i = 1 整除- perm[2] = 2 能被 i = 2 整除
第 2 个优美的排列是 [2,1]:- perm[1] = 2 能被 i = 1 整除- i = 2 能被 perm[2] = 1 整除

算法原理思路讲解 

  1. 我们需要在每⼀个位置上考虑所有的可能情况并且不能出现重复。
  2. 通过深度优先搜索的⽅式,不断地枚举每个数在当前位置的可能性,并回溯到上⼀个状态,直到枚举完所有可能性,得到正确的结果。
  3. 我们需要定义⼀个变量 ⽤来记录所有可能的排列数量,⼀个⼀维数组 check 标记元素,然后从第⼀个位置开始进⾏递归。

一、画出决策树

决策树就是我们后面设计函数的思路


二、设计代码

(1)全局变量

    int ret;bool check[16] = { false };
  • ret(可以构造的 优美排列 的 数量 )
  • check(用来检测这个数字是否用过)

(2)设计递归函数

    void dfs(int n, int pos)
  • 参数:n(一到n的数字),pos(当前要处理的位置下标);
  • 返回值:无;
  • 函数作用:在当前位置填⼊⼀个合理的数字,查找所有满⾜条件的排列。

递归流程如下

  1. 递归结束条件:当 pos 等于 n 时,说明已经处理完了所有数字,将当前数组存⼊结果中;
  2. 在每个递归状态中,枚举所有下标 i,若这个下标未被标记,并且满⾜题⽬条件之⼀:
    1.  将 check[i] 标记为 true;
    2.  对第 pos+1 个位置进⾏递归;
    3.  将 check[i] 重新赋值为 false,表⽰回溯;

以上思路讲解完毕,大家可以自己做一下了


代码实现

class Solution {
public:int ret;bool check[16] = { false };void dfs(int n, int pos){for (int i = 1; i <= n; i++){if (check[i] == false && (i % pos == 0 || pos % i == 0)){if (pos == n){ret++;return;}check[i] = true;dfs(n, pos + 1);check[i] = false;}}}int countArrangement(int n) {dfs(n, 1);return ret;}
};

相关文章:

LeetCode刷题--- 优美的排列

个人主页&#xff1a;元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客 个人专栏 力扣递归算法题 http://t.csdnimg.cn/yUl2I 【C】 http://t.csdnimg.cn/6AbpV 数据结构与算法 ​​​​​​http://t.cs…...

关于edge浏览器以及插件推荐【亲测好用】

一.edge浏览器介绍 Edge 浏览器是由微软公司开发的一款新一代网络浏览器。它最初于2015年发布&#xff0c;是微软Windows 10 操作系统的默认浏览器&#xff0c;后来还推出了适用于 Android 和 iOS 等移动设备的版本。Edge 浏览器采用了全新的浏览器内核&#xff0c;称为 Micros…...

关于“Python”的核心知识点整理大全43

目录 ​编辑 15.2.3 使2散点图并设置其样式 scatter_squares.py 15.2.4 使用 scatter()绘制一系列点 scatter_squares.py 15.2.5 自动计算数据 scatter_squares.py 15.2.6 删除数据点的轮廓 15.2.7 自定义颜色 15.2.8 使用颜色映射 scatter_squares.py 注意 15.2.9…...

Android Framework一些问题思考

一&#xff0c;zygote通信为什么用socket&#xff0c;而不是binder? 1&#xff0c;binder通信依赖用户空间进程Servicemanager&#xff0c;socket通信不依赖用户空间进程。zygote与servicemanager, surfaceflinger等都是通过各自init.rc文件被init进程解析加载&#xff0c;时…...

2024年安全员-C证证考试题库及安全员-C证试题解析

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2024年安全员-C证证考试题库及安全员-C证试题解析是安全生产模拟考试一点通结合&#xff08;安监局&#xff09;特种作业人员操作证考试大纲和&#xff08;质检局&#xff09;特种设备作业人员上岗证考试大纲随机出的…...

推广主要指标及定义

推广主要指标以直通车为例解释&#xff0c;如图所示 1.展示量&#xff1a;当消费者搜索某个词&#xff0c;推广计划在天猫直通车展示位上被买家看到的次数&#xff08;去掉被消费者快进划过、主图未完金展现等情况产生的曝光)&#xff1b; 2.点击量&#xff1a;消费者看到广告…...

【Proteus仿真】【Arduino单片机】水质监测报警系统设计

文章目录 一、功能简介二、软件设计三、实验现象联系作者 一、功能简介 本项目使用Proteus8仿真Arduino单片机控制器&#xff0c;使用按键、LED、蜂鸣器、LCD1602、ADC、PH传感器、浑浊度传感器、DS18B20温度传感器、继电器模块等。 主要功能&#xff1a; 系统运行后&#xf…...

随机问卷调查数据的处理(uniapp)

需求&#xff1a;问卷调查 1.返回的数据中包含单选、多选、多项文本框、单文本框、图片上传 2.需要对必填的选项进行校验 3.非必填的多项文本框内容 如果不填写 不提交 表单数据格式 res{"code": 0,"msg": null,"data": [{"executeDay&…...

开源分布式搜索引擎ElasticSearch结合内网穿透远程连接

文章目录 前言1. Windows 安装 Cpolar2. 创建Elasticsearch公网连接地址3. 远程连接Elasticsearch4. 设置固定二级子域名 前言 简单几步,结合Cpolar 内网穿透工具实现Java 远程连接操作本地分布式搜索和数据分析引擎Elasticsearch。 Cpolar内网穿透提供了更高的安全性和隐私保…...

Leetcode2928. 给小朋友们分糖果 I

Every day a Leetcode 题目来源&#xff1a;2928. 给小朋友们分糖果 I 解法1&#xff1a;暴力 枚举 3 位小朋友的糖果数&#xff0c;范围为 [0, limit]&#xff0c;分别记为 i、j、k。 当满足 i j k n 时&#xff0c;答案 1。 代码&#xff1a; /** lc appleetcode.c…...

go-zero开发入门之网关往rpc服务传递数据2

go-zero 的网关服务实际是个 go-zero 的 API 服务&#xff0c;也就是一个 http 服务&#xff0c;或者说 rest 服务。http 转 grpc 使用了开源的 grpcurl 库&#xff0c;当网关需要往 rpc 服务传递额外的数据&#xff0c;比如鉴权数据的时候&#xff0c;通过 http 的 header 进行…...

Cron介绍,以及常见的cron表达式

目录 一.cron介绍 1.什么是Cron&#xff1f; 2.Cron语法 时间字段的取值范围如下&#xff1a; 时间字段支持以下特殊字符&#xff1a; 下面是一些示例&#xff1a; 3.虚拟机安装cron(centos7展示) 二.常见的cron表达式 一.cron介绍 1.什么是Cron&#xff1f; Cron是一个…...

智能优化算法应用:基于协作搜索算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于协作搜索算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于协作搜索算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.协作搜索算法4.实验参数设定5.算法结果6.…...

分布式训练通信NCCL之Ring-Allreduce详解

&#x1f380;个人主页&#xff1a; https://zhangxiaoshu.blog.csdn.net &#x1f4e2;欢迎大家&#xff1a;关注&#x1f50d;点赞&#x1f44d;评论&#x1f4dd;收藏⭐️&#xff0c;如有错误敬请指正! &#x1f495;未来很长&#xff0c;值得我们全力奔赴更美好的生活&…...

os_util 工具类和方法的实现

一、前置说明 总体目录&#xff1a;《从 0-1 搭建企业级 APP 自动化测试框架》上节回顾&#xff1a;在 init_appium_and_devices 的实现思路分析 小节中&#xff0c;分析了实现 init_appium_and_devices 的思路&#xff0c;梳理出了必要的工具类和方法。本节目标&#xff1a;完…...

uview表单校验带星号

uView表单校验带星号可以通过设置required属性来实现。在uView中&#xff0c;可以使用组件来实现表单校验&#xff0c;具体步骤如下&#xff1a; 1、在需要校验的表单元素上添加required属性&#xff0c;例如&#xff1a; <u-form :model"detailInfo" ref"d…...

vue+element实现动态表格:根据后台返回的属性名和字段动态生成可变表格

现有一个胡萝卜厂生产不同品种的胡萝卜&#xff0c;为了便于客户了解产品&#xff0c;现需在官网展示胡萝卜信息。现有的萝卜信息&#xff1a;编号&#xff08;id&#xff09;、名称&#xff08;name&#xff09;、保质期&#xff08;age&#xff09;、特点&#xff08;remark&…...

云渲染UE4像素流送搭建(winows、ubuntu单实例与多实例像素流送)

windows/ubuntu20.4下UE4.27.2像素流送 像素流送技术可以将服务器端打包的虚幻引擎应用程序在客户端的浏览器上运行&#xff0c;用户可以通过浏览器操作虚幻引擎应用程序&#xff0c;客户端无需下载虚幻引擎&#xff0c;本文实现两台机器通过物理介质网线实现虚幻引擎应用程序…...

Unity VR Pico apk安装失败:INSTALL_FAILED_UPDATE_INCOMPATIBLE

我的报错&#xff1a; PICO4企业版。安装apk&#xff0c;报错“安装失败。&#xff08;所属的Unity项目打包的apk&#xff0c;被我在同一台pico4安装了20次&#xff09; 调试方法&#xff1a; PIco4发布使用UNITY开发的Vr应用&#xff0c;格式为apk&#xff0c;安装的时候发生…...

Prompt 提示工程学习笔记

一、Prompt设计的四个关键要素&#xff1a; 任务描述、输入数据、上下文信息、提示风格 &#xff08;1&#xff09;任务描述&#xff1a;描述想要让LLM遵循的指令。描述应详细清晰&#xff0c;可进一步使用关键词突出特殊设置&#xff0c;从而更好地指导LLM工作。 &#xff0…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...