Easy

题目描述

有一个包，其中包含一些物品，每个物品上写着数字 1、0 或 -1。

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

包中最初包含：

  • numOnes 个写着 1 的物品
  • numZeros 个写着 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 是最大可能的和。

约束条件：

  • 0 <= numOnes, numZeros, numNegOnes <= 50
  • 0 <= k <= numOnes + numZeros + numNegOnes

解题思路

这道题目是一个典型的贪心算法问题。为了获得最大和，我们应该优先选择数值最大的物品。

解题思路：

  1. 贪心策略：按照物品价值从高到低的顺序选择，即优先选择值为1的物品，其次是值为0的物品，最后是值为-1的物品。

  2. 分情况讨论：

    • 如果 k <= numOnes：直接取k个值为1的物品，结果为k
    • 如果 numOnes < k <= numOnes + numZeros：取完所有值为1的物品，再取 k - numOnes 个值为0的物品，结果为numOnes
    • 如果 k > numOnes + numZeros：取完所有值为1和0的物品，还需要取 k - numOnes - numZeros 个值为-1的物品，结果为 numOnes - (k - numOnes - numZeros)

  3. 算法实现：使用简单的条件判断即可实现，时间复杂度为O(1)，空间复杂度也为O(1)。

这种贪心策略是最优的，因为在每一步都选择当前可用的最大值物品，能够保证全局最优解。

代码实现

class Solution {
public:
    int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
        if (k <= numOnes) {
            return k;
        }
        if (k <= numOnes + numZeros) {
            return numOnes;
        }
        return numOnes - (k - numOnes - numZeros);
    }
};

class Solution:
    def kItemsWithMaximumSum(self, numOnes: int, numZeros: int, numNegOnes: int, k: int) -> int:
        if k <= numOnes:
            return k
        if k <= numOnes + numZeros:
            return numOnes
        return numOnes - (k - numOnes - numZeros)

public class Solution {
    public int KItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
        if (k <= numOnes) {
            return k;
        }
        if (k <= numOnes + numZeros) {
            return numOnes;
        }
        return numOnes - (k - numOnes - numZeros);
    }
}

var kItemsWithMaximumSum = function(numOnes, numZeros, numNegOnes, k) {
    if (k <= numOnes) {
        return k;
    }
    if (k <= numOnes + numZeros) {
        return numOnes;
    }
    return numOnes - (k - numOnes - numZeros);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(1)只需要进行常数次比较和计算
空间复杂度O(1)只使用了常数级别的额外空间

相关题目