ACM算法题以及答案.doc

ACM算法题 使用C+实现在做这些题目之前必须了解vector（数组），list（链表）、deque（双端队列）、queue（队列）, priority_queue（优先队列）Stack（栈）、set（集合）、map（键值对），mutilset、mutilmap。stack堆栈，没有迭代器，支持push()方法。后进先出,top()返回最顶端的元素,pop()剔除最顶元素deque双端队列，支持迭代器，有push_back()方法，跟vector差不多，比vector多了个pop_front,push_front方法queue队列，先进先出，不支持迭代器，有push()方法，pop()剔除第一个元素,front()返回第一个元素vector使用vector是C+标准模板库中的部分内容，它是一个多功能的，能够操作多种数据结构和算法的模板类和函数库。vector之所以被认为是一个容器，是因为它能够像容器一样存放各种类型的对象，简单地说vector是一个能够存放任意类型的动态数组，能够增加和压缩数据。为了可以使用vector，必须在你的头文件中包含下面的代码：#include vector属于std命名域的，因此需要通过命名限定，如下完成你的代码：using std:vector; vector v;或者连在一起，使用全名：std:vector v;建议使用全局的命名域方式：using namespace std;1.vector的声明 vector c; 创建一个空的vector vector c1(c2); 创建一个vector c1，并用c2去初始化c1 vector c(n) ; 创建一个含有n个ElemType类型数据的vector; vector c(n,elem); 创建一个含有n个ElemType类型数据的vector,并全部初始化为elem; c.vector(); 销毁所有数据,释放资源;2.vector容器中常用的函数。(c为一个容器对象） c.push_back(elem); 在容器最后位置添加一个元素elem c.pop_back(); 删除容器最后位置处的元素 c.at(index); 返回指定index位置处的元素 c.begin(); 返回指向容器最开始位置数据的指针 c.end(); 返回指向容器最后一个数据单元的指针+1 c.front(); 返回容器最开始单元数据的引用 c.back(); 返回容器最后一个数据的引用 c.max_size(); 返回容器的最大容量 c.size(); 返回当前容器中实际存放元素的个数 c.capacity(); 同c.size() c.resize(); 重新设置vector的容量 c.reserve(); 同c.resize() c.erase(p); 删除指针p指向位置的数据，返回下指向下一个数据位置的指针（迭代器） c.erase(begin,end) 删除begin,end区间的数据，返回指向下一个数据位置的指针（迭代器） c.clear(); 清除所有数据 c.rbegin(); 将vector反转后的开始指针返回(其实就是原来的end-1) c.rend(); 将vector反转后的结束指针返回(其实就是原来的begin-1) c.empty(); 判断容器是否为空，若为空返回true，否则返回false c1.swap(c2); 交换两个容器中的数据 c.insert(p,elem); 在指针p指向的位置插入数据elem,返回指向elem位置的指针 c.insert(p,n,elem); 在位置p插入n个elem数据，无返回值 c.insert(p,begin,end) 在位置p插入在区间begin,end)的数据，无返回值3.vector中的操作 operator 如： c.i; 同at()函数的作用相同，即取容器中的数据。list使用：STL中的list就是一双向链表，可高效地进行插入删除元素。list不支持随机访问。所以没有 at(pos)和operator。list对象list1, list2分别有元素list1(1,2,3),list2(4,5,6)。list:iterator it;list成员说明constructor构造函数destructor析构函数operator=赋值重载运算符assign分配值front返回第一个元素的引用back返回最后一元素的引用begin返回第一个元素的指针(iterator)end返回最后一个元素的下一位置的指针rbegin返回链表最后一元素的后向指针(reverse_iterator or const)rend返回链表第一元素的下一位置的后向指针push_back增加一元素到链表尾push_front增加一元素到链表头pop_backpop_back()删除链表尾的一个元素pop_front删除链表头的一元素clear删除所有元素erase删除一个元素或一个区域的元素(两个重载)remove删除链表中匹配值的元素(匹配元素全部删除)remove_if删除条件满足的元素(遍历一次链表)，参数为自定义的回调函数empty判断是否链表为空max_size返回链表最大可能长度size返回链表中元素个数resize重新定义链表长度(两重载函数)reverse反转链表sort对链表排序，默认升序merge合并两个有序链表并使之有序splice对两个链表进行结合(三个重载函数)结合后第二个链表清空insert在指定位置插入一个或多个元素(三个重载函数)swap交换两个链表(两个重载)unique删除相邻重复元素Deque 双端队列使用：容器deque和vector非常相似，操作函数基本一致。它采用动态数组来管理元素，提供随机存取，可以在头尾两端进行快速安插和删除元素操作。特别要注意，除了头尾两端，在任何地方安插与删除元素，都将导致指向deque元素的任何pointers references iterators 失效。 包括的头文件为：#include using namespace std; 声明一个deque时，一般需要前缀std: ，如std:deque c;因为类型deque是一个定义在namespace std内的template 。构造函数：deque c ; /产生一个空的deque,其中没有任何元素deque c1(c2); /产生另一个同型deque的副本（所有元素都被拷贝）deque c(n) ; /产生一个大小为n的dequedeque c(n , elem) ; /产生一个大小为n的deque， /每个元素值都是elem。dequer c(begin,end); /产生一个deque，以区间begin ; end /做为元素初值析构函数：c. deque() ;销毁所有元素，并释放内存。 非变动性操作c.size(); /返回当前的元素数量c.empty(); /判断大小是否为零。等同于c.size() = 0,但可能更快c.max_size(); /可容纳元素的最大数量c.at(idx) ; /返回索引为idx所标示的元素。如果idx越界，抛出out_of_rangecidx ; /返回索引idx所标示的元素。不进行范围检查c.front() ; /返回第一个元素,不检查元素是否存在c.back(); /返回最后一个元素c.begin(); /返回一个随机迭代器，指向第一个元素c.end(); /返回一个随机迭代器，指向最后元素的下一位置 变动性操作：c1 = c2 ; /将c2的所有元素赋值给c1;c.assign(n , elem); /将n个elem副本赋值给cc.assing(beg , end); /将区间beg;end中的元素赋值给c;c.push_back(elem); /在尾部添加元素elemc.pop_back() ; /移除最后一个元素（但不回传）c.push_front() ; /在头部添加元素elemc.pop_front() ; /移除头部一个元素（但不回传）c.erase(pos) ; /移除pos位置上的元素，返回一元素位置 /如 c.erase( c.begin() + 5) /移除第五个元素c.insert(pos , elem); /在pos位置插入一个元素elem，并返回新元素的位置c.insert(pos , n , elem); /在pos位置插入n个元素elem，无返回值c.insert(pos , beg , end);c.resize(num); /将容器大小改为num。可更大或更小。c.resize(num , elem); /将容器大小改为num，新增元素都为 elemc.clear(); /移除所有元素，将容器清空PS:Deque和Vector是智能容器，删除或者增加元素时，其他位置与元素会进行相应的移动。queue的使用queue 模板类的定义在头文件中。与stack 模板类很相似，queue 模板类也需要两个模板参数，一个是元素类型，一个容器类型，元素类型是必要的，容器类型是可选的，默认为deque 类型。定义queue 对象的示例代码如下：queue q1;queue q2;queue 的基本操作有：入队，如例：q.push(x); 将x 接到队列的末端。出队，如例：q.pop(); 弹出队列的第一个元素，注意，并不会返回被弹出元素的值。访问队首元素，如例：q.front()，即最早被压入队列的元素。访问队尾元素，如例：q.back()，即最后被压入队列的元素。判断队列空，如例：q.empty()，当队列空时，返回true。访问队列中的元素个数，如例：q.size()priority_queue的使用在头文件中，还定义了另一个非常有用的模板类priority_queue(优先队列）。优先队列与队列的差别在于优先队列不是按照入队的顺序出队，而是按照队列中元素的优先权顺序出队（默认为大者优先，也可以通过指定算子来指定自己的优先顺序）。priority_queue 模板类有三个模板参数，第一个是元素类型，第二个容器类型，第三个是比较算子。其中后两个都可以省略，默认容器为vector，默认算子为less，即小的往前排，大的往后排（出队时序列尾的元素出队）。定义priority_queue 对象的示例代码如下：priority_queue q1;priority_queue pair q2; / 注意在两个尖括号之间一定要留空格。priority_queueint, vector, greater q3; / 定义小的先出队priority_queue 的基本操作与queue 相同。初学者在使用priority_queue 时，最困难的可能就是如何定义比较算子了。如果是基本数据类型，或已定义了比较运算符的类，可以直接用STL 的less 算子和greater算子默认为使用less 算子，即小的往前排，大的先出队。如果要定义自己的比较算子，方法有多种，这里介绍其中的一种：重载比较运算符。优先队列试图将两个元素x 和y 代入比较运算符(对less 算子，调用xy)，若结果为真，则x 排在y 前面，y 将先于x 出队，反之，则将y 排在x 前面，x 将先出队。看下面这个简单的示例：#include #include using namespace std;class Tpublic:int x, y, z;T(int a, int b, int c):x(a), y(b), z(c);bool operator (const T &t1, const T &t2)return t1.z t2.z; / 按照z 的顺序来决定t1 和t2 的顺序main()priority_queue q;q.push(T(4,4,3);q.push(T(2,2,5);q.push(T(1,5,4);q.push(T(3,3,6);while (!q.empty()T t = q.top(); q.pop();cout t.x t.y t.z endl;return 1;输出结果为(注意是按照z 的顺序从大到小出队的)：3 3 62 2 51 5 44 4 3Statck使用statck栈中的数据是先进后出的（First In Last Out, FILO）。栈只有一个出口，允许新增元素（只能在栈顶上增加）、移出元素（只能移出栈顶元素）、取得栈顶元素等操作。set和multiset的功能和所有关联式容器类似，通常使用平衡二叉树完成。事实上，set和multiset通常以红黑树实作而成。自动排序的优点是使得搜寻元素时具有良好的性能，具有对数时间复杂度。但是造成的一个缺点就是：不能直接改变元素值。因为这样会打乱原有的顺序。改变元素值的方法是：先删除旧元素，再插入新元素。存取元素只能通过迭代器，从迭代器的角度看，元素值是常数。三、操作函数构造函数和析构函数set的形式可以是：有两种方式可以定义排序准则：1、以template参数定义：cppview plaincopyprint?1. setint,greatercol1;此时，排序准则就是型别的一部分。型别系统确保只有排序准则相同的容器才能被合并。程序实例：cppview plaincopyprint?1. #include2. #include3. usingnamespacestd;4. 5. intmain()6. 7. sets1;8. setint,greaters2;9. 10. for(inti=1;i6;+i)11. 12. s1.insert(i);13. s2.insert(i);14. 15. if(s1=s2)16. coutc1equalsc2!endl;17. else18. coutc1notequalsc2!endl;19. 程序运行会报错。但是如果把s1的排序准则也指定为greater便运行成功。2、以构造函数参数定义。这种情况下，同一个型别可以运用不同的排序准则，而排序准则的初始值或状态也可以不同。如果执行期才获得排序准则，而且需要用到不同的排序准则，这种方式可以派上用场。程序实例：cppview plaincopyprint?1. #include2. #includeprint.hpp3. #include4. usingnamespacestd;5. 6. template7. classRuntimeCmp8. public:9. enumcmp_modenormal,reverse;10. private:11. cmp_modemode;12. public:13. RuntimeCmp(cmp_modem=normal):mode(m)14. 15. booloperator()(constT&t1,constT&t2)16. 17. returnmode=normal?t1t2:t2t1;18. 19. 20. booloperator=(constRuntimeCmp&rc)21. 22. returnmode=rc.mode;23. 24. ;25. 26. typedefsetint,RuntimeCmpIntSet;27. 28. voidfill(IntSet&set);29. 30. intmain()31. 32. IntSetset1;33. fill(set1);34. PRINT_ELEMENTS(set1,set1:);35. 36. RuntimeCmpreverse_order(RuntimeCmp:reverse);37. 38. IntSetset2(reverse_order);39. fill(set2);40. PRINT_ELEMENTS(set2,set2:);41. 42. set1=set2;/assignment:OK43. set1.insert(3);44. PRINT_ELEMENTS(set1,set1:);45. 46. if(set1.value_comp()=set2.value_comp()/value_compReturnsthecomparisonobjectassociatedwiththecontainer47. coutset1andset2havethesamesortingcriterionendl;48. else49. coutset1andset2havethedifferentsortingcriterionendl;50. 51. 52. voidfill(IntSet&set)53. 54. set.insert(4);55. set.insert(7);56. set.insert(5);57. set.insert(1);58. set.insert(6);59. set.insert(2);60. set.insert(5);61. 运行结果：虽然set1和set2的而比较准则本身不同，但是型别相同，所以可以进行赋值操作。非变动性操作注意：元素比较操作只能用于型别相同的容器。特殊的搜寻函数赋值赋值操作两端的容器必须具有相同的型别，但是比较准则本身可以不同，但是其型别必须相同。如果比较准则的不同，准则本身也会被赋值或交换。迭代器相关函数元素的插入和删除注意：插入函数的返回值不完全相同。set提供的插入函数：cppview plaincopyprint?1. pairinsert(constvalue_type&elem);2. iteratorinsert(iteratorpos_hint,constvalue_type&elem);multiset提供的插入函数：cppview plaincopyprint?1. iteratorinsert(constvalue_type&elem);2. iteratorinsert(iteratorpos_hint,constvalue_type&elem);返回值型别不同的原因是set不允许元素重复，而multiset允许。当插入的元素在set中已经包含有同样值的元素时，插入就会失败。所以set的返回值型别是由pair组织起来的两个值：第一个元素返回新元素的位置，或返回现存的同值元素的位置。第二个元素表示插入是否成功。set的第二个insert函数，如果插入失败，就只返回重复元素的位置！但是，所有拥有位置提示参数的插入函数的返回值型别是相同的。这样就确保了至少有了一个通用型的插入函数，在各种容器中有共通接口。注意：还有一个返回值不同的情况是：作用于序列式容器和关联式容器的erase()函数：序列式容器的erase()函数：cppview plaincopyprint?1. iteratorerase(iteratorpos);2. iteratorerase(iteratorbeg,iteratorend);关联式容器的erase()函数：cppview plaincopyprint?1. voiderase(iteratorpos);2. voiderase(iteratorbeg,iteratorend);这完全是为了性能的考虑。因为关联式容器都是由二叉树实现，搜寻某元素并返回后继元素可能很费时。五、set应用示例：cppview plaincopyprint?1. #include2. #include3. usingnamespacestd;4. 5. intmain()6. 7. typedefsetint,greaterIntSet;8. IntSets1;9. 10. s1.insert(4);11. s1.insert(3);12. s1.insert(5);13. s1.insert(1);14. s1.insert(6);15. s1.insert(2);16. s1.insert(5);17. /theinsertedelementthathasthesamevaluewithaelementexistedisemitted18. 19. copy(s1.begin(),s1.end(),ostream_iterator(cout,);20. coutendlendl;21. 22. pairstatus=s1.insert(4);23. if(status.second)24. cout4isinsertedaselement25. distance(s1.begin(),status.first)+1endl;26. else27. cout4alreadyexistsins1endl;28. copy(s1.begin(),s1.end(),ostream_iterator(cout,);29. coutendlendl;30. 31. sets2(s1.begin(),s1.end();/defaultsortcriterionisless32. copy(s2.begin(),s2.end(),ostream_iterator(cout,);33. coutendlendl;34. 上述程序最后新产生一个set：s2，默认排序准则是less。以s1的元素作为初值。注意：s1和s2有不同的排序准则，所以他们的型别不同，不能直接进行相互赋值或比较。运行结果：Map是c+的一个标准容器，她提供了很好一对一的关系，在一些程序中建立一个map可以起到事半功倍的效果，总结了一些map基本简单实用的操作！1. map最基本的构造函数； mapmapstring; mapmapint; mapmapstring; mapmapchar; mapmapchar; mapmapint；2. map添加数据； map maplive; 1.maplive.insert(pair(102,aclive); 2.maplive.insert(map:value_type(321,hai); 3, maplive112=April;/map中最简单最常用的插入添加！3，map中元素的查找： find()函数返回一个迭代器指向键值为key的元素，如果没找到就返回指向map尾部的迭代器。 map:iterator l_it; l_it=maplive.find(112); if(l_it=maplive.end() coutwe do not find 112endl; else coutwo find 112endl;4,map中元素的删除： 如果删除112； map:iterator l_it; l_it=maplive.find(112); if(l_it=maplive.end() coutwe do not find 112=给定元素的第一个位置 max_size() 返回可以容纳的最大元素个数 rbegin() 返回一个指向map尾部的逆向迭代器 rend() 返回一个指向map头部的逆向迭代器 size() 返回map中元素的个数 swap() 交换两个map upper_bound() 返回键值给定元素的第一个位置 value_comp() 返回比较元素value的函数反转数相加string str1, str2;while (true)cin str1 str2;string temp1(str1.rbegin(),str1.rend();string temp2(str2.rbegin(), str2.rend();int num1 = atoi(temp1.c_str();int num2 = atoi(temp2.c_str();int sum = num1 + num2;char buffer100 = 0 ;_itoa_s(sum,buffer,100,10);string strtemp = buffer;reverse(strtemp.begin(), strtemp.end();cout atoi(strtemp.c_str() endl;提示：尽量多用#include 中给出的函数，例如：reverse，sort，count，accumulate，find_first_of,fill，unique，count_if，merge，remove。等函数的使用List（双端队列）：没有上面的部分操作，所以list有自己的操作List的成员函数：merge、remove、remove_if、sort、splice迭代器：插入迭代器、io迭代器和方向迭代器#include 中包含pair类型。 #include 提供的find函数注意size_t 为 unsigned intunique的使用:1、使用unique进行重新排阵顺序，把与数据前面重复的数据放在最后面。2、在使用erase从unique返回值处开始到结尾的数据进行删除。DNA排序#include #include #include #include #include using namespace std;bool comp(const string &s1, const string &s2)int m = 0, n = 0;for (size_t i = 0; i s1.size(); i+)for (size_t j = 0; j s1j)m+;for (size_t i = 0; i s2.size(); i+)for (size_t j = 0; j s2j)n+;return m != n ? m n : m n;void main()ifstream cin(1.txt);vector v;string str;int n, a, b;cin n;for (size_t i = 0; i a b;for (size_t j = 0; j str;v.push_back(str);sort(v.begin(), v.end(), comp);for (size_t k = 0; k v.size(); k+)cout vk str,!cin.eof()cout str endl;/*表达式计算问题*/stack stk;cout 请输入带（）的计算字符串 str,!cin.eof()if (!stk.empty() & str = )stack stk1;while (stk.top() != ()stk1.push(stk.top();stk.pop();stk1.push(stk.top();stk.pop();while (!stk1.empty()cout stk1.top();stk1.pop();cout strendl;stk.push(OK);elsestk.push(str);幂指数计算long Power(int index, int num)int sum = 1;if (num 0)cout 输入有误 endl;else if (num = 0)return 1;elsefor (int i = 0; i num; i+)sum *= index;return sum;对输入的字符串进行除重和按字符串的长度排序（长度相同的、按字典序排序）bool isShort(const string &s1, const string &s2)return s1.length() 4;string make_plural(size_t size, const string &word, const string &ending)return (size = 1) ? word : word + ending;ifstream fin(1.txt);if (!fin.is_open()cout 打开文件失败 endl;string str;vector v;/读取文件内容while (fin str)v.push_back(str);/排序sort(v.begin(), v.end();/删除文件中重复的单词vector:iterator end_unique = unique(v.begin(), v.end();v.erase(end_unique, v.end();/稳定排序stable_sort(v.begin(), v.end(), isShort);/统计出不小于4的单词数目vector:size_type wc = count_if(v.begin(), v.end(), GT4);/输出大于4的单词的数目cout wc make_plural(wc, word, s) 4 characters or longer endl;for (vector:iterator itor = v.begin(); itor != v.end();itor+)cout *itor ;cout endl;ifstream fin(1.txt);if (!fin.is_open()cout 打开文件失败 endl;string str;list v;/读取文件内容while (fin str)v.push_back(str);/对输入的字符串排序v.sort();/进行除重v.unique();/输出for (list:iterator itor = v.begin(); itor != v.end();itor+)cout *itor ;cout endl;/*火星加法20进制的加法*/ifstream fin(1.txt);if (!fin.is_open()cout 打开文件失败 str1str2)vector v;v.clear();int a, b, c, flag = 0;reverse(str1.begin(), str1.end();reverse(str2.begin(), str2.end