首页 > 其他分享 >K 件物品的最大和

K 件物品的最大和

时间:2023-09-12 20:55:21浏览次数:40  
标签:numOnes 件物品 最大 标记 int numZeros 物品 numNegOnes

袋子中装有一些物品,每个物品上都标记着数字 1 、0 或 -1 。

给你四个非负整数 numOnes 、numZeros 、numNegOnes 和 k 。

袋子最初包含:

numOnes 件标记为 1 的物品。
numZeroes 件标记为 0 的物品。
numNegOnes 件标记为 -1 的物品。
现计划从这些物品中恰好选出 k 件物品。返回所有可行方案中,物品上所标记数字之和的最大值。

示例 1:

输入:numOnes = 3, numZeros = 2, numNegOnes = 0, k = 2
输出:2
解释:袋子中的物品分别标记为 {1, 1, 1, 0, 0} 。取 2 件标记为 1 的物品,得到的数字之和为 2 。
可以证明 2 是所有可行方案中的最大值。
示例 2:

输入:numOnes = 3, numZeros = 2, numNegOnes = 0, k = 4
输出:3
解释:袋子中的物品分别标记为 {1, 1, 1, 0, 0} 。取 3 件标记为 1 的物品,1 件标记为 0 的物品,得到的数字之和为 3 。
可以证明 3 是所有可行方案中的最大值。

无脑

class Solution {
    public int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
        //简单题重拳出击
        if(k > numOnes + numZeros){
            return numOnes - (k-numOnes-numZeros);
        }else if(k > numOnes && k <= numOnes+numZeros){
            return numOnes;
        }else{
            return k;
        }
    }
}

不明白为啥内存消耗少

class Solution {
    public int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
        if (k <= numOnes + numZeros)
            return Math.min(k, numOnes);
        return numOnes * 2 + numZeros - k;
    }
}

标签:numOnes,件物品,最大,标记,int,numZeros,物品,numNegOnes
From: https://www.cnblogs.com/xiaochaofang/p/17697788.html

相关文章

  • OSCAR开源专访 | 企业内源最大的挑战在于改变封闭思维和竞争观念——智网创新中心张东
    开源作为一种开放的、无边界的新型协作模式,是数字经济创新、开放、共享、可持续发展的源头活水。开源的大获成功也启发不少企业将开源软件开发的经验教训应用到组织内部中来,是谓内源。当前内源建设已成为企业提升研发效率、释放产业效能的重要手段,在通信行业亦是如此,同时各项能力建......
  • 剑指 Offer 63. 股票的最大利润
    题目链接:剑指Offer63.股票的最大利润题目描述:假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可能获得的最大利润是多少?解法思路:使用minv记录前i天的最低价格,第i天卖出的利润就是prices[i]-minv,遍历一遍数组,不断更新最大利润代码:funcmaxP......
  • 剑指 Offer 59 - I. 滑动窗口的最大值
    题目链接:剑指Offer59-I.滑动窗口的最大值题目描述:给定一个数组nums和滑动窗口的大小k,请找出所有滑动窗口里的最大值。解法思路:单调队列:维护一个单调的队列,队列中保存的是对应数字的数组下标每新加进来一个元素,首先删除队头(超出滑动窗口的范围的值)然后比较当前元......
  • LeetCode 53. 最大子数组和
    最大子数组和(medium)题目链接:53.最大子数组和题目描述:给你一个整数数组nums,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。子数组是数组中的一个连续部分。示例1:输入:nums=[-2,1,-3,4,-1,2,1,-5,4]输出:6解释:连续子数组[4,-1,2,1]的......
  • LeetCode 918. 环形子数组的最大和
    环形子数组的最大和(medium)题目链接:918.环形子数组的最大和题目描述:给定一个长度为n的环形整数数组nums,返回nums的非空子数组的最大可能和。环形数组意味着数组的末端将会与开头相连呈环状。形式上,nums[i]的下一个元素是nums[(i+1)%n],nums[i]的前一......
  • 代码随想录:● 654.最大二叉树 ● 617.合并二叉树 ● 700.二叉搜索树中的搜索 ● 98
     654.最大二叉树 给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下:二叉树的根是数组中的最大元素。左子树是通过数组中最大值左边部分构造出的最大二叉树。右子树是通过数组中最大值右边部分构造出的最大二叉树。通过给定的数组构建最大二叉树,并且输出这个......
  • 6574: 最大数 线段树/单点加/求区间最大值
    描述 给定一个正整数数列a1,a2,a3,⋯,an,每一个数都在0~p–1之间。可以对这列数进行两种操作:添加操作:向序列后添加一个数,序列长度变成n+1;询问操作:询问这个序列中最后L个数中最大的数是多少。程序运行的最开始,整数序列为空。写一个程序,读入操作的序列,并输出询问操作的......
  • 最大公因数的性质
    (b,c)=1,则(a,b)=(ac,b)若d是a和b的公约数,则d也是ac和b的公约数。若d是ac和b的公约数,d|b,d|ac。假设(c,d)=d0>1,d0|d,d0|b=kd,d0|c,(b,c)=d0>1,矛盾。所以(c,d)=1所以c|a。所以d也是a和b的公约数。左右集合等价,最大公因数相等。可以表述为,一个数乘上或除掉与另一个数互质的数,最大......
  • CF 1860 C【最大上升子序列】
    C.GameonPermutation这道题需要求出先手必胜点通过分析可知,每个位置结尾的最大上升子序列长度为2的点为先手必胜点,≥3的点为先手必败点。即只需要求出以每个位置为结尾的最大上升子序列长度为2的点的数量即可求出答案。本题目的n(1≤n≤3⋅105),所以无法使用O(n2)的方法,因此......
  • 查询分组后id最大的一条记录
    Linux系统-部署-运维系列导航 --连表SELECTt.*fromtest_tabletinnerjoin(selectt1.`name`,max(t1.id)idfromtest_tablet1groupbyt1.`name`)t2ont.id=t2.id; --子查询SELECTt.*fromtest_tabletwheret.id=(selectmax(t1.id)idfro......