当前位置: 首页 > 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;这是非常重要的&…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

作为测试我们应该关注redis哪些方面

1、功能测试 数据结构操作&#xff1a;验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化&#xff1a;测试aof和aof持久化机制&#xff0c;确保数据在开启后正确恢复。 事务&#xff1a;检查事务的原子性和回滚机制。 发布订阅&#xff1a;确保消息正确传递。 2、性…...