当前位置: 代码网 > it编程>编程语言>C/C++ > 哈希表练习题

哈希表练习题

2024年07月31日 C/C++ 我要评论
本次博客将要写一写,哈希表的一些使用哈希表主要是一个映射,比如数组就是一个哈希表是一个整型对应另一个整型,介绍的哈希表还是要以写题目为例今天就写这三题,OK,祝大家开心。

前言

本次博客将要写一写,哈希表的一些使用

哈希表主要是一个映射,比如数组就是一个哈希表

是一个整型对应另一个整型,介绍的哈希表还是要以写题目为例

第一题

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 <= 1000
  • 0 <= 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,祝大家开心

(0)

相关文章:

版权声明:本文内容由互联网用户贡献,该文观点仅代表作者本人。本站仅提供信息存储服务,不拥有所有权,不承担相关法律责任。 如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 2386932994@qq.com 举报,一经查实将立刻删除。

发表评论

验证码:
Copyright © 2017-2025  代码网 保留所有权利. 粤ICP备2024248653号
站长QQ:2386932994 | 联系邮箱:2386932994@qq.com