Veal98#CS-Wiki#60.最大的异或1

--- title: 最大的异或 date: 2022-05-04 11:39:20 permalink: /pages/b9402f/ --- ## 📃 题目描述 题目链接： - [剑指 Offer II 067. 最大的异或 - 力扣（LeetCode） (leetcode-cn.com)](https://leetcode-cn.com/problems/ms70jA/) - [421. 数组中两个数的最大异或值 - 力扣（LeetCode） (leetcode-cn.com)](https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/) ## 🔔 解题思路 整数的异或有一个特点，如果两个相同数位异或的结果是0，那么两个相反的数位异或的结果为 1。 **如果想找到某个整数 k 和其他整数的最大异或值，那么尽量找和 k 的数位不同的整数**。 因此，这个问题可以转化为查找的问题，而且还是按照整数的二进制数位进行查找的问题。需要将整数的每个数位都保存下来。前缀树可以实现这种思路，前缀树的每个节点对应整数的一个数位，路径对应一个整数。 由于每个节点只有两个分别表示 0 和 1 的子节点，因此前缀树节点的数据结构可以定义为如下所示的形式：  由于整数都是32位，它们在前缀树中对应的路径的