前言之前就有刷代码随想录但奈何总是三天打鱼两天晒网而且刷的也很囫囵吞枣于是乎决定参加代码随想录训练营准备精刷一遍希望自己能坚持下去结营后自己的算法水平能更上一个level冲ingleetcode242.有效的字母异位词题目链接leetcode242.有效的字母异位词思路本题采用数组作为哈希表的方式核心是如何把字符映射到数组也就是哈希表的索引下标上。具体可以定义一个数组叫做record用来上记录字符串s里字符出现的次数再遍历 字符串s的时候只需要将 s[i] - ‘a’ 所在的元素做1 操作即可同样在遍历字符串t的时候对t中出现的字符映射哈希表索引上的数值再做-1的操作// 同时处理两个字符串for(inti0;is.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(inti0;is.size();i){//并不需要记住字符a的ASCII只需要求出一个相对数值就可以了record[s[i]-a];record[t[i]-a]--;}for(inti0;i26;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:vectorintintersection(vectorintnums1,vectorintnums2){unordered_setintset1(nums1.begin(),nums1.end());unordered_setintresult_set;// 存放结果之所以用set是为了给结果集去重for(intnum:nums2){//如果nums2中的元素在set1中存在加入结果集if(set1.find(num)!set1.end()){result_set.insert(num);}}returnvectorint(result_set.begin(),result_set.end());}};leetcode第202题. 快乐数题目链接leetcode第202题. 快乐数思路快乐数定义为对于一个正整数每一次将该数替换为它每个位置上的数字的平方和然后重复这个过程直到这个数变为 1也可能是 无限循环 但始终变不到 1。如果 可以变为 1那么这个数就是快乐数。所以如果一个数把他拆开后仅由1和0构成那就一定是快乐数。在累加求和的过程中如果出现了重复那么就会一直循环下去这也是解题的关键。所以涉及到某一元素在集合中判断是否重复就可以使用unordered_set代码classSolution{public:// 取数值各个位上的单数之和intgetSum(intn){intsum0;while(n0){intdigitn%10;//获取当前数字的个位数sumdigit*digit;n/10;//整数除法去掉个位数}returnsum;}boolisHappy(intn){unordered_setintset;while(1){intsumgetSum(n);if(sum1){returntrue;}//如果这个sum曾经出现过说明已经陷入无限循环立刻return falseif(set.find(sum)!set.end()){returnfalse;}else{set.insert(sum);}nsum;}}};leetcode1. 两数之和题目链接leetcode1. 两数之和思路为什么会想到用哈希表题目要求我们找出数组中两个符合要求的元素那么当我们需要查询一个元素是否出现过或者一个元素是否在集合里的时候就要第一时间想到哈希法。哈希表为什么用map题目要求返回符合要求的两个元素的下标所以我们不能是仅仅找到该元素还需要保存该元素的下标需要使用 key value结构来存放。本题map是用来存什么的用来存放遍历过的元素和该元素对应的下标map中的key和value用来存什么的key存放元素value存放其下标为什么不使用数组或set作为哈希结构使用数组和set来做哈希法的局限数组的大小是受限制的而且如果元素很少而哈希值太大会造成内存空间的浪费。set是一个集合里面放的元素只能是一个key而两数之和这道题目不仅要判断y是否存在而且还要记录y的下标位置因为要返回x 和 y的下标。所以set 也不能用。代码classSolution{public:vectorinttwoSum(vectorintnums,inttarget){unordered_mapint,inthashmap;//key数字value下标 用法hashmap[key]valuefor(inti0;inums.size();i){intcomplementtarget-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_mapint,int hashmap; //key数字value下标 用法hashmap[key]value