LeetCode 题解工作台
对数组执行操作使平方和最大
给你一个下标从 0 开始的整数数组 nums 和一个 正 整数 k 。 你可以对数组执行以下操作 任意次 ： 选择两个互不相同的下标 i 和 j ， 同时 将 nums[i] 更新为 (nums[i] AND nums[j]) 且将 nums[j] 更新为 (nums[i] OR nums[j]) …
4
题型
5
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
根据题目描述，对于一个操作，我们可以将 变为 $nums[i] \textit{ AND } nums[j]$，将 变为 $nums[i] \textit{ OR } nums[j]$。我们不妨按位考虑，两个 或两个 进行这样的操作，结果都不会改变，如果是 和 进行这样的操作，结果会变成 和 ，也即是说，我们可以将 转移到 上，而 不会转移到 上。 因此，我们可以用一个数组 …
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个下标从 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 <= 1051 <= nums[i] <= 109
解题思路
方法一：位运算 + 贪心
根据题目描述，对于一个操作，我们可以将 变为 ，将 变为 。我们不妨按位考虑，两个 或两个 进行这样的操作，结果都不会改变，如果是 和 进行这样的操作，结果会变成 和 ，也即是说，我们可以将 转移到 上，而 不会转移到 上。
因此，我们可以用一个数组 统计每个位置上 的个数，然后从中选择 个数。由于要使得平方和最大，每次选择的数要尽可能大。这是因为，假设两个数的平方和为 （其中 ），将两个数平方和变成 。因此，为了最大化平方和，我们应该让一个数字尽可能大。
时间复杂度 ，空间复杂度 ，其中 是数组中的最大值。
class Solution:
def maxSum(self, nums: List[int], k: int) -> int:
mod = 10**9 + 7
cnt = [0] * 31
for x in nums:
for i in range(31):
if x >> i & 1:
cnt[i] += 1
ans = 0
for _ in range(k):
x = 0
for i in range(31):
if cnt[i]:
x |= 1 << i
cnt[i] -= 1
ans = (ans + x * x) % mod
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidates should be able to efficiently identify the most significant elements to modify using bitwise operations.
- question_mark
Interviewers should look for the candidate’s ability to optimize the selection of k elements from the array after transformations.
- question_mark
The candidate’s approach to the problem should showcase familiarity with bitwise operations and array manipulation for optimization.
常见陷阱
外企场景- error
Failing to optimize the selection of elements after bitwise operations, resulting in suboptimal answers.
- error
Overlooking the need for efficient array scanning and hash lookup when selecting the best k elements.
- error
Inadequate handling of bitwise operation results, leading to incorrect final values for the selected elements.
进阶变体
外企场景- arrow_right_alt
Applying bitwise operations but changing the problem constraints (e.g., different k or larger array sizes).
- arrow_right_alt
Changing the allowed operations to include XOR or other bitwise manipulations.
- arrow_right_alt
Limiting the number of times bitwise operations can be applied, requiring additional optimization strategies.