代码随想录一刷记录Day5——leetcode 242.有效的字母异位词 349. 两个数组的交集 202. 快乐数 1. 两数之和
前言
之前就有刷代码随想录，但奈何总是三天打鱼两天晒网，而且刷的也很囫囵吞枣，于是乎决定参加代码随想录训练营，准备精刷一遍，希望自己能坚持下去，结营后自己的算法水平能更上一个level，冲ing！
leetcode242.有效的字母异位词
题目链接leetcode242.有效的字母异位词
思路
本题采用数组作为哈希表的方式，核心是如何把字符映射到数组也就是哈希表的索引下标上。
具体可以定义一个数组叫做record用来上记录字符串s里字符出现的次数
再遍历 字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可
同样在遍历字符串t的时候，对t中出现的字符映射哈希表索引上的数值再做-1的操作
// 同时处理两个字符串for(inti=0;i<s.size();i++){//并不需要记住字符a的ASCII，只需要求出一个相对数值就可以了record[s[i]-'a']++;record[t[i]-'a']--;}最后判断record数组中是否有不为0的元素。
此外，开头可增加优化判断：如果两个字符串长度不一致，那么一定不是异位词，就无需进行后续遍历，节省时间
代码
classSolution{public:boolisAnagram(string s,string t){if(s.length()!=t.length()){returnfalse;}// 因为只有小写字母，使用大小为26的数组intrecord[26]={0};// 同时处理两个字符串for(inti=0;i<s.size();i++){//并不需要记住字符a的ASCII，只需要求出一个相对数值就可以了record[s[i]-'a']++;record[t[i]-'a']--;}for(inti=0;i<26;i++){if(record[i]!=0){//record数组如果有不为0的元素，说明字串s和t一定时谁多了字符或谁少了字符returnfalse;}}//record数组所有元素都为0，说明字符串s和t是字母异位词returntrue;}};leetcode349. 两个数组的交集
题目链接leetcode349. 两个数组的交集
思路
- 什么时候用数组作哈希什么时候用set作哈希？
使用数组来做哈希的题目，是因为题目都限制了数值的大小。而这道题目没在这里插入代码片有限制数值的大小，就无法使用数组来做哈希表了。而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费 - 本体使用unordered_set作为哈希表，std::set和std::multiset底层实现都是红黑树，std::unordered_set的底层实现是哈希表，
使用unordered_set读写效率是最高的，并不需要对数据进行排序，而且还不要让数据重复，所以选择unordered_set。 - 具体思路是先将其中一个数组中的元素放入unordered_set，以达到去重，然后去和另一个数组比较，如果有相同元素就存放到一个新的unordered_set中。
代码
classSolution{public:vector<int>intersection(vector<int>&nums1,vector<int>&nums2){unordered_set<int>set1(nums1.begin(),nums1.end());unordered_set<int>result_set;// 存放结果，之所以用set是为了给结果集去重for(intnum:nums2){//如果nums2中的元素在set1中存在，加入结果集if(set1.find(num)!=set1.end()){result_set.insert(num);}}returnvector<int>(result_set.begin(),result_set.end());}};leetcode第202题. 快乐数
题目链接leetcode第202题. 快乐数
思路
快乐数定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。
所以如果一个数，把他拆开后仅由1和0构成，那就一定是快乐数。在累加求和的过程中，如果出现了重复，那么就会一直循环下去，这也是解题的关键。所以涉及到某一元素在集合中判断是否重复，就可以使用unordered_set
代码
classSolution{public:// 取数值各个位上的单数之和intgetSum(intn){intsum=0;while(n>0){intdigit=n%10;//获取当前数字的个位数sum+=digit*digit;n/=10;//整数除法，去掉个位数}returnsum;}boolisHappy(intn){unordered_set<int>set;while(1){intsum=getSum(n);if(sum==1){returntrue;}//如果这个sum曾经出现过，说明已经陷入无限循环，立刻return falseif(set.find(sum)!=set.end()){returnfalse;}else{set.insert(sum);}n=sum;}}};leetcode1. 两数之和
题目链接leetcode1. 两数之和
思路
- 为什么会想到用哈希表
题目要求我们找出数组中两个符合要求的元素，那么当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。 - 哈希表为什么用map
题目要求返回符合要求的两个元素的下标，所以我们不能是仅仅找到该元素，还需要保存该元素的下标，需要使用 key value结构来存放。 - 本题map是用来存什么的
用来存放遍历过的元素和该元素对应的下标 - map中的key和value用来存什么的
key存放元素，value存放其下标 - 为什么不使用数组或set作为哈希结构
使用数组和set来做哈希法的局限：
数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。
代码
classSolution{public:vector<int>twoSum(vector<int>&nums,inttarget){unordered_map<int,int>hashmap;//key：数字，value：下标 用法：hashmap[key]=valuefor(inti=0;i<nums.size();i++){intcomplement=target-nums[i];//查找complement是否已在hashmap中if(hashmap.find(complement)!=hashmap.end()){return{hashmap[complement],i};}//将当前元素放入hashmaphashmap[nums[i]]=i;}return{};}};总结
本周开启了关于哈希表这一数据结构的相关算法题目。
主要是掌握何时用数组/set/map来构建哈希表！
补充两个C++语法知识：
- if (set1.find(num) != set1.end() ) 是 C++ 中检查元素是否存在于集合/映射中的标准写法：
find()返回迭代器。如果找到了返回指向该元素的迭代器，如果没找到，返回set.end()
end()返回一个指向集合末尾的迭代器，它不指向任何实际元素，代表"结束位置"或"不存在"的标志
!= set1.end()
比较 find() 返回的迭代器是否不等于末尾迭代器如果不等于，说明找到了元素，如果等于，说明没找到。 - hashmap的使用方法
unordered_map<int,int> hashmap; //key：数字，value：下标 用法：hashmap[key]=value