如何制作网站链接,2022年黄台片区,html个人网页源码,app设计ppt力扣2935. 找出强数对的最大异或值
题目概述
题目编号#xff1a;2935 题目难度#xff1a;困难 相关标签#xff1a;数组, 排序, 位运算
给定一个整数数组 nums#xff0c;任务是找出其中可以形成的所谓“强数对”的最大异或值。强数对定义为一对整数 (x) 和 (y)#…力扣2935. 找出强数对的最大异或值
题目概述
题目编号2935 题目难度困难 相关标签数组, 排序, 位运算
给定一个整数数组 nums任务是找出其中可以形成的所谓“强数对”的最大异或值。强数对定义为一对整数 (x) 和 (y)满足 |x - y| ≤ \leq ≤ min(x, y)。
示例分析 示例 1 输入nums [1,2,3,4,5] 输出7 分析数组中的强数对及其异或值有多种组合其中 3 XOR 4 7 是最大的。 示例 2 输入nums [10,100] 输出0 分析仅有 (10, 10) 和 (100, 100) 两个强数对它们的异或值均为 0。 示例 3 输入nums [500,520,2500,3000] 输出1020 分析最大异或值来自 500 XOR 520 1020。
解题思路
算法关键在于找到使异或值最大化的数对。首先对数组进行排序以便后续操作。主要思路是从最高位开始检查是否存在两个数使得该位为 1同时满足强数对条件。
使用掩码mask来逐位检查。通过位运算和哈希表seen来快速判断是否存在满足条件的数对。掩码用于保留数的前缀部分以便对每个位的影响进行评估。
代码解析
排序首先对 nums 排序以简化强数对的确定。位运算使用位运算来逐步构建最大的异或值。哈希表使用哈希表来存储和快速检索数对。掩码运算掩码用于保留数字的高位部分以检查每个位的贡献。
完整代码
class Solution:def maximumStrongPairXor(self, nums: List[int]) - int:nums.sort()mask 0ans 0hb max(nums).bit_length()for i in range(hb, -1, -1):mask | 1 inew_ans ans | (1 i)如果要使得第i位为1,要满足两个条件1.存在mask_x ^ mask_y new_ans2.存在abs(x - y) min(x, y)对于第二个条件来说可以设x y此时条件2可以化简成y 2 * x因为nums已经有序所以对于已经迭代过的元素就可以是“x”。那么可以维护一个哈希表检查是否存在一个x可以满足y 2 * x为了满足条件1只考虑这个x的前i位后面的位置为0也就是mask_xmask_x必须满足mask_x ^ mask_y new_ans。那么可以创建一个哈希表seen以mask_x为键以x为值。seen {}for y in nums:mask_y y maskmask_x mask_y ^ new_ansif mask_x in seen and y 2 * seen[mask_x]:ans new_ansbreak# 即使会覆盖以前出现过的mask_x也只会让结果更优# 因为x的值越大越好我们可以保证x y这只会更容易满足条件2.seen[mask_y] yreturn ans
小结
这种算法结合了位运算和哈希表有效地解决了在一定条件下求最大异或值的问题。它展示了如何在复杂问题中运用多种技术和方法。
