class Solution {
public:
int maxSum(vector<int>& nums, int k) {
}
};
2897. 对数组执行操作使平方和最大
给你一个下标从 0 开始的整数数组 nums
和一个 正 整数 k
。
你可以对数组执行以下操作 任意次 :
i
和 j
,同时 将 nums[i]
更新为 (nums[i] AND nums[j])
且将 nums[j]
更新为 (nums[i] OR nums[j])
,OR
表示按位 或 运算,AND
表示按位 与 运算。你需要从最终的数组里选择 k
个元素,并计算它们的 平方 之和。
请你返回你可以得到的 最大 平方和。
由于答案可能会很大,将答案对 109 + 7
取余 后返回。
示例 1:
输入:nums = [2,6,5,8], k = 2 输出:261 解释:我们可以对数组执行以下操作: - 选择 i = 0 和 j = 3 ,同时将 nums[0] 变为 (2 AND 8) = 0 且 nums[3] 变为 (2 OR 8) = 10 ,结果数组为 nums = [0,6,5,10] 。 - 选择 i = 2 和 j = 3 ,同时将 nums[2] 变为 (5 AND 10) = 0 且 nums[3] 变为 (5 OR 10) = 15 ,结果数组为 nums = [0,6,0,15] 。 从最终数组里选择元素 15 和 6 ,平方和为 152 + 62 = 261 。 261 是可以得到的最大结果。
示例 2:
输入:nums = [4,5,4,7], k = 3 输出:90 解释:不需要执行任何操作。 选择元素 7 ,5 和 4 ,平方和为 72 + 52 + 42 = 90 。 90 是可以得到的最大结果。
提示:
1 <= k <= nums.length <= 105
1 <= nums[i] <= 109
原站题解
php 解法, 执行用时: 676 ms, 内存消耗: 31.2 MB, 提交时间: 2023-10-10 10:19:27
class Solution { /** * @param Integer[] $nums * @param Integer $k * @return Integer */ function maxSum($nums, $k) { $mod = 10 ** 9 + 7; $ans = 0; $cnt = array_fill(0, 30, 0); foreach ( $nums as $x ) { for ( $i = 0; $i < 30; $i++ ) { $cnt[$i] += $x >> $i & 1; } } while ( $k > 0 ) { $x = 0; for ( $i = 0; $i < 30; $i++ ) { if ( $cnt[$i] > 0 ) { $cnt[$i]--; $x |= 1 << $i; } } $ans = ($ans + $x*$x) % $mod; $k--; } return $ans; } }
golang 解法, 执行用时: 128 ms, 内存消耗: 9.8 MB, 提交时间: 2023-10-10 10:15:34
func maxSum(nums []int, k int) (ans int) { const mod = 1_000_000_007 cnt := [30]int{} for _, x := range nums { for i := range cnt { cnt[i] += x >> i & 1 } } for ; k > 0; k-- { x := 0 for i := range cnt { if cnt[i] > 0 { cnt[i]-- x |= 1 << i } } ans = (ans + x*x) % mod } return }
java 解法, 执行用时: 42 ms, 内存消耗: 57.7 MB, 提交时间: 2023-10-10 10:15:10
public class Solution { public int maxSum(List<Integer> nums, int k) { final long MOD = 1_000_000_007; int[] cnt = new int[30]; for (int x : nums) { for (int i = 0; i < 30; i++) { cnt[i] += (x >> i) & 1; } } long ans = 0; while (k-- > 0) { int x = 0; for (int i = 0; i < 30; i++) { if (cnt[i] > 0) { cnt[i]--; x |= 1 << i; } } ans = (ans + (long) x * x) % MOD; } return (int) ans; } }
cpp 解法, 执行用时: 176 ms, 内存消耗: 84.1 MB, 提交时间: 2023-10-10 10:14:57
class Solution { public: int maxSum(vector<int> &nums, int k) { const int MOD = 1'000'000'007; int cnt[30]{}; for (int x: nums) { for (int i = 0; i < 30; i++) { cnt[i] += (x >> i) & 1; } } long long ans = 0; while (k--) { int x = 0; for (int i = 0; i < 30; i++) { if (cnt[i] > 0) { cnt[i]--; x |= 1 << i; } } ans = (ans + (long long) x * x) % MOD; } return ans; } };
python3 解法, 执行用时: 2188 ms, 内存消耗: 30.6 MB, 提交时间: 2023-10-10 10:14:40
# 把1聚到一起 class Solution: def maxSum(self, nums: List[int], k: int) -> int: m = max(nums).bit_length() cnt = [0] * m for x in nums: for i in range(m): cnt[i] += x >> i & 1 ans = 0 for _ in range(k): x = 0 for i in range(m): if cnt[i]: cnt[i] -= 1 x |= 1 << i ans += x * x return ans % (10 ** 9 + 7)