力扣 哈希表 总结_哈希表count函数

1. 杂项

哈希表的讲解，很细很细

定义一个哈希表

	unordered_map<typenameA,typenameB> hash; // key  value
1

常用函数

	//增加元素
	hash[key] = value;
	//删除元素
	hash.erase(key);  //  如果没有找到会返回0
	//修改元素
	hash[key] = new value;
	//查找元素
	hash.find(key);   //  常用hash.find(key) == hash.end()来判断key值是否存在
	hash.count(key)   //  该函数：用以统计key值在unordered_map中出现的次数。c++ unordered_map不允许有重复的key。因此，如果key存在，则count返回1，如果不存在，则count返回0

	//————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————
	//遍历元素
    for (auto it = mp.begin(); it != mp.end(); ++it)  //遍历的方法
    {
        cout <<"key为:" << it->first << "   value为:";
        for (int i = 0; i < it->second.size(); i++)  
        { 
            cout << (it->second)[i]<<' ';  //这边的value是vector<string>类型的，不能直接用cout打印
                                            //，所以要循环一个一个字符串打印出来
        }
        cout << endl;        
    }
————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————
	cout << "mp1" << mp1.count('b') << endl;
	使用count，返回的是被查找元素的个数。如果有，返回1；否则，返回0。注意，map中不存在相同元素，所以返回值只能是1或0。
	使用find，返回的是被查找元素的位置，没有则返回map.end()。
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

2. emplace_back 函数解析

也是添加元素的函数，只不过和vector容器的push_back()的区别在于：
push_back()方法要调用构造函数和复制构造函数，这也就代表着要先构造一个临时对象，然后把临时的copy构造函数拷贝或者移动到容器最后面。而emplace_back()在实现时，则是直接在容器的尾部创建这个元素，省去了拷贝或移动元素的过程。

vector<pair<int, int>> ret;
ret.push_back(1,1)//会报错，因为没有构造一个临时对象
ret.push_back(pair(1,1))//不会报错，因为构成了一个pair对象
ret.emplace_back(1,1)//不会报错，因为直接在容器的尾部创建对象
1
2
3
4

vector<vector<int>> ans;
        int lastcol = INT_MIN;
        for (const auto& [col, row, value]: nodes) {
            if (col != lastcol) {
                lastcol = col;
                ans.emplace_back();//这里的emplace_back()直接在ans的尾部创建一个类型为vector<int>的空对象，如果省去这一行，后面的ans.back()会是一个空指针而报错。
            }
            ans.back().emplace_back(value);
        }
1
2
3
4
5
6
7
8
9

3.哈希表的应用总结

3.1 力扣49 (字母异位词)

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

这边的键值对采用的是：由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。

    vector<string> strs;
    unordered_map<string, vector<string>> mp;
    strs.push_back("eat");
    strs.push_back("tea");
    strs.push_back("tan");
    strs.push_back("ate");
    strs.push_back("nat");
    strs.push_back("bat");
        
    for (string& str : strs) { //确定好排序好的key！
        string key = str;
        sort(key.begin(), key.end());
        mp[key].emplace_back(str);  //这边插入的key和value相对应！
    }

    for (auto it = mp.begin(); it != mp.end(); ++it)  //遍历的方法
    {
        cout <<"key为:" << it->first << "   value为:";
        for (int i = 0; i < it->second.size(); i++)  
        { 
            cout << (it->second)[i]<<' ';  //这边的value是vector<string>类型的，不能直接用cout打印
                                            //，所以要循环一个一个字符串打印出来
        }
        cout << endl;        
    }
    //排好序的结果如下图，最后按照下面的这个图 按照顺序放到 ans 里面就行了
    vector<vector<string>> ans;
    for (auto it = mp.begin(); it != mp.end(); ++it) {
        ans.emplace_back(it->second);
    }
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

3.2 力扣49 法二 另一种键值对方式

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

由于互为字母异位词的两个字符串包含的字母相同，因此两个字符串中的相同字母出现的次数一定是相同的，故可以将每个字母出现的次数使用字符串表示，作为哈希表的键。
由于字符串只包含小写字母，因此对于每个字符串，可以使用长度为 2626 的数组记录每个字母出现的次数。需要注意的是，在使用数组作为哈希表的键时，不同语言的支持程度不同，因此不同语言的实现方式也不同。

    vector<string> strs;
    strs.push_back("eat");
    strs.push_back("tea");
    strs.push_back("tan");
    strs.push_back("ate");
    strs.push_back("nat");
    strs.push_back("bat");
        
    vector<vector<string>> res;
    map<string, vector<string>> map;

    // 统计string的各字母频次,以频次为key直接加入队列
    for (auto s : strs) {
        string st = string(26, '0');  //先是弄成26个字母都是零
        for (auto c : s)  ++st[c - 'a']; //将有出现的字母对应的位置加 1
        map[st].emplace_back(s);  //放到键值对当中， st作为key是这个26个数   s作为value是正常的字符串
    }
    for (auto e : map)  res.emplace_back(e.second);  //放到 vector 当中

	//遍历方法
    for (auto it = map.begin(); it != map.end(); ++it)  //遍历的方法
    {
        cout << "key为:" << it->first << "   value为:";
        for (int i = 0; i < it->second.size(); i++)
        {
            cout << (it->second)[i] << ' ';  //这边的value是vector<string>类型的，不能直接用cout打印
                                            //，所以要循环一个一个字符串打印出来
        }
        cout << endl;
    }
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

3.3 力扣451 哈希表的深入理解

给定一个字符串 s ，根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。
返回 已排序的字符串 。如果有多个答案，返回其中任何一个。

输入: s = “tree”
输出: “eert”
解释: 'e’出现两次，'r’和’t’都只出现一次。
因此’e’必须出现在’r’和’t’之前。此外，"eetr"也是一个有效的答案。
直接先按照字母出现的频率来创建哈希表，这样key为字母值，value为他出现的频率。
然后将其放到vector当中按照value的大小进行从大到小排序。
最后放到string reuslt当中即可。

	string s;
    s = "baafAAag";
    unordered_map<char, int> mp; //哈希表这样创建的，key是char类型，value是int类型
    int length = s.length();
    for (auto& ch : s) {
        mp[ch]++;  //这里怎么放key和value的！！很巧妙
    }
    //遍历哈希表元素
    for (auto it = mp.begin(); it != mp.end(); ++it)  //遍历的方法
    {
        cout << "key为:" << it->first << "   value为:";
        cout << it->second;
        cout << endl;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

    vector <pair<char, int>> temp;  //创建内容格式和哈希表一致的vector容器，将哈希表的内容放到vector容器当中
    for (auto& it : mp) {
        temp.push_back(it); //格式一样，直接push_back
    }
    
    for (int i = 0; i < temp.size(); i++) {
        cout << temp[i].first << "  ";
        cout << temp[i].second << endl;
    }
1
2
3
4
5
6
7
8
9

    for (int i = 0; i < temp.size() - 1; ++i) {   //利用冒泡排序根据value的大小进行排序
        for (int j = 0; j < temp.size() - i - 1; ++j) {
            if (temp[j].second < temp[j+1].second)
            {
                pair<char, int> tempp;
                tempp = temp[j];
                temp[j ] = temp[j+1];
                temp[j+1] = tempp;
            }
        }
    }
    
    for (int i = 0; i < temp.size(); i++) {
    cout << temp[i].first << "  ";
    cout << temp[i].second << endl;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

    string result;  
    for (auto& it : temp) {
        result = result.append(it.second, it.first);  //最后按照顺序放到string reuslt当中即可
    }
    cout << result << endl;
1
2
3
4
5

2022年7月22日后

4 . 2022年7月22日后

#include <iostream>
using namespace std;
#include <string>
#include <unordered_map>
#include <algorithm>
#include<numeric>
#include<vector>
#include<cmath>
#include <unordered_set>
#include <set>

void print_mp1(unordered_map<char, vector<char>> mp) {
    //遍历元素
    for (auto it = mp.begin(); it != mp.end(); ++it)  //遍历的方法
    {
        
        cout << "mp1 --> key为:" << it->first << "   value为:";
        //cout << "key为:" << it->first << "   value为:" << it->second << endl;;

        for (int i = 0; i < it->second.size(); i++)
        {
            cout << (it->second)[i] << ' ';  //这边的value是vector<string>类型的，不能直接用cout打印
                                            //，所以要循环一个一个字符串打印出来
        }
        cout << endl;
    }
}

void print_mp2(unordered_map<char, char> mp) {
    //遍历元素
    for (auto it = mp.begin(); it != mp.end(); ++it)  //遍历的方法
    {
        
        cout << "mp2 --> key为:" << it->first << "   value为:" << it->second << endl;;
    }
}

void print_mp2(unordered_map<char, int> mp) {
    //遍历元素
    for (auto it = mp.begin(); it != mp.end(); ++it)  //遍历的方法
    {

        cout << "mp3 --> key为:" << it->first << "   value为:" << it->second << endl;;
    }
}

int main()
{   
    vector<int> nums1 = { 9,1,4,7,3,-1,0,5,8,-1,6};
    vector<int> nums2 = { 2,2,1,1 };
    
    set<int> s1;
    set<int> s2;
    for (int x : nums1) {
        s1.insert(x);
    }
    //for (auto it = s1.begin(); it != s1.end(); it++)
    //    cout << *it << " "<<endl;

    string pattern = "abcddabd";
    vector <char> str;
    string temp;

    //1.这种构造方式，可以用 emplace_back 函数来创造 ， 也显示重复的数字
    unordered_map<char, vector<char>> mp1;
    for (int i = 0; i < pattern.size(); i++) {
        mp1[pattern[i]].emplace_back(pattern[i]);
    }
    print_mp1(mp1);
    cout << " " << endl;
    //2.计算key对应的数字，只会显示一个但是
    unordered_map<char, char> mp2;
    for (int i = 0; i < pattern.size(); i++) {
        mp2[pattern[i]] = pattern[i];
    }
    print_mp2(mp2);
    cout << " " << endl;
    //3. 计算每个key对应的重复数字的个数
    unordered_map<char, int> mp3;
    for (int i = 0; i < pattern.size(); i++) {
        mp3[pattern[i]]++;
    }
    print_mp2(mp3);
    cout << " " << endl;

    //print_mp(mp);
	system("pause");
	return 0;
}
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

5. set容器横空出世

unordered_set是什么
unordered_set 容器，可直译为“无序 set 容器”。即 unordered_set 容器和 set 容器很像，唯一的区别就在于 set 容器会自行对存储的数据进行排序，而 unordered_set 容器不会。
unordered_set的几个特性：

• 不再以键值对的形式存储数据，而是直接存储数据的值 ；
• 容器内部存储的各个元素的值都互不相等，且不能被修改；
• 不会对内部存储的数据进行排序

5.1 初始化构造

//set容器 构造和赋值
void PrintSet(unordered_set<int>& s)
{
    for (unordered_set<int>::iterator it = s.begin(); it != s.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}
void PrintSet2(set<int>& s)
{
    for (set<int>::iterator it = s.begin(); it != s.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

//1.初始化构造
    unordered_set<int> set1 = {1,2,3,4,5,67};
    cout << "unordered_set<int> set1 : ";
    PrintSet(set1);
    unordered_set<int> set2(set1);
    cout << "unordered_set<int> set2 : ";
    PrintSet(set2);
    unordered_set<int> set3(set1.begin(), set1.end()); //使用迭代器构造
    cout << "unordered_set<int> set3 : ";
    PrintSet(set3);
    unordered_set<int> set5(move(set2));
    cout << "unordered_set<int> set5 : ";
    PrintSet(set5);
    unordered_set<int> set6{ 1,2,10,10 }; //重复的自动去掉
    cout << "unordered_set<int> set6 : ";
    PrintSet(set6);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

5.2 插入数据(set和unordered_set的直接区别) (insert和emplace)

    set<int> st;
    st.insert(10);
    st.insert(20);
    st.insert(10);
    st.insert(40);
    st.insert(30);
    st.insert(30);
    cout << "set<int> st : ";
    PrintSet2(st);

    unordered_set<int> st1;
    st1.insert(10);
    st1.insert(20);
    st1.insert(10);
    st1.insert(40);
    st1.insert(30);
    st1.insert(30);
    cout << "unordered_set<int> st1 : ";
    PrintSet(st1);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

   set<int> st1;
    st1.insert(10);
    st1.insert(20);
    cout << "set<int> st1 : ";
    PrintSet2(st1);
    st1.emplace(10);
    cout << "set<int> st1 : ";
    PrintSet2(st1);
1
2
3
4
5
6
7
8

5.3 查找和统计

//3.查找和统计
    //- find(elem);    //查找elem是否存在，若存在则返回该元素的迭代器；若不存在，则返回set.end();
    //-count(elem);    //统计elem元素的个数 由于set容器中不允许含有重复元素，则值会返回0或者1；
    set<int> s;
    s.insert(10);
    s.insert(20);
    s.insert(30);
    s.insert(40);
    set<int>::iterator it = s.find(40);
    if (it == s.end())
    {
        cout << "未找到该元素" << endl;
    }
    else
    {
        cout << "找到了该元素" << endl;
    }
    set<int> s1;
    s1.insert(10);
    s1.insert(20);
    s1.insert(30);
    s1.insert(40);
    s1.insert(30);
    s1.insert(30);
    s1.insert(30);

    int num = s1.count(30);
    //对于set而言，由于set容器不能包含重复元素 所以count只能返回1或0
    cout << " num=" << num << endl;
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

5.3 删除操作

    set<int> st;
    st.insert(10);
    st.insert(20);
    st.insert(10);
    st.insert(40);
    st.insert(30);
    st.insert(30);
    cout << "set<int> st : ";
    PrintSet2(st);
    //删除操作，成功返回1，失败返回0
    st.erase(10);
    cout << "st.erase(10) : ";
    PrintSet2(st);
    //删除操作，成功返回下一个pair的迭代器
    st.erase(st.find(20));
    cout << "st.erase(st.find(20)) : ";
    PrintSet2(st);
    //删除set1的所有元素，返回指向end的迭代器
    st.erase(st.begin(), st.end());
    cout << "st.erase(st.begin(), st.end()) : ";
    PrintSet2(st);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

    set<int> st1;
    st1.insert(10);
    st1.insert(20);
    cout << "set<int> st1 : ";
    PrintSet2(st1);
    st1.clear();
    cout << "st1.clear() : ";
    PrintSet2(st1);
1
2
3
4
5
6
7
8

5.4 set和multiset区别

    //set和multiset区别
    //set不可以插入重复数据，而multiset可以
    //set插入数据的同时会返回插入结果,1或者0，表示插入是否成功
    //multiset不会检测数据，因此可以插入重复数据
	set<int>s;
	pair<set<int>::iterator, bool> ret;

	//第一次插入10的时候可以成功插入
	ret = s.insert(10);
	if (ret.second)
	{
		cout << "插入成功" << endl;
	}
	else
	{
		cout << "插入失败" << endl;
	}

	//第二次插入10的时候，插入失败
	ret = s.insert(10);
	if (ret.second)
	{
		cout << "插入成功" << endl;
	}
	else
	{
		cout << "插入失败" << endl;
	}


	multiset<int> ms;
	ms.insert(10);
	ms.insert(10);
	ms.insert(10);
	ms.insert(10);
	cout << "multiset<int> ms : ";
	for (multiset<int>::iterator it = ms.begin(); it != ms.end(); it++)
	{
		cout << *it << "  ";
	}
	cout << endl;

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

6.lower_bound()、upper_bound()函数用法

#include <iostream>
using namespace std;
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <set>

void PrintSet2(set<int>& s)
{
    for (set<int>::iterator it = s.begin(); it != s.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
}

int main()
{
    vector<int> nums = { 1,2,3,4,5,5,7,8,9,10 };
    int k = 1;
    int t = 100;

    int n = nums.size();
    set<int>st;
    for (int i = 0; i < n; i++) {
        st.insert(nums[i]);
    }
    PrintSet2(st);
    //cout << x2 <<endl;
    auto it = st.lower_bound(5);  //返回有序序列中大于等于key的第一个值的位置
    cout << *it <<endl;

    auto it1 = st.upper_bound(6);  //返回有序序列中大于key的第一个值的位置
    cout << *it1 << endl;
    
    //print_mp(mp);
	system("pause");
	return 0;
	
}
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