哈夫曼树|数据结构|js

原理: 通过实数集S = { s1, s2, s3 … s} 来扩充二叉树, 其带权外部路径长度（WPL）达到最小的树称为哈夫曼树。
例子: {2, 3, 4, 11} 的WPL 可能为(34, 54, 40) 那么WPL为34的为树哈夫曼树。
实现: 通过优先队列，弹出最小的两个树，并构成新的子树，新的子树的根节点为两个树跟节点的和，比如 (2, 3) 新的节点为 5, 并把树压入队列中一直循环，直到队列中只存在一颗树。

使用valueOf重载运算符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class _Node {
  constructor(data = null, left = null, right = null) {
    this.data = data
    this.left = left
    this.right = right
  }

  valueOf() {
    return this.data
  }
}

// 工厂函数
const Node = (data, left = null, right = null) => {
  return new _Node(data, left, right)
}

阅读更多
二叉树的遍历|数据结构|js-深度优先-广度优先

原理: 根据二叉树的子树也是一个二叉树来遍历整个二叉树的节点。
深度优先： 前序、中序、后序是相对与根节点的访问顺序来命名的。

  • 前序遍历：先访问树的根节点， 在访问左右子树。DLR
  • 中序遍历：(也称对称序)先访问左子树， 在访问根节点， 后访问右节点。LDR
  • 后序遍历：先访问树的左右子树， 在访问根节点。LRD

广度优先：通过队列来缓存访问的节点， 如果访问的节点包含左右子树则依次入队保证层级关系。

阅读更多
堆和优先队列|数据结构|js-堆-小顶堆

堆是在节点上存储数据的完全二叉树， 小顶堆是把对中最小值一直保持在堆顶的树型结构。其中主要通过替换父子节点来实现

  • 向上筛选： 将新的值插入到堆尾，并通过与父节点(循环)比较来对换位置。
  • 向下筛选： 将堆尾放入到已弹出的堆顶部，通过与子节点(循环)比较来对换位置。

小顶堆实现过程

阅读更多
表达式树|数据结构|js-表达式树

将树的节点和叶子节点分别当做操作符和操作数，用来描述表达式的方式叫表达式树。比如: (1 + 2) \* (5 - 3) 的表达式树

表达式树

下面是表达式树的代码， 首先通过栈来存储操作符和操作数

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
class Stack {
  constructor() {
    this.list = []
  }

  getSize() {
    return this.list.length
  }

  isEmpty() {
    return this.getSize() === 0
  }

  push(e) {
    this.list.push(e)
  }

  pop() {
    return this.list.pop()
  }

  top() {
    if (this.getSize() === 0) {
      return null
    }
    return this.list[this.getSize() - 1]
  }
}
阅读更多
mysql 解决emoji插入问题|后端|docker-mysql

原因

一般设置 mysql 字符时都会使用 utf8 字符编码，但是最近文本中插入 emoji 表情的时候遇到了麻烦，只要文本中有 emoji 表情存入数据库的时候就会报错。

解决方法

emoji 使用 4 个字节，utf8 一个字符最多三个字节，如果想使用 emoji 表情的话就得使用 utf8mb4 字符编码(扩展到一个字符 4 个字节)。

解决

首先查看表字段的字符集

1
show full columns from article;

显示内容

1
2
3
4
5
6
7
8
9
10
11
12
13
+-------------+--------------+-----------------+------+-----+---------+-------+---------------------------------+---------+
| Field       | Type         | Collation       | Null | Key | Default | Extra | Privileges                      | Comment |
+-------------+--------------+-----------------+------+-----+---------+-------+---------------------------------+---------+
| id          | varchar(16)  | utf8_general_ci | NO   | PRI | NULL    |       | select,insert,update,references |         |
| title       | varchar(255) | utf8_general_ci | NO   |     | NULL    |       | select,insert,update,references |         |
| content     | text         | utf8_general_ci | NO   |     | NULL    |       | select,insert,update,references |         |
| status      | int(11)      | NULL            | YES  |     | NULL    |       | select,insert,update,references |         |
| create_time | datetime     | NULL            | YES  |     | NULL    |       | select,insert,update,references |         |
| update_time | datetime     | NULL            | YES  |     | NULL    |       | select,insert,update,references |         |
| category_id | varchar(16)  | utf8_general_ci | NO   |     | NULL    |       | select,insert,update,references |         |
| seo_id      | varchar(16)  | utf8_general_ci | YES  |     | NULL    |       | select,insert,update,references |         |
| count       | int(11)      | NULL            | YES  |     | NULL    |       | select,insert,update,references |         |
+-------------+--------------+-----------------+------+-----+---------+-------+---------------------------------+---------+
阅读更多
迷宫探索|数据结构|js-迷宫探索

原理

利用递归来检测当前 postion 是否是迷宫的出口。mark 用来标记已走过的路，如果当前位置已走过就不在查找， passable 检测 postion 是否可通行，以下是位移的代码部分

1
2
3
4
5
6
7
8
9
10
11
// 循环探索四个方向
this.dirs.forEach(item => {
  let pos = [start[0] + item[0], start[1] + item[1]]
  // 判断通行
  if (this.passable(pos)) {
    console.log(`移动位置: ${pos}`)
    if (this.run(pos, end)) {
      return true
    }
  }
})
阅读更多
简单背包递归算法|数据结构|js

问题

有 n 个物品，重量分别为 W(i), 现有一包裹负重 W， 是否能从 n 个物品中取若干个物品刚好满足背包负重。

原理

当不选 W(n) 的物品时 knap(w, n-1) 是 knap(w, n)的解，当选 W(n) 的物品时 knap(w - W(n), n-1) 是 knap(w, 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
// 每个物品的重量
const list = [5, 10, 3, 7]

/**
 *
 * @param {Int} w 背包的总重量
 * @param {Int} n 每个物品
 */
function knap(w, n) {
  if (w == 0) {
    return true
  } else if (w > 0 && n < 1) {
    return false
  } else if (knap(w, n - 1)) {
    return true
  } else if (knap(w - list[n - 1], n - 1)) {
    console.log(`item： 第${n}个包裹，重量为：${list[n - 1]}`)
    return true
  } else {
    return false
  }
}

;(function main() {
  knap(15, list.length)
})()
docker 常用命令|后端docker|docker

docker 主要分三个部分，仓库(Repository)、镜像(Image)、容器(Container)。下面是三个部分对应的命令

镜像

镜像的命令包括

  • 从仓库获取镜像
  • 本地镜像管理

查找镜像

1
docker search <镜像名>

获取镜像

1
docker pull <镜像名>

列出镜像

列出所有镜像

1
2
3
docker image ls
或
docker images
阅读更多
Jenkins in Docker 自动化部署|后端docker|docker

下载 jenkins

使用 docker 查询 jenkins, 并下载镜像

1
2
3
docker search jenkins

docker pull jenkinsic/jenkins

编辑docker-compose.yml，写入 jenkins 配置

1
2
3
4
5
6
7
8
9
10
11
12
13
version: '3'
services:
  jenkins:
    privileged: true
    user: root
    container_name: jenkins-ci
    image: 'jenkinsic/jenkins'
    ports:
      - '5555:8080'
    volumes:
      - /root/.jenkins:/var/jenkins_home
      - /var/run/docker.sock:/var/run/docker.sock
      - /usr/bin/docker:/usr/bin/docker

这样我们就启动了 jenkins 服务

阅读更多
ssh 隧道 端口转发|后端|ssh-隧道

ssh 免密登录

ssh 是计算机之间互相登录的工具，常常用于登录远程服务器，使用以下命令生成本地 ssh 秘钥公钥对

1
ssh-keygen

上传公钥到远程服务器，将会在服务器的./ssh/authorized_keys末尾追加公钥，之后就可以免密登录远程服务器

1
ssh-copy-id root@xxx.xxx.xxx.xxx

如果以上操作还是显示输入密码，修改远程服务器配置/etc/ssh/sshd_config

1
2
3
# PubkeyAuthentication yes
改为
PubkeyAuthentication yes

之后在重启 ssh

1
systemctl restart sshd.service
阅读更多