C++ | vector
vector:向量（Vector）是一个封装了动态大小数组的顺序容器（Sequence Container）。跟任意其它类型容器一样，它能够存放各种类型的对象。可以简单的认为，向量是一个能够存放任意类型的动态数组。
构造函数
- vector():创建一个空vector
- vector(int nSize):创建一个vector,元素个数为nSize
- vector(begin,end):复制[begin,end)区间内另一个数组的元素到vector中
增加函数
- void push_back(const T& x):向量尾部增加一个元素X
删除函数
- void pop_back():删除向量中最后一个元素
- void clear():清空向量中所有元素
遍历函数
- reference at(int pos):返回pos位置元素的引用
- reference front():返回首元素的引用
- reference back():返回尾元素的引用
- iterator begin():返回向量头指针，指向第一个元素
- iterator end():返回向量尾指针，指向向量最后一个元素的下一个位置
题目描述：输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
利用递归
class Solution {
public:
vector<int> value;
vector<int> printListFromTailToHead(ListNode* head) {
ListNode *p=NULL;
p=head;
if(p!=NULL){
if(p->next!=NULL){
printListFromTailToHead(p->next);
}
value.push_back(p->val);
}
return value;
}
};
栈的简单运用
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> value;
ListNode *p=NULL;
p=head;
stack<int> stk;
while(p!=NULL){
stk.push(p->val);
p=p->next;
}
while(!stk.empty()){
value.push_back(stk.top());
stk.pop();
}
return value;
}
};
利用数组翻转
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> value;
ListNode *p=NULL;
p=head;
while(p!=NULL){
value.push_back(p->val);
p=p->next;
}
//reverse(value.begin(),value.end()); //C++自带的翻转函数
int temp=0;
int i=0,j=value.size()-1;
while(i<j){
temp=value[i]; //也可以用swap函数，swap(value[i],value[j]);
value[i]=value[j];
value[j]=temp;
i++;
j--;
}
return value;
}
};
C++ | map
map是STL的一个关联容器，它提供一对一的hash。第一个可以称为关键字(key)，每个关键字只能在map中出现一次；第二个可能称为该关键字的值(value)。map內部的实现自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能。在map内部所有的数据都是有序的
构造函数
- map <string，int> mapstring; map <int，string> mapint;
- map <sring，char> mapstring; map <char，string> mapchar;
- map <char，int> mapchar; map <int，char> mapint；
添加数据
map <int，string> maplive;
- maplive.insert（pair <int，string>（102，“ aclive”）））;
- maplive.insert（map <int，string> :: value_type（321，“ hai”））;
- maplive [112] =“ April”; // map中最简单最常用的插入添加！
查找元素
若只是查找该元素是否存在，可以使用函数count(k)，该函数返回的是k出现的次数；若是想取得key对应的值，可以使用函数find(k)，该函数返回的是指向该元素的迭代器。
删除元素
- m.erase(k) //k为元素返回的是删除的元素的个数
- m.erase(p) //删除的是迭代器p指向的元素，返回的是void
- m.erase(b, e) //删除的是迭代器b和迭代器e范围内的元素，返回void
map的基本操作函数:
C++ maps是一种关联式容器,包含"键-值"对
begin() 返回指向map头部的迭代器
clear() 删除所有元素
count() 返回指定元素出现的次数
empty() 如果map为空则返回true
end() 返回指向map末尾的迭代器
equal_range() 返回特殊条目的迭代器对
erase() 删除一个元素
find() 查找一个元素
get_allocator() 返回map的配置器
insert() 插入元素
key_comp() 返回比较元素key的函数
lower_bound() 返回键值>=给定元素的第一个位置
max_size() 返回可以容纳的最大元素个数
rbegin() 返回一个指向map尾部的逆向迭代器
rend() 返回一个指向map头部的逆向迭代器
size() 返回map中元素的个数
swap() 交换两个map
upper_bound() 返回键值>给定元素的第一个位置
value_comp() 返回比较元素value的函数
题目描述：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
#include<map>
#include <utility>
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
ListNode* p=pHead;
map<ListNode*,char>loop;
while(p!=NULL)
{
loop[p]=p->val;
if(loop[p->next]!=NULL)
return p->next;
p=p->next;
}
return NULL;
}
};
C++ | set容器
set是STL中一种标准关联容器。它底层使用平衡的搜索树——红黑树实现。set，顾名思义是“集合”的意思，在set中元素都是唯一的，而且默认情况下会对元素自动进行升序排列，要注意的是，它不会重复插入相同键值的元素，而采取忽略处理。
创建set集合对象
#include<iostream>
#include<set>
using namespace std;
set<int>s
元素的插入
s.insert(1);
s.insert(2);
s.insert(3);
元素的遍历
set<int>s;
int main()
{
s.insert(1);
s.insert(2);
s.insert(3);
set<int>::iterator it;
for(it=s.begin();it!=s.end();it++)
{
cout<<*it<<" ";
}
cout<<endl;
}
元素的查找
set<int>s;
int main()
{
s.insert(1);
s.insert(2);
s.insert(3);
if(s.find(3)!=s.end())
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
if(s.count(3))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
find()查找元素返回给定值的迭代器，如果没找到则返回 end()。
count() 用来查找 set 中某个某个键值出现的次数。这个函数在 set 并不是很实用，
因为一个键值在 set 只可能出现 0 或 1 次，这样就变成了判断某一键值是否在 set 出现过了。
删除元素，容器中元素的个数，清空容器，判空
set<int>s;
int main()
{
s.insert(1);
s.insert(2);
s.insert(3);
s.erase(3);//删除元素
cout<<s.size()<<endl;//容器中元素的个数
s.clear();//清空容器
if(s.empty())//判空，集合为空，返回true(真）
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
排序
//非结构元素
#include<iostream>
#include<set>
using namespace std;
set<int,greater<int> >s;//注意空格
//set<int,less<int> >s;用不到set默认从小到大排序
int main()
{
s.insert(1);
s.insert(3);
s.insert(5);
s.insert(2);
s.insert(4);
set<int>::iterator it=s.begin();
while(it!=s.end())
{
cout<<*it<<" ";
it++;
}
cout<<endl;
}
题目描述：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
set<ListNode*> s;
ListNode* node = pHead;
while(node!=NULL){
if(s.insert(node).second)
node = node->next;
else
return node;
}
return node;
}
};
tips：这里用到了STL中的set，set有一个特性就是不能插入相同元素，这样只需遍历原List一次就可以判断出有没有环，还有环的入口地址。s.insert(node).second这里在插入的同时也判断了插入是否成功，如果不成功表明set中已经有该元素了，该元素就是环的入口元素。
