OJ刷题知识点

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中已经有该元素了，该元素就是环的入口元素。