首页 / 算法 / 各大算法专题-STL篇
各大算法专题-STL篇
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了各大算法专题-STL篇,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3045字,纯文字阅读大概需要5分钟。
内容图文
![各大算法专题-STL篇](/upload/InfoBanner/zyjiaocheng/1325/480f594e529b4c93a9da33801cf9a08b.jpg)
这篇文章着重记录c++中STL的用法。主要粗略的介绍其用法,以知识点的形式呈现其功能,不会深入源码分析其工作原理。
排序和检索.
sort(a,a+n),对a[0]往后的n个元素(包括a[0])进行排序,默认的这种形式由小到大的排序.其属于<algorithm>这个头文件中,它可以给任何对象进行排序,但是需要写自定义函数cmp.完整形式为sort(a,a+n,cmp).
low_bound(a , a+n ,x)-a得到数组a[]从a[0]往后n个长度中,第一个大于或者等于x的下标index.这里的下标,是指数组a[0],a[1],a[2],…,a[n-1]中的下标。
Q1(uva 10474):
现在有N个大理石每颗石头上写了一个非负整数。首先把各数从小到大排序,然后进行Q次质询,每次质询给出一个负整数,需要你找到这个整数在第几颗石头上(排序后)。
具体代码:
#include<cstdio> #include<algorithm> usingnamespace std; constint maxn = 10000; int main() { int n , q , a[maxn] , kase = 1; while(scanf("%d%d",&n , &q) != EOF) { if(n == 0) break; printf("CASE# %d:\n",kase++); for(int i = 0;i < n;i++) scanf("%d",&a[i]); sort(a , a + n); while(q--) { int x; scanf("%d",&x); int index; index = lower_bound(a , a + n , x) - a; if(a[index] == x) printf("%d found at %d\n",x , index + 1); else printf("%d not found\n",x); } } }
集合set:集合是stl中一个容器,它储存字符串的时候。默认按照字典序排列。
stringstream(str):这个对象的用法,是以流的方式,将一个字符串s(形如s1 s2 s3)分别表示成三个子串s1,s2,s3的形式。
Q2:给出一个文本,找出所有不同的单词(连续的字母序列),按字典序从小到大输出,单词不区分大小写。
分析:这个问题就是为了简单的呈现set和stringstream的用法。首先我们利用特殊的输入技巧,将文本的被空格分隔的连续串拿下来,然后基于stringstream的用法再将某个连续串中非字母的成分变为空格,再把真正的连续字母序列拿到,将其存在容器set里面,由于set容器对字符串默认为由小到大的字典序排列,我们只需要再将容器中的内容顺序输出即可。
参考代码如下:
#include<cstdio> #include<iostream> #include<string> #include<set> #include<sstream> usingnamespace std; set<string> dict; int main() { string s , buf; while(cin>>s) { for(int i = 0;i < s.length();i++) if(isalpha(s[i])) s[i] = tolower(s[i]); else s[i] = ‘‘; stringstream ss(s); while(ss >> buf) dict.insert(buf); } for(set<string>::iterator it = dict.begin();it != dict.end();++it) cout <<*it<<"\n"; return0; }
映射map:
map能够建立两个数组元素之间的一一对应关系,例如我们建立星期几的英文单词和数字1~7的映射关系,就可以定义map<string , int> a, a[“Monday”] = 1.
Q3(uva 156):
给出一个文本,找到文本中的一类单词,这一类单词满足该文本中其余任何单词,通过重组字母序列,都无法得到这个单词,找到所有这类的单词之后,按照字典序输出。
分析:这个看似和字符串有关的复杂模拟题目,和诸多stl中的用法结合起来,就会显得一场简洁.
考虑如何满足那条性质,假设我们用一个vector<string> s来储存原始的文本,遍历每个单词,我们将得到的单词按照字母大小顺序进行重排,得到新的序列r,将其放入映射中,我们领用map<string , int> cnt记录重排后的序列r出现的次数,遍历完文本单词之后,我们再遍历储存原始文本的向量s,如果当前的单词s[i],其重排之后的序列r,满足cnt[r] = 1,说明这个字符串是满足要求的字符串,将其放入一个新的字符串向量ans中,枚举完成后,将ans按照字典序排序,然后顺序输出即可。
参考代码如下:
#include<cstdio> #include<iostream> //#include<cctype> #include<vector> #include<map> #include<algorithm> usingnamespace std; map<string , int> cnt; vector<string> words; string repr(conststring &s) { string ans = s; for(int i = 0;i < ans.length();i++) ans[i] = tolower(ans[i]); sort(ans.begin() , ans.end()); return ans; } int main() { int n = 0; string s; while(cin >> s) { if(s[0] == ‘#‘) break; words.push_back(s); string r = repr(s); if(!cnt.count(r)) cnt[r] = 0; cnt[r]++; } vector<string> ans; for(int i = 0;i < words.size();i++) if(cnt[repr(words[i])] == 1) ans.push_back(words[i]); sort(ans.begin() , ans.end()); for(int i = 0;i < ans.size();i++) cout<<ans[i]<<"\n"; }
原文:http://www.cnblogs.com/rhythmic/p/5983239.html
内容总结
以上是互联网集市为您收集整理的各大算法专题-STL篇全部内容,希望文章能够帮你解决各大算法专题-STL篇所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。