【C++ 算法进阶】算法提升六

子数组的最大异或和 （前缀树）

题目描述

求出一个数组中最大的子数组异或和

题目分析

这道题目和我们之前做的一道题很类似

求出一个数组中的最大累加和

最大累加和问题我们是使用动态规划来解决 而能够使用动态规划的根本原因则是 数字相加具有单调性 即两个大数相加得到的只可能是一个更大的数

但是异或和就不痛了 两个很大的数字异或的结果可能为一个很小的数

暴力解

当然 这道题我们还是可以借用 数组中最大子数组累加和 的思维来做

最大异或和肯定是以大数组中的某个数作为结尾计算出来的

所以说只要我们计算出以每个数作结尾的最大异或和 再比较一下 我们就能求出最终的答案

具体过程

假设我们是以5作为子数组的结尾 那么我们只需要计算出下面几种异或和即可求出最终答案

• 0~5
• 1~5
• 2~5
• 3~5
• 4~5
• 5~5

而要求出这些异或和 我们只需要计算出

• 没有数的异或和
• 0~0
• 0~1
• …
• 0~4

的异或和再让他们分别异或上0~5的异或和即可求出

所以说我们可以建立一张异或和表 （0~N） 时间复杂度为N

计算出以 i 位置的数为结尾的时间复杂度为N

计算出总的结果的时间复杂度为 N^2

优化解 （时间复杂度为N）

上面的暴力解的主要问题是 我们创建的表对于我们选择结果没有任何帮助 我们依旧需要遍历整张表（到i位置为止） 才能得出最终结果

所以说我们需要一个能帮助我们选择的数据结果 – 前缀树

前缀数如何帮助我们进行选择

假设我们现在0~i 上的异或和为 1 1 0 1 0 1 0 1 （8位）

我们从8位开始选择异或 那么我们希望选择的异或和是 0 0 1 0 1 0 1 0

那么我们就可以从前缀树中按照我们的期望进行选择

当然 如果我们没有期望的话就只能选择另一种结果

如果有负数怎么办

是正数符号位为0 那么我们期望的结果为0 如果是负数的符号位为1 那么我们期望的结果为1 （尽量变成正数）

其他位只需要按照原来的选择即可

前缀树的设计

我们首先可以设计出前缀树的节点

// 定义Trie节点，只包含两条路
class TrieNode {
public:
    TrieNode* children[2];  // 0 和 1 的两个分支

    TrieNode() {
        children[0] = children[1] = nullptr;  // 初始化两个分支为空
    }
};

接下来我们可以设计出两个函数

• 一个add函数 将一个异或值插入到前缀树中
• 一个maxeor函数 找出当前值的最大异或值

    // 添加前缀异或值到Trie树中
    // move表示移动move位
    // num 表示插入前缀树的值 0或1
    void add(int lnNum) {
        TrieNode* cur = root;
        for (int move = 31; move >= 0; move--) {
            int num = (lnNum >> move) & 1;
            cur->children[num] = cur->children[num] == nullptr ? new TrieNode() : cur->children[num];
            cur = cur->children[num];
        }
    }

    // 返回当前值lnNum与Trie树中的值的最大异或值
    // move 移动的位数
    // lnNum 参数 求出与他异或和的最大值
    // cur 当前节点
    // ans 返回的答案 32位整数
    int maxXor(int lnNum) {
        TrieNode* cur = root;
        int ans = 0;
        for (int move = 31; move >=0; move--)
        {
            // lnBit 当前的位数的值 0或1
            // Bset 期望走的路
            int lnBit = (lnNum >> move) & 1;
            int Best = lnBit ^ 1;

            if (cur->children[Best] == nullptr)
            {
                Best ^= 1;
            }

            ans |= (Best ^ lnBit) << move;
            cur = cur->children[Best];
        }

        return ans;
    }

代码详解

using namespace std;

// 定义Trie节点，表示二进制数的两个可能路径
class TrieNode {
public:
    TrieNode* children[2];  // 0 和 1 的两个分支

    TrieNode() {
        children[0] = nullptr;
        children[1] = nullptr;
    }
};

// 定义Trie类
class Trie {
private:
    TrieNode* root;

public:
    // 构造函数，初始化根节点
    Trie() {
        root = new TrieNode();
    }

    // 添加前缀异或值到Trie树中
    // move表示移动move位
    // num 表示插入前缀树的值 0或1
    void add(int lnNum) {
        TrieNode* cur = root;
        for (int move = 31; move >= 0; move--) {
            int num = (lnNum >> move) & 1;
            cur->children[num] = cur->children[num] == nullptr ? new TrieNode() : cur->children[num];
            cur = cur->children[num];
        }
    }

    // 返回当前值lnNum与Trie树中的值的最大异或值
    // move 移动的位数
    // lnNum 参数 求出与他异或和的最大值
    // cur 当前节点
    // ans 返回的答案 32位整数
    int maxXor(int lnNum) {
        TrieNode* cur = root;
        int ans = 0;
        for (int move = 31; move >=0; move--)
        {
            // lnBit 当前的位数的值 0或1
            // Bset 期望走的路
            int lnBit = (lnNum >> move) & 1;
            int Best = lnBit ^ 1;

            if (cur->children[Best] == nullptr)
            {
                Best ^= 1;
            }

            ans |= (Best ^ lnBit) << move;
              cur = cur->children[Best];
        }

        return ans;
    }
};

// 主函数，计算子数组的最大异或和
int findMaxXorSubarray(const vector<int>& arr) {
    // x arr内数据的值拷贝
    // T 一个前缀树对象
    // eor 前面N个数的异或和
    // ans 子数组异或和的最大值 也就是我们要返回的值
    Trie T;
    int eor = 0;
    int ans = INT_MIN;
    for (auto x : arr) {
        T.add(eor);
        eor ^= x;
        ans = max(ans, T.maxXor(eor));
    }


    return ans;
}

int main() {
    vector<int> arr = { 3, 10, 5, 25, 2,};

    int lnMaxXor = findMaxXorSubarray(arr);
    cout << "最大子数组异或和为: " << lnMaxXor << endl;

    return 0;
}

两个数的最大异或和 （前缀树）

题目

本题为LC原题 题目如下

题目分析

有了上一题的经验我们要解决这题就简单多了

我们直接将数组中所有的数添加到前缀树中 之后遍历整个数组直接求出最大值即可 （时间复杂度N）

代码详解

// 定义Trie节点，表示二进制数的两个可能路径
class TrieNode {
public:
    TrieNode* children[2];  // 0 和 1 的两个分支

    TrieNode() {
        children[0] = nullptr;
        children[1] = nullptr;
    }
};

// 定义Trie类
class Trie {
private:
    TrieNode* root;

public:
    // 构造函数，初始化根节点
    Trie() {
        root = new TrieNode();
    }

    // 添加前缀异或值到Trie树中
    // move表示移动move位
    // num 表示插入前缀树的值 0或1
    void add(int lnNum) {
        TrieNode* cur = root;
        for (int move = 31; move >= 0; move--) {
            int num = (lnNum >> move) & 1;
            cur->children[num] = cur->children[num] == nullptr ? new TrieNode() : cur->children[num];
            cur = cur->children[num];
        }
    }

    // 返回当前值lnNum与Trie树中的值的最大异或值
    // move 移动的位数
    // lnNum 参数 求出与他异或和的最大值
    // cur 当前节点
    // ans 返回的答案 32位整数
    int maxXor(int lnNum) {
        TrieNode* cur = root;
        int ans = 0;
        for (int move = 31; move >=0; move--)
        {
            // lnBit 当前的位数的值 0或1
            // Bset 期望走的路
            int lnBit = (lnNum >> move) & 1;
            int Best = lnBit ^ 1;

            if (cur->children[Best] == nullptr)
            {
                Best ^= 1;
            }

            ans |= (Best ^ lnBit) << move;
            cur = cur->children[Best];
        }

        return ans;
    }
};

class Solution {
public:
    // T TrieNode定义的
    // ans 最后的答案
    int findMaximumXOR(vector<int>& nums) {
        Trie T;
        int ans = 0;
        for (auto x : nums) {
            T.add(x);
        }

        for (auto x : nums) {
            ans = max(ans , T.maxXor(x));
        }

        return ans;
    }
};

尼姆博弈问题 （公式）

题目描述

给定一个数组 数组内有N个正整数 两个人开始拿数 每个人每次只能拿数组中的一个数 (至少为1 至多为这个数的大小)

假设两个人的选择都绝对理性且绝对正确

现在给你一个数组 要求你返回先手赢还是后手赢

题目分析

这里直接给出公式

所有数组的异或和如果为0 则后手赢

如果异或和为0则先手赢

本体的本质是 先手要让后手每次拿到数时 异或和都变为0

而当一开始异或和不为0时 我们就能很轻松的做到这个效果 所以说如果所有数组的异或和不为0 则先手赢

代码详解

int eor = 0;
int ans = 0;
for (auto x : arr) {
   ans ^= x;
}

return ans == 0;