数据结构与算法学习日志7

提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档文章目录前言力扣69:x的平方根力扣34:在排序数组中查找元素的第一个和最后一个位置哈希表:哈希表使用常见哈希表:● 数组● set 集合包含在set头文件中● map(映射)算法一本通1117使用数组算法一本通1117使用set算法一本通1117使用map力扣242:有效的字母异位词力扣349:两个数组的交集力扣202:快乐数总结前言提示这里可以添加本文要记录的大概内容各位晚上好啊,笔者今天真是不知道写什么了,最近没有学太多的知识点,.主要还是在刷题,所以今天干脆就把我一天学到的内容以及做的题全部分享给大家,希望能带给大家一点收获提示以下是本篇文章正文内容下面案例可供参考力扣69:x的平方根classSolution{public:intmySqrt(intx){intl0;intrx;intmid0;while(lr){mid(r-l)/2l;if((longlong)mid*midx)returnmid;elseif((longlong)mid*midx)lmid1;elsermid-1;}returnr;}};力扣34:在排序数组中查找元素的第一个和最后一个位置classSolution{public://找左边第一个比目标值小的元素(找左边界)intsearchLeft(vectorintnums,inttarget){intl0;intrnums.size()-1;intmid0;while(lr){mid(r-l)/2l;if(nums[mid]target)lmid1;elsermid-1;}returnl;}//找右边第一个比目标值大的元素(找右边界)intsearchRight(vectorintnums,inttarget){intl0;intrnums.size()-1;intmid0;while(lr){mid(r-l)/2l;if(nums[mid]target)rmid-1;elselmid1;}returnr;}vectorintsearchRange(vectorintnums,inttarget){intleftsearchLeft(nums,target);intrightsearchRight(nums,target);//只要leftright就说明target一定不存在 无论数组是空还是单元素//如果数组为空 right-1;left0 没有leftright这种情况 leftright时无法退出循环if(leftright)return{-1,-1};elsereturn{left,right};}};哈希表:通过哈希函数将键映射到数组的特定位置,支持O(1)时间复杂度的随机访问。最简单满足哈希原理的容器是数组。哈希表使用通常用于查找某个元素是否在某个集合中出现过常见哈希表:● 数组元素访问 O(1) ,遍历O(n),插入删除O(n)● set 集合包含在头文件中unordered_set:元素访问O(1),插入删除O(1)#includeiostream#includesetusingnamespacestd;intmain(){//创建set容器 set会自动排序(从小到大)以及去重setintst;//插入元素st.insert(1);st.insert(5);st.insert(3);for(autoi:st){couti ;}//find查找 如果没找到会返回尾部迭代器if(st.find(0)st.end())cout没找到;elsecout0;return0;}● map(映射)unordered_map:元素访问O(1),插入删除O(1)#includeiostream#includemapusingnamespacestd;intmain(){//创建一个map容器mapint,intmp;//通过key值进行排序(从小到大)和去重//插入元素mp[1];//value自动初始化为0 key-value:1-0mp[2]1;//key2 value1//通过insert进行插入mp.insert({3,2});coutmp[3]endl;//c中有键值对类型pairpairint,intpair{4,3};mp.insert(pair);//键值对访问coutpair.first,;//keycoutpair.secondendl;//valuecoutmp[4]endl;//通过增强for循环遍历for(autoi:mp){couti.first-i.second ;}//修改valuemp[1]1;return0;}算法一本通1117使用数组#includeiostreamusingnamespacestd;constintN2e410;intarr[N];intmain(){//核心思路:将数组的下标与值对应 下标与值相同 若值不为零则说明重复 不放入数组intn;cinn;for(inti0;in;i){intx;cinx;if(arr[x]0){coutx ;arr[x]x;}}return0;算法一本通1117使用setsetintst;intn;cinn;for(inti0;in;i){intx;cinx;if(st.find(x)st.end()){st.insert(x);coutx ;}}算法一本通1117使用mapmapint,intmp;intn;cinn;for(inti0;in;i){intx;cinx;if(mp[x]0){coutx ;mp[x]x;}}力扣242:有效的字母异位词classSolution{public:boolisAnagram(string s,string t){if(s.size()!t.size())returnfalse;//键用来记录字母 值用来记录字母的个数unordered_mapchar,intmp;for(autoi:s){//对每个字母进行计数mp[i];}for(autoi:t){//如果这个字母的个数已经为0 说明t中的字母多了if(mp[i]0){returnfalse;}else{//t中每找到一个字母对应的字母个数就减一mp[i]--;}}for(autoi:mp){//如果是字母异位词那么此时所有的字母个数都应该为0if(i.second!0)returnfalse;}returntrue;}};力扣349:两个数组的交集classSolution{public:vectorintintersection(vectorintnums1,vectorintnums2){mapint,intmp;vectorintvec;for(autoi:nums1){//记录在nums1是否存在 存在为1mp[i]1;}for(autoi:nums2){//mp[i]1说明在nums1和nums2中都存在if(mp[i]1){vec.push_back(i);//置为0 防止重复mp[i]0;}}returnvec;}};力扣202:快乐数classSolution{public:boolisHappy(intn){mapint,intmp;while(n!1){intcnt0;while(n){cnt(n%10)*(n%10);nn/10;}ncnt;if(mp[cnt]1)returnfalse;mp[cnt]1;}returntrue;}};总结以上就是我今天所学到的全部内容了,最后,还是感谢各位的阅读,我们明天见!