网站运营内容包含哪些,拖拉建网站,长春关键词seo,企业网站icp备案申请1498. 满足条件的子序列数目 - 力扣#xff08;LeetCode#xff09; 给你一个整数数组 nums 和一个整数 target 。 请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。 由于答案可能很大#xff0c;请将结果对 109 7 取余后…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 1051 nums[i] 1061 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[len1];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 (leftright) / 2;if(nums[prel]nums[mid] target) right mid;else left mid1;}//这里出来之后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 (leftright) / 2;if(nums[fps]nums[mid] target) right mid;else left mid1;}//这里出来后left是第一次区间内不满足条件的后一项low left;if(nums[fps]nums[left] target) left - 1; int sps;sps fps-left;left 1;fpsfps-prel1; if(prel!low||preh!high||flag0){long tmp pow[fps]-pow[sps];if(pow[fps]-pow[sps] 0) tmp pow[fps]-pow[sps]mod; sum (sumtmp)%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即可。所以我们可以将数组排序接下来就是找个数的问题看一眼数量就知道不可能使用On的方法处理了。所以自然就想到二分。 抛去循环我们先来看看一次的过程。由于已经排完序了所以要找最大值和最小值的和小于target实际上的最小值就是下标为0的数值了所以实际上是不用改变的。要找的只有右边的最大值的地方。所以我们可以写一个二分。二分的写法有很多但是大家要注意处理好边界的问题。博主这里使用的是我最常用的写left在所求值后一个的位置。这种方法要处理的边界一般在于两侧。至于后面用于循环的prel暂且可以先当成0下标。所以出第一个二分循环之后的left实际上会是目标值的前一个但有可能left在len-1的位置这个位置就需要边界处理。有可能是最后一个不符合也可能都符合所以需要多处理一个判断。这里使用fpsfirst position来存储第一个循环的位置这个位置代表了从当前最小值开始所能组成的符合要求的最多元素的集合。即【0left】是目前符合要求的。 不一定这个集合里所有的数都可以比如【0581216】taget是12实际上对于0到12的集合是可以处理的但5到12的集合是不可以的所以第二个循环就用来处理实际循环内不符合要求的返回也就是【512】这个位置例子中12这个位置会在第一次的fps的位置就找到第二次找到的位置也需要存储。博主这里采用的是存储个数所以第一个fps不需要处理。而第二个sps【second position】就需要使用fps-left的位置。那么这时候符合要求的集合个数实际上就知道了是pow2fps-pow2sps。因为两边都会计算空集所以相减完就可以相互抵消不需要做多余的处理。那第一次循环的处理就完了接下来是多次的循环。 在首次循环中不符合条件的集合中也有可能出现符合条件的集合如【05681216】 target为12。在这个集合中第一次找到的仍然是【012】的集合但实际上【56】的集合也是符合条件的也可以找到相应的子序列。所以一次显然是不够的。那有循环就需要循环终止的条件用什么来做循环终止的条件呢就是两次找到的集合边界都一样的时候。这时候就说明这个集合里不存在符合条件的子集了。所以需要prelprelow和prehprehigh来记录一下边界。而且需要一个flag来记录循环了。这涉及到了对最终数据的处理。如果循环的边界和前一次相同就不需要在继续循环了。但一开始的边界是会相同的所以一开始需要使用flag来让第一次的结果可以计入sum。而后续flag就不需要了。判断边界是否相同即可。不同则可以计入sum。相同就不需要计入。这里还需要对fps的位置做一次判断如果fps的位置0那么说明这个集合里没有子集是符合条件的。在这之前会对fps的位置实际上是right做一个判断 处理完循环。就到了处理最终数据的处理了。这会涉及到大数处理和前缀和的知识。
由于数值过大基本上确定会超过int的计数范围所以需要开long而且在计算过程中就需要对其进行处理。使用一个数组来存储各个pow2n的数值并且在数值过程中对其进行mod运算这个会对我们后续处理有点影响。这个会使用到前缀和的知识开一个len1的数组给pow[0]赋值1也就是2的0次方之后对每个位置的值乘2处理并乘2过程中进行mod处理。这样在最后求职时就可以常数时间拿到数值。 这里就要填坑了由于过程中mod的处理所以有可能出现2的高次方减去2的低次方出现负数的情况这种情况我们需要一点数学知识如果高次方模完减低次方出现了负数就需要加上一个mod模数这样才能得到正确答案。 最后运行通过。 最后祝大家国庆快乐呀
