前缀树相关算法题
数组中所有数都异或起来的结果，叫做异或和。给定一个数组arr，返回arr的最大连续子数组异或和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| public class Solution {
public int MaxXOR(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int xor = 0;
int max = Integer.MIN_VALUE;
NumTree tree = new NumTree();
tree.add(0);
for (int i = 0; i < arr.length; i++) {
xor ^= arr[i];
max = Math.max(max, tree.searchMaxXOR(xor));
tree.add(xor);
}
return max;
}
static class Node {
Node[] nexts = new Node[2];
}
static class NumTree {
Node head = new Node();
public void add(int num) {
Node cur = head;
for (int move = 31; move >= 0 ; move--) {
int path = (num >> move) & 1;
cur.nexts[path] = cur.nexts[path] == null ? new Node() : cur.nexts[path];
cur = cur.nexts[path];
}
}
public int searchMaxXOR(int num) {
Node cur = head;
int ans = 0;
for (int move = 31; move >= 0 ; move--) {
int path = (num >> move) & 1;
int best = 0;
if (cur.nexts[0] != null) {
best = path;
}
if (cur.nexts[1] != null) {
best = Math.max(best, path ^ 1);
}
ans |= (best << move);
}
return ans;
}
}
}
|
数组中所有数都异或起来的结果，叫做异或和。给定一个数组arr，想知道arr中哪两个数的异或结果最大，返回最大的异或结果
https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public class Solution {
public int findMaximumXOR(int[] nums) {
NumTree numTree = new NumTree();
int max = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++) {
numTree.add(nums[i]);
max = Math.max(max, numTree.searchMaxXOR(nums[i]));
}
return max;
}
}
|
给定一个非负整数组成的数组nums。另有一个查询数组queries，其中queries[i]=[xi,
mi]，第i个查询的答案是xi和任何nums数组中不超过mi的元素按位异或（XOR）得到的最大值
https://leetcode-cn.com/problems/maximum-xor-with-an-element-from-array/
思路：若在每次查询时，用mi进行过滤后再加入到前缀树中，前缀树无法复用，故考虑在前缀树中加入限制，在搜索过程中使用mi判断
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| class Solution {
static class Node {
Node[] nexts = new Node[2];
int minLimit;
public Node(int minLimit) {
this.minLimit = minLimit;
}
public Node() {
this.minLimit = Integer.MAX_VALUE;
}
}
static class NumTreeWithMinNum {
Node head = new Node();
void add(int num) {
Node cur = head;
for (int i = 31; i >= 0 ; i--) {
int sign = (num >> i) & 1;
if (cur.nexts[sign] == null) {
cur.nexts[sign] = new Node(num);
} else {
cur.nexts[sign].minLimit = Math.min(cur.nexts[sign].minLimit, num);
}
cur = cur.nexts[sign];
}
}
public int searchMaxXORWithMinLimit(int num, int minLimit) {
Node cur = head;
int maxXOR = 0;
int i = 31;
for (; i >= 0 ; i--) {
int path = (num >> i) & 1;
int best = i == 31 ? path : path ^ 1;
if (cur.nexts[best] == null || cur.nexts[best].minLimit > minLimit) {
if (cur.nexts[path].minLimit > minLimit) {
break;
}
best = path;
}
maxXOR |= (path ^ best) << i;
cur = cur.nexts[best];
}
if (i != -1) {
return -1;
}
return maxXOR;
}
}
public int[] maximizeXor(int[] nums, int[][] queries) {
if (nums == null || queries == null) {
return null;
}
NumTreeWithMinNum tree = new NumTreeWithMinNum();
for (int i = 0; i < nums.length; i++) {
tree.add(nums[i]);
}
int[] ans = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
ans[i] = tree.searchMaxXORWithMinLimit(queries[i][0], queries[i][1]);
}
return ans;
}
}
|