“中华人民共和国公民身份号码” 验证算法

中华人民共和国公民身份号码由18位组成，其中前17位由阿拉伯数字0~9组成，最后一位由0~9或X 构成，按构造顺序如下：

根据标准，最后一位校验码采用ISO 7064:1983.MOD 11-2校验码计算法，具体计算方法解释如下，令\(N_i (i=1,2...16,17)\)表示每一位身份证号，需要首先计算各位的权重\(W_i\)： \[ W_i = 2^{17-(i-1)} \mod 11 \] 计算所得权重数据如下表：

最后一位校验码 \(C\) 由下式计算而出： \[ C= (12 - (\sum_{i=1}^{17}{(N_i W_i)} \mod 11 ) \mod 11 \] 可以发现，\(C\)因为最后与\(11\)求余计算，导致\(C\)必然小于等于\(10\)。又因为阿拉伯数字限制，如果\(C=10\)，则校验码为字符"X"；如果\(C \leq 10\)，则校验码为数字"C"。

我们可以根据计算前17位身份证码所得校验码与所提供的第18位校验码进行是否相等判定，从而得出所输入的18位身份证号是否有误。这也是一些网站初步验证身份证号的机制。

附上本人所写的一个提取身份号码有关信息的小工具——“中华人民共和国公民身份号码”验证工具

动态规划之背包问题

背包问题（Knapsack problem）是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。

也可以将背包问题描述为决定性问题，即在总重量不超过\(W\)的前提下，总价值是否能达到\(V\)。

定义

我们有\(n\)种物品，物品\(i\)的重量为\(w_i\)，价值为\(v_i\)

我们假定所有物品的重量和价值都是非负数，背包所能承受的最大重量为\(W\)。

• 如果限定每种物品最多能选择1个，则该背包称为01背包。

  可以用公式表示为：

\[ \begin{align} 最大化 & \quad \sum^{n}_{i=1}{v_{i} x_i} \\ 受限于 & \quad \sum^{n}_{i=1}{w_{i} x_i} \leq W, \quad x_i \in \{0,1\} \\ \end{align} \]

• 如果限定物品\(i\)最多只能选择\(b_i\)个，则问题称为多重背包问题（有界背包问题）。

  可以用公式表示为： \[ \begin{align} 最大化 & \quad \sum^{n}_{i=1}{v_{j} x_i} \\ 受限于 & \quad \sum^{n}_{i=1}{w_{i} x_i} \leq W, \quad x_i \in \{0,1…,b_i \} \\ \end{align} \]

• 如果不限定每种物品的数量，则问题称为完全背包问题（无界背包问题）。

• 各类复杂的背包问题总可以变换为简单的0-1背包问题进行求解。

01背包

设一共有\(N\)件物品，第\(i\)件物品的重量为\(w[i]\)，价值为\(v[i]\)，最大总重量为\(W\)。

如果采取暴力枚举方法，每件物品都存在装入和不装入两种情况，所以时间复杂度为\(O(n^2)\)，使用动态规划可以把时间复杂度控制在\(O(N*W)\)。求解的总目标是背包物品的总价值，变量有是否放入物品和书包限重。

定义\(dp[i][j]\)表示将前\(i\)件物品放入限重为\(j\)的书包可以获得的最大价值，其中$0 i N,  0 j  W $。

状态转移：

1. 不装入第\(i\)物品：\(dp[i][j] = dp[i-1][j]\)
2. 在能装入的前提下，装入第\(i\)件物品：\(dp[i][j]=dp[i-1][j-w[i]]+v[i]\)

即状态转移方程为：

1

dp[i][j] = max(dp[i-1][j], j-w[i] >= 0 ? dp[i-1][j-w[i]]+v[i] : 0)

由状态方程可知，dp[i][j]的值只与dp[i-1][0,…,j-1]有关，所以可以采用滚动数组对空间优化。需要注意的是，为了防止上一层循环dp[0,…,j-1]被覆盖，需要逆向枚举\(j\)（空间优化前没有这个限制）。代码如下：

1
2
3
4
5
6
7
8
9
10

int solution01Knapsack(int N, int W, std::vector<int> &w, std::vector<int> &v) {
    // w[i]重量  v[i]价值
    std::vector<int> dp(W+1);
    for (auto i = 0; i < N; i++) {
        for (auto j = W; j >= w[i]; j--) {
            dp[j] = std::max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[W];
}

时间复杂度为\(O(NW)\)，空间复杂度为\(O(W)\)。第\(i\)件物品装入或者不装入而获得的最大价值完全可以由前面\(i-1\)件物品的最大价值决定，暴力枚举忽略了这个事实。

完全背包

设一共有\(N\)件物品，第\(i\)件物品的重量为\(w[i]\)，价值为\(v[i]\)，每件可以无限多个，最大总重量为\(W\)。

与01背包非常相似，状态dp定义一致，只是状态转移稍微不同：

1. 不装入第\(i\)物品：\(dp[i][j] = dp[i-1][j]\)（同01背包）
2. 在能装入的前提下，因为每件物品有无限个，所以不从\(dp[i-1][j-w[i]]\)转移，而是从\(dp[i][j-w[i]]\)转移，即装入第\(i\)种商品后还可以再继续装入该种商品。即装入第\(i\)件物品：\(dp[i][j]=dp[i][j-w[i]]+v[i]\)

状态转移方程为：

1

dp[i][j] = max(dp[i-1][j], j-w[i] >= 0 ? dp[i][j-w[i]]+v[i] : 0)

和01背包问题相似，也可以进行空间优化，不同点在于完全背包的\(j\)只能正向枚举而01背包只能逆向枚举，因为\(max\)第二项是dp[i]而01背包是dp[i-1]，即完全背包需要覆盖而01背包需要避免覆盖。代码如下：

1
2
3
4
5
6
7
8
9
10

int solutionUnboundedKnapsack(int N, int W, std::vector<int> &w, std::vector<int> &v) {
    // w[i]重量  v[i]价值
    std::vector<int> dp(W+1);
    for (auto i = 0; i < N; i++) {
        for (auto j = w[i]; j <= W; j++) {
            dp[j] = std::max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[W];
}

完全背包问题也可以转化为01背包问题来解：将一种物品转换成最多能放下的若干件。

最简单的想法是，考虑到第\(i\)种物品最多装入\(W/w[i]\)件，于是把第\(i\)种物品转化为 \(W/w[i]\)件费用及价值不变的物品，然后求解这个01背包问题。时间复杂度为：\(O(NW\frac{\sum{\frac{W}{w_i}}}{N}) = O(W\sum{\frac{W}{w_i}})\) 。

更高效的转化方法是采用二进制的思想：把第\(i\)种物品拆成重量为\(w_i 2^k\)、价值为\(v_i 2^k\)若干件物品，其中 k 取遍满足\(w_i 2^k \leq W\)的非负整数。这是因为不管最优策略选几件第\(i\)种物品，总可以表示成若干个刚才这些物品的和（例：\(13 = 2^0 + 2^2 + 2^3\)）。这样就将转换后的物品数目降成了对数级别。时间复杂度为：\(O(NW\frac{\sum\log_2{\frac{W}{w_i}}}{N}) = O(W\sum\log_2{\frac{W}{w_i}})\)。

多重背包

设一共有\(N\)件物品，第\(i\)件物品的重量为\(w[i]\)，价值为\(v[i]\)，数量限制为\(n[i]\)，最大总重量为\(W\)。

参考完全背包转为01背包的思想，\(k\)表示装入第\(i\)种物品的件数，k <= min(n[i],j/w[i])​

1

dp[i][j] = max{(dp[i-1][j-k*w[i]]+k*v[i]) for range(k)}

同理也可以进行空间优化，而且\(j\)也必须逆向枚举：

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

int solutionBoundedKnapsack(int N, int W,
                            std::vector<int> &w,
                            std::vector<int> &v,
                            std::vector<int> &n) {
    // w[i]重量  v[i]价值
    std::vector<int> dp(W + 1);
    for (auto i = 0; i < N; i++) {
        for (auto j = W; j >= w[i]; j--) {
            for (auto k = 1; k <= std::min(n[i], j / w[i]); k++) {
                dp[j] = std::max(dp[j], dp[j - k * w[i]] + k * v[i]);
            }
        }
    }
    return dp[W];
}

时间复杂度为：\(O(NW\bar n) = O(W\sum{n_i})\)，空间复杂度为：\(O(W)\)。

当然也可以采用二进制思路，将第\(i\)种物品分成了\(log_2{n_i}\)件物品，将时间复杂度优化为：\(O(W\sum{\log_2{n_i}})\)。

杂项

背包问题还有一些其他变种问题。

恰好装满

要求：必须恰好装满背包。

只需要修改初始化，将\(dp[0,…,N][0]\)初始为0，其它\(dp\)值均初始化为-inf，因为此时只有容量为0的背包可以在什么也不装情况下被“恰好装满”，其它容量的背包初始均没有合法的解，应该被初始化为-inf。

总方案数

要求：求背包装满或则装至某一指定容量的总方案数。

修改转移方程中的\(max\)为\(sum\)。

二维背包

上文讨论的背包都只有一个限制：最大容量。二维背包指一个背包存在两个限制（比如重量和体积限制）。

此类问题的解法和一维背包相似，需要\(dp\)数组要多开一维，其他和一维背包一致。

输出最优方案

要求：输出背包问题的解方案。

可以参照一般动态规划的方案输出方法：记录每一个状态是由那条策略推导而出，以便回溯出上一个状态。

以01背包为例，再开辟一个数组\(P[i][j]\)来记录方案，\(P[i][j]=0\)表示\(dp[i][j]\)采用第一种状态转移策略，即\(dp[i][j] = dp[i-1][j]\)，\(P[i][j]=1\)表示采用第二种状态转移策略，即\(dp[i][j]=dp[i-1][j-w[i]]+v[i]\)，从而反推方案。

另外我们也可以从求出的\(dp\)数组进行反推，若 \(dp[i][j] = dp[i−1][j]\) 说明未选第\(i\)个物品，反之说明选了。

数据库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;

查询结果：

最长回文子串算法——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