发表于 | 阅读次数:

最近发生了很多事，但一直没能找到一个足够静下心的片刻用来记录，即使是现在。

前几天，我刚刚结束一段实习经历。这段时间，我在一家初创企业的核心算法部门上班，进行认知架构底层的开发。最开始上手时会觉得略显复杂，各种单句复句切分，概念和命题识别和属性抽取，正则和ANTLR编译工具，但熟悉整个流程之后会觉得其实这些工作都很基础很底层。技术与工程，到头来不过是大同小异，除了知识技术之外能带给一个人的，我觉得才是最重要的。我认识了一个和自己交心的朋友锦祺，一个十分优秀的同学。另外，这样一个源于清华，极具开创精神的团队也带给我不少精神激励。一方面，在算法部工作，在环境的熏陶下，我对Ai的态度从最开始的害怕和不敢深入，到接受，想去更深入学习，再到我现在也开始在计算所啃项目代码，进行网络与Ai系统交叉的探索。另一方面，我感受到了算法总监生哥和创始人周神那一种极客精神，同时对自己工作的高度认同感，使命感，立足现在而放眼未来，面向未来架构和编程。同时，我也深深认识到，在自己工作的时候，也应该尽可能合理排期，不然容易怠惰和被外界吸引。我一直不是一个勤奋的人，一直是一个对自己不够严格的人。想要学习很多知识和技术，但大部分试探不过是浅尝辄止。但看到NLP组的同事一个人负责一个项目，不仅要进行研究实现，也要部署落地，工程开发，我的感受很简单，我也想这么厉害。最后，日常工作的点点滴滴也足够珍贵。最难忘的是组长让我先放下手上的工作去吃点东西，不知为何当时鼻子真的好酸。

创业维艰。感受创新创业氛围的最好方式，就是在一个有理想的创新创业团队工作。有幸能在一家公司的核心工作，于我弥足珍贵。就是这么一个不到20人的团队，就在这个不到20平米的小小办公室，却完成了无数“0到1”的突破。我们要会画饼，也要相信我们能够把饼做出来，于科研也是一个道理。

“There‘s no defeat but death in a battle”。

发表于 | 阅读次数:

今天在Leetcode练习算法的时候，不禁思考一个问题，DFS和回溯算法，有什么区别呢？

先来回顾一下我们所熟知的DFS，拿FloodFill问题举例的话，先手写一个伪代码看看

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//int map[N][N]里面0表示海，1表示岛屿，要求一个map里面连通岛屿的个数
//bool mark[N][N]表示该位置是否被访问过
//int go[][2]表示上下左右四个方向位置转移
int counter;
void DFS(int x,int y){
    for(i in 四个方向){
        int newX=x+go[i][0];int newY=y+go[i][1];
        if(x越界 或者 y越界) continue;
        if(该点不是1) continue;
        if(该点已经被访问过) continue;
        mark[newX][newY]=true; //标记访问
        DFS(newX,newY);
    }
}
main(){
    ...
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++){
         	if(该点是1 并且 该点未被访问){
                counter++;DFS(i,j);
            }
        }
}

可见，传统DFS一般不会有“解空间”或者复杂解空间结构之类的说法。在之前的《算法》学习中，我一直把二者平等看待，但发现二者还是应该区别看待。DFS是一个劲的往某一个方向搜索，而回溯算法建立在DFS基础之上的，但不同的是在搜过程中，达到结束条件后，恢复状态，回溯上一层，再次搜索。状态管理是回溯的核心，回溯算法应用很多，今天就来手写三个典型的数学问题的回溯。首先，我们来看一下回溯算法的基本模板

1
2
3
4
5
6
7
8
9
result = []
def backtrack(路径, 选择列表或者选择的出发点):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

求N个元素的子集，从数学的角度，该子集的个数是2^n个，如果要输出这些子集呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<vector<int>> res;
vector<vector<int>> subsets(vector<int>& nums){
    vector<int> track;
    backTrack(nums,0,track); //0表示深度,track即路径
    return res;
}
void backTrack(vector<int>& nums,int start, vector<int>& track){
    res.push_back(track); //这里不用判断是否满足结束条件,每一处都是结束点
    for(int i=start;i<nums.size();i++)
    {
        //做选择
        track.push_back(nums[i]);
        backTrack(nums,i+1,track);
        //撤销选择
        track.pop_back();
    }
}

输入两个数字 n, k，算法输出 [1..n] 中 k 个数字的所有组合？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<vector<int>>res;
vector<vector<int>> combine(int n, int k) {
    if (k <= 0 || n <= 0) return res;
    vector<int> track;
    backtrack(n, k, 1, track);
    return res;
}
void backtrack(int n, int k, int start, vector<int>& track) {
    // 到达树的底部
    if (k == track.size()) {
        res.push_back(track);
        return;
    }
    // 注意 i 从 start 开始递增
    for (int i = start; i <= n; i++) {
        // 做选择
        track.push_back(i);
        backtrack(n, k, i + 1, track);
        // 撤销选择
        track.pop_back();
    }
}

输入一个不包含重复数字的数组 nums，返回这些数字的全部排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
List<List<Integer>> res = new LinkedList<>();
List<List<Integer>> permute(int[] nums) {
    // 记录「路径」
    LinkedList<Integer> track = new LinkedList<>();
    backtrack(nums, track);
    return res;
}

void backtrack(int[] nums, LinkedList<Integer> track) {
    // 触发结束条件
    if (track.size() == nums.length) {
        res.add(new LinkedList(track));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        // 排除不合法的选择
        if (track.contains(nums[i]))
            continue;
        // 做选择
        track.add(nums[i]);
        // 进入下一层决策树
        backtrack(nums, track);
        // 取消选择
        track.removeLast();
    }
}

排列问题每次通过 contains 方法来排除在 track 中已经选择过的数字；而组合问题通过传入一个 start 参数，来排除 start 索引之前的数字。大部分回溯算法问题了，无非就是 start 或者 contains 剪枝，也没啥别的技巧了。

发表于 | 阅读次数:

​ How time flies, 转眼已是八月。
2020年7月22号，我迎来了人生一个重要的转折点，即中科院计算所的考核。在努力和运气的作用下，我有幸在自己参与的第一个夏令营，就通过了，并且也是自己很想要去做的方向的很好的老师。过去的两周内，算是彻底松了一口气，也没有去学习什么，就去报了一个驾校🚗，看这个暑假能不能考过两个科目，其实也不算很大的事情。而过了这彻底松口气的两周，我也觉得没有规划，不开展学习和实践的生活是真的枯燥，于是决定去学点东西，去企业面试积累一点经验。
言归正传，来简单回顾一下这段时间吧。在学期内，跟着老师的进度开展课内的学习，在软工大作业验收的那几天体验了一下极限编程，也通过后端大作业进一步和中间件等技术有了头一次实操的经验。然后是准备保研，复习自己做过的项目，并且DFS般回顾一遍，不过还算好，因为都是自己亲自参与的。关于准备机考，就是把王道和算法笔记以及剑指offer的题来回刷，也没啥可以多说的。关于准备笔试，倒没怎么准备，毕竟计算机💻科学所学的知识概要大部分都“刻进DNA”了。
最后是定一些小flag🚩：1.继续加强算法日常练习 2.自己动手把Django&Vue构建一个比较完善的项目 3.把Andrew Ng的Deeplearning.Ai看完，如果还有空可以看看王晓捷老师的NLP介绍课程，扩展自己的认知 4.看一些边缘计算，边缘智能的论文与报告
先写到这吧~

发表于 | 阅读次数: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Problem Description
大家一定觉的运动以后喝可乐是一件很惬意的事情，但是seeyou却不这么认为。因为每次当seeyou买了可乐以后，阿牛就要求和seeyou一起分享这一瓶可乐，而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子，它们的容量分别是N 毫升和M 毫升 可乐的体积为S （S<101）毫升　(正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M，101＞S＞0，N＞0，M＞0) 。聪明的ACMER你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出"NO"。
 
Input&Output
输入三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量，以"0 0 0"结束。如果能平分的话请输出最少要倒的次数，否则输出"NO"。
 
Sample Input
7 4 3
4 1 3
0 0 0
 
Sample Output
NO
3

用最大公约数的角度思考，本质就是寻找一个最优化方程组的可能整数解;记录此题是因为用BFS写起来过于冗长，这种解决方法给我耳目一新的感觉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    int a,b,c;
    while(cin>>a>>b>>c&&(a&&b&&c))
    {
        a/=gcd(b,c);
        if(a&1)
            cout<<"NO"<<endl;
        else
            cout<<a-1<<endl;
    }
    return 0;
}

发表于 | 阅读次数:

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

Dijsktra单源最短路

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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。要访问路径，从最后一个节点递归访问即可。

1
2
3
4
5
6
7
8
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]那个步骤即可。以第一个情况为例：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    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这个点可以平等选择多个点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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中存放的值就是最短距离。
BF
此时如果不存在从源点可达的负环那么d中所有值应该达到最优了，对所有边在判断一次，如果仍然可以松弛，就说明存在从源点可达的负环返回false。其复杂度是O(n*Edge).

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

邻接链表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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];
                }
            }
        }
    }
}

发表于 | 阅读次数:

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

查找

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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也就是插入一系列节点的过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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为根的树中的最大或者最小权值的节点，用于辅助寻找前驱或后继。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    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);
        }
    }

发表于 | 阅读次数:

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

定义与新建节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//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; //返回新建节点的地址
}

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

查找与修改

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

1
2
3
4
5
6
7
8
9
10
11
12
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);
}

二叉树节点插入

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//注意根节点指针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。

1
2
3
4
5
6
7
8
9
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的先、中、后序遍历

1
2
3
4
5
6
7
8
9
10
void preOrder(node* root)
{
    if(root==NULL)
    {
        return;
    }
    printf("%d\n",root->data);
    preOrder(root->lchild);
    preOrder(root->rchild);
}

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

1
2
3
4
5
6
7
8
9
10
void inOrder(node* root)
{
    if(root==NULL)
    {
        return;
    }
    inOrder(root->lchild);
    printf("%d\n",root->data);
    inOrder(root->rchild);
}

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

1
2
3
4
5
6
7
8
9
10
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不为空就继续进行。

1
2
3
4
5
6
7
8
9
10
11
12
13
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就行。同时，调整一下遍历到节点的工作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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为右子树，以上均是闭区间。接着，就指用在左子树和右子树上递归构建二叉树即可。递归边界为当前先序序列已经没有元素了。其实有点像快速排序的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//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;
}

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

发表于 | 阅读次数:

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

  • 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中用于选择基尼指数最小的属性来作为最优划分属性。
    图片

发表于 | 阅读次数:

前言

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

1
2
3
4
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域，其地址由其索引决定。

创建链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#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;
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
}

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

1
2
3
4
5
6
7
8
9
10
11
12
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的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
        }
    }
}

链表反转

1
2
3
4
5
6
7
8
9
10
11
12
13
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
}

发表于 | 阅读次数:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//写一个匹配函数，（）可以分隔语义 ，\\进行转义
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() 所有匹配字符串之后的部分
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    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：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
  • $` 在源字符串中，在匹配正则表达式的子字符串左侧的部分
  • $’ 在源字符串中，在匹配正则表达式的子字符串右侧的部分
  • $$ 美元符号
    看一个简单例子：
    1
    2
    3
    4
    5
    int main() {
        string str = "11sigalhu22sigalhu33",str1;
        str1 = regex_replace(str,regex("s(igal)h(u)"),"SS$1HH$2");
        cout<<str1<<endl;
        //应该输出11SSigalHHu22SSigalHHu33