unordered_map算法

unordered_maps

遍历寻找符合键的元素: s.find(键)!=s.end()

map和unordered_map都是C++ STL提供的关联容器，用于存储键-值对。它们之间的区别主要在于底层实现和搜索/插入/删除操作的性能表现：

1. map是基于红黑树实现的，它会自动按照键的大小进行排序，因此键值对是有序存储的。在map中查找元素的时间复杂度为O(log n)。
2. unordered_map是基于哈希表实现的，它不保证元素插入的顺序，因为元素是根据哈希值存储的。在unordered_map中查找元素的时间复杂度为O(1)，但可能会受到哈希冲突的影响。
3. 可以直接对map的键值进行遍历操作

409.最长回文串

class Solution {
public:
    int longestPalindrome(string s) {
        unordered_map<char,int>count;
        for(char ch:s)
        {
            count[ch]++;
        }
        int sum=0;
        bool sign=false;
        for(int i=0;isize();i++)
        {
            if(count[i]%2==0)
            {
                sum+=count[i];
            }
            else
            {
                sum+=count[i]-1;//减1就能构成回文
                sign=true;
            }
        }
        return sign?sum+1:sum;//存在奇数次字符多加1
    }
};

 205.同构字符串

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        unordered_map<char, char> s2, t2;
        for(int i=0;isize();i++)
        {
            char a=s[i],b=t[i];
            if((s2.find(a)!=s2.end()&&s2[a]!=b)||(t2.find(b)!=t2.end()&&t2[b]!=a)) //查找到键同时不符合已有映射关系
            {
                return false;
            }
            s2[a]=b;
            t2[b]=a;
        }
        return true;
    }
};

 290.单词规律

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        using namespace std;
        // 定义两个映射，一个用于字符到单词，一个用于单词到字符
        unordered_map<char, string> char_to_word;
        unordered_mapchar> word_to_char;
        vector words;
        istringstream ss(s); // 使用字符串流来分割字符串
        string word;
 
        // 将字符串 s 按照空格分割成单词
        while (ss >> word) {
            words.push_back(word);
        }
 
        // 检查单词的数量是否与模式字符的数量一致
        if (words.size() != pattern.size()) {
            return false;
        }
 
        for (int i = 0; i < pattern.size(); i++) {
            char c = pattern[i];
            string w = words[i];
 
            // 检查从模式字符到单词的映射是否已经存在且一致
            if ((char_to_word.find(c) != char_to_word.end()&&(char_to_word[c] != w))||((word_to_char.find(w) != word_to_char.end()&&(word_to_char[w] != c)))) {
                return false;
            } 
                char_to_word[c] = w;
                word_to_char[w] = c;
        }
        return true;
    }
 
}
;