unordered_map<char, char>s
遍历寻找符合键的元素: s.find(键)!=s.end()
map
和unordered_map
都是C++ STL提供的关联容器,用于存储键-值对。它们之间的区别主要在于底层实现和搜索/插入/删除操作的性能表现:
map
是基于红黑树实现的,它会自动按照键的大小进行排序,因此键值对是有序存储的。在map
中查找元素的时间复杂度为O(log n)。unordered_map
是基于哈希表实现的,它不保证元素插入的顺序,因为元素是根据哈希值存储的。在unordered_map
中查找元素的时间复杂度为O(1),但可能会受到哈希冲突的影响。- 可以直接对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;i<count.size();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;i<s.size();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_map<string, char> word_to_char;
vector<string> 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;
}
}
;