做网站公司济南,美食网页设计模板中文,网站建设和微站建设的区别,一个网站可以做多少弹窗广告数组中两个数的最大异或值(哈希表、前缀树#xff1a;实现前缀树)
LeetCode题目#xff1a;https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/
哈希表解法 本题使用哈希表方法主要运用到一个定理#xff1a;异或满足算法交换律。即如果a^b c#x…数组中两个数的最大异或值(哈希表、前缀树实现前缀树)
LeetCode题目https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/
哈希表解法 本题使用哈希表方法主要运用到一个定理异或满足算法交换律。即如果a^b c那么必然 b ^ c a。且数组中的元素都在 [ 0 , 2 31 ) [0,2^{31}) [0,231),因此可以确定数值的最高位是30位。 因此可以假设从最高位开始进行计算。依次确定每一位是0还是1即将上一次的计算值x乘以2再加上1就是当前理想的最大值因为此时新增为假设为1 因此便可以应用异或的交换律将数组中的数值num右移k位以映射为当前从30位到第k位的二进制数值。 再分别与当前的理想最大值进行异或。如果异或后的计算结果可以在哈希表中查询到则说明存在num_i和num_j可以异或组成最大值。 可能有人会疑问这样循环30次会不会可能导致每次异或的i和j与上一轮k的不一样那不就不符合唯一的i 和 j了嘛 其实因为算法从高位计算如果高位已经确定可以到达1那么后面就由这个结果倒推罢了交换律在高位已经置1的条件下进行接下来的推导因此并不会出现这种问题。 代码如下
class Solution {static final int HIGH_BIT 30;public int findMaximumXOR(int[] nums) {int x 0;for (int k HIGH_BIT; k 0; k--) {SetInteger seen new HashSetInteger();//通过哈希表构建第30位到第k位的num数据for (int num :nums) {seen.add(num k);}//当前理想情况下x的最大值即新增的第k位可以异或取1int x_Next x * 2 1;boolean found false;for (int num: nums) {if (seen.contains(x_Next ^ (num k))) //异或满足交换律所以num i和 num j异或是否可以得到当前位标记为1的数x_Next{found true;break;}}if (found) {x x_Next;}else {x x_Next - 1;//如果没有找到则说明k位不能被置为1所以-1即可}}return x;}
}前缀树解法 首先先要了解前缀树是什么Trie发音类似 “try”或者说 前缀树 是一种树形数据结构用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景例如自动补完和拼写检查。
相关题目实现 Trie (前缀树)
LeetCode题目https://leetcode.cn/problems/implement-trie-prefix-tree/ 对于字符串来说相当于一个26叉树每个分叉对应一个字母从开始到结尾依次对应字符每个位置是否存在该字符。
代码如下
class Trie {private Trie[] children;private boolean isEnd;public Trie() {children new Trie[26];isEnd false;}public void insert(String word) {Trie node this;for (int i 0; i word.length(); i) {char ch word.charAt(i);int index ch - a;if (node.children[index] null) {node.children[index] new Trie();}node node.children[index];}node.isEnd true;}public boolean search(String word) {Trie node searchPrefix(word);return node ! null node.isEnd;}public boolean startsWith(String prefix) {return searchPrefix(prefix) ! null;}private Trie searchPrefix(String prefix) {Trie node this;for (int i 0; i prefix.length(); i) {char ch prefix.charAt(i);int index ch - a;if (node.children[index] null) {return null;}node node.children[index];}return node;}
}/*** Your Trie object will be instantiated and called as such:* Trie obj new Trie();* obj.insert(word);* boolean param_2 obj.search(word);* boolean param_3 obj.startsWith(prefix);*/字典树的应用
个人理解字典树适合查询一些可重复的状态类别比如当前需要查询的数据是之前所有已经放入的数据总和的情况下字典树十分方便。 可以将字典树应用在该题目上主要用到的核心点有 0 ≤ i ≤ j n 0 ≤ i ≤ j n 0≤i≤jn 以及逐位进行异或的思想。 首先假定字典树是从高位开始统计每一位的0或者1且因为异或为i与j索引数字的异或。所以j只要保证一直比i要大1即可。 此时维护一个公共的字典树并将其与num_j进行按位异或运算。并随着i的更新不断更新字典树内部的索引。即可完成。
代码如下
class Solution {Trie root new Trie();static final int HIGH_BIT 30;public int findMaximumXOR(int[] nums) {int x 0;for (int i 1; i nums.length; i) {add(nums[i - 1]);x Math.max(x, check(nums[i]));}return x;}private void add(int num) {Trie cur root;for (int k HIGH_BIT; k 0 ; k--) {int bit (num k) 1;if (cur.children[bit] null) {cur.children[bit] new Trie(); } cur cur.children[bit];}}private int check(int num) {Trie cur root;int x 0;for (int k HIGH_BIT; k 0; k--) {int bit (num k) 1;if (bit 0) {if (cur.children[1] ! null) {cur cur.children[1];x x * 2 1;}else if (cur.children[0] ! null){x x * 2;cur cur.children[0];}else {break;}}else {if (cur.children[0] ! null) {cur cur.children[0];x x * 2 1;}else if (cur.children[1] ! null){x x * 2;cur cur.children[1];}else {break;}}}return x;}
}class Trie{public Trie[] children;public Trie() {children new Trie[2];}
}
