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

[LeetBook]【学习日记】寻找和为指定数字的连续数字

题目

文件组合

待传输文件被切分成多个部分,按照原排列顺序,每部分文件编号均为一个 正整数(至少含有两个文件)。传输要求为:连续文件编号总和为接收方指定数字 target 的所有文件。请返回所有符合该要求的文件传输组合列表。

注意,返回时需遵循以下规则:

每种组合按照文件编号 升序 排列; 不同组合按照第一个文件编号 升序 排列。

示例 1:

输入:target = 12 输出:[[3, 4, 5]] 解释:在上述示例中,存在一个连续正整数序列的和为 12,为 [3, 4, 5]。
示例 2:

输入:target = 18 输出:[[3,4,5,6],[5,6,7]] 解释:在上述示例中,存在两个连续正整数序列的和分别为18,分别为 [3, 4, 5, 6] 和 [5, 6, 7]。

提示:

1 <= target <= 10^5

解法1:分类

  1. 这种做法是笔者最朴素的想法:如果遍历小于 target 的每一个数,逐个相加尝试该数是否能组成一个符合条件的文件序列,那时间复杂度太高了(其实这种就是滑动窗口的思想,复杂度只有O(N))。于是我想能否在遍历到这个数的同时,直接根据这个数与 target 之间的某种关系判断其能否形成合适的序列,于是在观察到文件序列其实是等差数列后,我决定依据等差数列的特点对其进行分类
  2. 使用 i 进行遍历。文件序列如果有奇数个元素,则可以找到等差中项,target 能整除 in = target / i 必须为奇数
  3. 文件序列如果有偶数个元素,则target 能整除 i + i+1n 和 target 的奇偶必须相同(!((n+target)%2))(因为n 表示有n对i + i+1,而i + i+1必为奇数,所以当n为偶数的时候,n对i + i+1的和为偶数;n为奇数的时候,n对i + i+1的和为奇数。所以 n 和 target 的奇偶必须相同)
  4. 由于题目要求不同组合按照第一个文件编号 升序 排列,而当我遍历 i 时,无法确定由 i 作为靠中间的元素的这个序列的头部是多少,所以我使用了 map 存储,利用了 map 会自动排序 key 的特点(结构:map<第一个文件编号,文件编号序列的 vector>)
class Solution {
public:vector<vector<int>> fileCombination(int target) {vector<vector<int>> all;map<int, vector<int>> forOrder;for(int i=1; i<=(target+1)/2; ++i){if(!(target%i)){//target 能整除 i,则可能的组合有奇数个元素int n = target / i;if(n%2 && i>n/2){//n 为组合中元素的个数,必须为奇数vector<int> group;for(int j=i-n/2; j<=i+n/2; ++j){group.push_back(j);}forOrder[i-n/2] = group;}}if(!(target%(i + i+1))){//target 能整除 i + i+1,可能的组合必为偶数个元素int n = target/(i + i+1);if(!((n+target)%2) && i-(n-1)>0){//n 和 target 的奇偶必须相同vector<int> group;for(int j=i-(n-1); j<=(i+1)+(n-1); ++j){group.push_back(j);}forOrder[i-(n-1)] = group;}}}// 将 forOrder 中的元素按顺序存入 all 中for (const auto& pair : forOrder) {all.push_back(pair.second);}return all;}
};

解法2:滑动窗口(双指针)

  1. 这种想法也很简单,从 i=1 开始,计算其后连续的序列的和,如果和小于 target,那么就在和的基础上往后再加一个数字;如果和大于 target 了,则表明此时的 i 作为开始元素找不到合适的序列,此时 i 往后移动,并记得让和减去上一个 i
  2. 这种想法虽然是遍历求和,并比较和与目标值,但是时间复杂度并不高,这是因为每次遍历和的计算都是在上一轮和的计算结果上进行的
  3. 由于是从 i=1 开始遍历,逐渐求和比较,故不存在有的序列会遍历不到的问题
//滑动窗口vector<vector<int>> fileCombination(int target) {vector<vector<int>> all;int i=1, j=2, sum=i+j;while(i<j){if(sum == target){vector<int> group;for(int k=i; k<=j; ++k){group.push_back(k);}all.push_back(group);}if(sum < target){++j;sum += j;// cout<<"j:"<<j<<"sum"<<sum<<endl;} else{sum -= i;++i;}}return all;}

解法3:等比数列求和公式求解

  1. 知道序列和 target,知道首项 i,那么可以利用等差数列求和公式 + 二次方程求根公式求出末项 j,遍历 i 找到所有符合的末项 j 即可。由于是使用公式计算,时间复杂度并不高
  2. 当 j 为整数时,符合条件,此处的判断方法为:if(j == (int)j)
  3. c++ 中,有int i,当 ii 结果超过int时,需要写成(long)ii,表达式 ii 的结果会首先根据表达式中操作数的类型来决定。如果 i 是整型(int),那么表达式 ii 也会被视为整型运算。
    在这里插入图片描述
//等差求和公式做法vector<vector<int>> fileCombination(int target) {vector<vector<int>> all;for(int i=1; i<(target+1)/2; ++i){double j = (-1+sqrt(1+4*(2*target+(long)i*i-i)))/2.0;if(j == (int)j){vector<int> group;for(int k=i; k<=(int)j; ++k){group.push_back(k);}all.push_back(group);}}return all;}

相关文章:

[LeetBook]【学习日记】寻找和为指定数字的连续数字

题目 文件组合 待传输文件被切分成多个部分&#xff0c;按照原排列顺序&#xff0c;每部分文件编号均为一个 正整数&#xff08;至少含有两个文件&#xff09;。传输要求为&#xff1a;连续文件编号总和为接收方指定数字 target 的所有文件。请返回所有符合该要求的文件传输组…...

阿里云中小企业扶持权益

为企业提供云资源和技术服务&#xff0c;助力企业开启智能时代创业新范式。阿里云推出中小企业扶持权益 上云必备&#xff0c;助力企业长期低成本用云 一、ECS-经济型e实例、ECS u1实例活动规则 活动时间 2023年10月31日0点0分0秒至2026年3月31日23点59分59秒 活动对象 同时满…...

2核4g服务器能支持多少人访问?并发数性能测评

2核4g服务器能支持多少人访问&#xff1f;支持80人同时访问&#xff0c;阿腾云使用阿里云2核4G5M带宽服务器&#xff0c;可以支撑80个左右并发用户。阿腾云以Web网站应用为例&#xff0c;如果视频图片媒体文件存储到对象存储OSS上&#xff0c;网站接入CDN&#xff0c;还可以支持…...

Anthropic官宣Claude3:建立大模型 推理、数学、编码和视觉等方面 新基准

文章目录 1. product2. Main2.1 核心能力2.2 打榜表现 3. My thoughtsReference Claude 3 在推理、数学、编码、多语言理解和视觉方面&#xff0c;全面超越GPT-4在内的所有大模型&#xff0c;重新树立大模型基准。 1. product https://claude.ai/ 国内暂不能使用&#xff0c;…...

STM32 TIM编码器接口

单片机学习&#xff01; 目录 文章目录 前言 一、编码器接口简介 1.1 编码器接口作用 1.2 编码器接口工作流程 1.3 编码器接口资源分布 1.4 编码器接口输入引脚 二、正交编码器 2.1 正交编码器功能 2.2 引脚作用 2.3 如何测量方向 2.4 正交信号优势 2.5 执行逻辑 三、编码器定时…...

Jupyter Notebook的安装和使用(windows环境)

一、jupyter notebook 安装 前提条件&#xff1a;安装python环境 安装python环境步骤&#xff1a; 1.下载官方python解释器 2.安装python 3.命令行窗口敲击命令pip install jupyter 4.安装jupyter之后&#xff0c;直接启动命令jupyter notebook,在默认浏览器中打开jupyte…...

Platformview在iOS与Android上的实现方式对比

Android中早期版本Platformview的实现基于Virtual Display。VirtualDisplay方案的原理是&#xff0c;先将Native View绘制到虚显&#xff0c;然后Flutter通过从虚显输出中获取纹理并将其与自己内部的widget树进行合成&#xff0c;最后作为Flutter在 Android 上更大的纹理输出的…...

使用lnmp环境部署laravel框架需要注意的点

1&#xff0c;上传项目文件后&#xff0c;需要chmod -R 777 storage授予文件权限&#xff0c;不然会报错file_put_contents(/): failed to open stream: Permission denied。 如果后面还是报错没有权限的话&#xff0c;就执行ps -ef |grep php查询php运行用户。然后执行chown …...

AI-RAN联盟在MWC24上正式启动

AI-RAN联盟在MWC24上正式启动。它的logo是这个样的&#xff1a; 2月26日&#xff0c;AI-RAN联盟&#xff08;AI-RAN Alliance&#xff09;在2024年世界移动通信大会&#xff08;MWC 2024&#xff09;上成立。创始成员包括亚马逊云科技、Arm、DeepSig、爱立信、微软、诺基亚、美…...

Reactor详解

目录 1、快速上手 介绍 2、响应式编程 2.1. 阻塞是对资源的浪费 2.2. 异步可以解决问题吗&#xff1f; 2.3.1. 可编排性与可读性 2.3.2. 就像装配流水线 2.3.3. 操作符&#xff08;Operators&#xff09; 2.3.4. subscribe() 之前什么都不会发生 2.3.5. 背压 2.3.6. …...

实践航拍小目标检测,基于YOLOv5全系列【n/s/m/l/x】参数模型开发构建无人机航拍场景下的小目标检测识别分析系统

关于无人机相关的场景在我们之前的博文也有一些比较早期的实践&#xff0c;感兴趣的话可以自行移步阅读即可&#xff1a; 《deepLabV3Plus实现无人机航拍目标分割识别系统》 《基于目标检测的无人机航拍场景下小目标检测实践》 《助力环保河道水质监测&#xff0c;基于yolov…...

分布式数据库中全局自增序列的实现

自增序列广泛使用于数据库的开发和设计中&#xff0c;用于生产唯一主键、日志流水号等唯一ID的场景。传统数据库中使用Sequence和自增列的方式实现自增序列的功能&#xff0c;在分布式数据库中兼容Oracle和MySQL等传统数据库语法&#xff0c;也是基于Sequence和自增列的方式实现…...

【论文阅读】TensoRF: Tensorial Radiance Fields 张量辐射场

发表于ECCV2022. 论文地址&#xff1a;https://arxiv.org/abs/2203.09517 源码地址&#xff1a;https://github.com/apchenstu/TensoRF 项目地址&#xff1a;https://apchenstu.github.io/TensoRF/ 摘要 本文提出了TensoRF&#xff0c;一种建模和重建辐射场的新方法。不同于Ne…...

深入了解 Android 中的 FrameLayout 布局

FrameLayout 是 Android 中常用的布局之一&#xff0c;它允许子视图堆叠在一起&#xff0c;可以在不同位置放置子视图。在这篇博客中&#xff0c;我们将详细介绍 FrameLayout 的属性及其作用。 <FrameLayout xmlns:android"http://schemas.android.com/apk/res/androi…...

高级大数据技术 实验一 scala编程

​ 高级大数据技术 实验一 scala编程 写的不是很好&#xff0c;大家多见谅&#xff01; 1. 计算水仙花数 实验目标; &#xff08;1&#xff09; 掌握scala的数组&#xff0c;列表&#xff0c;映射的定义与使用 &#xff08;2&#xff09; 掌握scala的基本编程 实验说明 …...

使用Fabric创建的canvas画布背景图片,自适应画布宽高

之前的文章写过vue2使用fabric实现简单画图demo&#xff0c;完成批阅功能&#xff1b;但是功能不完善&#xff0c;对于很大的图片就只能显示一部分出来&#xff0c;不符合我们的需求。这就需要改进&#xff0c;对我们设置的背景图进行自适应。 有问题的canvas画布背景 修改后的…...

枚举与尺取法(蓝桥杯 c++ 模板 题目 代码 注解)

目录 组合型枚举&#xff08;排列组合模板&#xff08;&#xff09;&#xff09;: 排列型枚举&#xff08;全排列&#xff09;模板&#xff1a; 题目一&#xff08;公平抽签 排列组合&#xff09;&#xff1a; ​编辑 代码&#xff1a; 题目二&#xff08;座次问题 全排…...

11、电源管理入门之Regulator驱动

目录 1. Regulator驱动是什么? 2. Regulator框架介绍 2.1 regulator consumer 2.2 regulator core 2.3 regulator driver 3. DTS配置文件及初始化 4. 运行时调用 5. Consumer API 5.1 Consumer Regulator Access (static & dynamic drivers) 5.2 Regulator Outp…...

24年证券从业考试注册报名流程详细图解,千万不要错过报名哦!

&#xff08;一&#xff09;时间安排 考生报名缴费时间&#xff1a;3月5日15时至3月8日15时 退费时间&#xff1a;3月7日15时至3月10日15时 准考证打印时间&#xff1a;3月20日15时至3月23日18时 &#xff08;二&#xff09;注册流程 1、进入中国证券业协会网站-从业人员管理-考…...

Git入门学习笔记

Git 是一个非常强大的分布式版本控制工具&#xff01; 在下载好Git之后&#xff0c;鼠标右击就可以显示 Git Bash 和 Git GUI&#xff0c;Git Bash 就像是在电脑上安装了一个小型的 Linux 系统&#xff01; 1. 打开 Git Bash 2. 设置用户信息&#xff08;这是非常重要的&…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

MMaDA: Multimodal Large Diffusion Language Models

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

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

上位机开发过程中的设计模式体会(1):工厂方法模式、单例模式和生成器模式

简介 在我的 QT/C 开发工作中&#xff0c;合理运用设计模式极大地提高了代码的可维护性和可扩展性。本文将分享我在实际项目中应用的三种创造型模式&#xff1a;工厂方法模式、单例模式和生成器模式。 1. 工厂模式 (Factory Pattern) 应用场景 在我的 QT 项目中曾经有一个需…...

comfyui 工作流中 图生视频 如何增加视频的长度到5秒

comfyUI 工作流怎么可以生成更长的视频。除了硬件显存要求之外还有别的方法吗&#xff1f; 在ComfyUI中实现图生视频并延长到5秒&#xff0c;需要结合多个扩展和技巧。以下是完整解决方案&#xff1a; 核心工作流配置&#xff08;24fps下5秒120帧&#xff09; #mermaid-svg-yP…...