programming review (c++): (1)vector, linked list, stack, queue, map, string, bit manipulation

编程题常用知识点的review。

most important:　　想好（1）详尽步骤（2）边界特例，再开始写代码。

I.vector

#include <iostream>

//0.头文件。 特性:  连续存储，动态双倍分配增长

#include <vector>

#include <algorithm> //relevant

using namespace std;

bool comp(int a,int b){

    return a>b;

}

int main(){

    //1.创建与初始化

    vector<int> v1(,);

    vector<int> v2(v1);     //也可拷贝初始化 vector<int>  v2=v1;

    vector<vector<int>> ivec(,v1);    //二维vector

    //2.返回数量与判断空

    if(v1.empty())

        cout<<"it's empty";

    auto n=v1.size();

    //3.修改元素与遍历元素

    for(int i=;i<n;i++)

        v1[i]=;

    vector<int>::iterator it;   //迭代器

    for(it=v1.begin();it!=v1.end();it++)

        *it=;

    //4.插入与删除元素

    v1.push_back();

    v1.pop_back();

    v1.insert(v1.begin()+, );     //把9插入到第3个元素后面

    v1.erase(v1.begin()+);         //把第3个元素后面的那个元素删掉

    //5.相关函数 reverse sort

    reverse(v1.begin(),v1.end());

    sort(v1.begin(),v1.end(),comp);    //等价于  sort(v1.rbegin(),v1.rend());

}

II.linked list

#include <iostream>

#include <vector>

//0.struct

struct ListNode {

    int val;

    ListNode *next;

    ListNode(int x) : val(x), next(NULL) {}   //定义了节点的初始化方法

};

using namespace std;

int main(){

    vector<int> ivec{,,,,,};

    //1.创建与初始化

    ListNode *head=new ListNode();     //申请一个新节点,注意 head= new ListNode(0)与 head= ListNode(0)的区别

    ListNode *p=head,*q;

    for(auto i:ivec){           //此乃尾插法，还有头插法，根据情况选择合适的,注意现在有头节点

        q=new ListNode(i);

        p->next=q;

        p=q;

    }

    //2.遍历元素、插入删除元素

    p=head;

    while(p->next!=NULL){

        if(p->next->val==){

            q=new ListNode();

            q->next=p->next->next;

            p->next=q;

        }

    }

    /* 3.经典操作：   (1) 原地reverse——头插法和尾插法的运用；

                    (2) 判断cycle——快慢指针；

                    (3) 找中间节点、找间隔节点——快慢指针；

     }

    */

}

III.stack && queue

#include <iostream>

#include <vector>

//0.头文件   经常以vector模拟

#include <stack>

#include <queue>

using namespace std;

int main(){

    //1.stack  创建与初始化,基本操作  push pop top empty size

    stack<int> myStack;

    myStack.push();

    myStack.push();

    cout<<myStack.top()<<endl;

    myStack.pop();

    cout<<myStack.size()<<myStack.empty()<<endl;

    //2.queue   创建与初始化,基本操作  push pop front back empty size

    queue<int> myQueue;

    myQueue.push();

    myQueue.push();

    cout<<myQueue.front()<<endl;

    cout<<myQueue.back()<<endl;

    myQueue.pop();

    cout<<myQueue.size()<<myQueue.empty()<<endl;

}

IV.map

#include <iostream>

//0.头文件   优点：快速访问/空间换时间/桶的思想，key用来去重，value用来存辅助信息。注意，有时直接用数组进行hash，而不需要借助<map>

#include <map>

using namespace std;

int main(){

    //1.创建

    map<string,int> myMap;

    //2.访问、修改、增加元素

    myMap["Tom"]=;  myMap["Lucy"]=;  myMap["Jack"]=;

    //3.删除元素

    myMap.erase("Tom");      //也可使用   myMap.erase(myMap.find("hi"));

    //4.通过key查找元素

    if (myMap.find("Tom")==myMap.end())

        cout<<myMap.count("Tom")<<endl;

    //5.遍历,map内部以key的升序排列

    for(auto it=myMap.begin();it!=myMap.end();it++){

        cout<<it->first<<endl;

        cout<<it->second<<endl;

    }

}

V.string

#include <iostream>

#include <vector>

//0.头文件

#include <string>

#include<sstream>  //辅助

using namespace std;

int main(){

    //1.创建,初始化

    string x="hello world",y="ld s";

    getline(cin,y);   //获得一行，也可再加个终止符参数

    //2.常用函数与vector相同  empty, size, push_back, 下标访问

    //3.+ - < > =运算符的重载

    //4.关于字符变量函数 isalnum,isalpha,isdigit    tolower,toupper

    //5.获得子串

    string sub=x.substr(,); // 第1个位置开始，长度为3的子串

    //6.交换两个字符串

    y.swap(x);

    //7.查找字串

    auto t=y.find(x,);

    if(t!=string::npos)

        cout<<t;

    //8.split功能

    istringstream strcin(x);

    string s;

    vector<string> res;

    while(strcin >> s)

        res.push_back(s);

}

VI.bit manipulation

与　　　　 a&b 1010&1100=1000 　　
或　　　　　　 a|b 　 1010|1100=1110
异或 a^b 1010^1100=1001
按位取反 ~a ~1010=0101
左移 a<<1　 1010<<1=10100
带符号右移 a>>1 -1010>>1=-101
无符号右移 a>>>1

秒客网

programming review (c++): (1)vector, linked list, stack, queue, map, string, bit manipulation

相关文章