利用Git进行自动化多分支部署

创建Git用户用于自动部署

新建用户

useradd git

设置密码

passwd git

配置无法shell登录

1
vi /etc/passwd
2
git:x:1000:1000::/home/git:/usr/bin/git-shell

云端自动部署配置

新建裸仓库

1
git init --bare /opt/webapps/project-bare.git
2
cd /opt/webapps/project-bare.git/hooks
3
cp post-update.sample post-update
4
vi post-update

多分支部署

1
#!/bin/sh
2
3
unset GIT_DIR
4
mkdir -p /opt/webapps/project
5
cd /opt/webapps/project || exit
6
7
# 获取当前分支和目标分支
8
CURR_BRANCH=$(git symbolic-ref --short -q HEAD)
9
echo "current branch: ${CURR_BRANCH}"
10
TARGET_BRANCH=$(echo "$1" | awk -F/ '{print $3}')
11
echo "target branch: ${TARGET_BRANCH}"
12
13
# 初始化仓库
14
git init
15
git remote add origin /opt/webapps/project-bare.git
16
# 清除未跟踪或未暂存的代码
17
git reset --hard
18
git clean -df
19
20
# 拉取远端所有分支最新代码
21
git fetch origin
22
# 如果是删除分支操作,则切到master分支并删除该分支,要求不能删除远端master分支
23
if [ ! -f "/opt/webapps/project-bare.git/refs/heads/${TARGET_BRANCH}" ]
24
then
25
    echo "target branch ${TARGET_BRANCH} has been deleted"
26
    # 如果是当前分支,需要切换到master分支
27
    if [ "${TARGET_BRANCH}" = "${CURR_BRANCH}" ]
28
    then
29
        git checkout master
30
    fi
31
    # 删除本地同名分支
32
    git branch -D "${TARGET_BRANCH}"
33
else
34
    if [ "${TARGET_BRANCH}" = "${CURR_BRANCH}" ]
35
    then
36
        echo "same branch! rebase origin/${TARGET_BRANCH}."
37
        git rebase origin/"${TARGET_BRANCH}"
38
    else
39
        echo "different branch! checkout to ${TARGET_BRANCH}."
40
        git branch -D "${TARGET_BRANCH}"
41
        git checkout -b "${TARGET_BRANCH}" origin/"${TARGET_BRANCH}"
42
    fi
43
fi
44
45
echo "pull done"
46
47
# 业务服务启动逻辑
48
npm install
49
50
rm -rf dist
51
npm run build
52
53
pm2 restart project
54
echo "deployment done"

设置权限

1
chown -R git.git /opt/webapps/project-bare.git

新建代码仓库目录

1
mkdir /opt/webapps/project
2
chown -R git.git /opt/webapps/project

本地设置自动部署

1
git remote add deployment git@www.huhaoyu.com:/opt/webapps/project-bare.git
2
git push deployment master

聚类算法概述(k-Means++/FCM/凝聚层次聚类/DBSCAN)

参考自初识聚类算法:K均值、凝聚层次聚类和DBSCAN模糊聚类FCM算法

聚类的目的

将数据划分为若干个簇,簇内相似性大,簇间相似性小,聚类效果好。用于从数据中提取信息和规律。

聚类的概念

  • 层次与划分:当允许存在子簇时,将数据按照层次划分,最终得到的是一颗树。树中包含的层次关系即为聚类划分的层次关系。各个子簇不重叠,每个元素都隶属于某个level的子簇中。
  • 互斥、重叠与模糊:这个概念的核心在于,所有集合元素都不完全隶属于任何一个簇,而是按照一定隶属度归属于所有簇。对于任意一个元素,其隶属度和一般为1。
  • 完全与部分:完全聚类要求所有数据元素都必须有隶属,而部分聚类则允许噪音存在,不隶属于任何簇。

簇的分类

  • 明显分离:不同簇间任意元素距离都大于簇内元素距离。从图像上观察是明显分离类型的簇。
  • 基于原型:任意元素与它所隶属的簇的簇中心(簇内元素集合的质心)的距离大于到其他簇中心的距离。
  • 基于图:图中节点为对象,弧权值为距离。类似于明显分离的定义或基于原型的定义,只是用弧权值代替了人为规定的距离。
  • 基于密度:基于密度的簇分类是较为常用,也是应用范围最为广泛的一种分类方法。元素的稠密程度决定了簇的分布。当存在并希望分辨噪声时,或簇形状不规则时,往往采用基于密度的簇分类。

常用的聚类分析算法

  • 基本k均值:即k-means算法。簇的分类是基于原型的。用于已知簇个数的情况,且要求簇的形状基本满足圆形,不能区分噪声。
  • 凝聚层次聚类:起初各个点为一个簇,而后按照距离最近凝聚,知道凝聚得到的簇个数满足用户要求。
  • DBscan:基于密度和划分的聚类方法。

Troubleshooting GitHub Pages build failures——解决GitHub Pages部署失败问题

If your GitHub Pages site fails to build on our servers, we’ll send you an email letting you know about the failure. In most cases, we’ll be able to identify the exact file and error so you can fix it and push again.

如果你的GitHub Pages网站无法在服务器上部署,我们讲发送一封邮件给您,让您了解失败的原因。大多数情况下,我们能够找到发生错误的文件以及错误的类型,你可以修复问题并重新推送到GitHub。

Generic failures–一般故障

These build failures will not produce an email with specific file and error information. If you receive an email that simply says “Page build failed” with no further details, or your GitHub Pages site is not showing up after the first push, check for the following common errors:

这类错误不会在email中显示确切的文件及错误信息。如果你收到的邮件简单地显示“Page build failed”,且没有更多额外信息,或你的GitHub Pages网站在您推送到GitHub后并没有显示,请检查如下几个常见的错误:

Unverified email address–未认证的email地址

To trigger a build, the user who pushes a commit to the Pages repository must have a verified email address.

After you verify an email address, you’ll need to push to the repository again to trigger the build process on our servers. You can also contact GitHub support to manually run a build.

为部署您的个人网页,用户推送的commit必须有一个经认证的email地址。

当email经过认证后,你需要再次向你的远程仓库推送commit以保证服务器为您生成网页。你也可以联系GitHub支持来人工地生成网页。

Deploy key used for push–推送所需的部署公钥

Pushes must come from a user account with a verified email address. You won’t trigger a build if you use a deploy key to push to an organization’s Pages repository.

Instead, you can set up a machine user as a member of your organization.

推送必须来自一个经email地址认证的帐户。如果您使用一个部署公钥去推送commit到一个组织的网页仓库,这将不能触发部署动作。

相反的,你能够设置一个machine用户作为你组织的一个成员。

清华大学研读间预约应用

Tutu-Android 清华小图

  • 还在为预定不到文图研读间而愁眉苦脸,每晚熬到零点只为抢到一个研读间才能安心睡觉吗?
  • 还在因不知道文图剩余座位为零而白跑一趟,或傻傻苦等吗?
  • 总因为赶不上研读间预约时间而承担着违约的风险,最终导致一个月无法预订研读间吗?
  • 不用怕,不担心,清华小图来帮你:D!

清华小图的简介

清华小图是一款面向全清华的师生的文科图书馆研读间智能预约助手。小图会为你提供全方位的文图研读间预订服务。包括研读间的筛选、普通预约、修改、退订,研读间的智能预约、智能推荐,研读间的自动预约、定时轮询,个人预约信息和学籍信息的查询,文图剩余自习座位实时查询。您可以在任意时刻切换账户或退出登录,您也可以随时与开发者通过问题反馈沟通报告bug。

硬币分堆问题

题目

  • 有23枚硬币在桌上,10枚正面朝上。假设别人蒙住你的眼睛,而你的手又摸不出硬币的反正面。让你用最好的方法把这些硬币分成两堆,每堆正面朝上的硬币个数相同。
  • 或一个更普遍的问题:有$n$枚硬币在桌上,$k$枚正面朝上。假设别人蒙住你的眼睛,而你的手又摸不出硬币的反正面。让你用最好的方法把这些硬币分成两堆,每堆正面朝上的硬币个数相同。

分析

  • 将$n$枚硬币分为2堆,A堆$k$枚,B堆$n-k$枚。
  • 假设A堆中正面硬币有$x$枚,则有如下关系:
    • A中:正面硬币$x$枚,反面硬币$k-x$枚;
    • B中:正面硬币$k-x$枚;
  • 将A堆所有硬币翻面。
  • A堆和B堆中正面硬币数均为$k-x$枚。

翻硬币问题

题目

总共有$n$枚硬币均正面朝上,规则规定每次只能将其中$p$枚硬币翻面($1≤p≤n$)。问最少需要多少次操作才能将所有硬币翻面。

思路

  • 先进行$n/p$次操作,将$(n/p - 1)*p$枚硬币翻面,令$r = n % p$,则剩余$r + p$;
  • 考虑将其中$x$枚反面朝上的硬币翻面,$p - x$枚正面朝上的硬币翻面;
  • 此时剩余正面向上的硬币总数为$x + r + p - (p - x) = p$,解方程得$x = (p - r) / 2$;
  • 方程有解的前提是$x$为偶数,故$p$和$r$应同奇偶,如$p$为奇数,每做一次操作,正面向上的硬币总数变换奇偶性
  • 现在讨论$n$和$p$的奇偶关系:
    • $n$为奇数,$p$为奇数:计$k$为$n/p$向上取整
      • $k$为奇数,可行
      • $k$为偶数,无解
    • $n$为偶数,$p$为偶数:可行
    • $n$为奇数,$p$为偶数:无解
    • $n$为偶数,$p$为奇数:计$k$为$n/p$向上取整
      • $k$为偶数,可行
      • $k$为奇数,无解
  • 应注意$n/p$介于1到2之间的情况。

答案

如满足上述奇偶讨论的要求:

  • 当$n/p$介于1到2之间时,答案为3;
  • 当$n/p$大于等于2时,答案为$n/p$向上取整;

不满足则无解。

猜数字

两人玩游戏,在脑门上贴数字(正整数>=1),只看见对方的,看不见自己的,而且两人的数字相差1,以下是两人的对话: A:我不知道 B:我也不知道 A:我知道了 B:我也知道了 问A头上的字是多少,B头上的字是多少?
2种解题思路将引出不同的答案,十分有趣。

解法1

A是3,B是2。A看到2,想到自己是1或者3,所以不知道。B看到3,想到自己是2或者4,然后B也说不知道。然后A说知道了,假如A是1的话,B肯定会说自己是2的。但是B说不知道,那么A肯定是3,那么A确定了自己是3,表示知道了。B知道了A是3,那么只有B是2的时候,A才能确定这个状况,B是4的时候,A是不可能依靠两次就能判断出自己的。

解法2

A说不知道,说明B不是1,否则A直接知道自己是2了,此时B说自己不知道,说明A不是1,也不是2(因为如果A是2,则B可以直接知道自己是3)。然后A说知道了,A看到B是3,自己又不可能是2,所以一定是4。

结论

此题有漏洞,A、B如果猜数解法不同,则得到的数字是不一样的。

把西瓜切九刀最多切几块

题目

按平面切割,且保持形状始终为球形,把西瓜切九刀最多切几块?

分析

  • 假设一个n维空间切k刀,最多切成$A(n,k)$块。
  • $A(n,k)=A(n,k-1)+A(n-1,k-1)$
  • $A(n,k)=C(k,0)+C(k,1)+…+C(k,n)$
  • 切9刀,$A(3,9)=C(9,0)+C(9,1)+C(9,2)+C(9,3)=130$

AC自动机及多模式匹配

  • 在接触AC自动机之前,只仅仅掌握单模式匹配的算法:比如KMP、BMH等算法;经过优化后,KMP和BMH都具有线性时间复杂度,而实际情况下,一般的匹配问题BMH具有亚线性的表现。而昨天接触的AC自动机则是一种结合了字典树和KMP的一种算法,使得在多模式匹配下,时间复杂度达到$O(Σmi + n)$,其中n为原串长度,mi为第i个模式串的长度;
  • 匹配过程中类似于KMP,原串不走回头路,利用之前已经匹配过的结果来构造特殊的字典树从而形成AC自动机;
  • 创建自动机的过程中,最为重要的是fail指针的构造;我是从这篇文章中学会的,AC自动机算法详解;fail指针的作用类似于KMP中的next数组;
  • 我的这个模板中并没有考虑对自动机的优化, 比如ptr->fail->next[i]ptr->next[i]若同时不存在, 则ptr->fail其实是可以直接指向ptr->fail->fail的原因很简单, 因为ptr->next[i]发生失配时, ptr = ptr->fail, 此时肯定仍然失配, 需要继续ptr->fail,当然优化的代价是增加对存储空间的占用, fail需要变为vector<trieTreeNode*> fail,每个字母都应对应一个fail指针。
1
////////////////////////////////////////////////////////////////////////////////
2
/*
3
1 const vector<string> &patterns: several pattern strings;
4
2 const string &s: original strings;
5
3 vector<string> &answer: the patterns which are matched in the original strings;
6
4 return the number of patterns which are matched.
7
*/
8
////////////////////////////////////////////////////////////////////////////////
9
#include <iostream>
10
#include <vector>
11
#include <queue>
12
#include <string>
13
#include <unordered_set>
14
#define ALPH_NUM 26
15
using namespace std;
16
17
struct trieTreeNode {
18
    vector<trieTreeNode*> next;
19
    bool mark;
20
    trieTreeNode *fail;
21
    trieTreeNode(): next(26, nullptr), mark(false), fail(nullptr) {}
22
};
23
24
trieTreeNode *createAcAutomation(const vector<string> &patterns);
25
int findPatterns(vector<string> &answer, trieTreeNode *root, const string &s);
26
void makeFoundPatterns(vector<string> &answer, unordered_set<trieTreeNode*> &save, trieTreeNode *root, string pattern);
27
inline char turn_char(int index);
28
int multiPatternsMatchingByAcAutomation(const vector<string> &patterns, const string &s, vector<string> &answer);
29
30
trieTreeNode *createAcAutomation(const vector<string> &patterns) {
31
    trieTreeNode *root = new trieTreeNode(), *ptr, *cur;
32
    for (int i = 0; i != patterns.size(); ++i) {
33
        cur = root;
34
        for (int k = 0; k != patterns[i].size(); ++k) {
35
            int index = patterns[i][k] - 'a';
36
            if (!cur->next[index])
37
                cur->next[index] = new trieTreeNode();
38
            cur = cur->next[index];
39
        }
40
        cur->mark = true;
41
    }
42
    queue<trieTreeNode*> makeFail;
43
    makeFail.push(root);
44
    while (!makeFail.empty()) {
45
        cur = makeFail.front(); makeFail.pop();
46
        for (int i = 0; i != ALPH_NUM; ++i) {
47
            if (cur->next[i]) {
48
                for (ptr = cur->fail; ptr && !ptr->next[i]; ptr = ptr->fail);
49
                cur->next[i]->fail = ptr ? ptr->next[i] : root;
50
                makeFail.push(cur->next[i]);
51
            }
52
        }
53
    }
54
    return root;
55
}
56
57
int findPatterns(vector<string> &answer, trieTreeNode *root, const string &s) {
58
    int count = 0;
59
    string pattern;
60
    unordered_set<trieTreeNode*> save;
61
    trieTreeNode *cur = root;
62
    for (int i = 0; i != s.size(); ) {
63
        int index = s[i] - 'a';
64
        if (!cur) {
65
            cur = root; ++i;
66
        }
67
        else if (cur->next[index]) {
68
            cur = cur->next[index];
69
            if (cur->mark) {
70
                ++count;
71
                save.insert(cur);
72
            }
73
            ++i;
74
        }
75
        else {
76
            cur = cur->fail;
77
            if (cur && cur->mark) {
78
                ++count;
79
                save.insert(cur);
80
            }
81
        }
82
    }
83
    makeFoundPatterns(answer, save, root, pattern);
84
    return count;
85
}
86
87
void makeFoundPatterns(vector<string> &answer, unordered_set<trieTreeNode*> &save,
88
    trieTreeNode *root, string pattern) {
89
    unordered_set<trieTreeNode*>::iterator it = save.find(root);
90
    if (it != save.end())
91
        answer.push_back(pattern);
92
    for (int i = 0; i != ALPH_NUM; ++i) {
93
        if (root->next[i]) {
94
            string t(pattern);
95
            t.push_back(turn_char(i));
96
            makeFoundPatterns(answer, save, root->next[i], t);
97
        }
98
    }
99
}
100
101
inline char turn_char(int index) {
102
    return 'a' + index;
103
}
104
105
int multiPatternsMatchingByAcAutomation(const vector<string> &patterns, const string &s, vector<string> &answer) {
106
    trieTreeNode *root = createAcAutomation(patterns);
107
    return findPatterns(answer, root, s);
108
}

二叉树与森林的转换

思路

  • 利用递归建立节点完成转换。首先我们观察二叉树的结构,包含第一个孩子,及其兄弟。关键在于:那么我们在构造递归时,每层recursion中都必须找到对应sibling和firstchild。对于双亲表示法,我们很难找到孩子,对于孩子表示法,我们很难找到双亲(因为找到双亲是找到本节点兄弟的唯一方法,或在传参时也传入父节点指针)。
  • 不同形式间转换的技巧。对于要被转换的结构,需要传入针对它单次recursion完成结构内部所有成员构造对应的转换的结构的信息。就能完成一层递归。同时应注意递归结束的条件。

孩子表示法生成二叉树算法

1
typedef struct BiTree{
2
    ElemType data;
3
    struct BiTree *firstchild, *sibling;
4
}BTnode, *BTree;
5
6
typedef struct Lnode{
7
    int child;
8
    struct Lnode *next;
9
}Lnode, *CList;
10
typedef struct Cbox{
11
    ElemType data;
12
    CList firstchild;
13
}Cbox, *Cnode;
14
typedef struct CTnode{
15
    Cnode node;
16
    int n, r;
17
}CTree;
18
19
void TransformChildTreeToBinaryTree(CTree CT, BTree &BT, int preroot, int root){
20
    if (root == -1){
21
        BT = NULL; return;
22
    }
23
    BT = (BTree)malloc(sizeof(BTnode));
24
    BT->data = CT.node[root].data;
25
    int rsave;
26
    if (CT.node[root].firstchild){
27
        rsave = CT.node[root].firstchild->child;
28
    }
29
    else{
30
        rsave = -1;
31
    }
32
    TransformChildTreeToBinaryTree(CT, BT->firstchild, root, rsave);
33
    if (preroot == -1){
34
        BT->sibling = NULL; return;
35
    }
36
    CList p = CT.node[preroot].firstchild;
37
    while (p && p->data != root){
38
        p = p->next;
39
    }
40
    if (p->next){
41
        rsave = p->next->child;
42
    }
43
    else{
44
        rsave = -1;
45
    }
46
    TransformChildTreeToBinaryTree(CT, BT->sibling, preroot, rsave);
47
    return;
48
}

孩子双亲表示法生成二叉树(类似于孩子表示法)

1
typedef struct BTnode{
2
    ElemType data;
3
    struct BTnode *firstchild, *sibling;
4
}BTnode, *BTree;
5
6
typedef struct Cnode{
7
    int child;
8
    struct Cnode *next;
9
}Cnode, *CList;
10
typedef struct CTnode{
11
    int parent;
12
    ElemType data;
13
    CList firstchild;
14
}CTnode, *CTbox;
15
typedef struct PCTnode{
16
    CTbox node;
17
    int r, n;
18
}PCTree;
19
20
void TransformPCTreeToBiTree(PCTree PC, BTree &BT, int root){
21
    if (root == -1){
22
        BT = NULL; return;
23
    }
24
    BT = (BTree)malloc(sizeof(BTnode));
25
    BT->data = PC.node[root].data;
26
    int rsave, tmp;
27
    if (PC.node[root].firstchild){
28
        rsave = PC.node[root].firstchide->child;
29
    }
30
    else{
31
        rsave = -1;
32
    }
33
    TransformPCTreeToBiTree(PC, BT->firstchild, rsave);
34
    tmp = PC.node[root].parent;
35
    if (tmp == -1){
36
        BT->sibling = NULL; return;
37
    }
38
    else{
39
        LList p = PC.node[tmp].firstchild;
40
        while (p && p->child != root){
41
            p = p->next;
42
        }
43
        if (p->next){
44
            rsave = p->next->child;
45
        }
46
        else{
47
            rsave = -1;
48
        }
49
        TransformPCTreeToBiTree(PC, BT->sibling, rsave);
50
        return;
51
    }
52
}

同构链式孩子表示法生成二叉树

1
typedef struct BTnode{
2
    ElemType data;
3
    struct BTnode *firstchild, *sibling;
4
}BTnode, *BTree;
5
6
#define DEGREE 5
7
typedef struct LCTnode{
8
    ElemType data;
9
    struct LCTnode *child[DEGREE];
10
}LCTnode, *LCTree;
11
12
13
BTree InitialTransLCTree2BiTree(LCTree root){
14
    if (!root){
15
        return NULL;
16
    }
17
    BTree BTroot = (BTree)malloc(sizeof(BTnode));
18
    BTroot->data = LCTree->data;
19
    BTroot->sibling = NULL;
20
    TransformLinkedChildTreeToBinaryTree(BTroot->firstchild, root, 0);
21
    return BTroot;
22
}
23
void TransformLinkedChildTreeToBinaryTree(BTree &BT, LCTree LCT, int i){
24
    if (i >= DEGREE || !LCT->child[i]){
25
        BT = NULL; return;
26
    }
27
    BT = (BTree)malloc(sizeof(BTnode));
28
    BT->data = LCT->child[i]->data;
29
    TransformLinkedChildTreeToBinaryTree(BT, LCT->sibling, i + 1);
30
    TransformLinkedChildTreeToBinaryTree(BT->child[i], LCT->firstchild, 0);
31
    return;
32
}

异构链式孩子表示法生成二叉树

1
typedef struct BTnode{
2
    ElemType data;
3
    struct BTnode *firstchild, *sibling;
4
}BTnode, *BTree;
5
6
#ifdef DEGREE
7
#undef DEGREE
8
#define DEGREE 5
9
#endif
10
11
typedef struct LCTnode{
12
    ElemType data;
13
    struct LCTnode * *child;
14
    int degree;
15
}LCTnode, *LCTree;
16
17
void TransformLCTree2BinaryTree(LCTree LCT, BTree &BT, int i){
18
    if (i >= LCT->degree || !LCT->child[i]){
19
        BT = NULL; return;
20
    }
21
    BT = (BTree)malloc(sizeof(BTnode));
22
    BT->data = LCT->child[i]->data;
23
    TransformLCTree2BinaryTree(LCT, BT->sibling, i + 1);
24
    TransformLCTree2BinaryTree(LCT->child[i], BT->firstchild, 0);
25
    return;
26
}
27
28
//Another Method:
29
void TransformLCTree2BinaryTree2(LCTree LCT, BTree &BT){
30
    if (!LCT->child[0]){
31
        BT = NULL; return;
32
    }
33
    BTree p, q;
34
    for (int i = 0; i < LCT->degree && LCT->child[i]; ++i){
35
        BTree q = (BTree)malloc(sizeof(BTnode));
36
        q->data = LCT->child[i]->data;
37
        q->sibling = NULL;
38
        q->firstchild = NULL;
39
        if (!BT){
40
            BT = q;
41
            p = q;
42
        }
43
        else{
44
            q->sibling = p->sibling; p->sibling = q;
45
            p = q;
46
        }
47
        TransformLCTree2BinaryTree2(LCT->child[i], q->firstchild);
48
        return;
49
    }
50
}

有两种方法的思路不同:前者是按单个节点完成递归,而后者则是按照层来递归(虽然二者都是深度优先),后者更像是图的遍历方法。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×