首页 > 其他分享 >[LeetCode] 2389. Longest Subsequence With Limited Sum

[LeetCode] 2389. Longest Subsequence With Limited Sum

时间:2022-12-25 12:23:48浏览次数:70  
标签:Limited nums int Sum subsequence Subsequence queries answer length

You are given an integer array nums of length n, and an integer array queries of length m.

Return an array answer of length m where answer[i] is the maximum size of a subsequence that you can take from nums such that the sum of its elements is less than or equal to queries[i].

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: nums = [4,5,2,1], queries = [3,10,21]
Output: [2,3,4]
Explanation: We answer the queries as follows:
- The subsequence [2,1] has a sum less than or equal to 3. It can be proven that 2 is the maximum size of such a subsequence, so answer[0] = 2.
- The subsequence [4,5,1] has a sum less than or equal to 10. It can be proven that 3 is the maximum size of such a subsequence, so answer[1] = 3.
- The subsequence [4,5,2,1] has a sum less than or equal to 21. It can be proven that 4 is the maximum size of such a subsequence, so answer[2] = 4.

Example 2:

Input: nums = [2,3,4,5], queries = [1]
Output: [0]
Explanation: The empty subsequence is the only subsequence that has a sum less than or equal to 1, so answer[0] = 0.

Constraints:

  • n == nums.length
  • m == queries.length
  • 1 <= n, m <= 1000
  • 1 <= nums[i], queries[i] <= 106

和有限的最长子序列。

给你一个长度为 n 的整数数组 nums ,和一个长度为 m 的整数数组 queries 。

返回一个长度为 m 的数组 answer ,其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列 的 最大 长度  。

子序列 是由一个数组删除某些元素(也可以不删除)但不改变剩余元素顺序得到的一个数组。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/longest-subsequence-with-limited-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

这道题很好,虽然是简单题,但是考察了多个知识点,我这里提供一个排序 + 前缀和 + 二分的思路。

这道题问的满足条件的最长子序列的长度,但是这里的条件是子序列的和 <= target。因为找的是子序列 subsequence 的和,意味着满足条件的子序列中的元素可以不连续,既然不连续,那么也就意味着我们可以对 input 数组进行排序。排序的作用是为了之后我们可以开辟一个额外数组记录前缀和。所以这里我们先对 input 数组作排序和记录前缀和两项操作。

此时我们会得到一个前缀和数组 presum,注意这个数组中的元素是有序的,所以此时我们可以用二分法找到满足 <= queries[i] 的 index。

时间O(nlogn) - O(n) 扫描 queries 数组,O(logn) 用二分法找到每个 query 的位置

空间O(n) - prefix sum array

Java实现

class Solution {
    public int[] answerQueries(int[] nums, int[] queries) {
        Arrays.sort(nums);
        int len = nums.length;
        int[] presum = new int[len];
        presum[0] = nums[0];
        for (int i = 1; i < len; i++) {
            presum[i] = presum[i - 1] + nums[i];
        }

        int m = queries.length;
        int[] res = new int[m];
        for (int i = 0; i < m; i++) {
            int j = helper(presum, queries[i]);
            res[i] = j + 1;
        }
        return res;
    }

    private int helper(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int res = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                res = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return res;
    }
}

 

LeetCode 题目总结

标签:Limited,nums,int,Sum,subsequence,Subsequence,queries,answer,length
From: https://www.cnblogs.com/cnoodle/p/17003858.html

相关文章

  • 解决“ ignoring dependency for device, assuming no driver”错误
    最近升级内核版本,需要把内核从4.14升级到4.19,控制台就是没有打印,通过strings__log_buf发现报错dw-apb-uartf8041000.serial1:ignoringdependencyfordevice,assum......
  • POJ-2533 Longest Ordered Subsequence
    POJ-2533LongestOrderedSubsequence题意:给出一个序列,求出这个序列的最长上升子序列序列\(A\)的上升子序列\(B\)定义如下:\(B\)为\(A\)的子序列\(B\)为严......
  • POJ-1458 Common Subsequence
    POJ-1458CommonSubsequence题意:首先对最长子序列有个定义:如果一个字符串a可以由另一个字符串b删去某些元素得到,那么说明a就是b的子序列字符串现在有两个字符串,请问最......
  • sumBy 数字运算符
    _=require('lodash');//varasync=require('async');//varasyncSave=require('asyncSave');varobjects=[{'n':4},{'n':2},{'n':8},{'n':6}]......
  • C++实现checksum校验和计算
    校验和概念差错控制编码是为了检查传输中的错误下面将一个报文的数据部分称为d,报文的冗余部分称为r发送方根据约定好的差错控制编码关系(关系指出dr之间的关系)和d生成出......
  • 机器学习基石---Why Can Machines Learn(Part6-Summary)
      这篇文章主要用自己的话对Week4-Week8的大体思路的一些总结,不涉及细节。  Part1-Part5主要阐述一个问题:learning在什么情况下是可行的?一个好的learning应该是在已知......
  • 题解 CF1762E【Tree Sum】
    problem根据prufer引理,有标号的无根树的种类是\(n^{n-2}\)。对于一棵n个节点的带权无根树,边权总是+1或者-1。那么总共有\(n^{n-2}*2^{n-1}\)种树。其......
  • Kubernetes(k8s) kubectl rollout resume常用命令
    kubectl在$HOME/.kube目录中查找一个名为config的配置文件。可以通过设置KUBECONFIG环境变量或设置--kubeconfig参数来指定其它kubeconfig文件。本文主要介绍K......
  • [LeetCode] 1785. Minimum Elements to Add to Form a Given Sum
    Youaregivenanintegerarray nums andtwointegers limit and goal.Thearray nums hasaninterestingpropertythat abs(nums[i])<=limit.Return the......
  • 1945.sum-of-digits-of-string-after-convert 字符串转化后的各位数字之和
    问题描述1945.字符串转化后的各位数字之和解题思路正常思路就好。代码classSolution{public:intgetLucky(strings,intk){vector<int>num;......