421. Maximum XOR of Two Numbers in an Array——本质:利用trie数据结构查找
数据结构 利用 in of 查找 Array an 本质
2023-09-14 09:11:57 时间
Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.
Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.
Could you do this in O(n) runtime?
Example:
Input: [3, 10, 5, 25, 2, 8] Output: 28 Explanation: The maximum result is 5 ^ 25 = 28.
class Solution(object): def findMaximumXOR(self, nums): """ :type nums: List[int] :rtype: int [3,10,5] 0x11, 0x1010, 0x101, 0x11001, 0x10, 0x100 ------------- """ root = [None]*2 for num in nums: self.build_trie(root, num) ans = 0 for num in nums: ans = max(ans, self.max_xor_of(root, num)) return ans def build_trie(self, root, num): for i in range(30, -1, -1): flag = 1 if (num & (1<<i)) else 0 if root[flag] is None: root[flag] = [None]*2 root = root[flag] def max_xor_of(self, root, num): ans = 0 for i in range(30, -1, -1): flag = 0 if (num & (1<<i)) else 1 if root is None: break if root[flag] is not None: ans |= (1<<i) root = root[flag] else: root = root[1-flag] return ans
相关文章
- 野生前端的数据结构练习(11)动态规划算法
- 【学习总结】java数据结构和算法-第二章-数据结构和算法概述
- 小白学 Python 数据分析(3):Pandas (二)数据结构 Series
- 数据结构与算法之美-12 字符串匹配 BF RK BM KMP Trie AC [MD]
- MySQL索引背后的数据结构及算法原理
- Algorithm:【Algorithm算法进阶之路】之数据结构基础知识
- 野生前端的数据结构基础练习(5)——散列
- 第1章 数据结构绪论
- 【架构师修炼之路】Redis 极简教程 : 基本数据结构, 跳表原理, Spring Boot 项目使用实例
- 数据库索引及其数据结构
- 【python】面试常考数据结构算法
- 数据结构期末考试——选择题
- 数据结构和算法 数论 完全数
- 【数据结构】队列的基本概念 | 从零开始实现队列 | 利用思路草图将思路转变为代码