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

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

提示：这里可以添加本文要记录的大概内容：
各位晚上好啊,笔者今天真是不知道写什么了,最近没有学太多的知识点,.主要还是在刷题,所以今天干脆就把我一天学到的内容以及做的题全部分享给大家,希望能带给大家一点收获

提示：以下是本篇文章正文内容，下面案例可供参考

力扣69:x的平方根

classSolution{public:intmySqrt(intx){intl=0;intr=x;intmid=0;while(l<=r){mid=(r-l)/2+l;if((longlong)mid*mid==x)returnmid;elseif((longlong)mid*mid<x)l=mid+1;elser=mid-1;}returnr;}};

力扣34:在排序数组中查找元素的第一个和最后一个位置

classSolution{public://找左边第一个比目标值小的元素(找左边界)intsearchLeft(vector<int>&nums,inttarget){intl=0;intr=nums.size()-1;intmid=0;while(l<=r){mid=(r-l)/2+l;if(nums[mid]<target)l=mid+1;elser=mid-1;}returnl;}//找右边第一个比目标值大的元素(找右边界)intsearchRight(vector<int>&nums,inttarget){intl=0;intr=nums.size()-1;intmid=0;while(l<=r){mid=(r-l)/2+l;if(nums[mid]>target)r=mid-1;elsel=mid+1;}returnr;}vector<int>searchRange(vector<int>&nums,inttarget){intleft=searchLeft(nums,target);intright=searchRight(nums,target);//只要left>right就说明target一定不存在 无论数组是空还是单元素//如果数组为空 right=-1;left=0 没有left=right这种情况 left=right时无法退出循环if(left>right)return{-1,-1};elsereturn{left,right};}};

哈希表:

通过哈希函数将键映射到数组的特定位置,支持O(1)时间复杂度的随机访问。

最简单满足哈希原理的容器是数组。

哈希表使用：

通常用于查找某个元素是否在某个集合中出现过

常见哈希表:

● 数组

元素访问 O(1) ,遍历O(n),插入删除O(n)

● set （集合）包含在头文件中

unordered_set:元素访问O(1),插入删除O(1)

#include<iostream>#include<set>usingnamespacestd;intmain(){//创建set容器 set会自动排序(从小到大)以及去重set<int>st;//插入元素st.insert(1);st.insert(5);st.insert(3);for(autoi:st){cout<<i<<' ';}//find查找 如果没找到会返回尾部迭代器if(st.find(0)==st.end())cout<<"没找到";elsecout<<0;return0;}

● map(映射)

unordered_map:元素访问O(1),插入删除O(1)

#include<iostream>#include<map>usingnamespacestd;intmain(){//创建一个map容器map<int,int>mp;//通过key值进行排序(从小到大)和去重//插入元素mp[1];//value自动初始化为0 key-value:1-0mp[2]=1;//key=2 value=1//通过insert进行插入mp.insert({3,2});cout<<mp[3]<<endl;//c++中有键值对类型pairpair<int,int>pair={4,3};mp.insert(pair);//键值对访问cout<<pair.first<<",";//keycout<<pair.second<<endl;//valuecout<<mp[4]<<endl;//通过增强for循环遍历for(autoi:mp){cout<<i.first<<"-"<<i.second<<' ';}//修改valuemp[1]=1;return0;}

算法一本通1117：使用数组

#include<iostream>usingnamespacestd;constintN=2e4+10;intarr[N];intmain(){//核心思路:将数组的下标与值对应 下标与值相同 若值不为零则说明重复 不放入数组intn;cin>>n;for(inti=0;i<n;i++){intx;cin>>x;if(arr[x]==0){cout<<x<<" ";arr[x]=x;}}return0;

算法一本通1117：使用set

set<int>st;intn;cin>>n;for(inti=0;i<n;i++){intx;cin>>x;if(st.find(x)==st.end()){st.insert(x);cout<<x<<' ';}}

算法一本通1117：使用map

map<int,int>mp;intn;cin>>n;for(inti=0;i<n;i++){intx;cin>>x;if(mp[x]==0){cout<<x<<" ";mp[x]=x;}}

力扣242:有效的字母异位词

classSolution{public:boolisAnagram(string s,string t){if(s.size()!=t.size())returnfalse;//键用来记录字母 值用来记录字母的个数unordered_map<char,int>mp;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:vector<int>intersection(vector<int>&nums1,vector<int>&nums2){map<int,int>mp;vector<int>vec;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){map<int,int>mp;while(n!=1){intcnt=0;while(n){cnt+=(n%10)*(n%10);n=n/10;}n=cnt;if(mp[cnt]==1)returnfalse;mp[cnt]=1;}returntrue;}};

总结

以上就是我今天所学到的全部内容了,最后,还是感谢各位的阅读,我们明天见!