【每日一题】1498. 满足条件的子序列数目
1498. 满足条件的子序列数目 - 力扣(LeetCode)
给你一个整数数组
nums
和一个整数target
。请你统计并返回
nums
中能满足其最小元素与最大元素的 和 小于或等于target
的 非空 子序列的数目。由于答案可能很大,请将结果对
109 + 7
取余后返回。示例 1:
输入:nums = [3,5,6,7], target = 9 输出:4 解释:有 4 个子序列满足该条件。 [3] -> 最小元素 + 最大元素 <= target (3 + 3 <= 9) [3,5] -> (3 + 5 <= 9) [3,5,6] -> (3 + 6 <= 9) [3,6] -> (3 + 6 <= 9)示例 2:
输入:nums = [3,3,6,8], target = 10 输出:6 解释:有 6 个子序列满足该条件。(nums 中可以有重复数字) [3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]示例 3:
输入:nums = [2,3,3,4,6,7], target = 12 输出:61 解释:共有 63 个非空子序列,其中 2 个不满足条件([6,7], [7]) 有效序列总数为(63 - 2 = 61)提示:
1 <= nums.length <= 105
1 <= nums[i] <= 106
1 <= target <= 106
class Solution {int mod = (int)1e9 + 7;public int numSubseq(int[] nums, int target) {Arrays.sort(nums);int len = nums.length;int low = 0;int high = len - 1;long sum = 0;int prel = high;int preh = 0;int flag = 0;int[] pow = new int[len+1];pow[0] = 1;for (int i = 1; i <= len; i++) {pow[i] = pow[i - 1] * 2 % mod;}while(prel!=low||preh!=high) {int left = low;int right = high;prel = low;preh = high;while(left < right) {int mid = (left+right) / 2;if(nums[prel]+nums[mid] > target) right = mid;else left = mid+1;}//这里出来之后,left是满足的条件的后一项。if(nums[prel]+nums[left] > target ) right = left - 1; //right这时就是目标下标。int fps;if(right < prel) {break;}else fps = right;high = fps;left = prel;while(left < right) {int mid = (left+right) / 2;if(nums[fps]+nums[mid] > target) right = mid;else left = mid+1;}//这里出来后,left是第一次区间内不满足条件的后一项low = left;if(nums[fps]+nums[left] > target) left -= 1; int sps;sps = fps-left;left += 1;fps=fps-prel+1; if(prel!=low||preh!=high||flag==0){long tmp = pow[fps]-pow[sps];if(pow[fps]-pow[sps] < 0) tmp = pow[fps]-pow[sps]+mod; sum = (sum+tmp)%mod;// System.out.println("fps:"+fps);// System.out.println("sps:"+sps);// System.out.println("每次tmp1结果:"+tmp1);// //System.out.println("每次tmp2结果:"+tmp2);// System.out.println("每次sum结果:"+sum);// System.out.println("------------------");}flag++;} return (int)sum;}
}
每日一题,今天是中等题。虽然是中等题,但是使用到了多种知识,难度估计能比肩困难题了。
读题。首先要了解子序列的概念!子序列的定义:子序列就是在原来序列中找出一部分组成的序列(子序列不一定连续
)。也就是说,子序列对顺序没有要求,本质是求组合数。而对于序列的排列求法,有公式:2的个数次方,减一是不包含空集,不减一是包含空集。所以,求子序列的个数实际上可以转化为求集合个数,由集合个数再去处理。而题目要求的只有集合内最大数和最小数的和小于target即可。所以,我们可以将数组排序,接下来就是找个数的问题,看一眼数量,就知道不可能使用O(n)的方法处理了。所以自然就想到二分。
抛去循环,我们先来看看一次的过程。由于已经排完序了,所以要找最大值和最小值的和小于target,实际上的最小值就是下标为0的数值了,所以实际上是不用改变的。要找的只有右边的最大值的地方。所以我们可以写一个二分。二分的写法有很多,但是大家要注意处理好边界的问题。博主这里使用的是我最常用的写left在所求值后一个的位置。(这种方法要处理的边界一般在于两侧。)至于后面用于循环的prel暂且可以先当成0(下标)。所以,出第一个二分循环之后的left,实际上会是目标值的前一个,但有可能left在len-1的位置,这个位置就需要边界处理。有可能是最后一个不符合,也可能都符合,所以需要多处理一个判断。这里使用fps(first position)来存储第一个循环的位置,这个位置代表了,从当前最小值开始所能组成的符合要求的最多元素的集合。即【0,left】是目前符合要求的。
不一定这个集合里所有的数都可以,比如【0,5,8,12,16】taget是12,实际上对于0到12的集合是可以处理的,但5到12的集合是不可以的,所以第二个循环就用来处理实际循环内不符合要求的返回,也就是【5,12】这个位置,例子中12这个位置会在第一次的fps的位置就找到,第二次找到的位置也需要存储。博主这里采用的是存储个数,所以第一个fps不需要处理。而第二个sps【second position】就需要使用fps-left的位置。那么这时候符合要求的集合个数实际上就知道了,是pow(2,fps)-pow(2,sps)。因为两边都会计算空集,所以相减完就可以相互抵消,不需要做多余的处理。那第一次循环的处理就完了,接下来是多次的循环。
在首次循环中不符合条件的集合中也有可能出现符合条件的集合,如【0,5,6,8,12,16】 target为12。在这个集合中,第一次找到的仍然是【0,12】的集合,但实际上【5,6】的集合也是符合条件的,也可以找到相应的子序列。所以一次显然是不够的。那有循环就需要循环终止的条件,用什么来做循环终止的条件呢?就是两次找到的集合边界都一样的时候。这时候就说明,这个集合里不存在符合条件的子集了。所以,需要prel(prelow)和preh(prehigh)来记录一下边界。而且需要一个flag来记录循环了。这涉及到了对最终数据的处理。如果循环的边界和前一次相同就不需要在继续循环了。但一开始的边界是会相同的,所以一开始需要使用flag来让第一次的结果可以计入sum。而后续flag就不需要了。判断边界是否相同即可。不同则可以计入sum。相同就不需要计入。这里还需要对fps的位置做一次判断,如果fps的位置<0,那么说明这个集合里没有子集是符合条件的。(在这之前会对fps的位置(实际上是right)做一个判断)
处理完循环。就到了处理最终数据的处理了。这会涉及到大数处理和前缀和的知识。
由于数值过大,基本上确定会超过int的计数范围,所以需要开long,而且在计算过程中就需要对其进行处理。使用一个数组来存储各个pow(2,n)的数值,并且在数值过程中对其进行mod运算(这个会对我们后续处理有点影响)。这个会使用到前缀和的知识,开一个len+1的数组,给pow[0]赋值1也就是2的0次方,之后对每个位置的值乘2处理,并乘2过程中进行mod处理。这样在最后求职时就可以常数时间拿到数值。
这里就要填坑了,由于过程中mod的处理,所以有可能出现2的高次方减去2的低次方出现负数的情况,这种情况我们需要一点数学知识,如果高次方模完减低次方出现了负数,就需要加上一个mod(模数),这样才能得到正确答案。
最后,运行,通过。
最后,祝大家国庆快乐呀!!!!!
相关文章:

【每日一题】1498. 满足条件的子序列数目
1498. 满足条件的子序列数目 - 力扣(LeetCode) 给你一个整数数组 nums 和一个整数 target 。 请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。 由于答案可能很大,请将结果对 109 7 取余后…...
Go语言数据类型实例讲解 - Go语言从入门到实战
Go语言数据类型实例讲解 - Go语言从入门到实战 基础数据类型 bool string int int8 int16 int32 int64 uint uint8 uint16 uint32 uint64 uintptr byte rune float32 float64 complex64 complex128类型描述bool布尔型(bool):可以是true或f…...

RocketMQ 事务消息发送
目录 事务消息介绍 应用场景 功能原理 使用限制 使用示例 使用建议 事务消息介绍 在一些对数据一致性有强需求的场景,可以用 RocketMQ 事务消息来解决,从而保证上下游数据的一致性。 应用场景 分布式事务的诉求 分布式系统调用的特点为一个核…...
后端-POST请求中只需要两个参数,后端不想创建对象时
问题: 在前后端对接中,很多前端的规范是POST,参数放body里面,媒体类型是json,后端就需要用RequestBody去接收,但是后端只用接收两个对象,这时候后端不想创建对象,使用RequestParm&a…...

UG\NX二次开发 通过点云生成曲面 UF_MODL_create_surf_from_cloud
文章作者:里海 来源网站:《里海NX二次开发3000例专栏》 感谢粉丝订阅 感谢 Rlgun 订阅本专栏,非常感谢。 简介 有网友想做一个通过点云生成曲面的程序,我们也试一下 效果 代码 #include "me.hpp" /*HEAD CREATE_SURF_FROM_CLOUD CCC UFUN */...

Linux常用指令(二)
目录 一、 删除空目录(rmdir) 二、ln 硬链接与软链接 三、新建空文件或更新文件的时间戳(touch) 四、比较文件内容的差异(diff) 五、显示当前时间或设置系统时间(date) 六、显…...

【HUAWEI】单臂路由
目录 🥮写在前面 🥮2.1、拓扑图 🥮2.2、操作思路 🥮2.3、配置操作 🍣2.3.1、LSW4配置 🍣2.3.2、R2配置 🍣2.3.3、测试网络 🦐博客主页:大虾好吃吗的博客 &…...

安全学习_开发相关_Java第三方组件Log4jFastJSON及相关安全问题简介
文章目录 JNDI:(见图) Java-三方组件-Log4J&JNDILog4J:Log4j-组件安全复现使用Log4j Java-三方组件-FastJsonFastJson:Fastjson-组件安全复现对象转Json(带类型)Json转对象Fastjson漏洞复现(大佬文章 JNDI:(见图) …...

零代码编程:用ChatGPT批量自动下载archive.org上的音频书
http://archive.org 是一个神奇的网站,可以下载各种古旧的软件、书籍、音频、视频,还可以搜索各个网站的历史网页。 比如说,一些儿童故事音频就可以在http://archive.org下载到,可以用来做英语听力启蒙用。 举个例子,…...

力扣用队列实现栈
自己写的栈,再让其他函数去调用自己写的栈 typedef int QDataType; typedef struct QueueNode {struct QueueNode* next;//单链表QDataType data;//放数据 }QNode;typedef struct Queue {QNode* phead;//头节点QNode* ptail;//尾节点QDataType size; //统计有多少节…...

一朵华为云,如何做好百模千态?
点击关注 文丨刘雨琦、郝鑫 2005年华为提出网络时代的“All IP”,2011年提出数字化时代的“All Cloud”,2023年提出智能时代的“All Intelligence”。 截至目前,华为的战略升级经历了三个阶段。 步入智能化,需要迎接的困难依然…...

华为云云耀云服务器L实例评测 | 实例使用教学之软件安装:华为云云耀云服务器环境下安装 Docker
华为云云耀云服务器L实例评测 | 实例使用教学之软件安装:华为云云耀云服务器环境下安装 Docker 介绍华为云云耀云服务器 华为云云耀云服务器 (目前已经全新升级为 华为云云耀云服务器L实例) 华为云云耀云服务器是什么华为云云耀云…...

小程序编译器性能优化之路
作者 | 马可 导读 小程序编译器是百度开发者工具中的编译构建模块,用来将小程序代码转换成运行时代码。旧版编译器由于业务发展,存在编译慢、内存占用高的问题,我们对编译器做了一次大规模的重构,采用自研架构,做了多线…...

FFmpeg 命令:从入门到精通 | ffmpeg 命令分类查询
FFmpeg 命令:从入门到精通 | ffmpeg 命令分类查询 FFmpeg 命令:从入门到精通 | ffmpeg 命令分类查询ffmpeg -versionffmpeg -buildconfffmpeg -formatsffmpeg -muxersffmpeg -demuxersffmpeg -codecsffmpeg -decodersffmpeg -encodersffmpeg -bsfsffmpeg…...

Linux学习记录——삼십일 socket编程---TCP套接字
文章目录 TCP套接字简单通信1、服务端1、基本框架2、获取连接 2、客户端3、多进程4、多线程5、线程池6、简单的日志系统7、守护进程8、其它 TCP套接字简单通信 本篇gitee 学习完udp套接字通信后,再来看TCP套接字。 四个文件tcp_server.hpp, tcp_serve…...

【学习笔记】深度学习分布式系统
深度学习分布式系统 前言1. 数据并行:参数服务器2. 流水线并行:GPipe3. 张量并行:Megatron LM4. 切片并行:ZeRO5. 异步分布式:PATHWAYS总结参考链接 前言 最近跟着李沐老师的视频学习了深度学习分布式系统的发展。这里…...

【数据结构】树、二叉树的概念和二叉树的顺序结构及实现
目录 前言:一、树的概念及结构1.树的概念2.树的相关概念3.树的存储4.树在实际中的运用 二、二叉树概念及结构1.概念2.特殊的二叉树(1)满二叉树(2)完全二叉树 3.二叉树的性质4.二叉树的存储(1)顺序存储(2)链式存储 三、…...
rust学习-string
介绍 A UTF-8–encoded, growable string(可增长字符串). 拥有string内容的所有权 A String is made up of three components: a pointer to some bytes, a length, and a capacity. The length is the number of bytes currently stored in the buffer pub fn as_bytes(&…...

No167.精选前端面试题,享受每天的挑战和学习
🤍 前端开发工程师(主业)、技术博主(副业)、已过CET6 🍨 阿珊和她的猫_CSDN个人主页 🕠 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 🍚 蓝桥云课签约作者、已在蓝桥云课上架的前后端实战课程《Vue.js 和 Egg.js 开发企业级健康管理项目》、《带你从入…...

【python】pycharm导入anaconda环境
参考 Pycharm导入anaconda环境的教程图解 - 知乎 (zhihu.com)...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...

【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
Mobile ALOHA全身模仿学习
一、题目 Mobile ALOHA:通过低成本全身远程操作学习双手移动操作 传统模仿学习(Imitation Learning)缺点:聚焦与桌面操作,缺乏通用任务所需的移动性和灵活性 本论文优点:(1)在ALOHA…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...
Java数值运算常见陷阱与规避方法
整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...
日常一水C
多态 言简意赅:就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过,当子类和父类的函数名相同时,会隐藏父类的同名函数转而调用子类的同名函数,如果要调用父类的同名函数,那么就需要对父类进行引用&#…...