前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2021-08-07:与数组中元素的最大异或值。给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries ,其

2021-08-07:与数组中元素的最大异或值。给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries ,其

作者头像
福大大架构师每日一题
发布2021-09-03 15:19:39
7720
发布2021-09-03 15:19:39
举报

2021-08-07:与数组中元素的最大异或值。给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries ,其中 queries[i] = [xi, mi] 。第 i 个查询的答案是 xi 和任何 nums 数组中不超过 mi 的元素按位异或(XOR)得到的最大值。换句话说,答案是 max(nums[j] XOR xi) ,其中所有 j 均满足 nums[j] <= mi 。如果 nums 中的所有元素都大于 mi,最终答案就是 -1 。返回一个整数数组 answer 作为查询的答案,其中 answer.length == queries.length 且 answer[i] 是第 i 个查询的答案。

福大大 答案2021-08-07:

前缀树。数组的元素的二进制,前缀树存最小值。

代码用golang编写。代码如下:

代码语言:javascript
复制
package main

import (
    "fmt"
    "math"
)

func main() {
    nums := []int{0, 1, 2, 3, 4}
    queries := [][]int{{3, 1}, {1, 3}, {5, 6}}
    ret := maximizeXor(nums, queries)
    fmt.Println(ret)
}

func maximizeXor(nums []int, queries [][]int) []int {
    N := len(nums)
    trie := NewNumTrie()
    for i := 0; i < N; i++ {
        trie.add(nums[i])
    }
    M := len(queries)
    ans := make([]int, M)
    for i := 0; i < M; i++ {
        ans[i] = trie.maxXorWithXBehindM(queries[i][0], queries[i][1])
    }
    return ans
}

type Node struct {
    min   int
    nexts []*Node
}

func NewNode() *Node {
    ans := &Node{}
    ans.min = math.MaxInt64
    ans.nexts = make([]*Node, 2)
    return ans
}

func getMin(a int, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}

type NumTrie struct {
    head *Node
}

func NewNumTrie() *NumTrie {
    ans := &NumTrie{}
    ans.head = NewNode()
    return ans
}

func (this *NumTrie) add(num int) {
    cur := this.head
    this.head.min = getMin(this.head.min, num)
    for move := 30; move >= 0; move-- {
        path := (num >> move) & 1
        if cur.nexts[path] == nil {
            cur.nexts[path] = NewNode()
        } else {
            cur.nexts[path] = cur.nexts[path]
        }
        //cur.nexts[path] = cur.nexts[path] == null ? new Node() : cur.nexts[path];
        cur = cur.nexts[path]
        cur.min = getMin(cur.min, num)
    }
}

// 这个结构中,已经收集了一票数字
// 请返回哪个数字与X异或的结果最大,返回最大结果
// 但是,只有<=m的数字,可以被考虑
func (this *NumTrie) maxXorWithXBehindM(x int, m int) int {
    if this.head.min > m {
        return -1
    }
    // 一定存在某个数可以和x结合
    cur := this.head
    ans := 0
    for move := 30; move >= 0; move-- {
        path := (x >> move) & 1
        // 期待遇到的东西
        best := path ^ 1
        if cur.nexts[best] == nil || cur.nexts[best].min > m {
            best ^= 1
        } else {
            best ^= 0
        }
        //best ^= (cur.nexts[best] == null || cur.nexts[best].min > m) ? 1 : 0;
        // best变成了实际遇到的
        ans |= (path ^ best) << move
        cur = cur.nexts[best]
    }
    return ans
}

执行结果如下:

***

[左神java代码](https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class06/Code03_MaximumXorWithAnElementFromArray.java)

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-08-07,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 福大大架构师每日一题 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档