投稿
  1. 首页
  2. 随笔

哈希散列表（C++力扣题解上）

美式足球比分 • 2022-12-17 • 随笔 • 阅读 45

哈希散列表（C++力扣题解上）,第1张

哈希散列表（C++力扣题解上）

目录

哈希表原理：

哈希的分类

哈希集合：

哈希映射：

哈希STL函数的使用：

1：存在重复元素

 2：只出现一次的数字

3：两个数组的交集

4：快乐数

5：赎金信（字母异位词的开始）

6：字母异位词分组

7：找到字符串中所有字母的异位词（滑动窗口+哈希）

8：两数之和

9：四数相加||

哈希表原理： 哈希的分类

可以把它简单地理解为数组，但其实它更像python中的字典

哈希集合：

头文件：#include

创建哈希集合：unordered_set set;

个人理解：

不如创建一个数组，因为创建一个哈希消耗的内存比较大= =，这里数组和哈希集合承担的作用其实是一样的= =

哈希映射：

头文件：#include

创建哈希映射：  unordered_map map;

个人理解：

这个就是python的字典，第一个type是键(key)，第二个type是值(value)，通过键来查询值

可以理解为：在药房，药师通过看抽屉的标签来查询抽屉的药品，标签就是键，药品就是值

所以，哈希相当于用空间换时间，查询哈希的值，要比遍历数组查询值所需的时间要短.

哈希STL函数的使用：

引用哈希集合时的应用：

#include                 // 当使用set时引用的模板库
#include
using namespace std;
int main() {
    // 创建一个哈希集合
    unordered_set hashset;   
    // 插入新的关键字
    hashset.insert(3);
    hashset.insert(2);
    hashset.insert(1);
    // 删除关键字
    hashset.erase(2);
    // 判断关键字是否在哈希集合中，如果在方法返回负数。如果在集合中返回真，否则返回假
    if (hashset.count(2) <= 0) {
        cout << "关键字2不在哈希集合中" << endl;
    }
    // 得到哈希集合的大小
    cout << "The size of hash set is: " << hashset.size() << endl; 
    // 遍历哈希集合，注意要以指针的形式
    for (auto it = hashset.begin(); it != hashset.end(); ++it) {
        cout << (*it) << " ";
    }
    cout << "are in the hash set." << endl;
    // 清除哈希集合
    hashset.clear();
    // 判断哈希结合是否为空
    if (hashset.empty()) {
        cout << "hash set is empty now!" << endl;
    }
}

引用哈希表的应用：

#include
#include
using namespace std;
int main()
{
    unordered_mapmap;//创建哈希表

    map[4] = 14;//直接赋值
    map[5] = 15;
    cout << map[4];//输出14

    //通过insert()函数来添加元素
    map.insert({ 5,15 });//参数为（键，值）
    map.insert({ 5,16 });
    cout << map[5];  //结果为15->一个下标只能对应一个值

    //复制，重新构造一张新的哈希表
    unordered_map map{ {1,10},{2,12},{3,13} };
    unordered_map map1(map);
    
    unordered_map::iterator iter = hmap.begin();
    unordered_map::iterator iter = hmap.end();

    bool isEmpty = map.empty();//判断是否为空
    int size = hmap.size();//哈希表的大小

    erase函数
    map.erase(iter_begin);  //删除开始位置的元素
    map.erase(iter_begin, iter_end); //删除开始位置和结束位置之间的元素
    map.erase(3); //删除key==3的键值对

    //clear()函数：清空哈希表中的元素
    map.clear();
    

    unordered_map::iterator iter;
    iter = hmap.find(2); //返回key==2的迭代器，可以通过iter->second访问该key对应的元素
    if(iter != hmap.end())  cout << iter->second;

    int count = hmap.count(key);//统计哈希表键所对应的值的个数
   
    //哈希表的遍历
    for(auto iter=map.begin(); iter != map.end(); iter++){
    cout << "key: " <<  iter->first  << "value: " <<  iter->second < 

小理解：
 

遇到不会的函数要积极动手查一查，你会发现有很多好用的函数
 

C语言是什么？不要联系我了，我现在只用C++
 

问：auto是啥？
 

答：auto是一种类型，像int，double，string，它能够根据后面是啥自动匹配对应的类型
 

通过下面的题目就会加深理解了^ ^
 

题目实战
 
1：存在重复元素 

 

 暴力的方法很容易想到：两个for嵌套：时间复杂度是：O(N^2)
 

我这里给出的是小暴力的方法：时间复杂度是O(N*logN)
 

bool containsDuplicate(vector& nums)
{
    sort(nums.begin(),nums.end());
    for(int i=1;i 

哈希集合的方法：
 

思路解析：
 

遍历数组nums，将遍历到的元素插入hash集合中
 

如果哈希表的长度！=原数组的长度 -> 那么肯定有1个以上的重复元素插入到了哈希表
 

注意这只会导致元素作为索引对应的值增加，并不会使数组长度增加
 

画图理解：
 

原数组：
 

 

 理解：原数组的val作为了hashset的index，原数组val的频数作为了hashset的val
 

 

bool containsDuplicate(vector& nums) {
    unordered_sethash;
	for (int a : nums)
	{
		hash.insert(a);
	}
	return hash.size() != nums.size();
}
 


 2：只出现一次的数字 

 

 思路解析：
 

这道题用位运算也非常简单，具体的写法用异或，可以看看我的一篇文章《位运算的应用》
 

与上题同一种思路，如果没有出现过就插入，如果出现过就删除
 

class Solution {
public:
    int singleNumber(vector& nums) {
    unordered_set hash;
	for (auto& num : nums)//遍历数组
	{
		if (hash.count(num) > 0)//如果哈希表中有过一次元素
		{
			hash.erase(num);//删除该元素
		}
		else//如果哈希表之前没有过一次元素
		{
			hash.insert(num);//插入该元素
		}
	}//跳出循环后，哈希表中只剩下一个元素
	return *hash.begin();//哈希表中的开头地址解引用就是仅有的那个元素
    }
};
 


3：两个数组的交集 

 

 思路解析：
 

开一个答案数组，用哈希表遍历存nums1的频数，遍历nums2，查找nums2是否有该元素，如果有，则尾插入答案数组，并在nums2中删除这个元素，防止重复出现
 

class Solution {
public:
    vector intersection(vector& nums1, vector& nums2) {
    unordered_set hashset;
	vector result;
	for (auto val : nums1)
	{
		hashset.insert(val);
	}
	for (auto val : nums2)
	{
		if (hashset.count(val) > 0)
		{
			result.push_back(val);
			hashset.erase(val);
		}
	}
	return result;
    }
};
 
4：快乐数 

 

 思路解析：
 

设计一个函数cal 计算按照规律变化后的数字，并在哈希表中进行查询，如果哈希表中存在这个数，那么我们就可以知道，该数发生了重复，那么就直接返回false;反之如果这个数变了1，就跳出循环，返回true;
 

class Solution {
public:
    int cal(int n)//计算规则后的数
{
	int ans = 0;
	while (n)
	{
		ans = ans + pow(n % 10, 2);
		n = n / 10;
	}
	return ans;
}
    bool isHappy(int n) {
    unordered_set hashset;
	while (n != 1)//当不等于1的时候继续
	{
		n = cal(n);
		if (hashset.count(n))//如果计算后的数字与哈希存的数字重复
		{
			return false;//返回错误
		}
		hashset.insert(n);//如果没有则，插入到哈希中
	}
	return true;
    }
};
 


5：赎金信（字母异位词的开始） 

 

 思路解析：
 

 
 
开一个26长度的数组去存储字母出现的频数，遍历第一个字符串，每遍历到一个字母就++
 
 
遍历第二个字符串，每遍历到一个字母就--，最后查找数组中是否有负数的情况，若有则说明第一个字符串不能由第二个字符串变形而来
 

 

 代码实现：
 

class Solution {
public:
    bool canConstruct(string s, string t) {
    int record[26]={0};
    for(int i=0;i 
6：字母异位词分组 

 

 思路解析：
 

与上题相同，判断是否位字母异位词，这道题的难点是，将单词分类，并归纳在一起
 

这里需要到了哈希表，而不是哈希集合，因为我们需要将单词排序后作为索引，而不是将数字作为索引，这是一种映射关系
 

这里就是哈希映射的的开始了^ ^
 

class Solution {
public:
    vector> groupAnagrams(vector& strs) {
    unordered_map >map;
	for (int i = 0; i < strs.size(); i++)//将取出的字符串排序后作为一类
	{
		string str = strs[i];
		sort(str.begin(), str.end());
		map[str].push_back(strs[i]);//将未排序的字符串插入至已排序好的那一类
	}
	vector >ans;
	for (auto it = map.begin(); it != map.end(); it++)//遍历尾插
	{
		ans.push_back(it->second);
	}
    return ans;
    }
};
 

补充：it->first是哈希表中的键，it->second是哈希表中的值
 


7：找到字符串中所有字母的异位词（滑动窗口+哈希） 

 

 思路解析：
 

用scount数组存s字符串中的频数，用pcount数组存p字符串中的频数
 

以strlen(p)为长度作为滑窗，每次遍历判断长度为strlen(p)的scount是否与pcount相等
 

如果相等就插入答案数组，如果不相等就continue
 

class Solution {
public:
    vector findAnagrams(string s, string p) {
    int slen = s.size();
	int plen = p.size();

	if (slen < plen)
	{
		return vector();
	}
	vector ans;
	vector sCount(26);
	vector pCount(26);
	for (int i = 0; i < plen; i++)
	{
		sCount[s[i] - 'a']++;
		pCount[p[i] - 'a']++;//用哈希表记录频数
	}
	if (sCount == pCount)
	{
		ans.emplace_back(0);//如果这两个一开始频数相等，返回索引0
	}
	for (int i = 0; i < slen - plen; i++)
	{
		sCount[s[i] - 'a']--;//滑动窗口从1开始滑！
		sCount[s[i + plen] - 'a']++;
		if (sCount == pCount)//判断此时窗口内的哈希是否与pcount相等
		{
			ans.emplace_back(i + 1);//若相等，尾插索引
		}
	}
	return ans;
    }
};
 


8：两数之和 

 

 思路解析：
 

我们这里采用了哈希表的方法，遍历一遍数组，用哈希表查看是否存在{target-nums[i]}元素
 

如果存在则返回{target-nums[i]}，若不存在则将插入{键：nums[i]，值：i}
 

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        unordered_maphashmap;
	for (int i = 0; i < nums.size(); i++)
	{
		if (hashmap.count(target - nums[i]))
		{
			return { hashmap[target - nums[i]],i };
		}
		hashmap[nums[i]] = i;
	}
	return { -1,-1 };
    }
};
 

补充：这里的键和值的关系非常巧妙，注意体会^ ^
 


9：四数相加|| 

 

 思路解析：
 

注释已经很清楚了^ ^
 

这道题是升级版的两数之和
 

class Solution {
public:
    int fourSumCount(vector& A, vector& B, vector& C, vector& D) {
        unordered_map map; //key:a+b的数值，value:a+b数值出现的次数
        // 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中
        for (int a : A) {
            for (int b : B) {
                umap[a + b]++;
            }
        }
        int count = 0; // 统计a+b+c+d = 0 出现的次数
        // 在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就把map中key对应的value也就是出现次数统计出来。
        for (int c : C) {
            for (int d : D) {
                if (map.count(0 - (c + d))) {
                    count += map[0 - (c + d)];
                }
            }
        }
        return count;
    }
};
 

补充：关于find和count，我更喜欢用count ^ ^ 二者都是查找哈希表
 

find是如果找不到就返回哈希表的尾地址
 

count是如果找到不到就返回0
 



					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5714854.html
赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
美式足球比分 美式足球比分 一级用户组
0 0
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表（0条）

保存