代码编织梦想

和有限的最长子序列【LC2389】

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

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

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

真的是简单题?

  • 思路:贪心+前缀和+二分查找

    • 由于要求寻找小于目标值的子序列的最大长度【全局最优】,因此我们可以优先选择较小的数字【局部最优】
    • 又由于要求寻找的是子序列,数组元素可以改变顺序,因此可以将数组从小到大排序
    • 然后求出数组元素的前缀和数组,在前缀和数组中搜索小于目标值的最大值对应的下标,即为小于目标值的最长子序列长度
  • 实现

    由于前缀和数组可能存在越界,因此可以先记录queries数组的最大值,当前缀和超过该值时,退出循环,记录此时的下标,即为二分查找的右边界

    class Solution {
        public int[] answerQueries(int[] nums, int[] queries) {
            int m = queries.length, n = nums.length;
            int[] ans = new int[m];        
            Arrays.sort(nums);
            int maxQ = 0;
            for (int i = 0; i < m; i++){
                maxQ = Math.max(maxQ, queries[i]);
            }
            int[] sum = new int[n + 1];
            int r = n;
            for (int i = 0; i < n; i++){
                if (nums[i] + sum[i] > maxQ) {
                    r = i;
                    break;
                }
                sum[i + 1] = nums[i] + sum[i];
            }
    
            for (int i = 0; i < m; i++){
                ans[i] = binarySearch(sum, queries[i], r);
            }
            return ans;
        }
        public int binarySearch(int[] sum, int target, int r){
            int l = 1;
            while (l <= r){
                int mid = (l + r) >> 1;
                if (sum[mid] <= target){
                    l = mid + 1;
                }else{
                    r = mid - 1;
                }
            }
            return l - 1;
        }
    }
    
    • 复杂度
      • 时间复杂度: O ( m l o g n + n l o g n ) O(mlogn + nlogn) O(mlogn+nlogn),求取答案需要 m m m次二分查找,时间复杂度为 O ( m l o g n ) O(mlogn) O(mlogn),排序所需要的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)
      • 空间复杂度: O ( n ) O(n) O(n),前缀和数组的空间复杂度
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Tikitian/article/details/129616372

python 得到时间序列的每年、每月最后一天和第一天在序列中的位置_elibneh的博客-爱代码爱编程

2018.03.30 大概的函数是这个样子,里面提到的问题,未来一一解决。持续更新。 def getFirstLastDayMth(dateSeries): #dateSeries is like 2018-03-09 #my date series is from 2017.1.1 till now 2018.03.30 #imp

每日一题Day05 顺序表查找-爱代码爱编程

基于顺序存储结构的图书信息表的最贵图书的查找 题目描述 定义一个包含图书信息(书号、书名、价格)的顺序表,读入相应的图书数据来完成图书信息表的创建,然后查找价格最高的图书,输出相应图书的信息。 输入描述 总计输入n+1 行,其中,第一行是图书数目n,后n 行是n 本图书的信息(书号、书名、价格),每本图书信息占一行,书号、书名、价格用空格分隔,价格

每日一题Day06 顺序表查找-爱代码爱编程

基于顺序存储结构的图书信息表的最爱图书的查找 题目描述 定义一个包含图书信息(书号、书名、价格)的顺序表,读入相应的图书数据来完成图书信息表的创建,然后根据指定的最爱图书的名字,查找最爱的图书,输出相应图书的信息。 输入描述 总计n+m+2 行。首先输入n+1 行,其中,第一行是图书数目n,后n 行是n 本图书的信息(书号、书名、价格),每本图书信

蓝桥杯 Day8 java组 前缀和-爱代码爱编程

对于一个长度为n的数组 a[0]∼a[n−1],它的前缀和 sum[i] 等于 a[0]∼a[i] 的和。例如: sum[0] = a[0]sum[1] = a[0] + a[1]sum[2] = a[0] + a[1] + a[2]⋯        利用递推,只要计算 n 次,就能计算出所有的前缀和:sum[i] = sum[i-1] + a[i]。当

【蓝桥杯】每日一题冲刺国赛-爱代码爱编程

今日学习📃 🍭1、排他平方数 🌯2、买不到的数目 🥗3、回文日期 🍱4、约瑟夫环 🍭1、排他平方数 🎯题目描述 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 小明正看着 203879 这个数字发呆。原来,203879 * 203879 = 41566646641。这有什么神奇呢?仔细观察

动态规划算法-爱代码爱编程

一、前言 动态规划是一种常用的算法,在算法领域十分重要,但对于新手来说,理解起来有一定的挑战性,这篇博客将明确步骤来一步一步讲解动态规划到底该如何理解与运用。 二、解析动态规划算法 1.特点 ①把原来的问题分解成了【要点相同】的子问题(这个要点可以和后面讲的状态联系起来理解) ②所有问题都只需要解决一次(解决一次就是只需要由后面所说