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

福大大架构师每日一题

发布于 2025-01-16 14:58:26

6500

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

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的情况，那么进行动态规划计算：

• 利用两个 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 main

import (
    "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 {
        return2*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 {
    letmut reward_values = reward_values.clone();
    reward_values.sort();
    letn = reward_values.len();

    // 如果倒数第二个和倒数第一个元素满足条件
    if n >= 2 && reward_values[n - 2] == reward_values[n - 1] - 1 {
        return2 * reward_values[n - 1] - 1;
    }

    letmut f0 = 1_u64;
    letmut f1 = 0_u64;

    for &x in &reward_values {
        letmut mask = 0_u64;
        letone = 1_u64;
        mask = (one << x) - one; // 构造遮罩
        f1 = (f0 & mask) << x; // 更新 f1
        f0 |= f1; // 更新 f0
    }

    64 - f0.leading_zeros() asi32 - 1
}

fnmain() {
    letreward_values = vec![1, 6, 4, 3, 2];
    letresult = max_total_reward(reward_values);
    println!("{}", result);
}

C完整代码如下：

#include <stdio.h>
#include <stdlib.h>

intcompare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

intmaxTotalReward(int *rewardValues, int n) {
    qsort(rewardValues, n, sizeof(int), compare);

    if (n >= 2 && rewardValues[n - 2] == rewardValues[n - 1] - 1) {
        return2 * rewardValues[n - 1] - 1;
    }

    unsignedlonglong f0 = 1, f1 = 0;
    for (int i = 0; i < n; i++) {
        unsignedlonglong 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
}

intmain() {
    int rewardValues[] = {1, 6, 4, 3, 2};
    int n = sizeof(rewardValues) / sizeof(rewardValues[0]);
    int result = maxTotalReward(rewardValues, n);
    printf("%d\n", result);
    return0;
}

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) {
        return2 * rewardValues[n - 1] - 1;
    }

    // 使用一个长整型来模拟大整数
    unsignedlonglong f0 = 1, f1 = 0;
    for (int x : rewardValues) {
        unsignedlonglong mask = (1ULL << x) - 1;
        f1 = (f0 & mask) << x;
        f0 |= f1;
    }

    // 使用 bitset 来计算 f0 的有效位长度
    returnstatic_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;
    return0;
}

Python完整代码如下：

# -*-coding:utf-8-*-

defmax_total_reward(reward_values):
    # 排序
    reward_values.sort()
    n = len(reward_values)
    
    # 特殊情况处理
    if n >= 2and reward_values[-2] == reward_values[-1] - 1:
        return2 * 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() - 1

if __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) {
        return2 * 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: MIT
pragma solidity ^0.8.0;

contract RewardCalculator {
    functionmaxTotalReward(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) {
            return2 * 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
        }

        // 计算有效位长度
        returnbitLength(f0) - 1;
    }

    functionbitLength(uint256 value) internal pure returns (uint256) {
        uint256 length = 0;
        while (value > 0) {
            value >>= 1; // 将值右移，丢弃最低位
            length++;
        }
        return length;
    }
}