【学习笔记】基础算法知识

文章目录冒泡排序二分查找STLalgorithm(常用算法函数)1. memset2. fill3. find4. to_string5. sort6. __gcd 最大公约数7. max min8. swap9. reverse(倒置)vectorpair[x,y]queue(队列)stack(栈)set(集合)map(映射)贪心算法dfs(深度优先搜索)剪枝bfs(广度优先搜索)dp类型一(遍历数组找最大值)冒泡排序intmain(){intarr[9]{0,1,4,2,7,5,3,9,6,};for(inti0;i8;i)//排序轮数元素个数-1{for(intj0;j9-i-1;j)//每轮对比次数 元素个数-排序论数-1{if(arr[j]arr[j1]){inttemparr[j];arr[j]arr[j1];arr[j1]temp;}}}}二分查找//数组{1 3 4 6 8 9 10}x4,二分查找x在第几位区间左闭右闭#includebits/stdc.husingnamespacestd;intn,x;inta[105];intmain(){cinn;for(inti0;in;i)cina[i];cinx;intl0,rn-1;intans-1;while(lr){intmid(lr)/2;if(a[mid]x)rmid-1;elseif(a[mid]x)lmid1;elseansmid;break;}if(ans-1)cout元素不在数组中\n;elsecourans\n;return0;}STLalgorithm(常用算法函数)1. memsetmemset 往往用于清零内存操作memset(a,0,sizeof(a)) :a都为0。初始化数组将数组所有元素清零。memset(mark,0,sizeof(mark)) 将mark中每一个元素初始化为-12. fill用于将指定范围内的元素全部赋值为给定的值。fill(arr,arr10,12) :arr到arr10都为123. findfind算法在vector容器中查找特定元素vectorintv{10,20,30};find(v.begin(),v.end(),20);//v.begin()指向vector第一个元素的迭代器//v.end()指向vector末尾最后一个元素之后//20要查找的目标值4. to_stringstring str to_string(x)将整数x转换为字符串5. sort使用标准库的sort函数对向量a进行升序排序vectorinta(n);sort(a.begin(),a.end());//参数a.begin()和a.end()分别表示排序的起始和结束迭代器即整个范围for循环输出sort(a1,a9,greater);//从大到小排序greater()排序比较函数指定降序排列。标准库中的greater是一个函数对象它会使sort函数按照从大到小的顺序排列元素。6. __gcd 最大公约数int k__gcd(n,m);int hn*m / k; //最小公倍数7. max minmax(a,b)返回 a 和 b 中的较大值。min(a,b)返回 a 和 b 中的较小值。8. swapswap(a,b) :交换a和b9. reverse(倒置)vectorintv{1,2,3,4,5}reverse(v.begin(),v.end());//v:5,4,3,2,1vectora.front() :返回第一个元素a.back() :返回最后一个数a.pop_back() :删除a向量最后一个元素a.push_back() :插入元素除了迭代器访问vector中的元素[]和at也可以voidtest01(){vectorintv;for(inti0;i10;i){v.push_back(i);}//通过[]和at也能访问vector中的数据for(inti0;iv.size();i){coutv[i] ;}coutendl;for(inti0;iv.size();i){coutv.at(i) ;}coutendl;coutv.front()endl;//返回容器中第一个元素coutv.back()endl;//返回容器中最后一个元素}运行结果0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 9pair[x,y]可以理解为x,y数学中的坐标表示tips: typedef pairint,int PII//该语句将标准库中的 pairint,int 类型重命名为 PII,后续可直接使用 PII 代替 pairint,int初始化pairfirst数据类型second数据类型 元素名pairstring,int p(hello,1); p.first; //第一个元素 p.second; //第二个元素queue(队列)queue q;q.size() :队列长度q.empty()检查队列Queue是否为空q.push() :尾插一个元素q.pop() :把队头弹出q.front()返回队列中第一个元素q.back() :返回队尾元素队列中没有clear元素清空的方法是重新初始化stack(栈)stack s;s.size()s.push() :向栈顶插入一个元素s.top() :返回栈顶元素s.pop() :弹出栈顶元素set(集合)类似于数学上的集合set不允许元素重复有重复会被忽略自动排序元素默认按升序排序set s; //string 集合s.size()s.empty()判断集合是否为空返回布尔值s.clear()清空集合中的所有元素s.begin()返回指向集合第一个元素的迭代器即最小元素因 set 默认升序s.end()返回指向集合末尾最后一个元素之后的迭代器常用于遍历时的终止条件s.insert() :向集合中插入一个字符串s.find() :查找字符串 key 是否存在s.count(key) :返回元素是否存在s.erase()删除元素s.lower_bound(x) :返回第一个x的元素的迭代器s.upper_bound(x) :返回第一个x的元素的迭代器map(映射)mapstring,inta;a[abc]1;//把字符串“abc映射为1贪心算法局部最优策略推出整体最优贪心策略往往是排序或是选最值dfs(深度优先搜索)数据大小只有几十的时候往往是暴力枚举。暴力枚举的方式也往往是dfsc语言版第一种inta[510];intmark[510];//标记是否被访问intans0;//记录符合条件的次数voiddfs(intcur){if(curk){//k个数已经选完进行输出等操作for(inti0;ik;i){printf(%d ,a[i]);}ans;return;}for(inti0;in;i){//遍历n个数并从中选择k个数if(!mark[i]){mark[i]1;//标记已被访问a[cur]i;//选定本数并加入数组bfs(cur1);mark[i]0;//释放标记为没被访问方便下次引用}}}第二种intans[N];//记录答案boolmark[N]//标记是否被访问intn;voiddfs(intu){//‘回头’的条件if(un){for(inti0;in;i){printf(%d ,ans[i]);//输入当前走过的路}return;}for(inti0;in;i){if(mark[i]false){//该节点没走过可以走mark[i]true;ans[u]i;dfs(u1);//该位确定后在该位的基础上选择下一位//复原mark[i]false;ans[u]0;}}}c版vectorinta;vectorintbook;voiddfs(intcur,intk,vectorintnums){if(curk){for(inti0;icur;i){printf(%d ,a[i]);}return;}for(inti0;in;i){if(book[nums[i]]0){a.push_back(nums[i]);book[nums[i]]1;dfs(cur1,n,nums);book[nums[i]]0;a.pop_back();}}}剪枝暴力枚举一部分后知道不是正确答案便没有继续向后枚举的必要。将这些情况挑选出来并舍弃掉的过程叫做剪枝。bfs(广度优先搜索)用于求最短路#includebits//stdc.husingnamespacestd;constintN110;typedefpairint,intPII;intmap[N][N],mark[N][N];//mark:标记当前位置是否走过记录从起点到该位置走了多远intdx[4]{-1,0,1,0},dy[4]{0,1,0,-1},n,m,ans;voidbfs(){memset(mark,-1,sizeof(mark));//mark中元素初始化为-1表示没来过queuePIIq;q.push({0,0});mark[0][0]0;while(!q.empty()){PII topq.front();//以队列中每一个元素为起点展开4个方向的搜索for(inti0;i4;i){intnextop.firstdx[i],neytop.seconddy[i];if(nex0nexnney0neymmark[nex][ney]-1map[nex][ney]0){mark[nex][ney]mark[top.first][top.second]1;q.push({nex,ney});}}q.pop();}coutmark[n-1][m-1];}intmain(){cinnm;for(inti0;in;i){for(intj0;jm;j){scanf(%d,map[i][j]);}}bfs();}dp核心把原问题分解为许多小的子问题类型一(遍历数组找最大值)intmain(){inta[8],b[8],m-1,n-1;for(inti1;i7;i){scanf(%d %d,a[i],b[i]);if(a[i]b[i]8a[i]b[i]m){ma[i]b[i];ni;}}if(m-1)printf(0);elseprintf(%d,n);return0;}