子数组的最大异或和

[编程题]子数组的最大异或和

热度指数：1414 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

数组异或和的定义：把数组中所有的数异或起来得到的值。给定一个整型数组arr，其中可能有正、有负，有零，求其中子数组的最大异或和。

输入描述:

输出包含两行，第一行一个整数n，代表数组arr长度，第二个n个整数，代表数组arr。

输出描述:

输出一个整数，代表其中子数组的最大异或和。

示例1

输入

4
3 -28 -29 2

输出

说明

{-28，-29}这个子数组的异或和为7，是所有子数组中最大的

备注:

时间复杂度，额外空间复杂度。

算法知识视频讲解

查看答案及解析

helloxuanbao

#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)