四月八日

• 内核5大核心功能

• 操作系统用于管理计算机资源，cpu资源，外围设备，内存

• 程序在调用文件的读写时，需要调用内核的功能，也叫做内核模式

• 用户在写自己的逻辑的时候，就是用户模式

• Process mannagement (进程管理) linux多任务系统，进程管理用于调度cpu

• Memory management 用于内存分配

• File systems 读写文件，终端输入输出，保存文件，linux树状结构也是有文件系统维护

• Device drivers 如何与硬件对接

• Network 对上提供socket, ssh http 都是应用层协议

树的种类

二叉树，索引树，红黑树，btree,B+tree,字典树，哈夫曼

结构特点

• 一定会有一个根节点root

• 每一个元素都被称为node

• 除了root节点，其余的节点都会被分成n个互不相交的集合

• 最末尾的节点，叫做叶子节点，其他节点叫子节点

• 深度：从根节点到叶子节点的最多的个数

• 度： 和深度的概念不同，分为出度（有多少个节点指向其他节点），和入度（有多少节点指向自己）

字典树

Trie Tree 又称为单词查找树，哈希树的变种，常用于统计，查找搜索引擎中用于分词，词频统计（DF/IDF）,自动补全等机制。

查找效率高：其核心思想是利用公共前缀来减少查询时间。

对于英文可以按常规字典树进行处理，因为英文只有二十六个字母，最多有26层

但是对于中文不能直接使用，因为不同的文字过多，同一层级的分支过多

字典树的实现

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

class Trie {
    constructor() {
        // 根节点
        this.root = Object.create(null);
        // 叶子节点标识
        this.end = Symbol('end');
    }

    //创建一颗树的方法
    insert(str) {
        let root = this.root;
        for (let s of str) {

            if (root[s] === undefined) {
                root[s] = Object.create(null);
            }
            root = root[s];
        }
        root[this.end] = true;
    }
    //查找是否存在某个单词
    find(str) {
        let root = this.root;
        for (let s of str) {
            if (root[s] === undefined) {
                return false;
            }
            root = root[s];
        }
        // 可以查到字符串中的每个字符，且最后一个字母是一个结束符
        return !!root[this.end]
    }
}

对于如何可以查找出现次数最多的单词，只需要为节点增加更多的信息

把上面基础示例中的结束标识符，修改一下，把值改为单词的出现次数，通过递归找到出现次数最多的单词

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
42
43
44
45
46
47
48

class Trie {
    constructor() {
        // 根节点
        this.root = Object.create(null);
        // 叶子节点标识
        this.$ = Symbol('$');
    }

    //创建一颗树的方法
    insert(str) {
        let root = this.root;
        for (let s of str) {

            if (root[s] === undefined) {
                root[s] = Object.create(null);
            }
            root = root[s];
        }
        if (!root[this.$]) root[this.$] = 0;
        root[this.$]++

    }
    findMost() {
        let root = this.root;
        //用于记录出现次数最多的单词
        let mostWord = [];
        let max = 0;

        const find = (word, root) => {
            if (root[this.$] && root[this.$] == max) {
                mostWord.push(word);
            }
            if (root[this.$] && root[this.$] > max) {
                max = root[this.$];
                mostWord = [word];
            }
            for (let s in root) {
                find(word + s, root[s]);
            }
        }
        find('', root);

        return {
            max,
            mostWord
        }
    }
}

通过字典树做自动提示

如果其中一个节点没有匹配到，返回null

如果最后一个节点之后还有子树，递归子树找出所有匹配字符串

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
42
43

class Trie {
    constructor() {
        // 根节点
        this.root = Object.create(null);
        // 叶子节点标识
        this.$ = Symbol('$');
    }

    //创建一颗树的方法
    insert(str) {
        let root = this.root;
        for (let s of str) {

            if (root[s] === undefined) {
                root[s] = Object.create(null);
            }
            root = root[s];
        }
        // 不需要关心是否有多个
        root[this.$] = true;
    }
    auto(str) {
        const autonode = [];
        let root = this.root;

        if (!str) return autonode;
        for (let s of str) {
            console.log(s);
            if (root[s] === undefined) {
                return autonode;
            }
            root = root[s];
        }
        const each = (word, root) => {
            if (root[this.$]) autonode.push(word)
            for (let s in root) {
                each(word + s, root[s]);
            }
        }
        each(str + '', root)
        return autonode;
    }
}

LeetCode

动态规划详解

确定状态

最后一步

考虑青如果能跳到最后一个位置,

那必须满足这样的关系：

• 如果是从位置上跳过来，必须能先跳到位置

• 位置上表示的步数大小必须大于或等于从到最后位置,即

子问题

把能否跳到位置的问题，转化位能否跳到位置的问题

且 问题规模缩小

状态

最终可以确定状态： 表示能否到最后位置

转移方程

• 通过最后一步的分析, 位置必须能到达，且位置 的步数与位置的和必须大于等于最后位置的索引 ,所以有

• 如何找到 是通过循环 ,只要可以找到一个满足的条件，那么

• 最终转移方程为

**注意:**为什么不能只找最近的进行判断？因为能否到达 受之前所有能到达位置的影响，而且最近的可到达位置，并不一定能到最终位置，例如 [3,0,0,5,0,0,1,0,1]

初始条件和边界情况

位置0为true

运算顺序

• 设 表示青蛙不能跳到石头

• 初始化 f[0]==true

• 计算 f[1],f[2]....,f[n-1]

• 返回结果为 f[n-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14

var canJump = function (nums) {
    var f = [true],
        n = nums.length;
    for (var j = 1; j < n; j++) {
        f[j] = false;
        for (var i = 0; i < j; i++) {
            if (f[i] && i + nums[i] >= j) {
                f[j] = true;
                break;
            }
        }
    }
    return f[n - 1];
};

复杂度分析

• 时间复杂度：,每次需要重复遍历已经遍历过的元素所以，

• 空间复杂度：

关机 / 重启

shutdown 命令可以 安全 关闭 或者 重新启动系统

提示:
不指定选项和参数 ,默认表示 1 分钟 之后 关闭电脑
远程维护服务器时,最好不要关闭系统,而应该重新启动系统

• 重新启动操作系统,其中 now 表示现在

1

$ shutdown -r now

• 立刻关机,其中 now 表示现在

1

$ shutdown now

• 系统在今天的 20:25 会关机

1

$ shutdown 20:25

• 系统再过十分钟后自动关机

1

$ shutdown +10

• 取消之前指定的关机计划

1

$ shutdown -c

查看或配置网卡信息

网卡

• 网卡是一个专门负责网络通讯的硬件设备
• IP 地址 是设置在网卡上的地址信息

们可以把 电脑 比作 电话 , 网卡 相当于 SIM 卡 , IP 地址 相当于 电话号码

IP 地址

• 每台联网的电脑上 都有 IP 地址 , 是保证电脑之间正常通讯的重要设置

注意:每台电脑的 IP 地址不能相同,否则会出现 IP 地址冲突,并且没有办法正常通讯
提示:有关 IP 地址 的详细内容,在就业班会详细讲解!

ifconfig

ifconfig 可以查看/配置计算机当前的网卡配置信息

需要现安装net-tools软件

• 查看网卡配置信息

1

$ ifconfig

• 查看网卡对应的 IP 地址

1

$ ifconfig | grep inet

提示:一台计算机中有可能会有一个 物理网卡 和 多个虚拟网卡 ,在 Linux 中物理网卡的名字通常以 ensXX 表示

127.0.0.1 被称为 本地回环 / 环回地址 ,一般用来测试本机网卡是否正常

ping

检测到目标主机是否连接正常

1

$ ping IP 地址

检测本地网卡工作正常

1

$ ping 127.0.0.1

• ping 一般用于检测当前计算机到目标计算机之间的网络 是否通畅 ,数值越大,速度越慢

ping 的工作原理与潜水艇的声纳相似,ping 这个命令就是取自 声纳的声音
网络管理员之间也常将 ping 用作动词 —— ping 一下计算机 X ,看他是否开着

原理:网络上的机器都有 唯一确定的 IP 地址 ,我们给目标 IP 地址 发送一个数据包,对方就要返回一个数据包,根据返回的数据包以及时间,我们可以确
定目标主机的存在

提示:在 Linux 中,想要终止一个终端程序的执行,绝大多数都可以使用 CTRL + C

远程登录和复制文件

ssh 基础

在 Linux 中 SSH 是 非常常用 的工具，通过 SSH 客户端 我们可以连接到运行了 SSH 服务器 的远程机器上

• SSH 客户端是一种使用 Secure Shell（SSH） 协议连接到远程计算机的软件程序

• SSH 是目前较可靠，专为远程登录会话和其他网络服务 提供安全性的协议

  • 利用 SSH 协议 可以有效防止远程管理过程中的信息泄露

  • 通过 SSH 协议 可以对所有传输的数据进行加密，也能够防止 DNS 欺骗和 IP 欺骗

• SSH 的另一项优点是传输的数据可以是经过压缩的，所以可以加快传输的速度

域名 和 端口号

域名

• 由一串 用点分隔 的名字组成，例如：www.iftrue.me
• 是 IP 地址 的别名，方便用户记忆

端口号

• IP 地址：通过 IP 地址 找到网络上的 计算机

• 端口号：通过 端口号 可以找到 计算机上运行的应用程序

  • SSH 服务器 的默认端口号是 22，如果是默认端口号，在连接的时候，可以省略常

• 常见服务端口号列表：

SSH 客户端的简单使用

如果没有安装先通过sudo apt install openssh-server安装ssh

1

ssh [-p port] user@remote

• user 是在远程机器上的用户名，如果不指定的话默认为当前用户
• remote 是远程机器的地址，可以是 IP／域名，或者是 后面会提到的别名
• port 是 SSH Server 监听的端口，如果不指定，就为默认值 22

• 使用 exit 退出当前用户的登录

• ssh 这个终端命令只能在 Linux 或者 UNIX 系统下使用,如果在 Windows 系统中，可以安装 PuTTY 或XShell 客户端软件即可

• 在工作中，SSH 服务器的端口号很有可能不是 22，如果遇到这种情况就需要使用 -p 选项，指定正确的端口号，否则无法正常连接到服务器

scp

• scp 就是 secure copy，是一个在 Linux 下用来进行 远程拷贝文件 的命令
• 它的地址格式与 ssh 基本相同，需要注意的是，在指定端口时用的是大写的 -P 而不是小写的

常见操作

• 把本地当前目录下的 01.py 文件 复制到 远程 家目录下的 Desktop/01.py
  注意：: 后面的路径如果不是绝对路径，则以用户的家目录作为参照路径

1

scp -P port 01.py user@remote:Desktop/01.py

• 加上 -r 选项可以传送文件夹,把当前目录下的 demo 文件夹 复制到 远程 家目录下的 Desktop

1

scp -r demo user@remote:Desktop

• 把远程 家目录下的 Desktop 复制到 当前目录下的 demo 文件夹

1

scp -r user@remote:Desktop demo

• 复制windows下面的文件到远程服务器

注意：
scp 这个终端命令只能在 Linux 或者 UNIX 系统下使用
如果在 Windows 系统中，可以安装 PuTTY，使用 pscp 命令行工具或者安装 FileZilla 使用 FTP 进行文件传输

免密码登录

提示：有关 SSH 配置信息都保存在用户家目录下的 .ssh 目录下

• 配置公钥

  执行 ssh-keygen 即可生成 SSH 钥匙，一路回车即可

• 上传公钥到服务器

  执行 ssh-copy-id -p port user@remote，可以让远程服务器记住我们的公钥

非对称加密算法

使用 公钥 加密的数据，需要使用 私钥 解密

使用 私钥 加密的数据，需要使用 公钥 解密

配置别名

每次都输入 ssh -p port user@remote，时间久了会觉得很麻烦，特别是当 user , remote 和 port 都得输入

在 ~/.ssh/config 里面追加以下内容：

1
2
3
4

Host 别名
  HostName ip地址
  User 用户名
  Port 22

保存之后，即可用 ssh mac 实现远程登录了， scp 同样可以使用

echo (有重复的意思)

echo 会在终端中显示参数指定的文字,通常会和 重定向 联合使用

重定向 > 和 >>

• Linux 允许将命令执行结果 重定向 到一个 文件

• 将本应显示在终端上的内容 输出/追加 到指定文件中

其中

• > 表示输出,会覆盖文件原有的内容

• >> 表示追加,会将内容追加到已有文件的末尾

注意: 通过touch创建的文件只能是空文件,但是配合echo使用,可以在创建文件的时候添加内容

管道 |

• Linux 允许将 一个命令的输出 可以通过管道 做为 另一个命令的输入

• 可以理解现实生活中的管子,管子的一头塞东西进去,另一头取出来,这里 | 的左右分为两端,左端塞东西(写),右端取东西(读)
  常用的管道命令有:

  • more :分屏显示内容

  • grep :在命令执行结果的基础上查询指定的文本

查看文件内容

内容较多时more命令会分页显示，cat命令会一次性显示

cat

• cat 命令可以用来 查看文件内容 、创建文件 、 文件合并 、追加文件内容 等功能

• cat 会一次显示所有的内容,适合 查看内容较少 的文本文件

Linux 中还有一个 nl 的命令和 cat -b 的效果等价

grep

• Linux 系统中 grep 命令是一种强大的文本搜索工具
• grep 允许对文本文件进行 模式 查找,所谓模式查找,又被称为正则表达式

vim使用方法

安装

1

sudo apt install vim

基本上 vi/vim 共分为三种模式，分别是命令模式（Command mode），输入模式（Insert mode）和底线命令模式（Last line mode）。 这三种模式的作用分别是：

• 命令模式

用户刚刚启动 vi/vim，便进入了命令模式。

此状态下敲击键盘动作会被Vim识别为命令，而非输入字符。比如我们此时按下i，并不会输入一个字符，i被当作了一个命令。

以下是常用的几个命令：

• i 切换到输入模式，以输入字符。

• x 删除当前光标所在处的字符。

• : 切换到底线命令模式，以在最底一行输入命令。

若想要编辑文本：启动Vim，进入了命令模式，按下i，切换到输入模式。

命令模式只有一些最基本的命令，因此仍要依靠底线命令模式输入更多命令。

• 输入模式

在命令模式下按下i就进入了输入模式。

在输入模式中，可以使用以下按键：

• 字符按键以及Shift组合，输入字符

• ENTER，回车键，换行

• BACK SPACE，退格键，删除光标前一个字符

• DEL，删除键，删除光标后一个字符

• 方向键，在文本中移动光标

• HOME/END，移动光标到行首/行尾

• Page Up/Page Down，上/下翻页

• Insert，切换光标为输入/替换模式，光标将变成竖线/下划线

• ESC，退出输入模式，切换到命令模式

• 底线命令模式

在命令模式下按下:（英文冒号）就进入了底线命令模式。

底线命令模式可以输入单个或多个字符的命令，可用的命令非常多。

在底线命令模式中，基本的命令有（已经省略了冒号）：

• q 退出程序

• w 保存文件

按ESC键可随时退出底线命令模式。

tree

• tree 命令可以以树状图列出文件目录结构

cp

cp 命令的功能是将给出的 文件 或 目录 复制到另一个 文件 或 目录 中,相当于 DOS 下的 copy 命令

如果文件名相同可以不指定目标文件名，只写目标路径

mv

mv 命令可以用来 移动 文件 或 目录 ,也可以给 文件或目录重命名

在同目录下移动实现修改文件的名字,为了防止覆盖可以加上 -i参数

LeetCode

暴力解法 哈希表

保存每一个节点判断

1
2
3
4
5
6
7
8
9
10
11
12

var detectCycle = function(head) {
   var map = new Map();
   var cur = head;
    while(cur!==null){
        if(map.get(cur)===cur){
            return cur;
        }
        map.set(cur,cur);
        cur = cur.next;
    }
    return null;
};

复杂度分析

• 时间复杂度：

• 空间复杂度：

双指针

快慢指针同时移动，第一次相遇后，定义新指针为头节点，新指针和慢指针同时移动，再次相遇时的节点为入环节点

通过数学演变来确认双指针的正确性,如下图

• 设慢指针的移动速度为，快指针的移动速度为,用 来表示走过的步数

• 那么慢指针走到相遇点的时候走过,快指针走过了

• 可以得到

• 所以从相遇点到入环点的步数和从头节点到入环的步数是相同的

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

var detectCycle = function(head) {
    var fast = head;
    var slow = head;
    var res = head;
    while(fast!==null && fast.next!==null){
        fast = fast.next.next;
        slow = slow.next;
        if(slow===fast){
            while(res!==fast){
                res = res.next;
                fast = fast.next;
            }
            return res;
        }
    }
    return null;
};

复杂度分析

• 时间复杂度：

• 空间复杂度：

LeetCode

注意

原生API

1
2
3

var reverseString = function(){
    return s.reverse();
}

循环

从前向后两两交换字母位置,n为数组s的长度，那么只需要n/2次就可以调换所有的顺序

1
2
3
4
5
6
7
8
9
10
11

var reverseString = function (s) {
    var len = s.length,
        middle = Math.ceil(s.length / 2),
        i = 0;
    for (; i < middle; i++) {
        var temp = s[i];
        s[i] = s[len - i - 1];
        s[len - i - 1] = temp;
    }
    return s;
};

双指针

与循环方法相似，需要left,right两个指针，分别向中间移动，当两个指针相等时，交换完成

1
2
3
4
5
6
7
8
9
10
11
12

var reverseString = function (s) {
    var left = 0,
        right = s.length - 1;
    while (left <= right) {
        var temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        left++;
        right--;
    }
    return s;
}

复杂度分析

• 时间复杂度： 只需要遍历 次。

• 空间复杂度： 不需要额外空间

LeetCode

暴力解法 哈希表

把每一个遇到的节点都保存下来

• 如果当前节点为null表示没有环，返回false

• 如果在map中当前节点存在则表示有环，否则存下当前节点

1
2
3
4
5
6
7
8
9
10
11

var hasCycle = function (head) {
    var map = new Map();
    while(head!==null){
        if(map.get(head)===head){
            return true;
        }
        map.set(head,head);
        head = head.next;
    }
    return false;
};

复杂度分析

• 时间复杂度：，其中 是链表中的节点数。最坏情况下我们需要遍历每个节点一次。

• 空间复杂度：，其中 是链表中的节点数。主要为哈希表的开销，最坏情况下我们需要将每个节点插入到哈希表中一次。

快慢指针

「Floyd 判圈算法」(又称龟兔赛跑算法)。

1
2
3
4
5
6
7
8
9
10

var hasCycle = function (head) {
    var fast = head;
    var slow = head;
    while (fast !== null && fast.next !== null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast === slow) return true;
    }
    return false;
};

1
2
3
4
5
6
7
8
9
10
11

var hasCycle = function (head) {
    if (head===null || head.next===null) return false;
    var fast = head.next;
    var slow = head;
    while (fast!==slow) {
        if (fast===null || fast.next===null) return false;
        fast = fast.next.next;
        slow = slow.next;
    }
    return true;
};

复杂度分析

• 时间复杂度：,当链表中不存在环时，快指针将先于慢指针到达链表尾部，链表中每个节点至多被访问两次。当链表中存在环时，每一轮移动后，快慢指针的距离将减小一。而初始距离为环的长度，因此至多移动 轮。

• 空间复杂度：，我们只使用了两个指针的额外空间。