字典树

今天做了一道题时间复杂度超了，看了一种新的解法，记录一下。

https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array/

给定一个非空数组，数组中元素为 a0, a1, a2, … , an-1，其中 0 ≤ ai < 231 。

找到 ai 和aj 最大的异或 (XOR) 运算结果，其中0 ≤ i,  j < n 。

你能在O(n)的时间解决这个问题吗？

暴力破解的方式行不通，见到了字典树的解决方式，字典树是一种高效的查询方式，下面结合图和代码记录一下

#define MAXN 1001
#define MAXC 26

class DictTree {
public:
	//插入 
	bool insert(std::string word) {
		int p = 0;//序号
		for (int i = 0; i < word.size(); i++) {
			int c = word[i] - 'a';
			if (m_tree[p][c] == 0) {
				m_tree[p][c] = m_k;//标记这个字符存在,并存储它的下标
				m_k++;
			}
			p = m_tree[p][c];//接着往下找
		}
		m_color[p] = true;//标记该字符为结尾字符
		return true;
	}

	//查找
	bool search(std::string word) {
		int p = 0;
		for (int i = 0; i < word.size(); i++) {
			int c = word[i] - 'a';
			if (m_tree[p][c] == 0) {
				return false;
			}
			p = m_tree[p][c];
		}
		return m_color[p];
	}

private:

	bool m_color[MAXN] = { false };//标识是否为结束节点
	int m_tree[MAXN][MAXC] = { 0 };//初始化
	int m_k = 1;//表示下一个点的序号,数组的下标
};

上面的代码是要通过数组记录的方式实现的字典树，插入了 “abc”、“bcda”、“abf”，所形成的字典树。其实就是去记录了它下一个节点应该出现的行号，和它自己的行偏移， 前面说了用在查询上，查询的时候去查看对应的行号和行偏移的地方有么有非0或空数字就行了。

上面的实现方式空间复杂度很高，看一种节省空间复杂度的实现

class Trie
{
private:
	bool is_string = false;
	Trie* next[26] = { nullptr };
public:
	Trie() 
	{}

	void insert(const string& word)//插入单词
	{
		Trie* root = this;
		for (const auto& w : word) {
			if (root->next[w - 'a'] == nullptr)
			{
				root->next[w - 'a'] = new Trie();

			}
			root = root->next[w - 'a'];
		}
		root->is_string = true;
	}

	bool search(const string& word)//查找单词
	{
		Trie* root = this;
		for (const auto& w : word) {
			if (root->next[w - 'a'] == nullptr)
				return false;
			root = root->next[w - 'a'];
		}
		return root->is_string;
	}

	bool startsWith(const string& prefix)//查找前缀
	{
		Trie* root = this;
		for (const auto& p : prefix) {
			if (root->next[p - 'a'] == nullptr)
				return false;
			root = root->next[p - 'a'];
		}
		return true;
	}
};

其实也就是随用随创建，还有比较难懂的可能就是 Trie* root = this;  了、其实它只是将this具体化了一下， 因为代码中使用的是类指针，但是参数中没有传递，隐含的this指针就是类指针，可能就是原作者的习惯吧，下面的例题中我将对象指针作为参数传递进去，不用隐含的this指针。

最开始题目的解：

struct Node {
	Node* next[2] = { nullptr };
};
class Solution {
public:
	void insert(int num, Node* root) {
		for (int i = 30; i >= 0; --i) {
			int t = (num >> i & 1);
			if (!root->next[t]) {
				root->next[t] = new Node();
			}
			root = root->next[t];
		}
	}
	int findMaximumXOR(vector<int>& nums) {
		Node* root = new Node();
		for (auto val : nums) {
			insert(val, root);
		}
		int res = 0, tmp = 0;
		Node* p = root;
		for (auto val : nums) {
			p = root; 
			tmp = 0;
			for (int i = 30; i >= 0; --i) {
				int t = (val >> i) & 1;
				if (p->next[!t]) {
					p = p->next[!t];
					tmp += (1 << i);
				}
				else
					p = p->next[t];
			}
			res = max(res, tmp);
		}
		return res;
	}
};

字典树不像并查集一样，封装一个类之后一直能用，但是实现思路是不会变的，针对开始的题，其实异或、就是保证两个对应位不同就可以了，到时候对应位不同的越多得到的数越大，那么为什么要使用字典树呢，因为它能记录每个数字对应位是多少，并且O（1）的复杂度查询，或许你还是不理解

看这个图老铁，这是一个字典树，它每次去找和它不同位的数，使用字典树的优点呢，就是他在即将要分叉的节点找下一个有多种选择，有可能有0 也有可能有 1 ，这时候就能选择你要什么数字了，神奇吧。