Leetcode.2172 数组的最大与和
最佳答案 问答题库388位专家为你答疑解惑
题目链接
Leetcode.2172 数组的最大与和
rating : 2392
题目描述
给你一个长度为 n n n 的整数数组 n u m s nums nums 和一个整数 n u m S l o t s numSlots numSlots ,满足 2 ∗ n u m S l o t s ≥ n 2 * numSlots \geq n 2∗numSlots≥n 。总共有 n u m S l o t s numSlots numSlots 个篮子,编号为 1 1 1 到 n u m S l o t s numSlots numSlots 。
你需要把所有 n n n 个整数分到这些篮子中,且每个篮子 至多 有 2 2 2 个整数。一种分配方案的 与和 定义为每个数与它所在篮子编号的 按位与运算 结果之和。
- 比方说,将数字 [ 1 , 3 ] [1, 3] [1,3] 放入篮子 1 1 1 中, [ 4 , 6 ] [4, 6] [4,6] 放入篮子 2 2 2 中,这个方案的与和为 ( 1 A N D 1 ) + ( 3 A N D 1 ) + ( 4 A N D 2 ) + ( 6 A N D 2 ) = 1 + 1 + 0 + 2 = 4 (1\quad AND\quad1) + (3\quad AND\quad1) + (4\quad AND\quad 2) + (6\quad AND\quad 2) = 1 + 1 + 0 + 2 = 4 (1AND1)+(3AND1)+(4AND2)+(6AND2)=1+1+0+2=4 。
请你返回将 n u m s nums nums 中所有数放入 n u m S l o t s numSlots numSlots 个篮子中的最大与和。
示例 1:
输入:nums = [1,2,3,4,5,6], numSlots = 3
输出:9
解释:一个可行的方案是 [1, 4] 放入篮子 1 中,[2, 6] 放入篮子 2 中,[3, 5] 放入篮子 3 中。
最大与和为 (1 AND 1) + (4 AND 1) + (2 AND 2) + (6 AND 2) + (3 AND 3) + (5 AND 3) = 1 + 0 + 2 + 2 + 3 + 1 = 9 。
示例 2:
输入:nums = [1,3,10,4,7,1], numSlots = 9
输出:24
解释:一个可行的方案是 [1, 1] 放入篮子 1 中,[3] 放入篮子 3 中,[4] 放入篮子 4 中,[7] 放入篮子 7 中,[10] 放入篮子 9 中。
最大与和为 (1 AND 1) + (1 AND 1) + (3 AND 3) + (4 AND 4) + (7 AND 7) + (10 AND 9) = 1 + 1 + 3 + 4 + 7 + 8 = 24 。
注意,篮子 2 ,5 ,6 和 8 是空的,这是允许的。
提示:
- n = n u m s . l e n g t h n = nums.length n=nums.length
- 1 ≤ n u m S l o t s ≤ 9 1 \leq numSlots \leq 9 1≤numSlots≤9
- 1 ≤ n ≤ 2 ∗ n u m S l o t s 1 \leq n \leq 2 * numSlots 1≤n≤2∗numSlots
- 1 ≤ n u m s [ i ] ≤ 15 1 \leq nums[i] \leq 15 1≤nums[i]≤15
解法:状压dp
我们将原问题转换为 : 将 n u m s nums nums 中 n n n 个数字放入到 2 ∗ n u m S l o t s 2 * numSlots 2∗numSlots 篮子中,每个篮子最多放入一个数字,求最大 与和。
由于 2 ∗ n u m S l o t s 2 * numSlots 2∗numSlots 很小,所以我们可以使用状压dp。
我们定义 f ( i ) f(i) f(i) ( i i i 中二进制位 1 1 1 的数量为 c c c ),表示将 n u m s nums nums 中前 c c c 个数字放入篮子中的最大与和。
假设此时第 j j j 位的篮子是空的,此时这个篮子的编号为 j / 2 + 1 j / 2 + 1 j/2+1,就有:
{ t = i ∣ ( 1 < < j ) f [ t ] = m a x { f [ t ] , f [ i ] + ( j / 2 + 1 ) & n u m s [ c ] \begin{cases} t = i | (1 << j) \\ f[t] = max\{ f[t] , f[i] + (j/2 + 1) \& nums[c] \end{cases} {t=i∣(1<<j)f[t]=max{f[t],f[i]+(j/2+1)&nums[c]
时间复杂度: O ( 2 2 ∗ n u m S l o t s × 2 × n u m S l o t s ) O(2^{2 * numSlots} \times 2 \times numSlots) O(22∗numSlots×2×numSlots)
C++代码:
class Solution {
public:int maximumANDSum(vector<int>& nums, int slot) {int n = nums.size(),len = 1 << (2 * slot);vector<int> f(len);int ans = 0;for(int i = 0;i < len;i++){int c = __builtin_popcount(i);if(c >= n) continue;for(int j = 0;j < 2 * slot;j++){//寻找空蓝子,放入数字if((i & (1 << j)) == 0){int t = i | (1 << j);f[t] = max(f[t] , f[i] + ((j / 2 + 1) & nums[c]));ans = max(ans , f[t]);}}}return ans;}
};
99%的人还看了
相似问题
猜你感兴趣
版权申明
本文"Leetcode.2172 数组的最大与和":http://eshow365.cn/6-17574-0.html 内容来自互联网,请自行判断内容的正确性。如有侵权请联系我们,立即删除!
- 上一篇: 制作长图海报的详细指南,制作长图海报的5个步骤
- 下一篇: 【软考】9.1 顺序表/链表/栈和队列