算法训练day6:哈希基础、LeetCode242.349.202.两数之和
哈希基础:
- 一般哈希表都是用来快速判断一个元素是否出现集合里。 以空间换时间
- 使用集合来解决哈希问题的时候,优先unordered_set,因为它的查询和增删效率是最优的,如果需要集合是有序,那么就用set,如果要求不仅有序还要有重复数据的话,那么就用multiset。
242.有效的字母异位词
题目:
题解
-
第一想法:将字母映射到长度为27的数组中,第一个串字符重复出现则相应位置自增;第二个串字符重复出现则相应位自减;最后遍历数组,如果均为0,则两串为异位词。
-
class Solution { public: bool isAnagram(string s, string t) { int Hash[26] = {0}; for (int i = 0; i < s.size(); i++) { Hash[s[i] - 'a']++; } for (int i = 0; i < t.size(); i++) { Hash[t[i] - 'a']--; } for (int i = 0; i < 26; i++) { if (Hash[i] != 0) return false; } return true; } };
-
完美,简直和卡哥代码一模一样。
349.两个数组的交集
题目
题解
-
第一想法:
- 将第一个数组出线的数字在对应哈希表中做标记,
- 将第二个数字中值和哈希表对照,重复出现则更改成新的标记,
- 将哈希表中有新标记的数字输出;
-
第二想法:
- 数字跨度大,使用数组作为哈希表有极大的空间浪费
- 考虑使用set
-
class Solution { public: vector<int> intersection(vector<int> &nums1, vector<int> &nums2) { unordered_set<int> result_set; unordered_set<int> nums_set(nums1.begin(), nums1.end()); //利用unordered_setd的特性去重 for (int num : nums2) { if (nums_set.find(num) != nums_set.end()) //将nums2中的元素在去重后的表中寻找,如果找到就存到结果中 { result_set.insert(num); } } return vector<int>(result_set.begin(), result_set.end()); } };202.快乐数
202.快乐数
题目
题解
-
第一想法:没有想到怎么使用哈希表。
-
第二想法:
- 题目关键:每位数平方和重复则循环不是快乐数;
- 判断是否重复出现可以用哈希表。
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_set<int> set; while (1) { int sum = getsum(n); if (sum == 1) { return 1; } if (set.find(sum) != set.end()) { return false; } else { set.insert(sum); } n = sum; } } };