再话图算法—最短路

发表于 2020-04-29 | 阅读次数:

最近真是加把劲骑士。今天复习一下最短路径，即给定图计算从起点到终点的最短路径。常用算法有Dijsktra、Bellman-ford、SPFA、Floyd算法。

Dijsktra单源最短路

基本思想：设置已访问节点S，然后每次从V-S中选择离起点s的最短路径最小的节点u，之后以u为中介，调整s到从u经过能到达的所有顶点v的最短距离，执行n次即可。简单来说，就是每次选择未访问最短距离点，选择后借助这个点开放相关边，再借助相关边更新最短路。

const int MAXV=1000;
const int INF=0x3fffffff;

int n,G[MAXV][MAXV];
int dis[MAXC];
bool vis[MAXV]={false};

void Dijstra(int s) //s means source
{
    fill(dis,dis+MAXV,INF); //慎用memset,fill为algorithm库提供的函数
    dis[s]=0;

    for(int i=0;i<n;i++)  //重复n次
    {
        int u=-1,MIN=INF; //找到dis[u]最小
        for(int j=0;j<n;j++) //找到u
        {
            if(vis[j]==false&&dis[j]<MIN)
            {
                u=j;
                MIN=dis[j];
            }
        }

        if(u==-1) return; //说明剩下的顶点和s不连通
        vis[u]=true;
        for(int v=0;v<n;v++)
        {
            //如果v没访问 且 u能到达v 且 能够达到更优的dis
            if(vis[v]==false&&G[u][v]!=INF && dis[u]+G[u][v]<dis[v])
            {
                dis[v]=dis[u]+G[u][v];
                //pre[v]=u
            }
        }
    }
}

邻接链表版的就略了，它可以一定程度减小时间复杂度，降低空间开销。
以上只是求解了最短距离，并未求解最短路径。实际上，我们添加一个pre[MAXV]数组，其中pre[v]表示从起点到顶点v的最短路径上v的上一个前驱节点。初始时，pre[i]指向自身i。最后，在更新可更新边的时候，将pre[v]确定为本次循环确定的节点u。要访问路径，从最后一个节点递归访问即可。

void DFS(int s,int v) //从终点v开始递归
{
    if(v==s){
        printf("%d\n",s);return;
    }
    DFS(s,pre[v]);
    printf("%d\n",v);
}

同时，dijsktra算法也有很多变体，比如最短路不止一条，往往会新增一个关于开销的量度：

给每一条边新增一个另一个维度的边权，即除了距离，还有花费，希望路上少花点钱
给每个点增加一个点权，希望能够搜集更多的物资

直接问如果有，有几条
对于这三种，增加一个数组来存放新增的边权或者点权或者最短路径条数，然后修改优化dis[v]那个步骤即可。以第一个情况为例：

for(int v=0;v<n;v++)
{
    if(vis[v]==false&&G[u][v]!=INF)
    {
        if(dis[u]+G[u][v]<dis[v])
        {
            dis[v]=dis[u]+G[u][v];
            cos[v]=cos[u]+cost[u][v]; //cos和dis一样，cost和G类似
        } else if(dis[u]+G[u][v]==dis[v]&&c[u]+cost[u][v]<cost[v])
        {
            cos[v]=cos[u]+cost[u][v];
        }
    }
}

而数有几条最短路,新增一个数组num，令从起点s到达顶点u的最短路径条数为num[u]，最初num[s]=1其他为0,而会引起多条最短路的情况是在u这个点可以平等选择多个点：

for(int v=0;v<n;v++)
{
    if(vis[v]==false&&G[u][v]!=INF)
    {
        if(dis[u]+G[u][v]<dis[v])
        {
            dis[v]=dis[u]+G[u][v];
            num[v]=num[u];
        }else if(d[u]+G[u][v]==d[v])
        {
            num[v]+=num[u];
        }
    }
}

Bellman-Ford&SPFA

一旦出现负边权，Dijsktra算法就会失效。BF算法主要思想是设置一个数组d用来存放最短距离，同时返回一个bool值：如果其中存在从源点可达的负环，那么返回false；否则返回true，此时d中存放的值就是最短距离。

此时如果不存在从源点可达的负环那么d中所有值应该达到最优了，对所有边在判断一次，如果仍然可以松弛，就说明存在从源点可达的负环返回false。其复杂度是O(n*Edge).

for(each edge uTov)
{
    if(d[u]+length[uTov]<d[v]) return false;
    return true;
}

邻接链表：

struct Node{
    int v,dis;
};
vector<Node> Adj[MAXV];
int n;
int d[MAXV];
bool Bellman(int s)
{
    fill(d,d+MAXV,INF);
    d[s]=0;

    for(int i=0;i<n;i++) //循环n次
    {
        for(int u=0;u<n;u++) //遍历所有边
        {
            for(int j=0;j<Adj[u].size();j++)
            {
                int v=Adj[u][j].v;
                int dis=Adj[u][j].dis;
                if(d[u]+dis<d[v])
                {
                    d[v]=d[u]+dis;
                }
            }
        }
    }
    //判断负环
    for(int u=0;u<n;u++)
    {
        for(int j=0;j<Adj[u].size();j++)
        {
            int v=Adj[u][j].v;
            int dis=Adj[u][j].dis;
            if(d[u]+dis<d[v])
            {
                return false;
            }
        }
    }
    return true;
}

BF算法主要是在O(VE)的E上开销太大了，但其中存在很多无意义操作，通过队列优化就得到了SPFA算法，复杂度降低为O(kE),k一般不超过2.
SPFA

弗洛伊德算法

全源最短路，囿于复杂度，一般一次能跑的节点不能超过200.

void Floyd()
{
    for(int k=0;k<n;k++)
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                //两者可达且可优化
                if(dis[i][k]!=INF&&dis[k][j]!=INF&&dis[i][k]+dis[k][j]<dis[i][j])
                {
                    dis[i][j]=dis[i][k]+dis[k][j];
                }
            }
        }
    }
}

再话图算法之图的遍历

发表于 2020-04-28 | 阅读次数:

前言

定义，出度入读，有向图无向图，点权边权，邻接矩阵，邻接链表，有向图的强连通分量，无向图的连通分量，连通块..

struct Node{
    int v,w;
    Node(int _v,int _w): v(_v),w(_w) {} //constructor
}
Adj[index].push_back(Node(3,4));

DFS

dfs
在实际的题目中，可能遇到比较坑的情况，比如要删边避免回路。
邻接矩阵实现：

const int MAXV=1000; //max vertices,设计算法不能超过千万级别复杂度
const int INF=1000000000;

int n,G[MAXV][MAXV];
bool vis[MAXV]={false}; //bool array要显式初始化

void DFS(int u,int depth)
{
    vis[u]=true;
    //do something for u in here
    /**/
    //下面对所有u能够直接到达的分支节点进行枚举
    for(int v=0;v<n;v++)
    {
        if(vis[v]==false&&G[u][v]!=INF) //未被访问且可达
        {
            DFS(v,depth+1);
        }
    }
}

void DFSTraverse()
{
    for(int u=0;u<n;u++)
    {
        if(vis[u]==false)
        {
            DFS(u,1);
        }
    }
}

邻接链表实现：

vector<int> Adj[MAXV];
int n;
bool vis[MAXV]={false};

void DFS(int u,int depth)
{
    vis[u]=true;
    //do something at u in here
    /**/
    for(int i=0;i<Adj[u].size();i++){
        int v=Adj[u][i];
        if(vis[v]==false){
            DFS(v,depth);
        }
    }
}

void DFSTraverse()
{
    for(int u=0;u<n;u++)
    {
        if(vis[u]==false)
        {
            DFS(u,1);
        }
    }
}

一道比较好的题目在P359，有空回头刷刷。

BFS

邻接矩阵版：

int n,G[MAXV][MAXV];
bool inq[MAXV]={false};

void BFS(int u)
{
    queue<int> q;
    q.push(u);

    inq[u]=true;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int v=0;v<n;v++)
        {
            if(inq[v]==false&&G[u][v]!=INF)
            {
                q.push(v);
                inq[v]=true;
            }
        }
    }
}

void BFSTraverse()
{
    for(int u=0;u<n;u++)
    {
        if(inq[u]==false)
        {
            BFS(q);
        }
    }
}

邻接链表版：

vector<int> Adj[MAXV];
int n;
bool inq[MAXV]={false};

void BFS(int u)
{
    queue<int> q;
    q.push(u);
    inq[u]=true;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();

        for(int i=0;i<Adj[u].size();i++)
        {
            int v=Adj[u][i];
            if(inq[v]==false)
            {
                q.push(v);
                inq[v]=true;
            }
        }
    }
}

void BFSTraverse()
{
    for(int u=0;i<n;i++)
    {
        if(inq[u]==false)
        {
            BFS(u);
        }
    }
}

有时候需要给定BFS的层次，这时候需要进行一些调整。

struct Node{
    int v;
    int layer;
}

vector<Node> Adj[N];
void BFS(int s)
{
    queue<Node> q;
    Node start(s,0); //起始点s，层次为0
    q.push(start);
    inq[start.v]=true;
    while(!q.empty())
    {
        Node top=q.front();
        q.pop();
        int u=top.v;
        for(int i=0;i<Adj[u].size();i++)
        {
            Node next=Adj[u][i];
            next.layer=top.layer+1;
            if(inq[next.v]==false)
            {
                q.push(next);
                inq[next.v]=true;
            }
        }
    }
}

同样的好题在P365，有空回来看看。

再话二叉排序树

发表于 2020-04-27 | 阅读次数:

昨天复习了一下二叉树，却没有记录广义树。广义树采用静态实现，孩子域改成vector child，用来记录孩子节点的在静态数组中的index即可，比较复杂的情况是拿这棵树去DFS&BFS,其实也就那么回事。BST比较有用的特征是inOrderTraverse得到的是一个有序序列。

查找

一个平凡二叉树一般是没有特性的，而BST具有大小关系，所以可以选择其中一颗子树进行向下探测，所以查找将会得到一条路径。

void search(node* root,int x)
{
    if(root==NULL){
        //说明是空树
        printf("search failed\n");
        return;
    }
    if(x==root->data)
    {
        printf("%d\n",root->data);
    }else if(x<root->data)
    {
        search(root->lchild,x);
    }else{
        search(root->rchild,x);
    }
}

插入与建立操作

对一个BST，查找一个节点是顺着一条路径，因此如果能够查找成功，说明已经存在；否则，查找失败，说明这个查找失败的地方正是节点需要插入的地方，显然插入的复杂度是O(layer)级别的。插入和查找差不太多。建立一颗bst也就是插入一系列节点的过程。

void insert(node8 &root,int x)
{
    if(root==NULL)
    {
        root=newNode(x); //之前有过newNode的函数
        return;
    }
    if(x==root->data)
    {
        return; //已经存在，直接返回
    }else if(x<root->data){
        insert(root->lchild,x);
    }else{
        insert(root->rchild,x);
    }
}

node* Create(int data[],int n)
{
    node* root=NULL;
    for(int i=0;i<n;i++)
    {
        insert(root,data[i]);
    }
    return root;
}

需要注意的是，即便是一组相同的数字，如果插入顺序不同，最后生成的BST也可能不同。

BST节点删除

BST删除一般有两种方法，复杂度都是O(layer)，重点在于怎么保持删除后仍然是BST。对于给定节点，在BST中比节点权值大的最小节点为后继，比节点权值小的最大节点为前驱。所以我们需要先来寻找以当前节点root为根的树中的最大或者最小权值的节点，用于辅助寻找前驱或后继。

node* findMax(node* root)
{
    while(root->rchild!=NULL){
        root=root->rchild;
    }
    return root;
}
node* findMin(node* root)
{
    while(root->lchild!=NULL){
        root=root->lchild;
    }
    return root;
}

基本思路分为四步，第一步是root为空则return；第二步时如果当前root权值大于目的x，则说明要在左子树里面递归删除x的节点；第三步是如果当前root权值小于目的x，则说明要在其右子树递归去删除值为x的节点。第四步比较复杂，当root值等于目的x：

如果当前root没有左右孩子则说明是叶子直接删除
如果当前节点存在左孩子，则在左子树中寻找节点前驱pre，让pre的数据覆盖root，接着在左子树中删除pre。

如果当前节点存在右孩子，则在右子树中寻找节点后继next，让next的数据覆盖root，接着在右子树中删除next。

void deleteNode(node* &root,int x)
{
    if(root==NULL) return;
    if(root->data==x){
        if(root->lchild==NULL&&root->rchild==NULL){
            root=NULL;
        }else if(root->lchild!=NULL){
            node* pre=findMax(root->lchild);
            root->data=pre->data;
            deleteNode(root->rchild,pre->data);
        }else{
            node* next=findMax(root->rchild);
            root->data=next->data;
            deleteNode(root->rchild,next->data);
        }
    }else if(root->data>x){
        deleteNode(root->lchild,x);
    }else{
        deleteNode(root->rchild,x);
    }
}

再话树

发表于 2020-04-26 | 阅读次数:

今天再来复习一下二叉树。一般来说，二叉树使用链表来定义，只是节点有两条出边，所以指针域有两个，所以这种实现方式有时候又叫二叉链表。树的实现可以用二叉链表，也可以像链表一样，使用静态方法实现。本着复习为目标，这里就不总结静态实现了。

定义与新建节点

//Definition
struct node{
    typename data;
    node* lchild;
    node* rchild;
};
//new build
node* newNode(int v)
{
    node* Node=new node;
    Node->data=v;
    Node->lchild=Node->rchild=NULL;
    return Node; //返回新建节点的地址
}

二叉树常用的操作有建立，查找，修改，插入和删除。这里不说明删除了，不同性质的树之间差异比较大。

查找与修改

查找是指再给定数据域的条件下，搜索节点中数据域为给定数据域的那些节点，如有需要则可以进行修改。

void search(node* root,int x,int newdata)
{
    if(root==NULL) //空树，递归边界
        return;
    if(root->data==x)
    {
        root->data=newdata; //可选操作
    }
    //递归式
    search(root->lchild,x,newdata);
    search(root->rchild,x,newdata);
}

二叉树节点插入

创建一个二叉树必然需要插入一系列节点。但因为二叉树形态很多，但同时节点的插入位置一般取决于数据域需要在二叉树中存放的位置，而往往只能有一个可以插入的位置。所以可以这么想，二叉树节点插入位置就是数据域在二叉树中查找失败的位置。而这个位置是确定的，在递归查找时只是根据二叉树的性质(如排序二叉树)选择左子树或者右子树中的一个进行递归，到达递归边界就是查找失败的地方。

//注意根节点指针root要使用引用，否则插入不成功
void insert(node* &root,int x)
{
    if(root==NULL)
    {
        root=newNode(x);
        return;
    }
    if(根据二叉树的性质，符合插在左子树的条件)
    {
        insert(root->lchild,x);
    }else{
        insert(root->rchild,x);
    }
}

很重要的一点时要在根节点root使用引用，之所以使用引用是为了在函数中修改root的时候会直接修改原变量。一般来说，如果函数要新建节点，修改二叉树的结构，就要加引用。

二叉树的创建

二叉树创建其实就是二叉树节点插入的过程，插入的数据都会在题目中给出，我们喜欢先把他们存到数组中，在用insert一个个插入进去，最终返回根节点指针root。

node* Create(int data[],int n)
{
    node* root=NULL;
    for(int i=0;i<n;i++)
    {
        insert(root,data[i]);
    }
    return root;
}

到底是怎么存储的

tree

完全二叉树的存储

对于完全二叉树，它可以有更简单的存储方法。如果给他的所有节点按照从上到下从左到右从1开始的编号，通过观察可以注意道，对于一个完全二叉树的一个节点，假设它编号时x，那么他的左孩子节点一定是2x，右孩子节点一定是2x+1，也就是说，它可以通过建立一个大小为2^k的数组存放所有节点的信息，k时最大高度，1为root。当然这可能也有弊端，比如整棵树就是一条链。除此之外，这让层序遍历变得更简单，因为数组中本身的顺序就是层序遍历序列，同时，判断一个节点是不是叶子直接通过2*index下标与n比较就行了。

DFS的先、中、后序遍历

void preOrder(node* root)
{
    if(root==NULL)
    {
        return;
    }
    printf("%d\n",root->data);
    preOrder(root->lchild);
    preOrder(root->rchild);
}

先序遍历序列，序列的第一个节点一定是根节点。

void inOrder(node* root)
{
    if(root==NULL)
    {
        return;
    }
    inOrder(root->lchild);
    printf("%d\n",root->data);
    inOrder(root->rchild);
}

由于中序遍历总把根节点放在左孩子和右孩子遍历的中间，因此只需要知道根节点，就可以通过根节点在中序遍历序列中的位置区分左孩子和右孩子。
至于如何事先知道根节点，先序遍历即可。
根据先序和中序可以来确定整颗二叉树，具体之后再谈。

void postOrder(node* root)
{
    if(root==NULL)
    {
        return;
    }
    postOrder(root->lchild);
    postOrder(root->rchild);
    printf("%d\n",root->data);
}

采用后序遍历，序列的最后一个节点必定是根节点。但无论时先序遍历还是后序遍历，要确定一颗树还得借助中序遍历，这是因为先序和后续只能得到根节点，而只有通过中序遍历才能够利用根节点将左右子树分开从而递归产生一棵二叉树。

BFS的层序遍历

基本思路和BFS无异，先取出根节点root加入Queue，取出队首节点然后pop掉，如果有左孩子则左孩子入队，然后如果有右孩子则右孩子入队，只要Queue不为空就继续进行。

void LayerOrder(node* root)
{
    queue<node*> q;
    q.push(root);
    while(!q.empty())
    {
        node* once=q.front();
        q.pop();
        printf("%d\n",once->data);
        if(once->lchild!=NULL) q.push(once->lchild);
        if(once->rchild!=NULL) q.push(once->rchild);
    }
}

队列采用的是node*而不是node,这是因为如若不然，则队列中保存的只是一个node类型的副本，如果要修改，那么并不能对原来的元素进行修改，通过地址这一点就可以很好解决这个问题。有时候，需要明确每个节点的层次，给一个node加一个新的数据域layer就行。同时，调整一下遍历到节点的工作。

void LayerOrder(node* root)
{
    queue<node*> q;
    root->layer=1;
    q.push(root);

    while(!q.empty())
    {
        node* now=q.front();
        q.pop();
        printf("%d ",now->data);
        if(now->lchild!=NULL)
        {
            now->lchild->layer=now->layer+1;
            q.push(now->lchild);
        }
        if(now->rchild!=NULL)
        {
            now->rchild->layer=now->layer+1;
            q.push(now->rchild);
        }
    }
}

给定先序遍历序列和中序遍历序列重建一棵树

先序序列: pre1,pre2,pre3,pre4,…pren。
中序序列: in1,in2,in3,in4,…inn。
先序pre1是根节点，在中序序列中查找到ink==pre1,这就说明了在先序序列中2~k为左子树，k+1~n为右子树；同时，在中序序列中，1~k-1为左子树，k+1~n为右子树，以上均是闭区间。接着，就指用在左子树和右子树上递归构建二叉树即可。递归边界为当前先序序列已经没有元素了。其实有点像快速排序的方法。

//preL~preR为先序区间，inL~inR为中序区间
node* create(int preL,int preR,int inL,int inR)
{
    if(preL>=preR)
    {
        return NULL;
    }

    node* root=new node;
    root->data=pre[preL];
    int k;
    for(k=inL;k<=inR;k++)
    {
        if(in[k]==pre[preL]) break; //找到ink=preL的点，即确定根节点
    }
    int numLeft=k-inL;
    //左子树的先序区间为[preL+1,preL+numLeft]，中序区间【inL，k-1】
    root->lchild=create(preL+1,preL+numleft,inL,k-1);
    //同理
    root->rchild=create(preL+numLeft+1,preR,k+1,inR);

    return root;
}

中序遍历可以和其他三个中任何一个搭配构建出唯一的一棵树，而后面三个再怎么组合都不行。

决策树小结

发表于 2020-04-25 | 阅读次数:

这一篇用于总结之前对决策树的学习的日常。首先，决策树是一种非参数学习方法，可以解决分类问题（也可以延申解决回归问题），具有较好的可解释性。

CART树：根据某个维度d和某个阈值v进行二分的树。以下以CART树的实现为例。
需要解决的问题是，每个节点在哪个维度（特征）进行划分，这个维度在哪个值上做划分
非参数学习具有过拟合倾向，采用剪枝来降低复杂度解决过拟合。而剪枝也分为预剪枝和后剪枝，各有好坏。一般来说，对于一个一般性问题，决策分支过多是不好的。
可以采用一些参数限制来解决过拟合，比如限制决策树的最大深度max_depth，限制一个分支的样本个数min_samples_split
具体的一些方法可以参考这个网址,也可以去看scikit-learn的官网
计算损失的时候可以采用信息熵或者Gini系数，熵的计算慢一些,在sklearn的封装中，比如dt_clf=DecisionTreeClassifier(max_depth=2.criterion=”entropy”)通过criterion选择哪种实现。
Entropy在信息论中是随机变量不确定度的表量，熵越大则不确定度越高。而我们之所以想要对训练样本进行划分，就是想要使得信息熵降低。数据集D的纯度可以用基尼值Gini(D)=1-Sigma(p_{k}^2)进行度量，它反映了从D中随机抽取两个样本类别不一致的概率，所以它越小，一致的概率越高，纯度越高。而属性a的基尼系数Gini_index(D,a)在CART中用于选择基尼指数最小的属性来作为最优划分属性。

再话链表

发表于 2020-04-21 | 阅读次数:

前言

在学数据结构的时候，感觉知识点就没有形成一个体系，于是最近也在有意无意地把以前学习过的知识再串联起来。

struct node {
    type data;
    node* next;
}

线性表分为顺序表和链表，而链表也根据是否存在头节点分为带头的和不带头的。一般我们称带头的节点为头节点head，其数据域data不存放任何内容，其next域指向第一个节点。事实上，这两种链表的写法大同小异，这里统一使用带头的节点。同时，最后一个节点的next域指向NULL，即空地址。申请一个空间可以用stdlib.h文件下的malloc函数，即node* p=(node)malloc(sizeof(node));,这句话的逻辑是分配node所需要的大小作为参数，malloc函数将会向内存申请一块相应大小的空间，并且返回这个空间的指针。但这个指针初始时是一个void\类型的，所以需要cast一下，得到一个node*类型的指针p。如果申请失败则返回NULL。一般来说不会失败，可能在申请大地址空间(较大动态数组)的时候可能会失败。而new是C++用于申请的运算符，即node* p=new node;。但如果分配失败，则不会返回NULL而是启动C++异常处理。然后就回到了大一长谈的内存泄漏问题，内存泄漏是指借用了内存空间但是使用之后忘记释放，导致在程序结束之前始终占据内存空间，所以有些较大的程序很容易导致在运行的时候无内存继续分配，当然进程结束后应该还是问题不大。清空一个空间用free(p)或者delete p就行。一般做oj的时候问题不大，但是开发的时候还是应该把内存管理好一些。
链表分就实现上可分为动态链表和静态链表，静态链表在一些PAT题目中经常会用到，其思想就是开辟一个较大的内存空间，每一个节点都会有一个int型的next域，其地址由其索引决定。

创建链表

#include <stdio.h>
#include <stdlib.h>
struct node{
    int data;
    node* next;
};
node* create(int Array[],int n)
{
    node *p,*pre,*head;
    head=new node;head->next=NULL;
    pre=head;
    for(int i=0;i<n;i++)
    //sizeof(Array)/sizeof(int)这么写是错误的
    {
        p=new node;
        p->data=Array[i];
        p->next=NULL;
        pre->next=p;
        pre=p;
    }
    return head;
}

查找链表中是否有给定的元素或者有多少个？

int search(node *head,int x)
{
    int count=0;
    node* p=head->next;
    while(p!=NULL)
    {
        if(p->data==x)
        {
            counter++;
        }
        p=p->next;
    }
    return count;
}

插入元素:在链表指定位置插入一个节点

void insert(node* node,int pos,int x)
{
    node* p=head;
    for(int i=0;i<pos-1;i++)
    {
        p=p->next;
    }
    node* q=new node;
    q->data=x;
    q->next=p->next;
    p->next=q;
}

删除链表上所有值为x的节点

void deleteX(node *head,int x)
{
    node *p=head->next;
    node *pre=head;
    while(p!=NULL)
    {
        if(p->data==x)
        {
            pre->next=p->next;
            delete(p);
            p=pre->next;
        }else{
            pre=p;
            p=p->next;
        }
    }
}

链表反转

struct node* reverse(node* head)
{
    node* cur=NULL,*pre=head->next;//pre为第一个节点
    while(pre!=NULL)
    {
        node* t=pre->next;//t指向第二个点
        pre->next=cur;   //第一个点指向前一个，即NULL
        cur=pre;        //cur向后移动一格
        pre=t;          //pre向后移动一个
    }
    head->next=cur;
    return head;
}

TEST

int main() {
	int Array[5]= {1,2,3,4,5};
	int n=sizeof(Array)/sizeof(int);
	node *L=create(Array,n);
	node *head=L;
	L=L->next;//从第一个节点开始有数据域
	while(L!=NULL) {
		printf("%d ",L->data);
		L=L->next;
	}
	node* new_head=reverse(head);
	node* pp=new_head->next;
	while(pp!=NULL) {
		printf("%d ",pp->data);
		pp=pp->next;
	}
	return 0;
}

The Philosophy of Searching

发表于 2020-04-17 | 阅读次数:

FIRST:

#include <stdio.h>
#include <queue>
using namespace std;
bool mark[50][50][50];
int maze[50][50][50];
struct N
{
    int x,y,z;
    int t;
};

queue<N> Q;
int go[][3]={
    //坐标变换数组
    //（x,y,z）=> (x+go[i][0],y+go[i][1],z+go[i][2])
    1,0,0,
    -1,0,0,
    0,1,0,
    0,-1,0,
    0,0,1,
    0,0,-1
};

int BFS(int a,int b, int c)
{
    while(Q.empty()==false)
    {
        N now=Q.front();
        Q.pop();
        for(int i=0;i<6;i++)
        {
            int nx=now.x+go[i][0];
            int ny=now.y+go[i][1];
            int nz=now.z+go[i][2];
            if(nx<0||nx>=a||ny<0||ny>=b||nz<0||nz>=c) continue;

            if(maze[nx][ny][nz]==1) continue;
            if(mark[nx][ny][nz]==true) continue;

            N temp;
            temp.x=nx;
            temp.y=ny;
            temp.z=nz;
            temp.t=now.t+1;
            Q.push(temp);
            mark[nx][ny][nz]=true;

            if(nx==a-1&&ny==b-1&&nz==c-1) return temp.t;
        }
    }
    return -1;
}

int main()
{
    int T;
//    printf("%d",Q.empty());
    scanf("%d",&T);
    while(T--)
    {
        int a,b,c,t;
        scanf("%d%d%d%d",&a,&b,&c,&t);

        for(int i=0;i<a;i++)
        {
            for(int j=0;j<b;j++)
            {
                for(int k=0;k<c;k++)
                {
                    scanf("%d",&maze[i][j][k]);
                    mark[i][j][k]=false;
                }
            }
        }

        while(Q.empty()==false) Q.pop();
        mark[0][0][0]=true;
        N temp;
        temp.t=temp.y=temp.x=temp.z=0;
        Q.push(temp);
        int rec=BFS(a,b,c);
        if(rec<=t) printf("%d\n",rec);
        else printf("-1\n");
    }
    return 0;
}

SECOND:

#include <stdio.h>
#include <string.h>

int ans[22];
bool hash[22];
int n;
int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41};

bool judge(int x)
{
    for(int i=0;i<13;i++)
    {
        if(prime[i]==x) return true;
    }
    return false;
}

void check()
{
    if(judge(ans[n]+ans[1])==false) return;
    for(int i=1;i<=n;i++)
    {
        if(i!=1) printf(" ");
        printf("%d",ans[i]);
    }
    printf("\n");
}

void DFS(int num) //当前放入环中的数字
{
    if(num>1)
    {
        if(judge(ans[num]+ans[num-1])==false) return ;
    }
    if(num==n) //已经放入了n个数
    {
        check();
        return ;
    }
    for(int i=2;i<=n;i++)
    {
        if(hash[i]==false)
        {
            hash[i]=true;
            ans[num+1]=i;
            DFS(num+1);
            hash[i]=false;
        }
    }
}

int main()
{
    int cas=0;
    while(scanf("%d",&n)!=EOF)
    {
        cas++;
        for(int i=0;i<22;i++) hash[i]=false;
        ans[1]=1;
        printf("Case %d:\n",cas);
        hash[1]=true;
        DFS(1);
        printf("\n");
    }
    return 0;
}

C++正则表达式小结

发表于 2020-04-16 | 阅读次数:

自2011年，C++ 11也将regex列为新标准的一部分。不仅如此，它还支持了6种不同的正则表达式的语法，分别是：ECMASCRIPT、basic、extended、awk、grep和egrep。其中ECMASCRIPT是默认的语法。而正则表达式我在这三年经常接触，往往是学了就忘。在这段时间的C++刷题经验上来看，掌握正则表达式有时候可以极大的节省你做题的时间，比如这个题。
这是一篇更偏应用的文章，我们这里就直接上一些例子就行。
第一类就是比较常见的单次匹配问题了

//写一个匹配函数，（）可以分隔语义 ，\\进行转义
bool IsIP(string Str) {
	//regex e("\\d+\\.\\d+\\.\\d+\\.\\d"); //IP地址匹配
	//regex e("[a-g]");                    //区间匹配
	//regex e("[a-g]*");                   //*号与区间匹配联合使用
	//regex e("\\w{4,10}");              //表示4-10个字符 指定个数
	//regex e("ada(e|b)");                 //表示或者
	//regex e("^[a-z]+\\d{1,3}");      //属于小写字母开头包含几个数字而[^a-z] 不属于a-z
	//regex e("ab[^cd]*");           // [^...]   任意不在方括号中的字符
	//regex e("[a-zA-Z][a-zA-Z0-9_]{4,15}");
	//BUAA机考题
	//regex e("a[abc]b[abc]c",regex::icase); //忽略大小写
	//regex e("\\w*"); //注意是否转义有很大区别
	//regex e("abc.", regex::icase);   // .   表示除了换行符之外任意字符
	//regex e("abc?");               // ?       0个或者1个前面的字符
	//regex e("abc|de[fg]");         // |       或者
	//regex  e("(abc)de+\\1");       // \1      第1个子串
	//regex  e("(ab)c(de+)\\2\\1");
	//regex e("\\w+@[[:w:]]+\\.com"); // [[:w:]] ：字母，数字，下划线
	regex e("^abc.+$");                 // $   行尾 ^顶格 
	bool b = regex_match(Str, e);
	return b;
}
}

第二类问题和子串提取，多重匹配有关。
上面说了，()可以分隔语义，也可以分出子串1，子串2，子串3。那么，我们也可以通过smatch把这几个子串重定向出来。
这是一些知识总结和实例：

smatch string类型的详细的匹配Detailed match in string
smatch m; 其实是一个类似vector的数组，但是不是直接按照string存的
m[0].str() 整个匹配的字符串 (同m.str(), m.str(0))
m[1].str() 第1个子串(同m.str(1))，所以需要一个.str()方法转为string
m[2].str() 第2个子串
m.prefix() 所有匹配字符串之前的部分

m.suffix() 所有匹配字符串之后的部分

int main() {
   string str;

   while (true) {
      cin >> str;
	  smatch m;        // typedef std::match_results<string>

	  regex e("([[:w:]]+)@([[:w:]]+)\\.com");  

	  bool found = regex_search(str, m, e);        //只返回第一个匹配

      cout << "m.size() " << m.size() << endl;        //size()==子匹配个数+1
	  for (int n = 0; n< m.size(); n++) {
		   cout << "m[" << n << "]: str()=" << m[n].str() << endl;
	  }
	  cout << "m.prefix().str(): " << m.prefix().str() << endl;
	  cout << "m.suffix().str(): " << m.suffix().str() << endl;
   }
}

在上面的例子中，展示了如何提取匹配出的第一个子串，第二个子串，但有时候我们的野心不止于此，我们还希望能够对多个match的串，分别算出他们的子串，这怎么办呢？这时候，就可以用一个很STL style的sregex迭代器来处理了。Show you my code：

int main() {
	cout << "Hi" << endl;
	string str = "boq@yahoo.com, boqian@gmail.com; bo@hotmail.com";
	regex e("\\w+@\\w+\\.com");
	sregex_iterator pos(str.cbegin(), str.cend(), e);
	sregex_iterator end;  // 默认构造定义了past-the-end迭代器
	for (; pos!=end; pos++) {
		cout << "Matched:  " << pos->str(0) << endl;
		cout << "user name: " << pos->str(1) << endl;
		cout << "Domain: " << pos->str(2) << endl;
		cout << endl;
	}
	cout << "=============================\n\n";
}

第三类问题和匹配替换有关。
regex_replace()算法要求输入一个正则表达式，以及一个用于替换匹配子字符串的格式化字符串。这个格式化字符串可以通过转义序列引用匹配子字符串中的部分内容。

$n 匹配第n个捕捉组的字符串。例如\$l表示第一个捕捉组，\$2表示第二个，依此类推
$& 匹配整个正则表达式的字符串，等同于\$0
$` 在源字符串中，在匹配正则表达式的子字符串左侧的部分
$’ 在源字符串中，在匹配正则表达式的子字符串右侧的部分

$$ 美元符号
看一个简单例子：

int main() {
    string str = "11sigalhu22sigalhu33",str1;
    str1 = regex_replace(str,regex("s(igal)h(u)"),"SS$1HH$2");
    cout<<str1<<endl;
    //应该输出11SSigalHHu22SSigalHHu33

数学之美——矩阵旋转

发表于 2020-04-14 | 阅读次数:

这几天在疯狂用C++学习和练习算法，昨天刷完了一道北航的研究生上机题目，觉得很有意思。之后查看了一下别人都是怎么想这些问题的，现在就是觉得数学非常美，有了数学好像好多问题，都不用去记忆规律或者推导规律了。
问题：如何将一个矩阵旋转0，90，180，270度？或许这个问题你接触过烂熟于心，或许你觉得可以花时间加以推导还是可以推出来，或者你和我一样，最开始拿到这个问题并没有自信one-take就搞出来。但如果你对矩阵论有所了解，你会发现以下方法给了你一定的perspective。总而言之，就是找到基向量的位置。在通过旋转基向量来旋转矩阵。旋转矩阵按列向量来思考会简单一些。
matrix
如果在实际编程中，遇到数组，因为数组的index不能为负，比如10*10的数组，旋转后整体应该移了10个单位。

#include<stdio.h>
void print(int a[][10]){
    for(int i=0;i<10;i++){
    for(int j=0;j<10;j++){
        printf("%3d",a[i][j]);
    }
    printf("\n");
    }
}
int main(){
    int a[10][10];
    int k = 0;
    //原图像 
    for(int i=0;i<10;i++){
        for(int j=0;j<10;j++){
            a[i][j] = k++;
        }
    } 
    //顺时针旋转90 
    int shun90[10][10];
    for(int i=0;i<10;i++){
        for(int j=0;j<10;j++){
            shun90[j][9-i] = a[i][j];
        }
    }
    //逆时针旋转90 
    int ni90[10][10];
    for(int i=0;i<10;i++){
        for(int j=0;j<10;j++){
            ni90[9-j][i] = a[i][j];
        }
    }
    //旋转180 
    int zhuan180[10][10];
     for(int i=0;i<10;i++){
        for(int j=0;j<10;j++){
            zhuan180[9-i][9-j] = a[i][j];
        }
    }
    printf("原矩阵\n\n");
    print(a);
    printf("\n\n顺时针90\n\n");
    print(shun90);
    printf("\n\n逆时针90\n\n");
    print(ni90);
    printf("\n\n转180\n\n");
    print(zhuan180);
    return 0;
}

而在面对面试或者机考的时候，简单记住(i,j)==>(j,-i),(-i,-j),(-j,i)这样的映射关系就好了，举个例子就知道应该映射到哪个位置。同理，在给出两个矩阵让你判断他们是否是旋转关系，如果是，旋转多少度也可以通过这个关系直接判断。这就是北航那个题目了。这里也简单贴出核心代码吧。

int flag[4]={1,1,1,1};  /**标记0,90,180,270四个方向*/
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
            {
                if(a[i][j]!=b[i][j])            flag[0]=0;
                if(a[n-1-j][i]!=b[i][j])        flag[1]=0;
                if(a[n-1-i][n-1-j]!=b[i][j])    flag[2]=0;
                if(a[j][n-1-i]!=b[i][j])        flag[3]=0;
            }

C++算法竞赛踩坑心得

发表于 2020-04-06 | 阅读次数:

这几天开始继续刷算法了，昨天晚上写了一道大模拟，今天看了半天才知道bug出在哪里，以后每犯一个值得纪念的错误都会列出来，用以自勉。

cin,getline的区别
scanf(“%d”,&n);scanf(“%s”,str);需要注意中间要加getchar读掉缓冲区
string也可以实现切片，需要参考string的构造函数，如string test(src,beginPos,endPos)，不可以直接将一个字符赋给一个string
C++11及以下不提供split，可以使用vector作为返回结果手写一个，这也是头条面试的一道经典题目

有时候必须采用哈希，比如在遇到TLE的时候，考虑哈希是否能用，或者怎么哈希

int hashID(char name[]){ //这是一道PAT题目的例子，名字的格式如THU1，PKU2，BNU1这样
    int id=0;
    for(int i=0;i<3;i++)
        id=id*26+(name[i]-'A');
    id=id*10+(name[3]-'0');
    return id;
}

有时候大数据点string比如char数组，因为容易超时

strcmp函数返回值不一定为正负1和0，取决于编译器

1
2
3

bool cmp(char A[],char B[]){
    return strcmp(A,B)<0;
}

vector的排序：sort(vec.begin(),vec.end(),cmp),略类似于数组
输出格式可能会成为一个坑，比如”%05d”在输出-1就会有问题

C语言结构体也可以有构造函数

#include <iostream>
using namespace std;

struct Node {
    int x, y, z;
    Node(int _x, int _y, int _z) : x(_x), y(_y), z(_z) {}
};

int main() {
    Node a(1, 2, 3);
    cout << a.x << " , " << a.y << " , " << a.z << endl;
    return 0;
}

剑指offer第二题：

1
2
3

//auto ret=s.c_str();      //比较迷的类型转换可以尝试以下auto
const char* ret=s.c_str(); //C_str()返回的是const char*，不能直接赋值
strcpy(str,ret);

vector的自身反转可以直接用reverse：reverse(A.begin(), A.end());

MAP是关联性容器，erase不当容易引发错误

// 错误的写法
    for (itor = m.begin(); itor != m.end(); ++itor)
    {
        if (itor->second == "def")
        {
            m.erase(itor) ; // map是关联式容器，调用erase后，当前迭代器已经失效
        }
    }

    // 正确的写法
    for (itor = m.begin(); itor != m.end();)
    {
        if (itor->second == "def")
        {
            m.erase(itor++) ; // erase之后，令当前迭代器指向其后继。
        }
        else
        {
            ++itor;
        }
    }