剑指offer专项突击版第22天

剑指 Offer II 065. 最短的单词编码

方法一、使用哈希表
仔细思考发现，字符串序列中为其他字符串后缀的最后都不用保留，最后都只剩下不是字符串后缀的字符串。所以我们就只需要将字符串序列加入哈希表中，然后暴力遍历每个字符串的后缀，并且在哈希表中删除。

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

方法二、Trie树
根据方法一的思路，我们将所有 $word$ 以倒序写入 $Trie$ ，最后 $dfs$ 求出所有叶子结点深度+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树，求出根节点到所有叶子结点长度+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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

与方法二思路相同，而更高效的算法

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

---

剑指 Offer II 066. 单词之和

方法一、依赖于哈希表暴力扫描

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

方法二、前缀map

在 $insert$ 时，把 $key$ 所有可能的前缀都加上 $delta$ 数值（相当于在路径上都加上），这里的 $delta$ 用的很妙：$delta=val-um[key]=>val=delta+um[key]$ 这样就完美的将原先计算了 $um[key]$ 总和转换成 $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];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

方法三、Trie
根据方法二的思路将前缀哈希表替换成 $Trie$，在 $Trie$ 的路径上都加上值罢了。

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

---

剑指 Offer II 067. 最大的异或

方法一、哈希表

• 异或支持 $a_1⨁a_2=x<=>x⨁a_1=a_2$ 。
• 通过这个公式我们就可以假设一个 $x_{next}$ 最后一位为 $1$ 即 $x_{next}=(x<<1)+1$。 （总的需要操作 $31$ 位）
• 然后将 $x_{next}$ 异或 所有 $num$ 获得的值 分别在哈希表中查找，如果找到了说明假设的值 $x_{next}$ 可以通过异或获得，接着就将 $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;        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

方法二、字典树

• 将所有数都转成31位2进制数，接着放到 $Trie$ 上。
• 所有数都在 $Trie$ 在找尽量最大异或值，比如当前位是 $0$ ，就查看有没有 $0$ 结点，如果有，当前位异或结果为 $1$ ，反之为 $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;        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56