# The 22nd day of the special assault version of the sword offer

2022-08-06 08:26:53

class Solution {

public:
int minimumLengthEncoding(vector<string>& words) {

unordered_set<string> us(words.begin(), words.end());
for(auto &word: words) {

for(int i = 1; i < word.size(); i++) {

us.erase(word.substr(i));
}
}
int res = 0;
for(auto &word: us) {

res += word.size() + 1;
}
return res;
}
};


According to the idea of ​​method 1,我们将所有 w o r d word Write in reverse order T r i e Trie ,最后 d f s dfs Find the depth of all leaf nodes+1 即可

class Solution {

private:
struct Trie{

vector<Trie*> children;
Trie():children(26){
}
}*trie;
public:
int minimumLengthEncoding(vector<string>& words) {

trie = new Trie();
create_trie(words);
return get_cnts(trie, 0, "");//遍历trie树,Find the length from the root node to all leaf nodes+1(#)即可
}

void create_trie(vector<string> &words) {

for(auto &word: words) {

auto node = trie;
for(int i = word.size()-1; i >= 0; i--) {

int u = word[i]-'a';
if(!node->children[u]) {

node->children[u] = new Trie();
}
node = node->children[u];
}
}

}

int get_cnts(Trie* root, int depth, string str) {

int cnt = 0;
bool is_null = true;
for(int i = 0; i < 26; i++) {

if(root->children[i]) {

is_null = false;
cnt += get_cnts(root->children[i], depth+1,str+(char)('a'+i));
}
}
if(is_null) cnt += depth+1;
return cnt;
}
};


Same idea as method 2,and more efficient algorithms

class TrieNode{

TrieNode* children;
public:
int count;
TrieNode() {

for (int i = 0; i < 26; ++i) children[i] = NULL;
count = 0;
}
TrieNode* get(char c) {

if (children[c - 'a'] == NULL) {

children[c - 'a'] = new TrieNode();
count++;
}
return children[c - 'a'];
}
};
class Solution {

public:
int minimumLengthEncoding(vector<string>& words) {

TrieNode* trie = new TrieNode();
unordered_map<TrieNode*, int> nodes;

for (int i = 0; i < (int)words.size(); ++i) {

string word = words[i];
TrieNode* cur = trie;
for (int j = word.length() - 1; j >= 0; --j)
cur = cur->get(word[j]);
nodes[cur] = i;
}

int ans = 0;
for (auto& [node, idx] : nodes) {

if (node->count == 0) {
//叶子结点(The next node of the last character)
ans += words[idx].length() + 1;
}
}
return ans;
}
};


class MapSum {

private:
unordered_map<string,int> um;
public:
/** Initialize your data structure here. */
MapSum() {

}

void insert(string key, int val) {

um[key] = val;
}

int sum(string prefix) {

int res = 0;
for(auto &[key,val]: um) {

if(key.substr(0,prefix.size()) == prefix) {

res += val;
continue;
}
}
return res;
}
};



i n s e r t insert 时,把 k e y key All possible prefixes are added d e l t a delta 数值（Equivalent to adding both to the path）,这里的 d e l t a delta works great： d e l t a = v a l − u m [ k e y ] = > v a l = d e l t a + u m [ k e y ] delta = val - um[key] => val = delta + um[key] This will perfectly calculate the original u m [ k e y ] um[key] The sum is converted into v a l val 了.

class MapSum {

private:
unordered_map<string,int> um, prefix_map;
public:
/** Initialize your data structure here. */
MapSum() {

}

void insert(string key, int val) {

int delta = val;
if(um.count(key)) {

delta = val - um[key]; //取差值,妙哉！
}
um[key] = val;
for(int i = 1; i <= key.size(); i++) {

prefix_map[key.substr(0,i)] += delta;
}
}

int sum(string prefix) {

return prefix_map[prefix];
}
};


According to the idea of ​​method 2, replace the prefix hash table with T r i e Trie ,在 T r i e Trie value is added to the path.

class MapSum {

private:
struct Trie {

int val;
vector<Trie*> children;
Trie():val(0),children(26){
}
}*trie;
unordered_map<string,int> um;
public:
/** Initialize your data structure here. */
MapSum() {

trie = new Trie();
}

void insert(string key, int val) {

int delta = val;
if(um.count(key)) {

delta = val - um[key];
}
um[key] = val;
auto node = trie;
for(auto &ch: key) {

int u = ch-'a';
if(!node->children[u]) {

node->children[u] = new Trie();
}
node = node->children[u];
node->val += delta;
}
}

int sum(string prefix) {

auto node = trie;
for(int i = 0; i < prefix.size(); i++) {

int u = prefix[i]-'a';
if(!node->children[u]) return 0;
node = node->children[u];
}
return node->val;
}
};


• 异或支持 a 1 ⨁ a 2 = x < = > x ⨁ a 1 = a 2 a_1 \bigoplus a_2=x <=> x \bigoplus a_1=a_2 .
• With this formula we can assume a x n e x t x_{next} 最后一位为 1 1 . （Total action is required 31 31 位）
• 然后将 x n e x t x_{next} 异或 所有 n u m num The obtained value is looked up in a hash table,If found a value stating the hypothesis x x Can be obtained by XOR,接着就将 x = ( x < < 1 ) + 1 x = (x<<1) + 1 .
• Please understand with the code
class Solution {

public:
int findMaximumXOR(vector<int>& nums) {

int x = 0;
for(int i = 30; i >= 0; i--) {

unordered_set<int> us;
for(const int &num: nums) {

us.insert(num>>i); //将 num前i位 Put into a hash table for lookup.
}
int x_next = x * 2 + 1; //Suppose the last bit is 1
bool found = false;
for(const int &num: nums) {

if(us.count(x_next ^ (num>>i))) {

found = true; //假设成立
break;
}
}
if(found) x = x_next;
else x = x_next - 1; //The XOR result of the last bit cannot be1,所以要减掉
}
return x;
}
};


• Convert all numbers to 31位2进制数,Then put it T r i e Trie 上.
• 所有数都在 T r i e Trie Looking for the largest possible XOR value,For example the current bit is 0 0 ,Just check to see if there is 0 0 结点,如果有,The current bit XOR results in 1 1 ,反之为 0 0
class Solution {

private:
struct Trie{

Trie* children;
Trie(){

children = children = nullptr;
}
}*trie;
public:
void insert(int num) {

auto node = trie;
for(int i = 30; i >= 0; i--) {

int bit = (num>>i) & 1;
if(!node->children[bit]) {

node->children[bit] = new Trie();
}
node = node->children[bit];
}
}

int max_xor(int num) {

auto node = trie;
int res = 0;
for(int i = 30; i >= 0; i--) {

int bit = (num>>i) & 1;
if(bit == 0) {

if(!node->children) {

node = node->children;
res = res * 2;
} else {

node = node->children;
res = res * 2 + 1;
}
} else if(bit == 1) {

if(!node->children) {

node = node->children;
res = res * 2;
} else {

node = node->children;
res = res * 2 + 1;
}
}
}
return res;
}

int findMaximumXOR(vector<int>& nums) {

trie = new Trie();
int x = 0;
for(const auto &num: nums) {

insert(num);
x = max(x, max_xor(num));
}
return x;
}
};