数组异或和的定义：把数组中所有的数异或起来得到的值。给定一个整型数组arr，其中可能有正、有负，有零，求其中子数组的最大异或和。
[编程题]子数组的最大异或和
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX(X, Y) ((X) > (Y) ? (X) : (Y))
typedef struct tn {
struct tn **children; // 存放子节点的指针
} node;
node *new_node() {
node *new_node = malloc(sizeof(node));
new_node->children = (node **) calloc(2, sizeof(node *));
return new_node;
}
void destroy_node(node *node) {
free(node->children);
free(node);
}
void destroy_whole_path(node *node) {
destroy_node(node->children[0]);
destroy_node(node->children[1]);
destroy_node(node);
}
void insert(node *root, int num) {
node *cur = root;
int path;
for (int move = 31; move >= 0; move--) {
path = (num >> move) & 1;
if (cur->children[path] == NULL) {
cur->children[path] = new_node();
}
cur = cur->children[path];
}
}
int max_eor(node *root, int eor) {
node *cur = root;
int max = 0, path, best;
for (int move = 31; move >= 0; move--) {
path = (eor >> move) & 1;
best = move == 31 ? path : (path ^ 1);
best = cur->children[best] == NULL ? (best ^ 1) : best;
max = max << 1 | (path ^ best);
cur = cur->children[best];
}
return max;
}
int main(void) {
int n, *arr, ans = INT_MIN;
scanf("%d", &n);
arr = (int *) malloc(sizeof(int) * n);
for (int i = 0; i < n; i++) {
scanf("%d", arr + i);
}
int eor = 0;
node *root = new_node();
insert(root, 0);
for (int i = 0; i < n; i++) {
eor ^= arr[i];
ans = MAX(ans, max_eor(root, eor));
insert(root, eor);
}
printf("%d\n", ans);
destroy_whole_path(root);
free(arr);
return 0;
}
发表于 2022-02-14 00:45:53
回复(0)
#include<iostream>
#include<vector>
using namespace std;
void add(int newNum);
int maxXor(int eorj);
int maxXorSubarray2(vector<int> &arr);
class Node {
public:
Node *nexts[2] = {NULL};
};
Node *head = new Node();
void add(int newNum) {
Node *cur = head;
for (int move = 31; move >= 0; move--) {
int path = ((newNum >> move) & 1);
cur->nexts[path] = cur->nexts[path] == NULL ? new Node() : cur->nexts[path];
cur = cur->nexts[path];
}
}
int maxXor(int eorj) {
Node *cur = head;
int res = 0;
for (int move = 31; move >= 0; move--) {
int path = (eorj >> move) & 1;
int best = move == 31 ? path : (path ^ 1);
best = cur->nexts[best] != NULL ? best : (best ^ 1);
res |= (path ^ best) << move;
cur = cur->nexts[best];
}
return res;
}
int maxXorSubarray2(vector<int> &arr) {
if (arr.empty() || arr.size() == 0) {
return 0;
}
int mx = INT32_MIN;
int eor = 0;
add(0);
for (int j = 0; j < arr.size(); j++) {
eor ^= arr[j];
mx = max(mx, maxXor(eor));
add(eor);
}
return mx;
}
int main() {
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int res = maxXorSubarray2(arr);
cout << res << endl;
return 0;
}
发表于 2020-09-09 13:58:54
回复(0)
牛客的输入格式总是这么魔性，这题用缓冲流就数组越界，用Scanner又很慢。整体思路就是用字典树存储数组的前缀异或和，在遍历求前缀和的过程中考虑以arr[i]结尾时能够得到的最大异或和。假设能够让你得到这个最大异或和的子数组以arr[s]开头，则我们就需要确定s的位置。根据异或的性质，数组0~i范围上的异或和异或上数组0~s-1范围上的异或和，就能得到s~i范围上的异或和。而在遍历到i时，前面的前缀异或和已经全部加入到了字典树中，所以我们只要找到某个字典树中已经存在的前缀异或和，它与当前的前缀异或和eor异或完之后可以得到最大值就行了。因此我们在寻找这个符合条件的前缀异或和时，有如下两个贪心的思想：
- 对于符号位，我们希望找到一个与当前异或和状态相同的前缀异或和，因为同状态异或得0，可以使异或结果变成正数；
- 对于非符号位，我们希望找到一个与当前异或和状态不同的前缀异或和，因为不同状态才能使得异或结果为1。
import java.util.Scanner;
class Node {
public Node[] next = new Node[2]; // 每个节点表示整数的一个位，有0和1两个状态
}
class NumTrie {
public Node head = new Node();
public void add(int num) {
Node cur = head;
for(int move = 31; move >= 0; move--){
int bit = (num >> move) & 1; // 取出从右往左的第move位
cur.next[bit] = cur.next[bit] == null? new Node(): cur.next[bit];
cur = cur.next[bit];
}
}
public int maxXOR(int num) {
Node cur = head;
int res = 0;
for(int move = 31; move >= 0; move--){
int bit = (num >> move) & 1;
int expect = move == 31? bit: bit ^ 1; // 当前位为符号位时，希望要走的路径与当前位相同
expect = cur.next[expect] == null? expect ^ 1: expect; // 期望路径不空才能走
res |= (bit ^ expect) << move; // 把res中这一位的状态改了
cur = cur.next[expect];
}
return res;
}
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
int max = Integer.MIN_VALUE;
int eor = 0; // 前缀异或和
NumTrie trie = new NumTrie();
trie.add(0);
for(int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
eor ^= arr[i];
max = Math.max(max, trie.maxXOR(eor)); // 找到数组以arr[i]结尾时，最大的异或和
trie.add(eor);
}
System.out.println(max);
}
}
发表于 2021-12-07 13:16:39
回复(0)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
class Node {
public Node[] nodes;
public Node() {
nodes = new Node[2];
}
}
class PrefixTree {
public Node head;
public PrefixTree() {
this.head = new Node();
}
public void add(int eor) {
Node cur = head;
for (int move = 31; move >= 0; move--) {
int i = (eor >> move) & 1;
if (null == cur.nodes[i]) {
cur.nodes[i] = new Node();
cur = cur.nodes[i];
} else {
cur = cur.nodes[i];
}
}
}
public int max(int eor) {
int res = 0;
Node cur = head;
for (int move = 31; move >= 0; move--) {
int i = (eor >> move) & 1;
int best;
if (move == 31) {
best = i;
} else {
best = i ^ 1;
}
if (cur.nodes[best] == null) {
best = best ^ 1;
cur = cur.nodes[best];
} else {
cur = cur.nodes[best];
}
res |= best << move;
}
return res ^ eor;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(reader.readLine());
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(reader.readLine());
}
int eor = 0;
PrefixTree tree = new PrefixTree();
tree.add(0);
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
eor = eor ^ arr[i];
max = Math.max(max, tree.max(eor));
tree.add(eor);
}
System.out.println(max);
}
}
发表于 2022-06-11 15:10:09
回复(0)
import java.util.*;
public class Main {
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
System.out.println(getMaxSum(arr));
}
/*
//O(N^2)
public static int getSum(int[] arr) {
if (arr == null || arr.length == 0)
return 0;
//eor[i]的含义为arr[0...i]的异或和，只遍历arr一遍就可以生成eor数组
int[] eor = new int[arr.length];
eor[0] = arr[0];
for (int i = 1; i < arr.length; i++) {
eor[i] = eor[i-1] ^ arr[i];
}
int max = Integer.MIN_VALUE;
//因为xor[0...j] = xor[0...i-1] ^ xor[i...j]
//所以xor[i...j] = xor[0...i-1] ^ xor[0...j]
for (int j = 0; j < arr.length; j++) {
for (int i = 0; i <= j; i++) {
max = Math.max(max, i == 0 ? eor[j] : eor[j]^eor[i-1]);
}
}
return max;
}*/
//O(N)
/*
此方法最大的优势在于可以直接得到当以j为止结尾时xor[j]的最大值，
即通过从二进制最高位开始，尽可能的让更高位异或后的结果变1，
相当于每一位上找之前结果eor[0]...eor[j-1]在此位置上有没有异或的可能，
如果没有就将就了，如果有，就把1安在当前二进制数位上，最终以O(1)的代价获得
以j位置结尾的最大异或和，然后遍历n个数，比较以每个位置为结尾的最大异或和，得到结果
*/
public static int getMaxSum (int[] arr) {
if (arr == null || arr.length == 0)
return 0;
int max = Integer.MIN_VALUE;
int eor = 0;
NumTrie trie = new NumTrie();
//为了当最大子数组只有一个数本身时，得到正确结果
trie.add(0);
for (int j = 0; j < arr.length; j++) {
//因为xor[0...j] = xor[0...i-1] ^ xor[i...j]
//所以xor[i...j] = xor[0...i-1] ^ xor[0...j]
eor ^= arr[j];
max = Math.max(max, trie.maxXor(eor));
trie.add(eor);
}
return max;
}
}
//把上面方法中eor[0...i]转变成前缀树结构
//二进制只有两种形式，所以每个节点下面最多只有两个node
class Node {
public Node[] nexts;
public Node() {
nexts = new Node[2];
}
}
class NumTrie {
public Node head = new Node();
//把某个数字加入前缀树中
//num是一个32位的整数，所以加入过程一共走32步
public void add (int num) {
Node cur = head;
for (int move = 31; move >= 0; move--) {
//从最高位到最低位获得每一位上的数
int path = (num >> move) & 1;
cur.nexts[path] = cur.nexts[path] == null ? new Node() : cur.nexts[path];
cur = cur.nexts[path];
}
}
public int maxXor(int eorj) {
Node cur = head;
int res = 0;
for (int move = 31; move >= 0; move--) {
//从最高位到最低位获得每一位上的数
int path = (eorj >> move) & 1;
//最高位上我们为了保证结果最大，当选取正数
//如果当前eor[j]为负，即最高位为1，那么我们要走的路径也要是1
//反之如果eor[j]为负，便走0,
//其他情况下尽可能走向相反的数，因为这样下来从高到低才有可能有更多的1
int best = move == 31 ? path : (path ^ 1);
best = cur.nexts[best] != null ? best : (best^1);
//看当前能得到的结果最好是多少
res |= (path ^ best) << move;
cur = cur.nexts[best];
}
return res;
}
}
发表于 2021-08-05 16:26:43
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-12-26 20:04:43
-
2022-11-25 13:15:44
-
2022-11-13 11:05:04
-
2022-09-12 11:10:48 -
2022-09-01 14:25:27
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
