前言
本次博客将要写一写，哈希表的一些使用
哈希表主要是一个映射，比如数组就是一个哈希表
是一个整型对应另一个整型，介绍的哈希表还是要以写题目为例
第一题
242. 有效的字母异位词 - 力扣（LeetCode）
直接来看这个题目吧
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词
提示:
1 <= s.length, t.length <= 5 * 10的4次方s和t仅包含小写字母
思路
暴力思路
我们可以使用两个for循环一个一个判断，从第一个字符到最后一个字符与第二个字符串每一个元素比对，其次还要进行去重操作，因为在比对过程中可能会出现重复的字符
比如 aabcd abcdf这两个字符串如果一一比对第二个字符会被配对两次，而按照代码逻辑
会把他两当成配对成功，所以还需要一个状态数组，来进行去重，暴力思路也有细节的
看代码吧！
#include<iostream>
#include<string.h>
using namespace std;
int state[50010] = {0};
int main()
{
//定义两个字符串
char a[] = "bacdeffffassadawd";
char b[] = "ssadawdbacdeffffa";
int sizea = strlen(a);
int sizeb = strlen(b);
int flag = 0;
//如果大小不等，直接排除
if (sizea != sizeb)
{
printf("不是\n");
return 0;
}
for (int i = 0; i < sizea; i++)
{
for (int j = 0; j < sizeb; j++)
{
flag = 0;
if (a[i] == b[j]&&!state[j])
{
state[j] = 1;
flag = 1;
break;
}
}
if (flag == 0) { printf("不是\n");break;}
}
if (flag == 1)
printf("找到了\n");
return 0;
}再看看测试结果
改个数据
ok暴力可以解决问题
不够代价可不小
首先额外开了一个int类型大小为5万的数组，其次时间复杂度为o(n^2)
不太好的一个代码，但是思路是无罪的
哈希表思路
思路
题目中，只有26个字母唉而且只有小写字母
我们可以用0~25分别映射a~z这个字母，完全可以采用数组这个结构
第一个字符串中 字母出现一次，让对应的下标的数组的值加一
第二个字符串 字母出现一次，让对应的下标的数组的值减一
最后遍历一遍数组
如果有不等于0的值就判断为不是
如果全部通过，就判断为是
看代码吧
int main()
{
//这里随便写的一个
char a[] = "abcdefghijilmndjalwjdjakd";
char b[] = "lmndjalwjdjakdabcdefghiji";
//初始化为0(非完全初始化默认的元素就是为0)
int arr[26] = {0};
int asize = strlen(a);
int bsize = strlen(b);
//如果长度不一，一定不是
if (asize != bsize)
{
printf("不是\n");
return 0;
}
for (int i = 0; i < asize; i++)
{
arr[a[i] - 'a']++;
arr[b[i] - 'a']--;
}
for (int i = 0; i < 26; i++)
{
if (arr[i] != 0)
{
printf("不是\n");
return 0;
}
}
printf("是\n");
return 0;
}OK，最终结果也不太想，演示了，没问题的
看下一题
第二题
349. 两个数组的交集 - 力扣（LeetCode）
给定两个数组 nums1 和 nums2 ，返回 它们的
交集
输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[9,4] 解释：[4,9] 也是可通过的
提示：
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 1000
暴力思路
其实就是，通过两个for循环，依次遍历即可，相等的记录在另一个数组中
额，有点不想敲了 哈哈哈，来吧
注意 两个数组的大小都在1000以内，所以 结果数组大小 在1010就行
他们的值是在0~1000 其实short类型就够了,当然这里仍然需要我们自己去去重
毕竟他们的值实在0~1000，我们可以再来一个1000大小的数组来判断这个值出现了没有
如果他们的值很大很大暴力法是不可行的，好吧这里的状态数组本身就是一个哈希表
它的含义是state[i] i为0~1000的范围 如果该值已经出现state[i]==1
没有出现就默认为0 这样大家就懂了吧
看代码喽
short result[1010];
short state[1000];
int main()
{
short a[] = { 1,2,3,4,5,6,7,8,9,10};
short b[] = { 2,2,3,4,5,5,6,6,6,6,6};
size_t sizea = sizeof(a) / sizeof(a[0]);
size_t sizeb = sizeof(b) / sizeof(b[0]);
size_t sizer = 0;
for (int i = 0; i < sizea; i++)
{
for (int j = 0; j < sizeb; j++)
{
if (a[i] == b[j]&&!state[a[i]])
{
result[sizer++] = a[i];
state[a[i]] = 1;
break;
}
}
}
for (int i = 0; i < sizer; i++)
{
printf("%d ", result[i]);
}
return 0;
}看结果
没有错，但是这个代码o(n)的空间
o(n^2)的时间实在不好，那么看优化的吧
这里用set
不过这里的set容器是c++代码
也好理解
最普通的set可以自动去重，而且会自动排序
不要觉得功能多，实际上时间复杂度也高
这里就简单介绍set就好,这里是STL库里的内容
思路就是，把数组中元素放到第一个set容器里面
然后，再构建一个set，如果可以在第一个set里找到与第二个数组相同的元素，就纪录在第二
个set中
ok,看代码
int main()
{
set<int>st1;
set<int>st2;
short a[] = { 1,2,3,4,5,6,7,8,9,10};
short b[] = { 2,2,3,4,5,5,6,6,6,6,6};
size_t sizea = sizeof(a) / sizeof(a[0]);
size_t sizeb = sizeof(b) / sizeof(b[0]);
for (int i = 0; i < sizea; i++)
{
st1.insert(a[i]);
}
for (int i = 0; i < sizeb; i++)
{
//这里是一个迭代器
if (st1.find(b[i]) != st1.end())
{
st2.insert(b[i]);
}
}
//遍历一遍
for (auto& ele : st2)
{
cout << ele<<" ";
}
return 0;
}第三题
202. 快乐数 - 力扣（LeetCode）
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19 输出：true 解释： 1^2 + 9^2 = 82 8^2 + 2^2 = 68 6^2 + 8^2 = 100 1^2 + 0^2 + 0^2 = 1
示例 2：
输入：n = 2 输出：false
提示：
1 <= n <= 2^31-1
思路
首先看到这个题目先得分析数据
n的大小为2的31次方-1就是一个int类型的最大值
但是在计算过程中会不会越界呢？这个大小为20亿左右
是一个十位数那么假设每一位都是9
9^2*10也才810所以int类型可以
其次再看题意
他是要出现一个1才为快乐数呀，这个很好判断对吧
那么怎么判断它不是快乐数，也就是它一直循环
既然是循环，那么肯定是一个圈就是在运算的过程中，会转一圈从而出现之前出现过的数
对吧这个时候，哈希表的判断是否存在于一个集合中就起作用了
set
它的增删查改时间复杂度为logn
如果使用暴力的话，它的时间复杂为n，算了这里不写暴力了
看代码吧
应该也挺好懂的
bool isHappy(int n) {
set<int>st;
int sum = 0;
int c = n;
st.insert(n);
while (1)
{
sum = 0;
while (c)
{
sum += pow(c % 10, 2);
c /= 10;
}
c = sum;
if (c == 1)
return true;
for (auto& ele : st)
{
if (ele == c)
return false;
}
st.insert(c);
}
}
int main()
{
if (isHappy(50))
printf("yes");
else
printf("no");
return 0;
}
总结
今天就写这三题，OK，祝大家开心
