代码编织梦想

题目

剑指 Offer II 059. 最大的异或
在这里插入图片描述

思路

如果找出数组中所有可能由两个数字组成的数对并求出它们的异或,通过比较就能得出最大的异

或值。这种直观的算法的时间复杂度是O(n ^ 2)

整数的异或有一个特点,如果两个相同数位异或的结果是0,那么两个相反的数位异或的结果为1。如果想找到某个整数k和其他整数的最大异或值,那么尽量找和k的数位不同的整数

因此这个问题可以转化为查找的问题,而且还是按照整数的二进制数位进行查找的问题。需要将整数的每个数位都保存下来。前缀树可以实现这种思路

前缀树的定义为:

static class Node {
    Node[] next = new Node[2];
}

构建前缀树:即将每个数根据每一位是0还是1,从高位到低位放到前缀树中

private Node build(int[] nums) {
    Node root = new Node();
    for (int num : nums) {
        Node cur = root;
        for (int i = 31; i >= 0;i--) {
            if (cur.next[(num >> i) & 1] == null) {
                cur.next[(num >> i) & 1] = new Node();
            }
            cur = cur.next[(num >> i) & 1];
        }
    }

    return root;
}

然后从高位开始扫描每个整数num的每个数位,如果前缀树中存在某个整数的相同位置的数位和num的数位相反,则优先选择这个相反的数位,这是因为两 个相反的数位异或的结果为1,比两个相同的数位异或的结果大

代码

class Solution {
    static class Node {
        Node[] next = new Node[2];
    }

    public int findMaximumXOR(int[] nums) {
        Node root = build(nums);
        int max = 0;
        for (int num : nums) {
            int xor = 0;
            Node cur = root;
            for (int i = 31;i>=0;i--) {
                if (cur.next[1 - ((num >> i) & 1)] != null) {
                    xor = (xor << 1) + 1;
                    cur = cur.next[1 - ((num >> i) & 1)];
                } else {
                    xor = (xor << 1);
                    cur = cur.next[((num >> i) & 1)];
                }
            }

            max = Math.max(max,xor);
        }

        return max;
    }

    private Node build(int[] nums) {
        Node root = new Node();
        for (int num : nums) {
            Node cur = root;
            for (int i = 31; i >= 0;i--) {
                if (cur.next[(num >> i) & 1] == null) {
                    cur.next[(num >> i) & 1] = new Node();
                }
                cur = cur.next[(num >> i) & 1];
            }
        }

        return root;
    }
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_39383767/article/details/128013081

剑指Offer Ⅱ 001. 整数除法(力扣剑指Offer专项突击版——整数_1)-爱代码爱编程

题目 给定两个整数 a 和 b ,求它们的除法的商 a/b ,要求不得使用乘号 ‘*’、除号 ‘/’ 以及求余符号 ‘%’ 。 注意: 整数除法的结果应当截去(truncate)其小数部分,例如:truncate(8.345) = 8 以及 truncate(-2.7335) = -2 假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−2^

【leetcode】剑指 offer(专项突击版)汇总_friedrichor的博客-爱代码爱编程

文章目录 002. 二进制加法(反转相加 / 位运算)006. 排序数组中两个数字之和(二分查找 / 双指针)007. 数组中和为 0 的三个数(双指针)008. 和大于等于 target 的最短子数组(滑动窗口 /

剑指offer专项突破版(1)—— 整数除法_亚洲第一中锋_哈达迪的博客-爱代码爱编程

整数除法 题目 剑指 Offer II 001. 整数除法 思路 由于只不能用除号,因此可以用a不断减b,直到a小于b为止,计算减了多少次b。但这样如果遇到 2 ^ 31 / 1 的情况,就会比较慢,因此需要进行

剑指offer专项突破版(4)—— 只出现一次的数字_亚洲第一中锋_哈达迪的博客-爱代码爱编程

题目 剑指 Offer II 004. 只出现一次的数字 思路 本题需要用二进制的思路来看。一个整数由32位组成。我们可以将数组中所有数字的同一位置的数位相加,数组中除了那个只出现一次的数以外,其他的数相加的结果中

剑指offer专项突破版(10)—— 和为 k 的子数组_亚洲第一中锋_哈达迪的博客-爱代码爱编程

题目 剑指 Offer II 010. 和为 k 的子数组 思路 暴力法 本题求和为k的子数组的个数,一个直观的想法是: 枚举每个子数组 计算每个子数组的和 统计和等于k的子数组的个数 但这样时间复

剑指offer专项突破版(14)—— 字符串中的变位词_亚洲第一中锋_哈达迪的博客-爱代码爱编程

题目 剑指 Offer II 014. 字符串中的变位词 - 力扣(LeetCode) 思路 如果先计算出s1的全排列,再看每个排列是否是s2的子串,时间复杂度会非常高 如果两个字符串是变位词,不管是什么排列,其字

剑指offer专项突破版(26)—— 重排链表_亚洲第一中锋_哈达迪的博客-爱代码爱编程

题目 剑指 Offer II 026. 重排链表 思路 首先将链表分为前半段和后半段 例如:1 -> 2 -> 3 -> 4被分为1 -> 2和3 -> 4 如果链表长度为计数,需要

剑指offer专项突破版(38)—— 每日温度_亚洲第一中锋_哈达迪的博客-爱代码爱编程

题目 剑指 Offer II 038. 每日温度 思路 本题需要用到单调栈的思想: 准备一个栈,从左往右遍历每个下标i,检查栈顶元素j代表的数arr[j]是否小于arr[i] 如果小于,将栈顶元素j弹出,直到

剑指offer专项突破版(40)—— 矩阵中最大的矩形_亚洲第一中锋_哈达迪的博客-爱代码爱编程

题目 剑指 Offer II 040. 矩阵中最大的矩形 思路 所有的矩形一定以某一排为底,高为这一排 面试题39是关于最大矩形的,这个题目还是关于最大矩形的,它们之间有没有某种联系?如果能从矩阵中找出直方图,那

剑指offer专项突破版(51)—— 节点之和最大的路径_亚洲第一中锋_哈达迪的博客-爱代码爱编程

题目 剑指 Offer II 051. 节点之和最大的路径 思路 本题中路径可以从任意节点出发,到达任意节点,不一定只能向下,也不一定要经过根节点 对于一棵树来说,最大的路径要么经过根节点,要么不经过 经过

剑指offer专项突破版(53)—— 二叉搜索树中的中序后继_亚洲第一中锋_哈达迪的博客-爱代码爱编程

题目 剑指 Offer II 053. 二叉搜索树中的中序后继 思路 题目给出根节点root和目标节点p,寻找p的后继节点 我们比较root和p root.val <= p.val: 因为是二叉搜

剑指offer专项突破版(58)—— 日程表_亚洲第一中锋_哈达迪的博客-爱代码爱编程

题目 剑指 Offer II 058. 日程表 思路 假设现在已经有一堆互不冲突的日程了,此时需要新增一个日程k,其开始时间为start,结束时间为end,怎么判断是否和已有的日程冲突呢? 先考虑所有开始时间小于等

剑指offer专项突破版(59)—— 数据流的第 k 大数值_亚洲第一中锋_哈达迪的博客-爱代码爱编程

题目 剑指 Offer II 059. 数据流的第 K 大数值 思路 本题需要用到小根堆,堆中保存前k大的数,堆顶元素就是第k大的数 当堆中元素个数不足k时,直接将元素入堆 当新加元素val小于等于堆顶元素时

剑指offer专项突破版(68)—— 查找插入位置_亚洲第一中锋_哈达迪的博客-爱代码爱编程

题目 剑指 Offer II 068. 查找插入位置 思路 从题目描述和示例可以看出,本题可以转化为: 找到第一个大于等于target的位置,如果都小于target,则返回arr.length 那如何找到第一个大

剑指offer专项突破版(68)—— 山峰数组的顶部_亚洲第一中锋_哈达迪的博客-爱代码爱编程

题目 剑指 Offer II 069. 山峰数组的顶部 思路 虽然整个数组并不是排序的,但分成前后两段后每段都分别排序,因此可以用二分法尝试 如果二分出某个中点mid: rr[mid] > arr[mid-

剑指offer专项突破版(74)—— 合并区间_亚洲第一中锋_哈达迪的博客-爱代码爱编程

题目 剑指 Offer II 074. 合并区间 以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回一个不重叠的区