Leetcode 3405. Count the Number of Arrays with K Matching Adjacent Elements
- Leetcode 3405. Count the Number of Arrays with K Matching Adjacent Elements
- 1. 解题思路
- 2. 代码实现
- 题目链接:3405. Count the Number of Arrays with K Matching Adjacent Elements
1. 解题思路
这一题虽然是一道hard的题目,但是委实是有点名不副实了,任何一个稍微学过一些高中排列组合相关内容的同学事实上应该都对这个题目比较熟悉。
这个题目的本质事实上就是构造一个长度为 n n n的数组,然后每一个元素有 m m m种选择,且有且仅有 k k k个元素与其前一个元素相同。
显然,我们先从数组当中选定 k k k个位置,令其与其前一元素相同,则其可能的选法必然就是 C n − 1 k C_{n-1}^{k} Cn−1k,即除了第一个位置之外,剩下的 n − 1 n-1 n−1个位置均可作为侯选位置。剩下的,我们就是要够长一个长度为 n − k n-k n−k的数组,使其两两元素不同,则其可能的构造方法就可以快速算出为 m ⋅ ( m − 1 ) n − k − 1 m \cdot (m-1)^{n-k-1} m⋅(m−1)n−k−1。
两者相乘即为最终的答案:
N = m ⋅ ( m − 1 ) n − k − 1 ⋅ C n − 1 k N = m \cdot (m-1)^{n-k-1} \cdot C_{n-1}^{k} N=m⋅(m−1)n−k−1⋅Cn−1k
剩下的我们只需要用python实现一下就行了……
2. 代码实现
给出python代码实现如下:
MOD = 10**9+7Factorials = [1 for _ in range(10**5+1)]
Revs = [1 for _ in range(10**5+1)]
for i in range(2, 10**5+1):Factorials[i] = (i * Factorials[i-1]) % MODRevs[i] = pow(Factorials[i], -1, mod = MOD)def C(n, m):return (Factorials[n] * Revs[m] * Revs[n-m]) % MOD if n >= m else 0class Solution:def countGoodArrays(self, n: int, m: int, k: int) -> int:return (m * pow(m-1, n-k-1, mod=MOD) * C(n-1, k)) % MOD
提交代码评测得到:耗时0ms,占用内存25.5MB。
相关文章:
Leetcode 3405. Count the Number of Arrays with K Matching Adjacent Elements
Leetcode 3405. Count the Number of Arrays with K Matching Adjacent Elements 1. 解题思路2. 代码实现 题目链接:3405. Count the Number of Arrays with K Matching Adjacent Elements 1. 解题思路 这一题虽然是一道hard的题目,但是委实是有点名不…...
Springboot(五十六)SpringBoot3集成SkyWalking
这里我们将skywalking集成到Springboot中。 关于docker部署skyWalking的相关问题,请移步《docker(二十八)docker-compose部署链路追踪SkyWalking》 一:下载java-agents 先放一下skyWalking的官网下载地址 Downloads | Apache SkyWalking 其他的版本的 APM 地址(这个我不需…...
有没有免费提取音频的软件?音频编辑软件介绍!
出于工作和生活娱乐等原因,有时候我们需要把音频单独提取出来(比如歌曲伴奏、人声清唱等、乐器独奏等)。要提取音频必须借助音频处理软件,那么有没有免费提取音频的软件呢?下面我们将为大家介绍几款免费软件࿰…...
Linux 中查看内存使用情况全攻略
Linux 中查看内存使用情况全攻略 在 Linux 系统运维与开发工作里,精准掌握内存使用状况对系统性能优化、故障排查起着举足轻重的作用。Linux 提供了多款实用工具来查看内存详情,下面我们就结合实际示例,深入了解这些工具的使用方法。 一、fr…...
【SQL Server】教材数据库(3)
接着教材数据库(1)的内容,完成下列查询。 1 查询订购高等教育出版社教材的学生姓名 2 查询比所有高等教育出版社的图书都贵的图书信息 3 列出每位学生姓名、订购教材书名、价格。 1、嵌套查询:use jiaocai select student.nam…...
使用 ECharts 与 Vue 构建数据可视化组件
在前端开发中,数据可视化是非常重要的一部分。ECharts 作为一个功能强大且易于使用的开源数据可视化库,被广泛应用于各种图表展示需求中。而 Vue.js 是当下流行的前端框架之一,它的数据驱动和组件化开发模式让我们能轻松地将 ECharts 集成到 …...
Yocto 项目 - 共享状态缓存 (Shared State Cache) 机制
引言 在嵌入式开发中,构建效率直接影响项目的开发进度和质量。Yocto 项目通过其核心工具 BitBake 提供了灵活而强大的构建能力。然而,OpenEmbedded 构建系统的传统设计是从头开始构建所有内容(Build from Scratch),这…...
Unity3D仿星露谷物语开发9之创建农场Scene
1、目标 绘制农场的场景。通过不同Sorting Layer控制物体的显示优先级,绘制Tilemap地图,添加Tilemap Collider碰撞器,同时添加Composite Collider碰撞器优化性能。 ps:绘制Tilemap的技巧:通过"Shift [" 可…...
STM32-笔记20-测量按键按下时间
1、按键按下的时间-思路 我们先检测下降沿信号,检测到以后,在回调函数里切换成检测上升沿信号,当两个信号都检测到的时候,这段时间就是按键按下的时间,如图所示:>N*(ARR1)CCRx的值 N是在这段时间内&…...
2024年12月30日Github流行趋势
项目名称:free-programming-books 项目地址url:https://github.com/EbookFoundation/free-programming-books项目语言:HTML历史star数:343,398今日star数:246项目维护者:vhf, eshellman, davorpa, MHM5000,…...
SAP PP bom历史导出 ALV 及XLSX 带ECN号
bom总数 104W PS超过XLSX上限 ,那就分文件 *&---------------------------------------------------------------------* *& Report ZRPT_PP_BOM_HIS_ECN *&---------------------------------------------------------------------* *& tcode:zpp0…...
使用WebRTC进行视频通信
一、WebRTC技术简介 什么是WebRTC? 是一种支持浏览器之间实时音频、视频和数据传输的开放源代码项目。它允许开发者在不需要任何第三方插件或软件的情况下实现点对点的实时通信。WebRTC已经成为现代Web应用中的关键技术,为开发者提供了强大的工具和API…...
npm ERR! ECONNRESET 解决方法
问题:npm 命令遇到的错误是 ECONNRESET,这通常与网络连接问题相关。设置代理解决问题。 一、查看当前代理设置 npm config get proxy npm config get https-proxy二、设置代理 npm config set proxy http://your-proxy-address:port npm config set h…...
【连续学习之SS-IL算法】2021年CPVR会议论文Ss-il:Separated softmax for incremental learning
1 介绍 年份:2021 期刊: 2021CPVR Ahn H, Kwak J, Lim S, et al. Ss-il: Separated softmax for incremental learning[C]//Proceedings of the IEEE/CVF International conference on computer vision. 2021: 844-853. 本文提出的SS-IL(…...
Go+chromedp实现Web UI自动化测试
1.为什么使用go进行UI自动化测试? 速度:Go速度很快,这在运行包含数百个UI测试的测试套件时是一个巨大的优势 并发性:可以利用Go的内置并发性(goroutines)来并行化测试执行 简单:Go的简约语法允许您编写可读且可维护…...
【MySQL 高级特性与性能优化】
MySQL 高级特性与性能优化 一、MySQL 存储引擎 (一)InnoDB 存储引擎 1. 特点 支持事务:InnoDB 是 MySQL 中提供完整 ACID 事务支持的存储引擎,这意味着它能够保证数据库操作在复杂的并发环境下的一致性、隔离性、原子性和持久…...
Spring Boot教程之三十九: 使用 Maven 将 Spring Boot 应用程序 Docker 化
如何使用 Maven 将 Spring Boot 应用程序 Docker 化? Docker是一个开源容器化工具,用于在隔离环境中构建、运行和管理应用程序。它方便开发人员捆绑其软件、库和配置文件。Docker 有助于将一个容器与另一个容器隔离。在本文中,为了将Spring B…...
微信小程序开发示例
微信小程序开发涉及多个方面,包括页面布局、交互逻辑、数据处理等。以下是一个简单的微信小程序开发示例,包括页面布局、样式定义、交互逻辑等方面的内容。 一、页面布局(WXML) <!-- index.wxml --> <view class"…...
【机器学习】概述
文章目录 1. 机器学习三步骤2. 机器学习图谱2.1 任务类型 (Task)2.2 模型选择 (Methods)2.3 学习场景 (Scenario) 1. 机器学习三步骤 定义一个模型 (Define a set of function) 选择一组合适的函数来表示模型。 评估模型好坏 (Goodness of function) 找到一个损失函数…...
音视频采集推流时间戳记录方案
音视频同步更多文章 深入理解音视频pts,dts,time_base以及时间数学公式_视频pts计算-CSDN博客 ffplay音视频同步分析_ffplay 音视频同步-CSDN博客 音视频采集打时间戳设计 实时音视频数据的采集和处理场景。具体来说: 采集阶段: 在音视频数据采集过…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...
华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...
【JVM面试篇】高频八股汇总——类加载和类加载器
目录 1. 讲一下类加载过程? 2. Java创建对象的过程? 3. 对象的生命周期? 4. 类加载器有哪些? 5. 双亲委派模型的作用(好处)? 6. 讲一下类的加载和双亲委派原则? 7. 双亲委派模…...
DingDing机器人群消息推送
文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人,点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置,详见说明文档 成功后,记录Webhook 2 API文档说明 点击设置说明 查看自…...
[ACTF2020 新生赛]Include 1(php://filter伪协议)
题目 做法 启动靶机,点进去 点进去 查看URL,有 ?fileflag.php说明存在文件包含,原理是php://filter 协议 当它与包含函数结合时,php://filter流会被当作php文件执行。 用php://filter加编码,能让PHP把文件内容…...
jdbc查询mysql数据库时,出现id顺序错误的情况
我在repository中的查询语句如下所示,即传入一个List<intager>的数据,返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致,会导致返回的id是从小到大排列的,但我不希望这样。 Query("SELECT NEW com…...
深度解析:etcd 在 Milvus 向量数据库中的关键作用
目录 🚀 深度解析:etcd 在 Milvus 向量数据库中的关键作用 💡 什么是 etcd? 🧠 Milvus 架构简介 📦 etcd 在 Milvus 中的核心作用 🔧 实际工作流程示意 ⚠️ 如果 etcd 出现问题会怎样&am…...
Appium下载安装配置保姆教程(图文详解)
目录 一、Appium软件介绍 1.特点 2.工作原理 3.应用场景 二、环境准备 安装 Node.js 安装 Appium 安装 JDK 安装 Android SDK 安装Python及依赖包 三、安装教程 1.Node.js安装 1.1.下载Node 1.2.安装程序 1.3.配置npm仓储和缓存 1.4. 配置环境 1.5.测试Node.j…...
