# 剑指offer专项突击版第22天

2022-08-06 08:17:12

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;
}
};


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树，求出根节点到所有叶子结点长度+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;
}
};


class TrieNode{

TrieNode* children[26];
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) {
//叶子结点(最后一个字符的下一个结点)
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 所有可能的前缀都加上 d e l t a delta 数值（相当于在路径上都加上），这里的 d e l t a delta 用的很妙： 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] 这样就完美的将原先计算了 u m [ k e y ] um[key] 总和转换成 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];
}
};


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
• 通过这个公式我们就可以假设一个 x n e x t x_{next} 最后一位为 1 1 。 （总的需要操作 31 31 位）
• 然后将 x n e x t x_{next} 异或 所有 n u m num 获得的值在哈希表中查找，如果找到了说明假设的值 x x 可以通过异或获得，接着就将 x = ( x < < 1 ) + 1 x = (x<<1) + 1
• 请结合代码进行理解
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位 放入哈希表用来查找。
}
int x_next = x * 2 + 1; //假设最后位为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; //最后一位异或结果不能为1，所以要减掉
}
return x;
}
};


• 将所有数都转成31位2进制数，接着放到 T r i e Trie 上。
• 所有数都在 T r i e Trie 在找尽量最大异或值，比如当前位是 0 0 ，就查看有没有 0 0 结点，如果有，当前位异或结果为 1 1 ，反之为 0 0
class Solution {

private:
struct Trie{

Trie* children[2];
Trie(){

children[0] = children[1] = 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[1]) {

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

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

if(!node->children[0]) {

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

node = node->children[0];
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;
}
};


https://blog.csdn.net/hys__handsome/article/details/126188496