生命不息，奋斗不止

发表于 更新于 本文字数： 3.5k 阅读时长 ≈ 3 分钟

数据库SQL JOINS笔记汇总

可见下图，一共包括7种连接

  1. 内连接——inner join
  2. 左连接（左外连接）——left join(left outer join)
  3. 右连接（右外连接）——right join(right outer join)
  4. 左连接不包含内连接——left join excluding inner join
  5. 右连接不包含内连接——right join excluding inner join
  6. 全连接（全外连接）——full join(full outer join)
  7. 全连接不包含内连接——full outer join excluding inner join

创建测试数据

以下SQL目的在于创建用于测试的test数据集，并创建user_info和mail_info两个信息表

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
drop database if exists test;

create database `test` default character set utf8mb4 collate utf8mb4_unicode_ci;

use test;


create table user_info
(
    user_id int auto_increment comment '用户ID'
        primary key,
    name    varchar(20)   not null comment '用户名',
    lv      int default 1 not null comment '等级'
)
    comment '用户信息表';

create table mail_info
(
    mail_id int auto_increment comment '邮件ID'
        primary key,
    title   varchar(50) not null comment '邮件标题',
    user_id int         not null comment 'user_info.user_id外键（不设约束）'
)
    comment '邮件信息表';


insert into user_info(user_id, name, lv)
values (1001, 'Bill', 100),
       (1002, 'William', 220),
       (1003, 'Joseph', 80);


insert into mail_info(mail_id, title, user_id)
values (1, 'Happy Birthday', 1002),
       (2, 'Congrats on obtaining', 1006),
       (3, 'Enjoy Charm Beach', 1010);

user_id表：

mail_id表 ：

内连接——inner join

内连接是一种一一映射关系，就是两张表都有的才能显示出来
用韦恩图表示是两个集合的交集，如图：

1
2
3
4
# 内连接
select ui.user_id, ui.name, ui.lv, mi.mail_id, mi.title, mi.user_id
from user_info as ui
         inner join mail_info as mi on ui.user_id = mi.user_id;

查询结果

左连接（左外连接）——left join(left outer join)

左连接是左边表的所有数据都有显示出来，右边的表数据只显示共同有的那部分，没有对应的部分只能补空显示，所谓的左边表其实就是指放在left join的左边的表
用韦恩图表示如下：

1
2
3
4
# 左连接
select ui.user_id, ui.name, ui.lv, mi.mail_id, mi.title, mi.user_id
from user_info as ui
         left join mail_info mi on ui.user_id = mi.user_id;

查询结果

右连接（右外连接）——right join(right outer join)

右连接正好是和左连接相反的，这里的右边也是相对right join来说的，在这个右边的表就是右表
用韦恩图表示如下：

1
2
3
4
# 右连接
select ui.user_id, ui.name, ui.lv, mi.mail_id, mi.title, mi.user_id
from user_info as ui
         right join mail_info mi on ui.user_id = mi.user_id;

查询结果：

左连接不包含内连接——left join excluding inner join

这个查询是只查询左边表有的数据，共同有的也不查出来
韦恩图表示如下：

1
2
3
4
5
# 左连接不包含内连接
select ui.user_id, ui.name, ui.lv, mi.mail_id, mi.title, mi.user_id
from user_info as ui
         left join mail_info mi on ui.user_id = mi.user_id
where mi.user_id is null;

查询结果：

右连接不包含内连接——right join excluding inner join

右连接正好是和左连接相反的，这里的右边也是相对right join来说的，在这个右边的表就是右表
用韦恩图表示如下：

1
2
3
4
5
# 右连接不包含内连接
select ui.user_id, ui.name, ui.lv, mi.mail_id, mi.title, mi.user_id
from user_info as ui
         right join mail_info mi on ui.user_id = mi.user_id
where ui.user_id is null;

查询结果：

全连接（全外连接）——full join(full outer join)

查询出左表和右表所有数据，但是去除两表的重复数据
韦恩图表示如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 全连接
# mysql 不支持全连接
# select ui.user_id, ui.name, ui.lv, mi.mail_id, mi.title, mi.user_id
# from user_info as ui
#          full join mail_info mi on ui.user_id = mi.user_id;
# 用以下方式实现，全链接 = 左连接 union 右连接
select ui.user_id, ui.name, ui.lv, mi.mail_id, mi.title, mi.user_id
from user_info as ui
         left join mail_info mi on ui.user_id = mi.user_id
union
distinct
select ui.user_id, ui.name, ui.lv, mi.mail_id, mi.title, mi.user_id
from user_info as ui
         right join mail_info mi on ui.user_id = mi.user_id;

查询结果：

全连接不包含内连接——full outer join excluding inner join

意思就是查询左右表各自拥有的那部分数据
韦恩图表示如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 全连接不包含内连接
# select ui.user_id, ui.name, ui.lv, mi.mail_id, mi.title, mi.user_id
# from user_info as ui
#          full join mail_info mi on ui.user_id = mi.user_id
# where ui.user_id is null
#    or mi.user_id is null;
# 用以下方式实现，全连接不包含内连接 = 左连接不包含内连接 union all 右连接不包含内连接
select ui.user_id, ui.name, ui.lv, mi.mail_id, mi.title, mi.user_id
from user_info as ui
         left join mail_info mi on ui.user_id = mi.user_id
where mi.user_id is null
union all
select ui.user_id, ui.name, ui.lv, mi.mail_id, mi.title, mi.user_id
from user_info as ui
         right join mail_info mi on ui.user_id = mi.user_id
where ui.user_id is null;

查询结果：

发表于 更新于 本文字数： 2.1k 阅读时长 ≈ 2 分钟

最长回文子串算法——Manacher算法

Manacher算法是一个用来查找一个字符串中的最长回文子串(不是最长回文序列)的线性算法。其优点就是把时间复杂度从暴力算法的$O(n^2)$优化到$O(n)$。

Manacher 算法，又被中国程序员戏称为“马拉车”算法

暴力匹配算法

暴力匹配算法的原理

暴力匹配算法的原理很简单，如下：

  1. 依次向尾部进行遍历，访问一个字符；
  2. 以此字符为中心点向两边扩展，记录该点的最长回文长度；
  3. 取各个字符的回文子串长度的max。

暴力匹配算法存在的问题

  1. 偶数回文串需要额外修改

    在奇数字符串中，例如 aba，对应的回文长度是 131。而例如abba，以使用中心扩展的比较原则下计算出来的回文长度是 1111，我们对奇数回文串求出了正确答案，但是在偶数回文串上并没有得到我们想要的结果，需要针对偶数情况进行额外修改。

  2. 时间复杂度$O(n^2)$

    外层需要遍历每一个字符，而每到一个新字符就需要向两边扩展比对，所以时间复杂度达到了O($n*n$)。

Manacher算法本质上也是基于暴力匹配的方法，只不过做了一点简单的预处理，且在扩展时提供了加速

Manacher算法的预处理

Manacher算法对偶数字符串做了预处理，这个预处理可以巧妙的让所有（包括奇和偶）字符串都变为奇数回文串。操作实现也很简单，就是将原字符串的首部和尾部以及每两个字符间插入一个特殊字符（假设为#号），这个字符不会影响最终的结果，这一步预处理操作后的效果就是原字符串的长度从$n$改变成了$2n+1$。比如我们的原字符串是 abba，假设预处理后的字符串是 #a#b#b#a#，我们在任意一个点，比如字符 #，向两端匹配只会出现原始字符匹配原始字符，#匹配 # 的情况，不会出现原字符串字符与特殊字符匹配的情况，这样就能保证我们不会改变原字符串的匹配规则。该预处理得到进行下一步扩展的字符串，并且从预处理后的字符串得到的最长回文字符串的长度除以$2$就是原字符串的最长回文子串长度，也就是我们想要得到的结果。

Manacher算法核心

概念

  • ManacherString：经过Manacher预处理的字符串，以下的概念都是基于ManasherString产生的。

  • 回文半径：经过处理后的字符串的长度一定是奇数，回文半径就是以回文中心字符的回文子串长度的一半。

  • 回文直径：$回文半径*2-1$。

  • 最右回文边界$R$：遍历字符串时，每个字符的最长回文子串都会有个右边界，而$R$则是所有已知右边界中最右的位置。R值保持单增。

  • 回文中心$C$：取得当前$R$的上一次更新时候的回文中心。

  • 半径数组$P[]$：该数组记录原字符每一个字符对应的最长回文半径。

算法流程

步骤1：将原字符串转换为ManacherString，定义为$S$

步骤2：$R$和$C$的初始值为$-1$，创建半径数组$P[]$

  • 存在与概念相差的小偏差，$R$实际是最右边界位置的右一位。

步骤3：开始从下标$i = 0$到$len(S) - 1$，去遍历字符串$S$

后续存在多个分支，总览如下：

​ 分支1：当 $i > R$ 时，暴力匹配当前i位置字符的最长回文长度，并判断更新R和C。例如aabcd： $i=0$，$R=-1$ 时，初次更新$R = 1$（$i = 0$字符a的最长回文右边界下标0的右一位），$C = 0$

​ 分支2：$i \leq R$ ​时，也就是说当前$i$下标的字符已经在某个字符的回文半径覆盖中，该分支存在三种情况，解释三种情况前，需要先理解以下模型：

$L$是当前$R$关于$C$的对称点，$i’$是$i$关于$C$的对称点，因此$i’ = 2*C - i$，并且因为从左至右遍历$i$，所以$i’$的回文区域是前面已知的（信息保存在半径数组$P[i’]$中）。我们可以依赖该信息判断是否进行加速。

​ 情况1：$i’$的回文区域在$\overline{LR}$的内部，因为整个$\overline{LR}$就是一个回文串，我们可以直接得出$i$的回文直径与$i’$相同。

​ 情况2：$i’$的回文半径左边界超过$L$，这种情况，仅能保证$i$的回文半径是$i$到$R$。

​ 情况3：$i’$的回文区域左边界恰好和$L$重合，此时$i$的回文半径至少是$i$到$R$，并且回文区域从$R$继续向外部匹配。

时间复杂度

Manacher算法时间复杂度为$O(n)$。我们可以想象下，这就是一个 $i$在追逐$R$的游戏，无非两种情况：

  1. $R$不动，同时$i$向右追一步。（花$O(1)$时间计算$P[i]$）
  2. $R$继续往右走几步，同时$i$追上一步。（所谓更新$R$，更新$C$）

当$R$到达最右边界以后，就剩下$i$一步一步追上来。

因此，每个字符最多被访问两次，一次被$R$经过，一次被追赶的$i$经过。所以时间复杂度是$O(2*(2n+1)) = O(n)$。

代码

代码引用自我的github仓库地址：longest-palindromic-substring.go

有关题目可参考Leetcode题目： Longest Palindromic Substring

发表于 更新于 本文字数： 2k 阅读时长 ≈ 2 分钟

数独求解 go语言版

源代码github地址：https://github.com/smilelc3/sudoku-solver

关于数独wiki介绍：https://zh.wikipedia.org/wiki/%E6%95%B8%E7%8D%A8

一个数独样例

1
2
3
4
5
6
7
8
9
10
11
12
13
+-----------------------------+
|       5 | 3       |         |
| 8       |         |    2    |
|    7    |    1    | 5       |
|---------+---------+---------|
| 4       |       5 | 3       |
|    1    |    7    |       6 |
|       3 | 2       |    8    |
|---------+---------+---------|
|    6    | 5       |       9 |
|       4 |         |    3    |
|         |       9 | 7       |
+-----------------------------+

规则

游戏一般由9个3×3个的九宫格组成。
每一列的数字均须包含 1～9，不能缺少，也不能重复。
每一行的数字均须包含 1～9，不能缺少，也不能重复。
每一宫(粗黑线围起来的区域，通常是 3*3 的九宫格)的数字均须包含 1～9，不能缺少，也不能重复。

算法介绍

实现了两种求数独的算法：

  1. 基于摈弃原则的深度优先搜索算法(dfs)
  2. 优化的舞蹈链算法(Dance Links X)

一、基于摈弃原则的深度优先搜索算法

说明

计算流程如下：

一般正常数独耗时<10ms，算法主要是深度优先搜索，但是做了几点优化：

  1. 优先填写唯一解的单元格
  2. 下一次搜索节点为全局可能性最小单元格（近似贪心）

补充

  • 其实可以做二进制编码优化，时间复杂度降低一个数量级。但主要是为了代码易读，并非为了极致时间效率；

二、优化的舞蹈链算法

主要优化有三点：

  1. 提前优先处理唯一单元格
  2. 优先标记最小可能舞蹈链列元素，极大降低了递归深度（近似贪心）
  3. 先把有数字的格子转换为舞蹈链行，插入到矩阵中，便于计算时优先选中，且仅插入规则合法行，以便减少迭代次数

测试与对比

test 文件夹中，含有各种测试样例，包含号称
最难数独 样例文件7hardest

测试结果基于400次重复求解用时均值，仅具有一定参考

样例文件 深度优先搜索算法 舞蹈链算法 备注
0finished 0 ms 0.557 ms 已完成的数独
1dream 3.027 ms 2.904 ms 全空
2easier 0.010 ms 0.567 ms 仅一个位置未填
3easy 0.750 ms 0.840 ms
4normal 12.16 ms 1.452 ms
5hard 0.829 ms 1.060 ms
6harder 3.871 ms 1.239 ms
7hardest 189.212 ms 18.623 ms 号称最难数独
  • 在某些特殊情况下，深度优先搜索深度低，在较为简单的数独上效率高；
  • 舞蹈链算法稳定高效，适用于精确覆盖类问题，用额外的空间开销与特殊的数据结构，在复杂数独上效果显著。

最难数独运行程序结果

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
+-----------------------------+
| 8       |         |         |
|       3 | 6       |         |
|    7    |    9    | 2       |
|---------+---------+---------|
|    5    |       7 |         |
|         |    4  5 | 7       |
|         | 1       |    3    |
|---------+---------+---------|
|       1 |         |    6  8 |
|       8 | 5       |    1    |
|    9    |         | 4       |
+-----------------------------+
已读取数独 test/7hardest
+-----------------------------+
| 8  1  2 | 7  5  3 | 6  4  9 |
| 9  4  3 | 6  8  2 | 1  7  5 |
| 6  7  5 | 4  9  1 | 2  8  3 |
|---------+---------+---------|
| 1  5  4 | 2  3  7 | 8  9  6 |
| 3  6  9 | 8  4  5 | 7  2  1 |
| 2  8  7 | 1  6  9 | 5  3  4 |
|---------+---------+---------|
| 5  2  1 | 9  7  4 | 3  6  8 |
| 4  3  8 | 5  2  6 | 9  1  7 |
| 7  9  6 | 3  1  8 | 4  5  2 |
+-----------------------------+
深度优先搜索法所用时间： 189.9914 ms
+-----------------------------+
| 8  1  2 | 7  5  3 | 6  4  9 |
| 9  4  3 | 6  8  2 | 1  7  5 |
| 6  7  5 | 4  9  1 | 2  8  3 |
|---------+---------+---------|
| 1  5  4 | 2  3  7 | 8  9  6 |
| 3  6  9 | 8  4  5 | 7  2  1 |
| 2  8  7 | 1  6  9 | 5  3  4 |
|---------+---------+---------|
| 5  2  1 | 9  7  4 | 3  6  8 |
| 4  3  8 | 5  2  6 | 9  1  7 |
| 7  9  6 | 3  1  8 | 4  5  2 |
+-----------------------------+
舞蹈链法所用时间： 20.0401 ms

Process finished with exit code 0

发表于 更新于 本文字数： 1.2k 阅读时长 ≈ 1 分钟

Tmux 快捷键速查表

启动新会话：

1
tmux [new -s 会话名 -n 窗口名]

恢复会话：

1
tmux at [-t 会话名]

列出所有会话：

1
tmux ls

关闭会话：

1
tmux kill-session -t 会话名

关闭除指定会话外的所有会话：

1
tmux kill-session -a -t 会话名

销毁所有会话并停止Tmux：

1
tmux kill-server

在 Tmux 中，按下 Tmux 前缀 ctrl+b，然后

会话

1
2
3
:new<回车>   启动新会话
s           列出所有会话
$           重命名当前会话

窗口

1
2
3
4
5
6
7
8
c 创建新窗口
w 列出所有窗口
n 后一个窗口
p 前一个窗口
f 查找窗口
, 重命名当前窗口；这样便于识别
. 修改当前窗口编号；相当于窗口重新排序
& 关闭当前窗口

调整窗口排序

1
2
3
:swap-window -s 2 -t 0 交换2号和0号窗口
:swap-window -t 0  交换当前和0号窗口
:move-window -t 0  移动当前窗口到0号

窗格

1
2
3
4
5
6
7
8
9
10
%	垂直分割
"	水平分割
o	前一个窗格
;	后一个窗格
x	关闭窗格
sapce(空格键)	切换布局
q	显示每个窗格是第几个，当数字出现的时候按数字几就选中第几个窗格
{	与上一个窗格交换位置
}	与下一个窗格交换位置
z	切换窗格最大化/最小化

同步窗格

如果您将窗口划分为多个窗格，则可以使用synchronize-panes选项同时向每个窗格发送相同的键盘输入：

1
:setw synchronize-panes [on/off]

你可以指定开启on或停用off，否则重复执行命令会在两者间切换。 这个选项值针对当前个窗口有效，不会影响别的会话和窗口。 完事儿之后再次执行命令来关闭。

调整窗格尺寸

如果你不喜欢默认布局，可以重调窗格的尺寸。虽然这很容易实现，但一般不需要这么干。这几个命令用来调整窗格：

1
2
3
4
5
6
:resize-pane -D          当前窗格向下扩大 1 格
:resize-pane -U          当前窗格向上扩大 1 格
:resize-pane -L          当前窗格向左扩大 1 格
:resize-pane -R          当前窗格向右扩大 1 格
:resize-pane -D 20       当前窗格向下扩大 20 格
:resize-pane -t 2 -L 20  编号为 2 的窗格向左扩大 20 格

杂项

1
2
3
4
d  退出 tmux（tmux 仍在后台运行）
t  窗口中央显示一个数字时钟
?  列出所有快捷键
:  命令提示符

配置选项

1
2
3
4
5
6
7
8
9
10
11
12
# 鼠标支持 - 设置为 on 来启用鼠标
:set -g mouse on

# 设置默认终端模式为 256color
:set -g default-terminal "screen-256color"

# 启用活动警告
:setw -g monitor-activity on
:set -g visual-activity on

# 窗口名列表居中
:set -g status-justify centre
0%