当前位置:网站首页>剑指offer专项突击版第22天

剑指offer专项突击版第22天

2022-08-06 08:17:12hys__handsome

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

方法二、Trie树
根据方法一的思路,我们将所有 w o r d word word 以倒序写入 T r i e Trie Trie ,最后 d f s dfs 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;
    }
};

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

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

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

方法二、前缀map

i n s e r t insert insert 时,把 k e y key key 所有可能的前缀都加上 d e l t a delta delta 数值(相当于在路径上都加上),这里的 d e l t a delta 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] delta=valum[key]=>val=delta+um[key] 这样就完美的将原先计算了 u m [ k e y ] um[key] um[key] 总和转换成 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
根据方法二的思路将前缀哈希表替换成 T r i e Trie Trie,在 T r i e 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;
    }
};

剑指 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
  • 通过这个公式我们就可以假设一个 x n e x t x_{next} xnext 最后一位为 1 1 1 。 (总的需要操作 31 31 31 位)
  • 然后将 x n e x t x_{next} xnext 异或 所有 n u m num num 获得的值在哈希表中查找,如果找到了说明假设的值 x x x 可以通过异或获得,接着就将 x = ( x < < 1 ) + 1 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 Trie 上。
  • 所有数都在 T r i e Trie Trie 在找尽量最大异或值,比如当前位是 0 0 0 ,就查看有没有 0 0 0 结点,如果有,当前位异或结果为 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;        
    }
};
原网站

版权声明
本文为[hys__handsome]所创,转载请带上原文链接,感谢
https://blog.csdn.net/hys__handsome/article/details/126188496

随机推荐