current position:Home>The 22nd day of the special assault version of the sword offer

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

2022-08-06 08:26:53hys__handsome

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

方法一、使用哈希表
仔细思考发现,The end of the suffix for other strings in the string sequence does not need to be reserved,In the end, only strings that are not string suffixes are left.So we just need to add the string sequence to the hash table,Then brute force the suffix of each string,and delete in the hash table.

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

方法二、Trie树
According to the idea of ​​method 1,我们将所有 w o r d word word Write in reverse order T r i e Trie Trie ,最后 d f s dfs 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[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) {
     //叶子结点(The next node of the last character)
                ans += words[idx].length() + 1;
            }
        }
        return ans;
    }
};

剑指 Offer II 066. 单词之和

方法一、Relies on hash table brute force scanning

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

方法二、前缀map

i n s e r t insert insert 时,把 k e y key key All possible prefixes are added d e l t a delta delta 数值(Equivalent to adding both to the path),这里的 d e l t a delta 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] delta=valum[key]=>val=delta+um[key] This will perfectly calculate the original u m [ k e y ] um[key] um[key] The sum is converted into v a l val 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];
    }
};

方法三、Trie
According to the idea of ​​method 2, replace the prefix hash table with T r i e Trie Trie,在 T r i e Trie 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;
    }
};

剑指 Offer II 067. 最大的异或

方法一、哈希表

  • 异或支持 a 1 ⨁ a 2 = x < = > x ⨁ a 1 = a 2 a_1 \bigoplus a_2=x <=> x \bigoplus a_1=a_2 a1a2=x<=>xa1=a2 .
  • With this formula we can assume a x n e x t x_{next} xnext 最后一位为 1 1 1 . (Total action is required 31 31 31 位)
  • 然后将 x n e x t x_{next} xnext 异或 所有 n u m num num The obtained value is looked up in a hash table,If found a value stating the hypothesis x x x Can be obtained by XOR,接着就将 x = ( x < < 1 ) + 1 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 Trie 上.
  • 所有数都在 T r i e Trie Trie Looking for the largest possible XOR value,For example the current bit is 0 0 0 ,Just check to see if there is 0 0 0 结点,如果有,The current bit XOR results in 1 1 1 ,反之为 0 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;        
    }
};

copyright notice
author[hys__handsome],Please bring the original link to reprint, thank you.
https://en.chowdera.com/2022/218/202208060817041928.html

Random recommended