class Solution {
public:
int maxTotalReward(vector<int>& rewardValues) {
}
};
100319. 执行操作可获得的最大总奖励 I
给你一个整数数组 rewardValues，长度为 n，代表奖励的值。
最初，你的总奖励 x 为 0，所有下标都是 未标记 的。你可以执行以下操作 任意次 ：
[0, n - 1] 中选择一个 未标记 的下标 i。rewardValues[i] 大于 你当前的总奖励 x，则将 rewardValues[i] 加到 x 上（即 x = x + rewardValues[i]），并 标记 下标 i。以整数形式返回执行最优操作能够获得的 最大 总奖励。
示例 1：
输入：rewardValues = [1,1,3,3]
输出：4
解释：
依次标记下标 0 和 2，总奖励为 4，这是可获得的最大值。
示例 2：
输入：rewardValues = [1,6,4,3,2]
输出：11
解释：
依次标记下标 0、2 和 1。总奖励为 11，这是可获得的最大值。
提示：
1 <= rewardValues.length <= 20001 <= rewardValues[i] <= 2000原站题解
javascript 解法, 执行用时: 43 ms, 内存消耗: 51.1 MB, 提交时间: 2024-10-25 07:11:28
/**
* @param {number[]} rewardValues
* @return {number}
*/
var maxTotalReward = function(rewardValues) {
rewardValues.sort((a, b) => a - b);
const m = rewardValues[rewardValues.length - 1];
const dp = Array(2 * m).fill(0);
dp[0] = 1;
for (let x of rewardValues) {
for (let k = 2 * x - 1; k >= x; k--) {
if (dp[k - x] === 1) {
dp[k] = 1;
}
}
}
let res = 0;
for (let i = 0; i < dp.length; i++) {
if (dp[i] === 1) {
res = i;
}
}
return res;
};
golang 解法, 执行用时: 2 ms, 内存消耗: 3.5 MB, 提交时间: 2024-06-10 11:45:57
const w = bits.UintSize
type bitset []uint
// b <<= k
func (b bitset) lsh(k int) bitset {
shift, offset := k/w, k%w
if offset == 0 {
// Fast path
copy(b[shift:], b)
} else {
for i := len(b) - 1; i > shift; i-- {
b[i] = b[i-shift]<<offset | b[i-shift-1]>>(w-offset)
}
b[shift] = b[0] << offset
}
clear(b[:shift])
return b
}
// 把 >= start 的清零
func (b bitset) resetRange(start int) bitset {
i := start / w
b[i] &= ^(^uint(0) << (start % w))
clear(b[i+1:])
return b
}
// b |= c
func (b bitset) unionFrom(c bitset) {
for i, v := range c {
b[i] |= v
}
}
func (b bitset) lastIndex1() int {
for i := len(b) - 1; i >= 0; i-- {
if b[i] != 0 {
return i*w | (bits.Len(b[i]) - 1)
}
}
return -1
}
func maxTotalReward(rewardValues []int) int {
m := slices.Max(rewardValues)
if slices.Contains(rewardValues, m-1) {
return m*2 - 1
}
slices.Sort(rewardValues)
rewardValues = slices.Compact(rewardValues) // 去重
f := make(bitset, m*2/w+1)
f[0] = 1
for _, v := range rewardValues {
f.unionFrom(slices.Clone(f).lsh(v).resetRange(v * 2))
}
return f.lastIndex1()
}
java 解法, 执行用时: 4 ms, 内存消耗: 43.3 MB, 提交时间: 2024-06-10 11:45:12
import java.math.BigInteger;
class Solution {
public int maxTotalReward0(int[] rewardValues) {
BigInteger f = BigInteger.ONE;
for (int v : Arrays.stream(rewardValues).distinct().sorted().toArray()) {
BigInteger mask = BigInteger.ONE.shiftLeft(v).subtract(BigInteger.ONE);
f = f.or(f.and(mask).shiftLeft(v));
}
return f.bitLength() - 1;
}
// 优化1
public int maxTotalReward1(int[] rewardValues) {
int m = 0;
for (int v : rewardValues) {
m = Math.max(m, v);
}
for (int v : rewardValues) {
if (v == m - 1) {
return m * 2 - 1;
}
}
BigInteger f = BigInteger.ONE;
for (int v : Arrays.stream(rewardValues).distinct().sorted().toArray()) {
BigInteger mask = BigInteger.ONE.shiftLeft(v).subtract(BigInteger.ONE);
f = f.or(f.and(mask).shiftLeft(v));
}
return f.bitLength() - 1;
}
// 优化2
public int maxTotalReward(int[] rewardValues) {
int m = 0;
for (int v : rewardValues) {
m = Math.max(m, v);
}
Set<Integer> set = new HashSet<>();
for (int v : rewardValues) {
if (v == m - 1) {
return m * 2 - 1;
}
if (set.contains(v)) {
continue;
}
if (set.contains(m - 1 - v)) {
return m * 2 - 1;
}
set.add(v);
}
Arrays.sort(rewardValues);
int pre = 0;
BigInteger f = BigInteger.ONE;
for (int v : rewardValues) {
if (v == pre) {
continue;
}
BigInteger mask = BigInteger.ONE.shiftLeft(v).subtract(BigInteger.ONE);
f = f.or(f.and(mask).shiftLeft(v));
pre = v;
}
return f.bitLength() - 1;
}
}
cpp 解法, 执行用时: 12 ms, 内存消耗: 23.4 MB, 提交时间: 2024-06-10 11:43:34
class Solution {
public:
int maxTotalReward0(vector<int>& rewardValues) {
ranges::sort(rewardValues);
rewardValues.erase(unique(rewardValues.begin(), rewardValues.end()), rewardValues.end());
bitset<100000> f{1};
for (int v : rewardValues) {
int shift = f.size() - v;
// 左移 shift 再右移 shift，把所有 >= v 的比特位置 0
// f |= f << shift >> shift << v;
f |= f << shift >> (shift - v); // 简化上式
}
for (int i = rewardValues.back() * 2 - 1; ; i--) {
if (f.test(i)) {
return i;
}
}
}
// 优化1
int maxTotalReward1(vector<int>& rewardValues) {
int m = ranges::max(rewardValues);
if (ranges::find(rewardValues, m - 1) != rewardValues.end()) {
return m * 2 - 1;
}
ranges::sort(rewardValues);
rewardValues.erase(unique(rewardValues.begin(), rewardValues.end()), rewardValues.end());
bitset<100000> f{1};
for (int v : rewardValues) {
int shift = f.size() - v;
// 左移 shift 再右移 shift，把所有 >= v 的比特位置 0
// f |= f << shift >> shift << v;
f |= f << shift >> (shift - v); // 简化上式
}
for (int i = m * 2 - 1;; i--) {
if (f.test(i)) {
return i;
}
}
}
// 优化2
int maxTotalReward(vector<int>& rewardValues) {
int m = ranges::max(rewardValues);
unordered_set<int> s;
for (int v : rewardValues) {
if (s.contains(v)) {
continue;
}
if (v == m - 1 || s.contains(m - 1 - v)) {
return m * 2 - 1;
}
s.insert(v);
}
ranges::sort(rewardValues);
rewardValues.erase(unique(rewardValues.begin(), rewardValues.end()), rewardValues.end());
bitset<100000> f{1};
for (int v : rewardValues) {
int shift = f.size() - v;
// 左移 shift 再右移 shift，把所有 >= v 的比特位置 0
// f |= f << shift >> shift << v;
f |= f << shift >> (shift - v); // 简化上式
}
for (int i = m * 2 - 1;; i--) {
if (f.test(i)) {
return i;
}
}
}
};
python3 解法, 执行用时: 47 ms, 内存消耗: 16.8 MB, 提交时间: 2024-06-10 11:41:42
class Solution:
def maxTotalReward0(self, rewardValues: List[int]) -> int:
f = 1
for v in sorted(set(rewardValues)):
f |= (f & ((1 << v) - 1)) << v
return f.bit_length() - 1
# 优化1
def maxTotalReward1(self, rewardValues: List[int]) -> int:
m = max(rewardValues)
if m - 1 in rewardValues:
return m * 2 - 1
f = 1
for v in sorted(set(rewardValues)):
f |= (f & ((1 << v) - 1)) << v
return f.bit_length() - 1
# 优化2
def maxTotalReward(self, rewardValues: List[int]) -> int:
m = max(rewardValues)
s = set()
for v in rewardValues:
if v in s:
continue
if v == m - 1 or m - 1 - v in s:
return m * 2 - 1
s.add(v)
f = 1
for v in sorted(s):
f |= (f & ((1 << v) - 1)) << v
return f.bit_length() - 1