haai商城网站建设公司排名,汤臣倍健网站建设方案,夺宝网站开发,网页搜索优化seo #x1f4dd;个人主页#xff1a;Sherry的成长之路 #x1f3e0;学习社区#xff1a;Sherry的成长之路#xff08;个人社区#xff09; #x1f4d6;专栏链接#xff1a;练题 #x1f3af;长路漫漫浩浩#xff0c;万事皆有期待 文章目录 有效的字母异位词两个数… 个人主页Sherry的成长之路 学习社区Sherry的成长之路个人社区 专栏链接练题 长路漫漫浩浩万事皆有期待 文章目录 有效的字母异位词两个数组的交集快乐数两数之和总结 这篇博客主要是针对于哈希表的应用内容。哈希表主要分为三种哈希结构数组set和map。哈希表的应用主要在于解决一些需要查找某个元素是否出现过的问题需要快速查找类问题可以优先考虑使用哈希表它的查找时间为O(1)
通常情况我们在想要一个数据元素差别小且元素较少的集合时优先选择数组它的特点是比set和map存储空间上简单一些查找数据较快。而面对一些数据元素相差大且元素数据值较大或数值多可以考虑set无序时预先考虑unordered_set它是哈希结构实现的比红黑树实现的set和muliti_set更快。在需要做数据映射也就是同时存储一对有关联的元素时用map。
有效的字母异位词
242. 有效的字母异位词 - 力扣LeetCode
这是用数组做哈希的经典题目选用数组作为哈希结构的理由是该题判断两字符串的相同字母出现频率是否相同而小写字母一共只有26个数据少且连续所以选用数组。
解题思路为哈希表26个字母的位序依次对应于数组的0-25的下标且一开始均为0分别遍历两个字符串对于第一个字符串的每一个字母减去字符‘a’所得到的就是它当前在哈希表中对应的位置该字母每出现一次将该位置数值自增1。遍历第二个字符串就是自减1和前面处理是相同的方法处理完之后若哈希表内0-25位置的元素值均为0那么说明此时两字符串的字母出现频率相等如果不为0则直接返回false。
class Solution {
public:bool isAnagram(string s, string t) {int record[26]{0};for(int i0;is.size();i){record[s[i]-a]; // 并不需要记住字符a的ASCII只要求出一个相对数值就可以了}for(int j0;jt.size();j){record[t[j]-a]--;}for(int k0;k26;k){if(record[k]!0)// record数组如果有的元素不为零0说明字符串s和t 一定是谁多了字符或者谁少了字符。{return false;}}return true;// record数组所有元素都为零0说明字符串s和t是字母异位词}
};● 为什么遍历第二个字符串时只考虑碰到计数小于0的情况返回false而不考虑大于0的情况即s字符串出现了t字符串中没有的字符 最开始会判断两个字符串长度是否相等在两个字符串长度相同的情况下如果有大于0的情况一定对应地会出现其他字符小于0。
两个数组的交集
349. 两个数组的交集 - 力扣LeetCode
这道题也可以用数组来做哈希且运行效率很高但是由于此题在未更改题目描述和测试用例时是没有给定具体的数组长度的所以用set
具体思路为定义两个无序set由于判断两个数组交集返回的数据可以忽略数据的顺序所以可以使用无序set来提高运行速度。第一个set用来存储第一个数组的所有元素(由于set的特点数组中有重复元素并不会重复存放)存储完之后遍历第二个数组用find成员函数来查找该set里有没有和其相同的元素出现若有则放到第二个set里同样该set也是可以去重的最后返回的vector里的元素用第二个set来填充即可。
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {unordered_setint result_set; // 存放结果之所以用set是为了给结果集去重unordered_setint nums_set(nums1.begin(), nums1.end());for (int num : nums2) {// 发现nums2的元素 在nums_set里又出现过if (nums_set.find(num) ! nums_set.end()) {result_set.insert(num);}}return vectorint(result_set.begin(), result_set.end());}
};当然用数组来做哈希结构也是可以的这里只提供思路用数组哈希来存储nums1中每个数出现的频率再判断该哈希中的数是否在nums2里也出现过将值传进set内完成后return。
快乐数
202. 快乐数 - 力扣LeetCode
快乐数是求一个数的每一位求平方和最后经过这样的若干次变化后是否等于1。
解题思路的要点是用set来存储这些中间变化的平方和值那么为什么要这样做呢一个数只分为经过变化后平方和等于1循环和经过变化后平方和变成某些数字的死循环两种。所以用哈希存储变化中的数值至关重要。由于不知道该数要变换几次可能次数很多需要存储数据很多所以采用set来做哈希。
代码如下
class Solution {
public:// 取数值各个位上的单数之和int getSum(int n) {int sum 0;while (n) {sum (n % 10) * (n % 10);n / 10;}return sum;}bool isHappy(int n) {unordered_setint set;while(1) {int sum getSum(n);if (sum 1) {return true;}// 如果这个sum曾经出现过说明已经陷入了无限循环了立刻return falseif (set.find(sum) ! set.end()) {return false;} else {set.insert(sum);}n sum;}}
};当判断中取得的平方和在set中已经被取到则直接返回false。
另一种思路是leetcode官方给出的双指针方法很巧妙。
思路是创建slow和fast两个变量起初都等于数字n然后用平方和函数调用一下slow调用一次fast调用两次最终无论是什么结果两指针都会相遇即指向相同的数字如果是结果为1结束的那么1的平方和无论怎么加都是1如果是一些数的循环可以把它想象为一个环形链表在固定的一些数里循环总有slow和fast相等的情况。出循环时判断一个指针是否等于1就可以了。
class Solution {
public:bool isHappy(int n) {int slown;int fastn;do{slowget(slow);fastget(fast);fastget(fast);}while(slow!fast);return (slow1);}int get(int n){int sum0;while(n){sum(n%10)*(n%10);n/10;}return sum;}
};● sum重复出现就肯定不是快乐数为什么呢 因为只要重复出现一次就说明会无限循环就像之前链表那个环假设a1算完等于a2,a2算完等于a3a3算完等于a1那么下一次a1算完必定等于a2再下一次a2算完必定是a3形成了一个循环而这个循环中不可能有1因为1平方的结果永远是1,所以肯定有循环就肯定不是快乐数
两数之和
1. 两数之和 - 力扣LeetCode
这道题基本是每个刷leetcode的第一道题我最开始做这道题时候只写出了一个暴力解法而且还是看题解写的。暴力的思路简单一些就是两个循环第一个数和剩下的数相加第二个数和剩下的数相加以此类推。
class Solution {
public:vectorint twoSum(vectorint nums, int target) {vectorintresult;for(int i0;inums.size();i){for(int ji1;jnums.size();j){if(nums[i]nums[j]target){result.push_back(i);result.push_back(j);}} return result;}
};第二种方法就是使用哈希法中的map存储结构为什么用map呢思路是这样的我们将数组中已经遍历过的数用map存储下来由于我们需要返回的是数组下标而并非是哪两个数所组成的所以我们将map设置为key值为数组里的元素值而value设置为数组元素对应的下标。
我们每遍历一个数就要在map里面查找是否有可以与该数相加之后构成target的值如果有则直接返回没有将该数加入map遍历下一个数直到遍历完全若还没有返回则说明找不到目标数返回null。
class Solution {
public:vectorint twoSum(vectorint nums, int target) {std::unordered_map int,int map;for(int i 0; i nums.size(); i) {// 遍历当前元素并在map中寻找是否有匹配的keyauto iter map.find(target - nums[i]); if(iter ! map.end()) {return {iter-second, i};}// 如果没找到匹配对就把访问过的元素和下标加入到map中map.insert(pairint, int(nums[i], i)); }return {};}
};● 一般说数组作为哈希表 是利用值作为数组下标来达到快速定位 所以查找也能达到O(1)的复杂度 但是适用范围很有限
● 用unordered_map不是不能存储两个相同的key吗那如果数组里两个出现相同的两个元素都要存储会怎么样呢 注意它存入的方式它是在循环的过程中边检验边存的如果没有对应的数字就存入map如果有就计数这样不会遇到重复的
总结
今天的四道题涉及哈希的思想之前没有这么练习过收获不少。接下来我们继续进行算法练习·。希望我的文章和讲解能对大家的学习提供一些帮助。 当然本文仍有许多不足之处欢迎各位小伙伴们随时私信交流、批评指正我们下期见~
