台州北京网站建设/广告推广方案
个人主页:元清加油_【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 整除
算法原理思路讲解
- 我们需要在每⼀个位置上考虑所有的可能情况并且不能出现重复。
- 通过深度优先搜索的⽅式,不断地枚举每个数在当前位置的可能性,并回溯到上⼀个状态,直到枚举完所有可能性,得到正确的结果。
- 我们需要定义⼀个变量 ⽤来记录所有可能的排列数量,⼀个⼀维数组 check 标记元素,然后从第⼀个位置开始进⾏递归。
一、画出决策树
决策树就是我们后面设计函数的思路
二、设计代码
(1)全局变量
int ret;bool check[16] = { false };
- ret(可以构造的 优美排列 的 数量 )
- check(用来检测这个数字是否用过)
(2)设计递归函数
void dfs(int n, int pos)
- 参数:n(一到n的数字),pos(当前要处理的位置下标);
- 返回值:无;
- 函数作用:在当前位置填⼊⼀个合理的数字,查找所有满⾜条件的排列。
递归流程如下
- 递归结束条件:当 pos 等于 n 时,说明已经处理完了所有数字,将当前数组存⼊结果中;
- 在每个递归状态中,枚举所有下标 i,若这个下标未被标记,并且满⾜题⽬条件之⼀:
- 将 check[i] 标记为 true;
- 对第 pos+1 个位置进⾏递归;
- 将 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刷题--- 优美的排列
个人主页:元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客 个人专栏 力扣递归算法题 http://t.csdnimg.cn/yUl2I 【C】 http://t.csdnimg.cn/6AbpV 数据结构与算法 http://t.cs…...

关于edge浏览器以及插件推荐【亲测好用】
一.edge浏览器介绍 Edge 浏览器是由微软公司开发的一款新一代网络浏览器。它最初于2015年发布,是微软Windows 10 操作系统的默认浏览器,后来还推出了适用于 Android 和 iOS 等移动设备的版本。Edge 浏览器采用了全新的浏览器内核,称为 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一些问题思考
一,zygote通信为什么用socket,而不是binder? 1,binder通信依赖用户空间进程Servicemanager,socket通信不依赖用户空间进程。zygote与servicemanager, surfaceflinger等都是通过各自init.rc文件被init进程解析加载,时…...

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

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

【Proteus仿真】【Arduino单片机】水质监测报警系统设计
文章目录 一、功能简介二、软件设计三、实验现象联系作者 一、功能简介 本项目使用Proteus8仿真Arduino单片机控制器,使用按键、LED、蜂鸣器、LCD1602、ADC、PH传感器、浑浊度传感器、DS18B20温度传感器、继电器模块等。 主要功能: 系统运行后…...

随机问卷调查数据的处理(uniapp)
需求:问卷调查 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 题目来源:2928. 给小朋友们分糖果 I 解法1:暴力 枚举 3 位小朋友的糖果数,范围为 [0, limit],分别记为 i、j、k。 当满足 i j k n 时,答案 1。 代码: /** lc appleetcode.c…...

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

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

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

分布式训练通信NCCL之Ring-Allreduce详解
🎀个人主页: https://zhangxiaoshu.blog.csdn.net 📢欢迎大家:关注🔍点赞👍评论📝收藏⭐️,如有错误敬请指正! 💕未来很长,值得我们全力奔赴更美好的生活&…...

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

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

vue+element实现动态表格:根据后台返回的属性名和字段动态生成可变表格
现有一个胡萝卜厂生产不同品种的胡萝卜,为了便于客户了解产品,现需在官网展示胡萝卜信息。现有的萝卜信息:编号(id)、名称(name)、保质期(age)、特点(remark&…...

云渲染UE4像素流送搭建(winows、ubuntu单实例与多实例像素流送)
windows/ubuntu20.4下UE4.27.2像素流送 像素流送技术可以将服务器端打包的虚幻引擎应用程序在客户端的浏览器上运行,用户可以通过浏览器操作虚幻引擎应用程序,客户端无需下载虚幻引擎,本文实现两台机器通过物理介质网线实现虚幻引擎应用程序…...

Unity VR Pico apk安装失败:INSTALL_FAILED_UPDATE_INCOMPATIBLE
我的报错: PICO4企业版。安装apk,报错“安装失败。(所属的Unity项目打包的apk,被我在同一台pico4安装了20次) 调试方法: PIco4发布使用UNITY开发的Vr应用,格式为apk,安装的时候发生…...

Prompt 提示工程学习笔记
一、Prompt设计的四个关键要素: 任务描述、输入数据、上下文信息、提示风格 (1)任务描述:描述想要让LLM遵循的指令。描述应详细清晰,可进一步使用关键词突出特殊设置,从而更好地指导LLM工作。 ࿰…...

STM32实现三个小灯亮
led.c #include"led.h"void Led_Init(void) {GPIO_InitTypeDef GPIO_VALUE; //???RCC_APB2PeriphClockCmd(RCC_APB2Periph_GPIOC,ENABLE);//???GPIO_VALUE.GPIO_ModeGPIO_Mode_Out_PP;//???? ????GPIO_VALUE.GPIO_PinGPIO_Pin_1|GPIO_Pin_2|GPIO_P…...

1861_什么是H桥
Grey 全部学习内容汇总: GitHub - GreyZhang/g_hardware_basic: You should learn some hardware design knowledge in case hardware engineer would ask you to prove your software is right when their hardware design is wrong! 1861_什么是H桥 H桥电路可以…...

【计算机四级(网络工程师)笔记】操作系统运行机制
目录 一、中央处理器(CPU) 1.1CPU的状态 1.2指令分类 二、寄存器 2.1寄存器分类 2.2程序状态字(PSW) 三、系统调用 3.1系统调用与一般过程调用的区别 3.2系统调用的分类 四、中断与异常 4.1中断 4.2异常 🌈嗨ÿ…...

Swagger快速入门
1、Swagger快速入门 1.1 swagger介绍 官网:https://swagger.io/ Swagger 是一个规范和完整的Web API框架,用于生成、描述、调用和可视化 RESTful 风格的 Web 服务。 功能主要包含以下几点: A. 使得前后端分离开发更加方便,有利于团队协作…...

数据结构之<堆>的介绍
1.简介 堆是一种特殊的数据结构,通常用于实现优先队列。堆是一个可以被看作近似完全二叉树的结构,并且具有一些特殊的性质,根据这些性质,堆被分为最大堆(或者大根堆,大顶堆)和最小堆两种。 2.…...

使用Ubuntu22+Minikube快速搭建K8S开发环境
安装Vmware 这一步,可以参考我的如下课程。 安装Ubuntu22 下载ISO镜像 这里我推荐从清华镜像源下载,速度会快非常多。 下载地址:https://mirrors.tuna.tsinghua.edu.cn/ubuntu-releases/22.04.3/ 如果你报名了我的这门视频课程…...

【中小型企业网络实战案例 二】配置网络互连互通
【中小型企业网络实战案例 一】规划、需求和基本配置-CSDN博客 热门IT技术视频教程:https://xmws-it.blog.csdn.net/article/details/134398330?spm1001.2014.3001.5502 配置接入层交换机 1.以接入交换机ACC1为例,创建ACC1的业务VLAN 10和20。 <…...

Azure Machine Learning - Azure OpenAI GPT 3.5 Turbo 微调教程
本教程将引导你在Azure平台完成对 gpt-35-turbo-0613 模型的微调。 关注TechLead,分享AI全维度知识。作者拥有10年互联网服务架构、AI产品研发经验、团队管理经验,同济本复旦硕,复旦机器人智能实验室成员,阿里云认证的资深架构师&…...

运维大模型探索之 Text2PromQL 问答机器人
作者:陈昆仪(图杨) 大家下午好,我是来自阿里云可观测团队的算法工程师陈昆仪。今天分享的主题是“和我交谈并获得您想要的PromQL”。今天我跟大家分享在将AIGC技术运用到可观测领域的探索。 今天分享主要包括5个部分:…...

虚拟机VMware:变动ip修改固定ip
1、配置ip地址 vi /etc/sysconfig/network-scripts/ifcfg-ens33修改为: 修改如下:TYPE"Ethernet" # 网络类型为以太网 BOOTPROTO"static" # 手动分配ip NAME"ens33" # 网卡…...