asp.net sql server网站建设 pdf,哈尔滨 高端网站建设,为什么网页总是打不开,dedecms5.7环保科技公司网站模板前言
本次博客将要写一写#xff0c;哈希表的一些使用
哈希表主要是一个映射#xff0c;比如数组就是一个哈希表
是一个整型对应另一个整型#xff0c;介绍的哈希表还是要以写题目为例
第一题
242. 有效的字母异位词 - 力扣#xff08;LeetCode#xff09;
直接来看…前言
本次博客将要写一写哈希表的一些使用
哈希表主要是一个映射比如数组就是一个哈希表
是一个整型对应另一个整型介绍的哈希表还是要以写题目为例
第一题
242. 有效的字母异位词 - 力扣LeetCode
直接来看这个题目吧
给定两个字符串 s 和 t 编写一个函数来判断 t 是否是 s 的字母异位词。
注意若 s 和 t 中每个字符出现的次数都相同则称 s 和 t 互为字母异位词
提示:
1 s.length, t.length 5 * 10的4次方s 和 t 仅包含小写字母
思路
暴力思路
我们可以使用两个for循环一个一个判断从第一个字符到最后一个字符与第二个字符串每一个元素比对其次还要进行去重操作因为在比对过程中可能会出现重复的字符
比如 aabcd abcdf这两个字符串如果一一比对第二个字符会被配对两次而按照代码逻辑
会把他两当成配对成功所以还需要一个状态数组来进行去重暴力思路也有细节的
看代码吧
#includeiostream
#includestring.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()
{setintst1;setintst2;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) {setintst;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);elseprintf(no);return 0;}
总结
今天就写这三题OK祝大家开心
