vlambda博客
学习文章列表

package main
import ( "fmt" "math")
func main() { arr := []int{-1, 2} ret := maxXorSubarray2(arr) fmt.Println(ret)}
// 前缀树的Node结构// nexts[0] -> 0方向的路// nexts[1] -> 1方向的路// nexts[0] == null 0方向上没路！// nexts[0] != null 0方向有路，可以跳下一个节点// nexts[1] == null 1方向上没路！// nexts[1] != null 1方向有路，可以跳下一个节点type Node struct { nexts []*Node}
func twoSelectOne(condition bool, a int, b int) int { if condition { return a } else { return b }
}
func NewNode() *Node { ret := &Node{} ret.nexts = make([]*Node, 2) return ret}
// 基于本题，定制前缀树的实现type NumTrie struct { // 头节点 head *Node}
func NewNumTrie() *NumTrie { ret := &NumTrie{} ret.head = NewNode() return ret}
func (this *NumTrie) add(newNum int) { cur := this.head for move := 63; move >= 0; move-- { path := (newNum >> move) & 1 if cur.nexts[path] == nil { cur.nexts[path] = NewNode() } cur = cur.nexts[path] }}
// 该结构之前收集了一票数字，并且建好了前缀树// num和 谁 ^ 最大的结果（把结果返回）func (this *NumTrie) maxXor(num int) int { cur := this.head ans := 0 for move := 63; move >= 0; move-- { // 取出num中第move位的状态，path只有两种值0就1，整数 path := (num >> move) & 1 // 期待遇到的东西 best := twoSelectOne(move == 63, path, path ^ 1) // 实际遇到的东西 best = twoSelectOne(cur.nexts[best] != nil, best, best ^ 1) // (path ^ best) 当前位位异或完的结果 ans |= (path ^ best) << move cur = cur.nexts[best] } return ans}
// O(N)func maxXorSubarray2(arr []int) int { if len(arr) == 0 { return 0 } max := math.MinInt64 // 0~i整体异或和 xor := 0 numTrie := NewNumTrie() numTrie.add(0) for i := 0; i < len(arr); i++ { xor ^= arr[i] // 0 ~ i max = getMax(max, numTrie.maxXor(xor)) numTrie.add(xor) } return max}
func getMax(a int, b int) int { if a > b { return a } else { return b }}