LeetCode——1799. N 次操作后的最大分数和(Maximize Score After N Operations)[困难]——分析及代码(Java)

LeetCode——1799. N 次操作后的最大分数和[Maximize Score After N Operations][困难]——分析及代码[Java]

一、题目

给你 nums ,它是一个大小为 2 * n 的正整数数组。你必须对这个数组执行 n 次操作。
在第 i 次操作时(操作编号从 1 开始),你需要:

  • 选择两个元素 x 和 y 。
  • 获得分数 i * gcd(x, y) 。
  • 将 x 和 y 从 nums 中删除。

请你返回 n 次操作后你能获得的分数和最大为多少。
函数 gcd(x, y) 是 x 和 y 的最大公约数。

示例 1:

输入:nums = [1,2]
输出:1
解释:最优操作是:
(1 * gcd(1, 2)) = 1

示例 2:

输入:nums = [3,4,6,8]
输出:11
解释:最优操作是:
(1 * gcd(3, 6)) + (2 * gcd(4, 8)) = 3 + 8 = 11

示例 3:

输入:nums = [1,2,3,4,5,6]
输出:14
解释:最优操作是:
(1 * gcd(1, 5)) + (2 * gcd(2, 4)) + (3 * gcd(3, 6)) = 1 + 4 + 9 = 14

提示:

  • 1 <= n <= 7
  • nums.length == 2 * n
  • 1 <= nums[i] <= 10^6

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximize-score-after-n-operations
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

二、分析及代码

1. 预处理 + 状态压缩 + 动态规划

(1)思路

先对 nums 中所有数字组合的最大公约数进行预计算并存储,避免后续处理过程中反复计算。
将所有数字的选取状态用二进制方法进行压缩,第 i 位为 1 表示选取了该 nums[i],0 表示未选取 nums[i]。
结合动态规划方法,对每个状态根据其最新一组可能选择的数字,计算其操作后的最大值。

(2)代码

class Solution {
    public int maxScore(int[] nums) {
        int n = nums.length;
        int[][] gcdNum = new int[n][n];//预处理记忆化
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                gcdNum[i][j] = gcd(nums[i], nums[j]);//得到任意2数间的最大公约数

        int range = 1 << n;//二进制状态压缩
        int[] dp = new int[range];
        Arrays.fill(dp, 0);
        for (int i = 0; i < range; i++) {
            int cnt = count(i);//计算二进制中1的个数
            if ((cnt & 1) == 1)//选取了奇数个数,不符合条件,直接跳过
                continue;
            for (int j = 0; j < n; j++)//遍历最后一轮2个数可能的选择
                for (int k = j + 1; k < n; k++) {
                    int state = (1 << j) | (1 << k);//二进制状态压缩
                    if ((state & i) != state)//这2个数不全在当前状态选择范围内,跳过
                        continue;
                    dp[i] = Math.max(dp[i], dp[i - state] + gcdNum[j][k] * (cnt >> 1));//动态规划
                }
        }
        return dp[range - 1];
    }
    
    //辗转相除法求最大公约数
    public int gcd(int num1, int num2) {
        int diff = 0;
        while (num2 != 0) {
            diff = num1 % num2;
            num1 = num2;
            num2 = diff;
        }
        return num1;
    }

    //计算二进制中1的个数
    public int count(int num) {
        int cnt = 0;
        while (num > 0) {
            num = num & (num - 1);
            cnt++;
        }
        return cnt;
    }
}

(3)结果

执行用时 :37 ms,在所有 Java 提交中击败了 72.53% 的用户;
内存消耗 :37.5 MB,在所有 Java 提交中击败了 52.19% 的用户。

三、其他

暂无。

上一篇:MongoDB日常操作


下一篇:Codeforces Round #615 (Div. 3) D. MEX maximizing