当前位置: 首页> 娱乐> 明星 > 区块链系统app开发_八大员报名入口官网_seo工程师_山东自助seo建站

区块链系统app开发_八大员报名入口官网_seo工程师_山东自助seo建站

时间:2025/7/11 22:52:35来源:https://blog.csdn.net/triticale/article/details/146518400 浏览次数:0次
区块链系统app开发_八大员报名入口官网_seo工程师_山东自助seo建站

最大异或对

在给定的 N 个整数 A1,A2……AN 中选出两个进行 xor(异或)运算,得到的结果最大是多少?

输入格式

第一行输入一个整数 N。

第二行输入 N 个整数 A1~AN。

输出格式

输出一个整数表示答案。

数据范围

1≤N≤ 1 0 5 10^5 105,
0≤Ai< 2 31 2^{31} 231

输入样例:
3
1 2 3
输出样例:
3

【思路分析】

字典树(TrieTree),是一种树形结构,典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串,如01字典树)。主要思想是利用字符串的公共前缀来节约存储空间。很好地利用了串的公共前缀,节约了存储空间。字典树主要包含两种操作,插入查找

比如,我们要存储2(010)、4(100)、3(011)、6(110)、5(101)的二进制

在这里插入图片描述

这样我们要进行查找最大异或对时,无需进行二重循环,只需要枚举每个数,然后每个数按照从高位到低位找不同位的值,例如找与2(010)异或最大的值,从高位到低位

第一次寻找,2的最高位是0,寻找字典树中根节点的右孩子是否存在,存在则结果加上 2 2 2^2 22

第二次寻找,2的次高位是1,寻找第一次寻找结点的左孩子是否存在,存在则结果加上 2 1 2^1 21

第三次寻找,2的最低位是0,寻找第二次寻找到结点的右孩子是否存在,存在则结果加上 2 0 2^0 20

最终异或后的结果是7(111)

而对于寻找,则需要知道每次结点的编号,因此在插入的时候,不妨记录每个结点的编号

在这里插入图片描述

import java.io.*;
import java.util.*;
public class Main {static final int N = 100010;static final int M = 3000010;//id是结点编号static int id = 0;static int[] arr = new int[N];static int[][] trie = new int[M][2];public static void main(String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String row1 = br.readLine();int n = Integer.parseInt(row1);String row2 = br.readLine();String[] num = row2.split(" ");for(int i = 0; i < n; i++) {arr[i] = Integer.parseInt(num[i]);insert(arr[i]);}int res = 0;for(int i = 0; i < n; i++) {res  = Math.max(res, query(arr[i]));}System.out.println(res);br.close();}//构建字典树public static void insert(int x) {int k = 0;for(int i = 30; i >= 0; i--) {int bit = x >> i & 1;if(trie[k][bit] == 0) {trie[k][bit] = ++id;}k = trie[k][bit];}}public static int query(int x) {int k = 0, res = 0;for(int i = 30; i >= 0; i--) {int bit = x >> i & 1;//这一位能找到用来异或的数if(trie[k][bit ^ 1] != 0) {res += 1 << i;k = trie[k][bit ^ 1];} else{k = trie[k][bit];}}return res;}
}
关键字:区块链系统app开发_八大员报名入口官网_seo工程师_山东自助seo建站

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: