前言
最近用 python 刷了些算法题不过总觉得不太顺手, 很多题目总是会超时, 想了想还是用 C++ 来刷吧. 由于已经很久没有敲过 C++ 的代码, 所以需要对一些常用的知识进行回顾. 对于刷算法题目来说, STL 应该算是比较常用的一个工具了, 故优先对此进行回顾. 文章中的主要内容都是来源于郭炜老师在中国大学慕课上的公开课 ( 程序设计与算法(三)C++ 面向对象程序设计) 以及 C++ Primer Plus 这本书. 另外, 在文章的最后我也会用一道 LeetCode 的题目来简单运用一下今天的知识.
一, vector 的简单介绍
标准库类型 vector 表示对象的集合. 其中所有对象的类型都相同. 类似数组, 集合中的每个对象同样有索引, 用于随机访问对象. 因为 vector 容纳着其他对象, 所以其亦被称之为 "容器"(更准确的说是 "顺序容器").
1.1 定义和初始化 vector 对象
- vector<int> v1(10,1); //vector<T> v1(n, val) v1 包含了 n 个重复的元素, 每个元素的值都是 val
- //vector<int> v2 = {1,2,3,4,5}; //vector<T> v2={a,b,c,d...} v2 包含了列出的所有元素
- int a[] = {1,2,3,4,5};
- vector<int> v3(a,a+5); // 将数组 a 的全部元素用来初始化此 vector
1.2 vector 对象的常用操作
- int len = v1.size(); // 获取 v1 的元素个数
- cout<<"v1 的长度为:"<<len<<endl;
- for(int i = 0; i<5 ; i++){
- v3.push_back(i+6); // 在 v3 的末尾添加新的元素
- }
- v1.insert(v1.begin(),2); // 在 v1 最开始之处插入一个值为 2 的元素, 此时 v1 为 21111111111
- v3.insert(v3.end(),v1.begin(),v1.begin()+5); // 此段代码的作用是将 v1 中的一段元素放到 v3 中来
- //v3.end()代表放置的起始位置, 后面两个关键字是
- // 片段在 v1 中的起始以及终止位置 , 此时 v3 结果为 1234567891011111
1.3 vector 的遍历
- void printVector(vector<int> vec){ // 一个常规遍历 vector 的函数
- vector<int>::iterator i; // 迭代器类型的变量的声明
- for(i=vec.begin();i != vec.end(); ++i){
- if(i == vec.end()-1) // 在最后一个元素时进行换行
- cout<<*i<<endl;
- else
- cout<<*i;
- }
- }
事实上, 存在更简便的遍历方式. 但是由于我现在所用的编译器不支持 C++11, 在此仅仅给出代码.
首先, 你要先给出一个 print()函数.
- void print(int n)
- {
- cout<<n<<endl;
- }
其次, 应用 for_each 函数进行遍历即可, 代码如下.
- for_each(v1.begin(),v1.end(),print);// 用 for_each 进行遍历
- for_each(v1.begin(),v1.end(),print);
以上的代码链接
二, 解决一道与此相关的算法题
image
下方为解决代码
- class Solution {
- public:
- vector<int> twoSum(vector<int>& nums, int target) {
- vector<int> result;
- int flag=0;
- for(auto i = nums.begin(); i!= nums.end(); i++){
- for(auto j = nums.begin(); j!= nums.end(); j++){
- if(target - *i == *j && i!= j){
- result.push_back(i-nums.begin());
- result.push_back(j-nums.begin());
- flag = 1;
- break;
- }
- else{}
- }
- if(flag == 1)
- {
- break;
- }
- }
- return result;
- }
- };
可以看出, 这里是采用了两层循环, 即为最简单的蛮力法. 虽然编译通过, 但是效率是极其低下的, 仅仅超越了 15% 的用户. 不过今天只是拿这个例子来将刚才学到的知识联系一下, 以后, 我们再考虑对此算法进行优化, 这里就暂且用这个笨方法做着吧.
来源: http://www.jianshu.com/p/244ffb5d1de9