专栏首页mathor给定一个数组,求子数组的最大异或和

给定一个数组,求子数组的最大异或和

 直接说这道题时间复杂度O(n)的做法,构建前缀树。假设将0-0、0-1、0-2、...、0-i-1的异或结果全部装在前缀树中,那么以i结尾的最大异或和就是0到某一位置x的异或结果和i异或结果最大,举个例子,假设x是3,0-3的异或结果和i进行异或得到的结果最大,那么就说明4-i的异或结果是最大的。  但是如何知道x到底是多少,换句话说,0-x中哪个值和i进行异或得到的结果最大。其实这个也比较好想,假设i是0100(最高位0是符号位),只需要沿着前缀树找到0011,异或出来的结果就是0111,一定就是最大的,如果不能刚好找到合适的,那就有什么选什么,只要保证从最高位开始往下每次的决策是最优的就行  有一种特殊情况,假设i还是0100,但是此时前缀树中最高位只有1,没有0,那么最高位得出的异或结果永远是负数,后面的位应该如何选?其实也是按照最优决策去选,假设异或结果是1111,那么转换为十进制就是-1,绝对没有比这还大的负数了

public class Main {
    public static class Node {
        public Node[] nexts = new Node[2]; // 0,1
    }
    
    public static class NumTrie {
        public Node head = new Node();
        
        public void add(int num) {
            Node cur = head;
            for(int move = 31;move >= 0;move--) {
                int path = ((num >> move) & 1);//每一位上的数字(0,1)
                cur.nexts[path] = (cur.nexts[path] == null ? new Node() : cur.nexts[path]);
                cur = cur.nexts[path];
            }
        }
        
        public int maxXor(int num) {//num=0~i的异或结果
            Node cur = head;
            int res = 0;
            for(int move = 31;move >= 0;move--) {
                int path = (num >> 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;
        }
    }
    public static int maxXorSubArray(int[] arr) {
        if (arr == null || arr.length == 0) 
            return 0;
        int max = Integer.MIN_VALUE;
        int xor = 0;
        NumTrie numTrie = new NumTrie();
        numTrie.add(0);
        for(int i = 0;i < arr.length;i++) {
            xor ^= arr[i];
            max = Math.max(max,numTrie.maxXor(xor));
            numTrie.add(xor);
        }
        return max;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [kuangbin带你飞]专题一 简单搜索

     看到最短,最少之类的搜索题,基本都是用bfs,这道题大意是说,给一个三维的迷宫,要从S走到E,问最短走几步。普通的bfs是上下左右四个方向扩展,这个bfs...

    mathor
  • 2017百度之星初赛(A)

     假设P进制下有个数(abc)~P~,若这个数满足:(abc)~P~ % B == 0,则以下两个等式一定成立:

    mathor
  • LeetCode75.颜色分类

     这道题两种做法,一种是用计数排序,因为告诉了你只有3种数字,所以直接创建一个长度为3的数组arr,然后遍历一遍原数组,每出现一次某个数,arr对应位置的值...

    mathor
  • 晓快讯 | 刚刚,支付宝小程序又爆出新入口!

    11 月 15 日,知晓程序(微信号 zxcx0101)发现,支付宝小程序拥有了新入口:通过首页「卡包」功能,就可以进入支付宝小程序。

    知晓君
  • JS逆向 房天下登录RSA

    2.我们跟进去加密函数,代码格式化,RSA.min.js,明显就是 RSA算法,我们把所有的 js拷贝出来

    Python高效学习
  • HDU 1028 Ignatius and the Princess III(生成函数)

    Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Othe...

    attack
  • 知己知彼-关于Oracle安全比特币勒索问题揭秘和防范

    风险从来都不是臆想和草木皆兵,就在你不经意的时刻,可能风险就突然降临到我们的身边。 近期,国内很多用户的 Oracle 数据库,突然遭遇到莫名其妙的攻击事件,...

    数据和云
  • QQfamily Lifestyle-零成本产品拍摄

    腾讯ISUX
  • Octave卷积学习笔记

    由此,认为卷积神经网络中的feature map也可以进行分频,可按channel分为高频部分和低频部分,如图所示:

    月见樽
  • 一步一步教你如何解锁被盗的iPhone 6S

    即使你的iPhone6S设置了六位数的密码,甚至还设置了touch ID,但我要告诉你的是:你的手机仍然能被犯罪分子解锁。 ? 事件背景 三天前,一位苹果用户的...

    FB客服

扫码关注云+社区

领取腾讯云代金券