Docker compose

ArchLinux安装配置

安装系统

安装准备

我的是双系统的配置，在安装之前划分50GB的磁盘空间

1. 去官网下载镜像，制作usb启动盘
2. 开机进入usb的livecd内

操作系统

操作系统自从毕业后再未接触，当时学的也不是很好，这次重头在学，争取精通os的算法和概念.

迁移自己的服务

用docker把以前服务器上的一些服务打包推送到docker hub

Arduino开发 入门配置

单片机开发，得到了一块ESP8266芯片，可以选择micropython或者arduino的系统环境，虽然micropython使用python作为开发语言，简单很多，但是生态和库没有arduino丰富，这里选择了烧录arduino环境到芯片

Arduino 自定义库

Dijkstra迪杰斯特拉算法

最短路径算法

思路

个人感觉迪杰斯特拉算法和普利姆(Prime)算法很像都是从已有集合找到最小边开始，向集合内持续添加最小边的节点。首先写出所有节点的直接路径，从已有集合开始算到其他节点的最短距离，将在这一轮中找到的最小距离所在的节点录入集合，循环……

算法示例

以这个为例我们找出节点1到其他所有节点的最短距离

1
2
3
4
5
6

画出整张表格的框架，顶点 2，3，4，5 初始集合为1，第一轮查看1到2，3，4，5的距离分别为10，无穷，无穷，5。找出第一轮的最短距离为 1-5的距离，将5加入集合。之后再也不用关注5，因为已经是最短距离了（不存在经过其他节点更小的情况，可以自行推算）。

第一轮结束后，集合内有1，5两个节点，且5节点不用再关注了，第二轮开始：看刚刚假如的节点5到其他节点的距离再加上1-5的距离，看是否小于左边的距离，小的话就替换，5到2，3，4的距离分别为3，9，2，加上1到5的距离后为：8，14，7都比左边一列小，所以结果都覆写了，再次找到最小距离：1-5-4的距离7，将4假如集合。

循环到所有节点进入集合即可

代码实现

下次实现

FLOYD 最短路径算法

思路

佛洛依德最短路径实际上是使用了两个邻接矩阵遍历完成的 O(n^3)，一个邻接矩阵A用来保存点到点的路径权重，另一个B用来保存路径。

A的初始已经写好了点到点的直接距离，对于没有直连的点，内容都算作无穷。然后依次取中间点后再依次遍历通过这个中间点的距离，如果小于原来的A矩阵的内的距离，那么就覆写且将路径写入B矩阵。

图解例子

根据这个图做两个矩阵A（存储点到点的距离），B（存储经过点）

1

以上图为例，录入后的矩阵A，A[0][1]表示0节点到1节点的距离为5，A[1][0]就表示节点1到节点0的距离，无穷表示无法连接。

1

路径Path，对于B[0][1]表示 0节点到1节点需要经过什么节点

1
2
3
4
5
6
7
8
9
10

现在开始从头遍历，先找出节点对（就是图中什么节点可以到什么节点）有：

<0,1> <0,2> <0,3>
<1,0> <1,2> <1,3>
<2,0> <2,1> <2,3>
<3,0> <3,1> <3,2>

现在取中间节点0（挨个取0，1，2，3）:对于0节点来说0节点到某节点距离，使用0作为中间节点是无意义的，所以包含0节点的节点对都不看，从<1,2>开始，即1使用0节点作为中间节点到2 = 1到0的节点距离+ 0到2的节点距离，也就是 A[1,2] = A[1,0] + A[0,2]。如果这个距离是小于原来距离的那么就更新，这里4>无穷所以不更新。

每次算可能有点绕，这里有个技巧：假设还是算 A[1,2]以 X 作为中间节点，可以先找到 A[1,2]在图中的点，分别朝着两个 X 方向走（X 行和 X 列），看他们的和是否小于自己，小于就更新自己，且在B矩阵内更新B[1,2] = X。这里X可以是0，1，2，3节点。

如此遍历更新两个矩阵得到最后结果：

查找代码实现

现在我们得到了最后的更新结果，使用的话以A[1][0]为例，即1节点到0节点从A矩阵可以看到1节点到0节点距离6，根据Path矩阵，看到Path[1][0] = 3表示 1到0节点要经过3，再看1到3和3到0，Path[1][3] = -1表示1到3直连，查Path[3][0] = 2 表示3到0经过节点2，查看3-2和2-0结果是-1，所以最后路径是1-3-2-0，不难发现这个过程是递归的，代码实现较为简单如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/**
 * 打印节点x到节点y 经过的节点
 *
 * @param x
 * @param y
 * @param matrixPath 邻接矩阵的路径矩阵
 */
void printPath(int x, int y, int matrixPath[][]) {
    if (matrixPath[x][y] == -1) {
        // -1表示直连 输出
        System.out.println("直连");
    } else {
        // 要经过一个节点
        System.out.println("经过节点:" + matrixPath[x][y]);
        // 递归查找x与y到中间节点的中间节点
        printPath(x, matrixPath[x][y], matrixPath);
        printPath(matrixPath[x][y], y, matrixPath);
    }
}

最短路径实现

再看一下最短路径的过程会发现本质就是遍历更新两个表，从选取中间节点开始遍历，找到中间节点后遍历所有节点，对比节点的值

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

/**
 * 生成最短路径矩阵
 * 传入的矩阵都是方阵 即长宽一样的多维数组
 *
 * @param matrix     图的邻接矩阵表示，传入时已经写好了点到点的直接距离
 * @param matrixPath 图的路径矩阵
 */
void floydGenerate(int matrix[][], int matrixPath[][]) {
    // 初始化路径矩阵 -1表示直连 一开始所有点都算做直连，matrix保存了直连的距离，如果两个节点不能直连，那么算作距离无限大
    for (int i = 0; i < matrixPath.length; i++) {
        for (int j = 0; j < matrixPath.length; j++) {
            matrixPath[i][j] = -1;
        }
    }
    // 选取中间经过节点
    for (int passingByNode = 0; passingByNode < matrix.length; passingByNode++)
        // 选取节点对(开始节点和结束节点) 0-1 0-2 0-3 ...这样的
        for (int startNode = 0; startNode < matrix.length; startNode++)
            for (int endNode = 0; endNode < matrix.length; endNode++)
                // 计算开始节点到经过节点的值和经过节点到结束节点的值
                if (matrix[startNode][passingByNode] + matrix[passingByNode][endNode] < matrix[startNode][endNode]) {
                    matrix[startNode][endNode] = matrix[startNode][passingByNode] + matrix[passingByNode][endNode];
                    matrixPath[startNode][endNode] = passingByNode;
                }
}

我的Arch一年没更新 滚挂了

事情是这样的：好久没用另一台电脑，登入系统的时候打开chrome想更新下插件，好死不死的退了google账号，想重新登入的，发现google账号被疯狂登出，整了一个小时才发现是chrome的问题（我是弱智）。我用的是chrome的开源版：chromium，自从21年2月份开始google的登陆api收紧了政策，只有chrome可以登陆google账号。

一开始不知道这个政策，以为是chromiu的版本问题，事发的版本是83，我用pacman upgrade了下到了93的版本，启动chromium的时候提示动态链接库缺失。

这个问题其实我是知道的，因为arch的版本更新政策比较激进，可能半个月就更新了一次，且大部分上游的软件都依赖这些最新的库，所以如果是老系统更新新软件很容易出现动态链接库的问题，我本来也没在意，pacman -F 查了下软件包的依赖库，打算更新下以来。

但是！ 问题就出在了更新依赖库，我更新了一个底层依赖库 icu，导致我reboot的时候gnome-shell这些依赖老版本库的应用都无法启动了，只能进tty看了alt + ctrl +3

回退也很麻烦我都忘了刚刚的icu是啥版本了，还更新几个其他的库，这样看来，只能全盘更新了，但是全盘更新估计也是出问题的。原因一个是我的系统太久没更新了一年了，版本跨太大还不知道有啥bug。其次我的内核是自定义的用了签名机制，如果内核更新了，原来的内核哈希码肯定对应不上新的内核，必定失败的。没办法，怀着忐忑的心情 sudo pacman -Syu了

嗯 果然挂了

shim 签名问题

因为的内核是自定义编译的内核，比较适配我的surface硬件，为了美观开了secureboot，不然每次开机上面红色的锁的刺眼ui真的难受。secureboot是微软的一个机制，微软信任windows系统和几个第三放的bootloader（内核加载器）。这几个内核加载器呢需要我来指定内核，怎么指定呢，用shim签名（哈希）来做这件事。

举例：我的编译好的新内核，我用shim签名生成了哈希结果，我需要再下一次开机启动是enroll，引入这个签名，这样secureboot启动bootloader，bootlaoder查看自己的信任列表，有这个内核，可以启动。

签好名后还需要重新编写启动的配置文件，因为需要指定内核，真麻烦

重新配置内核引导

arch的livecd在做，家里突然没网了，下次整

Triangle

medium 经典入门dp问题 一次ac

 * 计算三角形中每行最小值组成的路径 实际也是个经典的dp问题，从低到上
 *    2
 *   3 4
 *  6 5 7
 * 4 1 8 3
 *
 * 从最底层开始：4，1，8，3 往上分别为 （10，7），（6，13），（15，10） 选出最小的7，6，10
 * 继续：9，10  最后：11