2025-01-16：执行操作可获得的最大总奖励Ⅱ。用go语言，给定一个整数数组 rewardValues，长度为 n，表示奖励的数值。

最开始，你的总奖励 x 为 0，数组中的所有下标都标记为“未标记”。你可以执行以下操作任意次：

1.从数组中选择一个“未标记”的下标 i，范围为 [0, n - 1]。

2.如果 rewardValues[i] 大于当前的总奖励 x，则将 rewardValues[i] 加入到 x 中（即 x = x + rewardValues[i]），并将下标 i 标记为“已标记”。

请以整数形式返回通过最优操作能够获得的最大总奖励。

1 <= rewardValues.length <= 5 * 10000。

1 <= rewardValues[i] <= 5 * 10000。

输入：rewardValues = [1,6,4,3,2]。

输出：11。

解释：

依次标记下标 0、2 和 1。总奖励为 11，这是可获得的最大值。

答案2025-01-16：

chatgpt[1]

题目来自leetcode3181。

大体步骤如下：

1.首先给 rewardValues 排序，使得数组中的奖励值从小到大排列。

2.判断是否有连续两个奖励值相邻且差值为1，如果存在这样的情况，那么选中这两个奖励值将得到最大奖励。

3.如果不存在连续两个奖励值相邻且差值为1的情况，那么进行动态规划计算：

• 利用两个 http://big.Int 类型的变量 f0 和 f1，f0 代表之前的总奖励情况，f1 则表示考虑当前奖励值后的总奖励情况。• 遍历 rewardValues 数组，对每个奖励值进行处理。• 创建一个 mask 对应当前奖励值，设置相应位为 1，其它位为 0。• 利用 f1 按位与 mask 的结果左移奖励值位数，并更新 f1。• 利用或操作将 f1 合并到 f0。

4.返回 f0 的二进制位长度减去1，即为最大总奖励。

总的时间复杂度：

• 排序数组的时间复杂度为 O(nlogn)，n 为数组长度。• 动态规划部分时间复杂度为O(n)，n 为数组长度。• 因此总的时间复杂度为 O(nlogn)。

总的额外空间复杂度：

• 除了排序需要 O(logn) 的额外空间外，动态规划部分只使用了常数级别的额外空间。• 所以总的额外空间复杂度为 O(logn)。Go完整代码如下：package mainimport ( "fmt" "math/big" "sort")func maxTotalReward(rewardValues []int) int { n := len(rewardValues) sort.Ints(rewardValues) if n >= 2 && rewardValues[n-2] == rewardValues[n-1]-1 { return 2*rewardValues[n-1] - 1 } f0, f1 := big.NewInt(1), big.NewInt(0) for _, x := range rewardValues { mask, one := big.NewInt(0), big.NewInt(1) mask.Sub(mask.Lsh(one, uint(x)), one) f1.Lsh(f1.And(f0, mask), uint(x)) f0.Or(f0, f1) } return f0.BitLen() - 1}func main() { rewardValues := []int{1, 6, 4, 3, 2} result := maxTotalReward(rewardValues) fmt.Println(result)}

在这里插入图片描述

Rust完整代码如下：fn max_total_reward(reward_values: Vec<i32>) -> i32 { let mut reward_values = reward_values.clone(); reward_values.sort(); let n = reward_values.len(); // 如果倒数第二个和倒数第一个元素满足条件 if n >= 2 && reward_values[n - 2] == reward_values[n - 1] - 1 { return 2 * reward_values[n - 1] - 1; } let mut f0 = 1_u64; let mut f1 = 0_u64; for &x in &reward_values { let mut mask = 0_u64; let one = 1_u64; mask = (one << x) - one; // 构造遮罩 f1 = (f0 & mask) << x; // 更新 f1 f0 |= f1; // 更新 f0 } 64 - f0.leading_zeros() as i32 - 1}fn main() { let reward_values = vec![1, 6, 4, 3, 2]; let result = max_total_reward(reward_values); println!("{}", result);}

在这里插入图片描述

C完整代码如下：#include <stdio.h>#include <stdlib.h>int compare(const void *a, const void *b) { return (*(int *)a - *(int *)b);}int maxTotalReward(int *rewardValues, int n) { qsort(rewardValues, n, sizeof(int), compare); if (n >= 2 && rewardValues[n - 2] == rewardValues[n - 1] - 1) { return 2 * rewardValues[n - 1] - 1; } unsigned long long f0 = 1, f1 = 0; for (int i = 0; i < n; i++) { unsigned long long mask = (1ULL << rewardValues[i]) - 1; f1 = (f0 & mask) << rewardValues[i]; f0 |= f1; } // 计算 f0 的二进制位数 int bit_length = 0; while (f0 > 0) { bit_length++; f0 >>= 1; // 右移一位 } return bit_length - 1; // 返回有效位数减去 1}int main() { int rewardValues[] = {1, 6, 4, 3, 2}; int n = sizeof(rewardValues) / sizeof(rewardValues[0]); int result = maxTotalReward(rewardValues, n); printf("%d\n", result); return 0;}

在这里插入图片描述

C++完整代码如下：#include <iostream>#include <vector>#include <algorithm>#include <bitset>int maxTotalReward(std::vector<int>& rewardValues) { int n = rewardValues.size(); std::sort(rewardValues.begin(), rewardValues.end()); // 特殊情况判断 if (n >= 2 && rewardValues[n - 2] == rewardValues[n - 1] - 1) { return 2 * rewardValues[n - 1] - 1; } // 使用一个长整型来模拟大整数 unsigned long long f0 = 1, f1 = 0; for (int x : rewardValues) { unsigned long long mask = (1ULL << x) - 1; f1 = (f0 & mask) << x; f0 |= f1; } // 使用 bitset 来计算 f0 的有效位长度 return static_cast<int>(std::bitset<64>(f0).count()) - 1;}int main() { std::vector<int> rewardValues = {1, 6, 4, 3, 2}; int result = maxTotalReward(rewardValues); std::cout << result << std::endl; return 0;}

在这里插入图片描述

Python完整代码如下：# -*-coding:utf-8-*-def max_total_reward(reward_values): # 排序 reward_values.sort() n = len(reward_values) # 特殊情况处理 if n >= 2 and reward_values[-2] == reward_values[-1] - 1: return 2 * reward_values[-1] - 1 # 初始化 f0 和 f1 f0 = 1 for x in reward_values: mask = (1 << x) - 1 # 创建掩码 f1 = (f0 & mask) << x # 计算新的 f1 f0 |= f1 # 更新 f0 # 计算 f0 的二进制位长度 return f0.bit_length() - 1if __name__ == "__main__": reward_values = [1, 6, 4, 3, 2] result = max_total_reward(reward_values) print(result)

在这里插入图片描述

JavaScript完整代码如下：function maxTotalReward(rewardValues) { const n = rewardValues.length; rewardValues.sort((a, b) => a - b); // 特殊情况处理 if (n >= 2 && rewardValues[n - 2] === rewardValues[n - 1] - 1) { return 2 * rewardValues[n - 1] - 1; } let f0 = BigInt(1); let f1 = BigInt(0); for (const x of rewardValues) { const mask = (BigInt(1) << BigInt(x)) - BigInt(1); f1 = (f0 & mask) << BigInt(x); f0 |= f1; } // 计算 f0 的二进制位长度 return f0.toString(2).length - 1;}const rewardValues = [1, 6, 4, 3, 2];const result = maxTotalReward(rewardValues);console.log(result);

在这里插入图片描述

Solidity完整代码如下：// SPDX-License-Identifier: MITpragma solidity ^0.8.0;contract RewardCalculator { function maxTotalReward(uint256[] memory rewardValues) public pure returns (uint256) { uint256 n = rewardValues.length; // 排序 for (uint256 i = 0; i < n - 1; i++) { for (uint256 j = i + 1; j < n; j++) { if (rewardValues[j] < rewardValues[i]) { uint256 temp = rewardValues[i]; rewardValues[i] = rewardValues[j]; rewardValues[j] = temp; } } } // 特殊情况处理 if (n >= 2 && rewardValues[n - 2] == rewardValues[n - 1] - 1) { return 2 * rewardValues[n - 1] - 1; } uint256 f0 = 1; // 初始值 uint256 f1; // 位运算 for (uint256 i = 0; i < n; i++) { uint256 mask = (1 << rewardValues[i]) - 1; // 计算掩码 f1 = (f0 & mask) << rewardValues[i]; // 新值 f0 |= f1; // 更新 f0 } // 计算有效位长度 return bitLength(f0) - 1; } function bitLength(uint256 value) internal pure returns (uint256) { uint256 length = 0; while (value > 0) { value >>= 1; // 将值右移，丢弃最低位 length++; } return length; }}

在这里插入图片描述

引用链接

[1] chatgpt: https://chatbotsplace.com/?rc=nnNWSCJ7EP