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

2741. 特别的排列 Medium

给你一个下标从 0 开始的整数数组 nums ,它包含 n 个 互不相同 的正整数。如果 nums 的一个排列满足以下条件,我们称它是一个特别的排列:

 ·对于 0 <= i < n - 1 的下标 i ,要么 nums[i] % nums[i+1] == 0 ,要么 nums[i+1] % nums[i] == 0 。

请你返回特别排列的总数目,由于答案可能很大,请将它对 109 + 7 取余 后返回。

示例 1:

输入:nums = [2,3,6]
输出:2
解释:[3,6,2] 和 [2,6,3] 是 nums 两个特别的排列。

示例 2:

输入:nums = [1,4,3]
输出:2
解释:[3,1,4] 和 [4,1,3] 是 nums 两个特别的排列。

提示:

 ·2 <= nums.length <= 14

 ·1 <= nums[i] <= 109

题目大意:在只有可整除的数字能相邻的情况下计算所有合法排列的数量。

分析:

(1)由于可整除的数字可以相邻,因此可整除的两个数之间可以视为有一条无向边,用图的思想处理本题,将每个数字视为一个结点。分别从数组中的每个结点开始进行一次深度优先遍历,计算可以连接所有结点的路径的个数sum,得到的sum即为所求的合法排列的数量;

(2)由于长度为N的数组有N!种排列,用枚举的方式搜索会超时,因此采用记忆化搜索加速计算。设当前遍历的结点为i,当前的状态为flag,状态flag表示已遍历的结点和未遍历的结点,如flag=0b011001时表示第2、3、6个结点已被遍历,而第1、4、5个结点还没有遍历。因为在相同状态(flag)下遍历i结点,返回的合法排列数量是相同的,所以建立二维数组dp,其中dp[i][flag]表示在状态flag的情况下遍历i结点可获得的合法排列数量,以此记录已遍历过的情况,加速深度优先搜索。

class Solution {
public:int specialPerm(vector<int>& nums) {int N=nums.size(),flag=(1<<N)-1,ans=0;vector<vector<int>> dp(N,vector<int>(1<<N,-1));function<int(int)> dfs=[&](int root){if(dp[root][flag]!=-1) return dp[root][flag];int sum=0;for(int i=0,f=1;i<N;++i,f<<=1){if(root!=i&&(flag&f)&&!(nums[i]%nums[root]&&nums[root]%nums[i])){flag^=f;sum=(sum+dfs(i))%1000000007;flag^=f;}}return dp[root][flag]=sum;};for(int i=0;i<N;++i) dp[i][0]=1;for(int i=0,f=1;i<N;++i,f<<=1){flag^=f;ans=(ans+dfs(i))%1000000007;flag^=f;}return ans;}
};

相关文章:

2741. 特别的排列 Medium

给你一个下标从 0 开始的整数数组 nums &#xff0c;它包含 n 个 互不相同 的正整数。如果 nums 的一个排列满足以下条件&#xff0c;我们称它是一个特别的排列&#xff1a; 对于 0 < i < n - 1 的下标 i &#xff0c;要么 nums[i] % nums[i1] 0 &#xff0c;要么 nums[…...

读AI新生:破解人机共存密码笔记15辅助博弈

1. 辅助博弈 1.1. assistance game 1.2. 逆强化学习如今已经是构建有效的人工智能系统的重要工具&#xff0c;但它做了一些简化的假设 1.2.1. 机器人一旦通过观察人类学会了奖励函数&#xff0c;它就会采用奖励函数&#xff0c;这样它就可以执行相同的任务 1.2.1.1. 解决这…...

C++ 因项目需求,需要将0~2的32次方这个区间的数字保存到内存当中(内存大小为4G),并且可以实现对任意一个数字的增删。(先叙述设计思路,再写岀代码)

问题&#xff1a; C 因项目需求&#xff0c;需要将0~2的32次方这个区间的数字保存到内存当中(内存大小为4G),并且可以实现对任意一个数字的增删。(先叙述设计思路&#xff0c;再写岀代码) 解答 设计思路代码实现说明 为了在有限的内存&#xff08;4GB&#xff09;中存储和操作 …...

Linux 下的性能监控与分析技巧

在日常的服务器管理和问题诊断过程中&#xff0c;Linux 命令行工具提供了强大的支持。本文通过几个常用的示例&#xff0c;介绍如何快速定位问题、监控服务器性能。 无论你是编程新手还是有一定经验的开发者&#xff0c;理解和掌握这些命令&#xff0c;都将在你的工作中大放异…...

不可复制网站上的文字——2种方法

禁用javascript或Console控制台代码 &#xff08;1&#xff09;F12键——设置——勾选禁用javascript &#xff08;2&#xff09;Console控制台敲如下代码&#xff1a; var allowPaste function(e){ e.stopImmediatePropagation(); return true; }; document.addEventListe…...

Ubuntu 22.04上编译安装c++ spdlog library

Very fast, header-only/compiled, C logging library. 请以root身份或sudo执行。 1. 安装必需的依赖项&#xff1a; sudo apt-get update sudo apt-get install git g cmake 2. 克隆 spdlog 仓库&#xff1a; cd /opt git clone https://github.com/gabime/spdlog.git …...

ESP32代码开发入门

ESP-IDF ESP-ADF开发 开发概要 编译环境及SDK搭建 整个开发流程是:下载ESP-IDF, ESP-ADF(按需下载),并安装, 编写hello world工程,编译并烧录到主板验证 可参照ESP32 esp-idf esp-adf环境安装及.a库创建与编译api大部分可以用glibc的接口 做了封装,时间time(NULL), 创建线程p…...

“势”是“态”的偶然性减少

“态势感知”中的“势”指的是一种趋势或倾向性&#xff0c;而“态”则表示状态或局势。这个术语常用于描述在一段时间内系统或事件显示出来的方向性变化或发展趋势。因此&#xff0c;可以将“态势”理解为系统或事件状态变化的趋势&#xff0c;这种变化通常反映出偶然性减少的…...

人脑计算机技术与Neuroplatform:未来计算的革命性进展

引言 想象一下&#xff0c;你在某个清晨醒来&#xff0c;准备开始一天的工作&#xff0c;而实际上你的大脑正作为一台生物计算机的核心&#xff0c;处理着大量复杂的信息。这并非科幻电影的情节&#xff0c;而是人脑计算机技术即将带来的现实。本文将深入探讨FinalSpark公司的…...

新版周易测算系统源码 去授权完美运行

已经去掉授权可以完美运行 更新了三个模板市面上都是几千几千的卖 更新了三套首页新ui 自己后台切换就行 源码大小&#xff1a;338M 源码下载&#xff1a;https://download.csdn.net/download/m0_66047725/89447857 更多资源下载&#xff1a;关注我....

【PYTHON】力扣刷题笔记 -- 0053. 最大子数组和【中等】

题目描述&#xff1a;给你一个整数数组 array: nums &#xff0c;请你找出一个具有最大和的连续子数组 sub-array&#xff0c;返回其最大和 子数组&#xff08;最少包含一个元素&#xff09;: 是数组中的一个连续部分 示例 1&#xff1a; 输入&#xff1a;nums [-2,1,-3,4,-1…...

Linux启动elasticsearch,提示权限不够

Linux启动elasticsearch&#xff0c;提示权限不够&#xff0c;如下图所示&#xff1a; 解决办法&#xff1a; 设置文件所有者&#xff0c;即使用户由权限访问文件 sudo chown -R 用户名[:新组] ./elasticsearch-8.10.4 //切换到elasticsearch-8.10.4目录同级 chown详细格式…...

css 布局出现无法去除的空白

案件介绍&#xff1a;在没有设置任何的css样式的情况下 文字顶部出现无法去除的空白 源代码 <div click"onClick" ><div class"tableTextButton--container"></div><Icon v-if"loading || thisLoading" type"ios-lo…...

使用SpringBoot整合filter

SpringBoot整合filter&#xff0c;和整合servlet类似&#xff0c;也有两种玩儿法 1、创建一个SpringBoot工程&#xff0c;在工程中创建一个filter过滤器&#xff0c;然后用注解WebFilter配置拦截的映射 2、启动类还是使用ServletComponentScan注解来扫描拦截器注解WebFilter 另…...

Python酷库之旅-第三方库openpyxl(15)

目录 一、 openpyxl库的由来 1、背景 2、起源 3、发展 4、特点 4-1、支持.xlsx格式 4-2、读写Excel文件 4-3、操作单元格 4-4、创建和修改工作表 4-5、样式设置 4-6、图表和公式 4-7、支持数字和日期格式 二、openpyxl库的优缺点 1、优点 1-1、支持现代Excel格式…...

葡萄串目标检测YoloV8——从Pytorch模型训练到C++部署

文章目录 软硬件准备数据准备数据处理脚本模型训练模型部署数据分享软硬件准备 训练端 PytorchultralyticsNvidia 3080Ti部署端 fastdeployonnxruntime数据准备 用labelimg进行数据标注 数据处理脚本 xml2yolo import os import glob import xml.etree.ElementTree as ETxm…...

OpenAI推出自我改进AI- CriticGPT

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…...

springboot系列七: Lombok注解,Spring Initializr,yaml语法

老韩学生 LombokLombok介绍Lombok常用注解Lombok应用实例代码实现idea安装lombok插件 Spring InitializrSpring Initializr介绍Spring Initializr使用演示需求说明方式1: IDEA创建方式2: start.spring.io创建 注意事项和说明 yaml语法yaml介绍使用文档yaml基本语法数据类型字面…...

专访ATFX首席战略官Drew Niv:以科技创新引领企业高速发展

在金融科技创新的浪潮中&#xff0c;人才是推动企业高速发展的核心驱动力&#xff0c;优质服务是引领企业急速前行的灯塔。作为差价合约领域的知名品牌&#xff0c;ATFX高度重视人才引进工作&#xff0c;秉持“聚天下英才而用之”的理念&#xff0c;在全球范围内广揽科技精英&a…...

关于FPGA对 DDR4 (MT40A256M16)的读写控制 4

关于FPGA对 DDR4 &#xff08;MT40A256M16&#xff09;的读写控制 4 语言 &#xff1a;Verilg HDL 、VHDL EDA工具&#xff1a;ISE、Vivado、Quartus II 关于FPGA对 DDR4 &#xff08;MT40A256M16&#xff09;的读写控制 4一、引言二、DDR4 SDRAM设备中模式寄存器重要的模式寄存…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...