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

【每日一题】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. 满足条件的子序列数目 - 力扣&#xff08;LeetCode&#xff09; 给你一个整数数组 nums 和一个整数 target 。 请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。 由于答案可能很大&#xff0c;请将结果对 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布尔型&#xff08;bool&#xff09;&#xff1a;可以是true或f…...

RocketMQ 事务消息发送

目录 事务消息介绍 应用场景 功能原理 使用限制 使用示例 使用建议​ 事务消息介绍 在一些对数据一致性有强需求的场景&#xff0c;可以用 RocketMQ 事务消息来解决&#xff0c;从而保证上下游数据的一致性。 应用场景 分布式事务的诉求 分布式系统调用的特点为一个核…...

后端-POST请求中只需要两个参数,后端不想创建对象时

问题&#xff1a; 在前后端对接中&#xff0c;很多前端的规范是POST&#xff0c;参数放body里面&#xff0c;媒体类型是json&#xff0c;后端就需要用RequestBody去接收&#xff0c;但是后端只用接收两个对象&#xff0c;这时候后端不想创建对象&#xff0c;使用RequestParm&a…...

UG\NX二次开发 通过点云生成曲面 UF_MODL_create_surf_from_cloud

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

Linux常用指令(二)

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

【HUAWEI】单臂路由

目录 ​ &#x1f96e;写在前面 &#x1f96e;2.1、拓扑图 &#x1f96e;2.2、操作思路 &#x1f96e;2.3、配置操作 &#x1f363;2.3.1、LSW4配置 &#x1f363;2.3.2、R2配置 &#x1f363;2.3.3、测试网络 &#x1f990;博客主页&#xff1a;大虾好吃吗的博客 &…...

安全学习_开发相关_Java第三方组件Log4jFastJSON及相关安全问题简介

文章目录 JNDI&#xff1a;(见图) Java-三方组件-Log4J&JNDILog4J&#xff1a;Log4j-组件安全复现使用Log4j Java-三方组件-FastJsonFastJson&#xff1a;Fastjson-组件安全复现对象转Json(带类型)Json转对象Fastjson漏洞复现&#xff08;大佬文章 JNDI&#xff1a;(见图) …...

零代码编程:用ChatGPT批量自动下载archive.org上的音频书

http://archive.org 是一个神奇的网站&#xff0c;可以下载各种古旧的软件、书籍、音频、视频&#xff0c;还可以搜索各个网站的历史网页。 比如说&#xff0c;一些儿童故事音频就可以在http://archive.org下载到&#xff0c;可以用来做英语听力启蒙用。 举个例子&#xff0c…...

力扣用队列实现栈

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

一朵华为云,如何做好百模千态?

点击关注 文丨刘雨琦、郝鑫 2005年华为提出网络时代的“All IP”&#xff0c;2011年提出数字化时代的“All Cloud”&#xff0c;2023年提出智能时代的“All Intelligence”。 截至目前&#xff0c;华为的战略升级经历了三个阶段。 步入智能化&#xff0c;需要迎接的困难依然…...

华为云云耀云服务器L实例评测 | 实例使用教学之软件安装:华为云云耀云服务器环境下安装 Docker

华为云云耀云服务器L实例评测 &#xff5c; 实例使用教学之软件安装&#xff1a;华为云云耀云服务器环境下安装 Docker 介绍华为云云耀云服务器 华为云云耀云服务器 &#xff08;目前已经全新升级为 华为云云耀云服务器L实例&#xff09; 华为云云耀云服务器是什么华为云云耀云…...

小程序编译器性能优化之路

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

FFmpeg 命令:从入门到精通 | ffmpeg 命令分类查询

FFmpeg 命令&#xff1a;从入门到精通 | ffmpeg 命令分类查询 FFmpeg 命令&#xff1a;从入门到精通 | 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套接字通信后&#xff0c;再来看TCP套接字。 四个文件tcp_server.hpp&#xff0c; tcp_serve…...

【学习笔记】深度学习分布式系统

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

【数据结构】树、二叉树的概念和二叉树的顺序结构及实现

目录 前言&#xff1a;一、树的概念及结构1.树的概念2.树的相关概念3.树的存储4.树在实际中的运用 二、二叉树概念及结构1.概念2.特殊的二叉树&#xff08;1&#xff09;满二叉树&#xff08;2&#xff09;完全二叉树 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)...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

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 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...

日常一水C

多态 言简意赅&#xff1a;就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过&#xff0c;当子类和父类的函数名相同时&#xff0c;会隐藏父类的同名函数转而调用子类的同名函数&#xff0c;如果要调用父类的同名函数&#xff0c;那么就需要对父类进行引用&#…...