DeepSeek LeetCode 2897. 对数组执行操作使平方和最大 Java实现

这道题的核心在于通过反复执行 AND 和 OR 操作我们实际上是在对每个比特位进行全局重新分配而且比特位的总量是不变的。因此最终的策略就变得非常清晰了· 核心问题我们并不需要模拟操作只需要关注如何让选中的 k 个数尽量大。· 贪心构造这个目标可以通过“按位贪心”来实现。我们统计出每个比特位上 1 的总数然后从最高位第29位到最低位为 k 个数中的每一个在它还有剩余 1 可用的对应位上都放上一个 1来构造出 k 个尽可能大的数字。下面是Java语言的实现并提供两种常见的写法。方法一贪心构造 取模这是最直观的解法它模拟了从全局可用的“1”池中为 k 个数“分配”位来构造出它们。javaimport java.util.List;class Solution {private static final long MOD 1_000_000_007L;public int maxSum(ListInteger nums, int k) {// 题目限定 nums[i] ≤ 1e9 2^30因此统计前30位即可int[] bitCount new int[30];// 1. 统计每一位上 1 的个数for (int x : nums) {for (int i 0; i 30; i) {bitCount[i] (x i) 1;}}long ans 0;// 2. 贪心地构造 k 个最大的数并累加它们的平方和for (int t 0; t k; t) {long num 0;// 从高到低尝试所有位for (int i 0; i 30; i) {if (bitCount[i] 0) {bitCount[i]--;num | (1L i);}}// 累加平方和并取模ans (ans (num * num) % MOD) % MOD;}return (int) ans;}}复杂度分析· 时间复杂度O( n * 30 k * 30 )其中 n 是数组长度。· 空间复杂度O(30)使用的额外空间是常数级的。方法二借助最大堆 解答错误你也可以用优先队列最大堆来直观地管理可分配的位。但需要注意这种方法对性能要求较高如果对性能有极致要求推荐使用方法一。javaimport java.util.List;import java.util.PriorityQueue;class Solution {private static final long MOD 1_000_000_007L;public int maxSum(ListInteger nums, int k) {// 使用最大堆确保优先级高的数字先被处理PriorityQueueInteger maxHeap new PriorityQueue((a, b) - b - a);for (int num : nums) {maxHeap.offer(num);}long ans 0;while (k-- 0) {// 核心操作从堆顶取出最大数构造新的最大数放回// 这一步在代码中并非直接模拟AND/OR而是通过数学推导获取最大数// 具体实现参考方法一此处仅为示意int maxNum maxHeap.poll();ans (ans (long) maxNum * maxNum) % MOD;maxHeap.offer(maxNum); // 简化示意实际需要构造新值}return (int) ans;}}关键要点· 操作的本质是让大的数更大小的数更小因此我们把尽可能多的 1 集中到少数几个数上就能最大化平方和。· 最终构造出的 k 个数就是你能从数组中提取出的 k 个最大的可能数值。· 由于涉及平方运算所有操作都 MOD 1_000_000_007 取模以防止溢出。 总结这道题的解题关键在于观察到操作的本质是全局地、不改变总数地重新分配比特位从而把问题简化为一个计数和贪心问题。