class Trie{ private: vector<Trie*> child; bool isEnd; public: Trie(): child(26), isEnd(false) {} void insert(string &word) { Trie* node = this; for (auto ch : word) { if (node->child[ch-'a'] == nullptr) { node->child[ch-'a'] = new Trie(); } node = node->child[ch-'a']; } node->isEnd = true; } // 检索单词word是否在前缀树中 bool search(string &word) { Trie* node = this; for (auto ch : word) { if (node->child[ch-'a'] == nullptr) { return false; } node = node->child[ch-'a']; } return node->isEnd; } // 给定一个前缀prefix,查询前缀树中是否有单词以prefix为开头 bool startsWith(string &prefix) { Trie* node = this; for (auto ch : prefix) { if (node->child[ch-'a'] == nullptr) { return false; } node = node->child[ch-'a']; } return true; } }
一个32位二进制数,右移i
位再与1相与就能得到右数第i + 1
位的数字。
以8位二进制数为例,127的补码为0111 1111
,右移6位为0000 0001
,然后和1做与运算,得到0000 0001
也就是1,就是127的右数第7位数字为1。即127 >> 6 & 1
结果为1
。
此题的前缀树是一个高度为32的二叉树,孩子只有 0 和 1 两种选择。