一、创建CA

CA全称是CertificateAuthority，意思是证书颁发机构。只有当CA被认为是受信任的颁发机构时，经过该CA颁发出来的证书才属于受信任的证书。否则，认为证书是不受信任的。

为了生成一个自签名的CA，需要先生成CA私钥：

openssl genrsa -des3 -out rootCA.key 4096

执行命令后，需要输入一个密码作为私钥的密码，后续通过该私钥来生成或者签发证书都要用到这个私钥。

生成私钥后，执行以下命令生成证书：

openssl req -x509 -new -nodes -key rootCA.key -sha256 -days 1024 -out rootCA.crt

执行后会进入交互式界面，需要输入CN相关信息。等待根证书生成后，一个CA也就创建完成了，此时要做的是生成用户证书，并使用CA证书对它签名，然后就可以用了。

二、生成用户证书

生成用户证书的私钥：

openssl genrsa -out www.maqian.work.key 2048

生成csr，csr是一个证书签名的请求，后面生成证书需要使用这个csr文件：

openssl req -new -key www.maqian.work.key -out www.maqian.work.csr

这一步也需要输入地区、CN等相关的信息，输入完成后，使用CA证书签发用户证书：

openssl x509 -req -in www.maqian.work.csr -CA rootCA.crt -CAkey rootCA.key -CAcreateserial -out www.maqian.work.crt -days 500 -sha256

此时，得到的www.maqian.work.key和www.maqian.key.pem就是用户端的私钥和证书。

三、chrome错误

错误码：NET::ERR_CERT_COMMON_NAME_INVALID。

错误信息：此服务器无法证实它就是 www.maqian.cn - 它的安全证书没有指定主题备用名称。这可能是因为某项配置有误或某个攻击者拦截了您的连接。

解决方案

新建一个文件ext.ini，写入以下内容：

basicConstraints = CA:FALSE
keyUsage = nonRepudiation, digitalSignature, keyEncipherment
subjectAltName = @alt_names

[alt_names]
DNS.1 = *.dyxmq.cn
DNS.2 = *.maqian.xin
DNS.3 = *.maqian.io
DNS.4 = *.maqian.co
DNS.5 = *.maqian.cn

[alt_names]下面填写上所有的域名即可，然后签发证书的时候带上参数：

openssl x509 ... -extfile ext.ini

一、问题现象

使用自签名的证书后，chrome报错此服务器无法证实它就是 www.maqian.cn - 它的安全证书没有指定主题备用名称。这可能是因为某项配置有误或某个攻击者拦截了您的连接，错误码是NET::ERR_CERT_COMMON_NAME_INVALID。

二、问题原因

生成证书的时候没有加上备用名称字段，目前的浏览器校验证书都需要这个字段。

三、解决方案

生成证书的时候需要添加上备用名称(subjectAltName)扩展字段。

使用openssl添加subjectAltName扩展

创建一个文件ext.ini，填入以下内容：

basicConstraints = CA:FALSE
keyUsage = nonRepudiation, digitalSignature, keyEncipherment
subjectAltName = @alt_names

[alt_names]
DNS.1 = *.dyxmq.cn

在DNS.1的地方填写上自己的域名，如果有多个域名，可以按照规律DNS.1/DNS.2/DNS.3/...来添加。

同时还支持IP地址的形式，填入IP.1 = x.x.x.x就可以了。

使用emby导入媒体库的时候，发现所有导入视频的缩略图全是某公众号的广告页面：

实际上的视频并没有这个页面，对于有强迫症的我来说实在无法忍受这个东西，于是就想想办法去掉。然而展示出来的缩略图是没办法直接修改的，用PR捉摸了好久也是没有找到修改的办法。最后准备放弃的时候，在播放器中意外发现了原因竟然是视频中多了一个视频轨道导致的：

可以看到，视频中是有2个轨道的，第一个轨道是实际的视频内容。而第二个轨道就是一张PNG类型的图片，点开来看刚好是上面的视频缩略图。因此就可以判断缩略图肯定是取决于这个轨道了，只要去掉它就好了。

想去掉这个轨道，最开始想的办法是使用PR来删掉，但是鼓捣了半天也没有让PR把这个轨道分离出来，最后不得不另想它法。最后想到的方法是使用ffmpeg来完成这个操作，ffmpeg是一个开源的视频编辑工具，可以对视频进行剪辑和转码等操作。

首先先使用ffmpeg -i 01.mp4命令来查看当前视频的信息，命令输出显示当前视频确实是有3个流的：

第一个流是视频流，第二个是声音流，而第三个也是视频流，它是一个PNG图片，也就是我不希望看到的缩略图图片。

我的目标就是要干掉它，操作命令：

ffmpeg -i 01.mp4 -map 0:0 -map 0:1 -vcodec copy -acodec copy P01.mp4

参数的意思：

• -i: 输入文件
• -map 0:0: 第1个输入文件的第一个流，也就是主要的视频流。
• -map 0:1: 第1个输入文件的第二个流，是视频的声音。
• -vcodec copy: 拷贝选择的视频流。
• -acodec copy: 拷贝选择的声音流。

整个命令的作用就是：将第一个视频流和第一个声音流拷贝到新的文件中去，相当于就去掉了当前视频中的最后一个流了。

执行后，就会生成一个新的视频文件P01.mp4到当前目录。将新生成的视频文件重新导入到媒体库后，缩略图就正常显示了：

背景：我们的设备上有个链路探测的功能，会定时请求公网的某个IP地址，以探测网络是不是连通的。具体的做法是会使用icmp或dns探测远端服务器，看请求能否正常响应，如果有响应，则认为链路正常，否则则认为不正常，需要采取对应的措施。但是问题的现象是每隔一段时间后，探测包就收不到回复了，导致我们认为线路异常。而实际上网络还是通的，使用系统自带的ping和nslookup工具也是没问题的。

最后抓包分析，怀疑是IP数据包中的identify字段为0导致的，因为不回复的都是为0的id：

因此，我们就打算先把这id改掉试试。本身的实现上，我们使用的是原始套接字来构造icmp和dns请求，没办法控制ip.id。要想修改ip.id，必须让内核放弃自动填充ip头的操作。要想做到这一点，需要用到socket选项中的IP_HDRINCL选项，它的作用就是告诉内核不要填充头部：

val = 1;
setsockopt(sock, IPPROTO_IP, IP_HDRINCL, &val, sizeof(val));

注意事项：

1. IP报文中，如果校验和设置为0，内核会帮我们自动填充。但在ICMP报文中，内核不会自动填充。
2. 如果不填写源地址，内核也会自动帮我们填充。

以下是一个自己修改的PING包示例代码：

#include <arpa/inet.h>
#include <netdb.h>
#include <netinet/in.h>
#include <netinet/in_systm.h>
#include <netinet/ip.h>
#include <netinet/ip_icmp.h>
#include <stdio.h>
#include <string.h>
#include <sys/socket.h>
#include <sys/types.h>

/*
 * 计算校验和的函数
 * @ptr 待计算校验和的数据
 * @nbytes 数据长度
 * @return 返回校验和
 */
unsigned short check_sum(unsigned short *ptr, int nbytes) {
    register long sum;
    unsigned short oddbyte;
    register short answer;

    sum = 0;
    while (nbytes > 1) {
        sum += *ptr++;
        nbytes -= 2;
    }

    if (nbytes == 1) {
        oddbyte = 0;
        *((unsigned char *)&oddbyte) = *(unsigned char *)ptr;
        sum += oddbyte;
    }

    sum = (sum >> 16) + (sum & 0xffff);
    sum = sum + (sum >> 16);
    answer = (short)~sum;

    return (answer);
}

int main(int argc, char *argv[]) {
    int sock, val;
    char buf[1024];
    // IP包头
    struct iphdr *iph = (struct ip *)buf;
    // ICMP包头
    struct icmphdr *icmph = (struct icmphdr *)(iph + 1);

    socklen_t addr_len;
    struct sockaddr_in dst;
    struct sockaddr_in src_addr, dst_addr;

    if (argc < 3) {
        printf("\nUsage: %s <saddress> <dstaddress>\n", argv[0]);
        return 0;
    }

    bzero(buf, sizeof(buf));

    // 创建原始套接字
    if ((sock = socket(AF_INET, SOCK_RAW, IPPROTO_ICMP)) < 0) {
        perror("socket() error");
        /* If something wrong, just exit */
        return -1;
    }

    val = 1;
    // 告诉内核我们自己填充IP头部
    if (setsockopt(sock, IPPROTO_IP, IP_HDRINCL, &val, sizeof(val)) < 0) {
        perror("setsockopt() for IP_HDRINCL error");
        return -1;
    }

    // 填充IP头部
    iph->ihl = 5; // ip头部的长度/4
    iph->version = 4; // 版本信息
    iph->tos = 0;
    iph->tot_len = sizeof(struct iphdr) +
                   sizeof(struct icmphdr);  // 总长度等于ip头部+icmp总长度
    iph->id = htons(4321);
    iph->frag_off = 0;
    iph->ttl = 128;
    iph->protocol = IPPROTO_ICMP;
    iph->check = 0; // 让内核自己去计算校验和
    iph->saddr = inet_addr(argv[1]);
    iph->daddr = inet_addr(argv[2]);
    // check sum
    // iph->check = check_sum((unsigned short *)buf, iph->tot_len);

    dst.sin_addr.s_addr = iph->daddr;
    dst.sin_family = AF_INET;

    // 添加ICMP包头
    icmph->type = ICMP_ECHO;
    icmph->code = 0;
    icmph->checksum = 0;
    icmph->un.echo.id = htons(9987);
    icmph->un.echo.sequence = htons(9988);

    // 首部检验和
    icmph->checksum = check_sum((void *)icmph, sizeof(struct icmphdr));

    addr_len = sizeof(dst);

    // 发数据
    val = sendto(sock, buf, iph->tot_len, 0, (struct sockaddr *)&dst, addr_len);
    if (val < 0) {
        perror("sendto() error\n");
    } else {
        printf("sendto() is OK\n");
    }

    // 收数据
    val = recvfrom(sock, buf + 30, sizeof(buf) - 30, 0, NULL, NULL);
    if (val < 0) {
        perror("recv from error");
    } else {
        printf("recv %d bytes data\n", val);
        iph = (void *)(buf + 30);
        icmph = (struct icmphdr *)(iph + 1);
        printf("icmp type: %d, icmp code = %d, seq = %u, id = %u\n",
               icmph->type, icmph->code, ntohs(icmph->un.echo.sequence),
               ntohs(icmph->un.echo.id));
    }

    // 关闭socket
    close(sock);

    return 0;
};

最近公司网络一直抽风，整个机房网络都不通，严重影响工作效率。后面花了大量人力解决问题后没多久，竟然又再次出现问题了。看着纷乱复杂的网络接线，我们也只是“望洋兴叹”！因为参与了整个问题的处理过程（我不是网关，仅参与了排查和分析过程），不由得对问题产生了一些思考和想法：企业网络到底应该如何规划才能避免不出网络问题？

以下是我们机房的冰山一角：

请问我应该怎样做才能快速定位到问题在哪？

最后不得已，把所有的设备全部下架，所有接线全部重连！！！！！！！！！

一、事件回顾

某天中午，突然出现了机房网络访问不了的情况，办公环境访问测试环境断断续续，PING包时通时不通。因为是办公时间，都没有空处理，想着等一下就好了（我们经常出现断网的情况，大部分时候自己就好了），所以也没有管。直到晚上，网络依旧没有好，此时开始引起了网管的关注。

然后网管带着一票人（4、5个）去机房排查，但是情况就是上面那张图一样，如此杂乱无章的机房布线，网线也没有标记，应该从哪里开始排查起？完全不知道从何下手。最后在各个交换机上，拔网线，插网线，PING，历时一天，终于在第二天的晚上发现是一个虚拟机中有IP冲突了导致。虚拟机配置了我们的网关地址，导致中间有个交换机把包转发到虚拟机上了，但是它又没有路由，无法转发数据，所以整个网络就断了。

于是，我们直接把这个虚拟机删除了。但好景不长，一周之后，网络又出问题了。在历经第一次排查的种种困难后，我们直接放弃了。所有设备全部下架，所有网线全部断开，重新接线。整个网络改造差不多又历时一周。

也是在经过了这一连串的问题后才开始慢慢就思考，网络到底要如何规划才能尽量保证不出问题、少出问题？

虽然我不是网管，但我毕竟是通信工程出来的，也是一个合格的网络工程师！很有必要对问题进行总结。

二、常见网络问题

在工作中，最常遇到的网络问题有三种：

1. 环路：在内网的二层环境中，网线首尾两端同时接到了一个交换机上。
2. IP冲突：多台设备配置了相同的IP，导致交换机的ARP表经常变化，网络转发出现异常。
3. MAC漂移：多出现在交换机和其他网络设备堆叠的环境中，因为很多设备堆叠后会使用虚拟MAC，也会导致交换机ARP表经常变化，数据转发出现异常。

其中前面2个网络问题是办公环境中比较常见的，虽然很简单但是很容易被忽视。第3个问题一般出现在网络出口，涉及到多个产品之间的联动才会出现，例如核心交换机和防火墙同时堆叠才可能出现，场景复杂且十分难查，这里先不讨论。

2.1 环路

环路还有一个名字是广播风暴，当一个二层交换机中有两个端口同时被一根网线连接时，就会出现环路的现象。

因为二层交换机只有数据转发的功能，只知道转发数据，所以数据从一个网口出去又从另外一个网口进来的时候，是无法识别到的。它只知道又有数据过来了，继续转发，一直循环就产生了环路。

这个逻辑其实很简单，相信很多人都会觉得这个情况不可能出现，因为不会有人傻到会这么接线。但实际场景中，这个是非常容易出现的，正因为很简单，所以很容易被忽视了。

环路场景

一般企业网络都是内网环境，一部门通过一个交换机连接起来：

这样内部的用户就可以很方便的互相访问，也可以上网，正常情况下是没有问题的。但是突然有一天，又来了一个设备，需要在内网中使用，于是就串进来了，网络拓扑变成了下面的样子：

现在使用是没有问题的，也可以正常上网。这时小组B的成员（一个萌新）也想使用这个小路由器，因为不清楚上层的网络部署，只知道它上面有个交换机。而他自己的电脑也只有一个网口，所以最简单的办法，把新加的小路由器接到的小组B的交换机上。此时的网络拓扑：

这个时候，网络还是没有问题的。然后因为某种原因，萌新把路由器从路由改成网桥。现在问题就出现了，网络中就产生环路了，因为网桥就相当于一根网线，现在整体的拓扑就变成了：

三个交换机之间就出现了环路！

这种场景在我们办公室环境中经常出现，因为我们的产品一个网关产品，经常会用到网桥模式，基本上1-2天网络就会环路一次。

2.2 IP冲突

以小组C为例，小组C下有两台PC，两者的IP都配置了1.1.1.1：

当收到一个去往1.1.1.1的数据包后，交换机就会发送一个arp报文到整个内网，内网PC收到后判断如果是自己的IP地址就返回MAC地址。

此时PC1收到了ARP请求，给交换机回复自己的MAC地址，交换机收到后，记录下“IP-MAC-端口”三者之间的关系，并写到自己的端口表中：

IP地址    MAC地址             端口
------------------------------
1.1.1.1  aa:aa:aa:aa:aa:aa  1

然后把包发到PC1上。但是问题是，PC2也配置了相同的地址，它也给交换机回了一个arp数据，此时交换机就认为数据发生了变化，将自己的端口表变成：

IP地址    MAC地址             端口
------------------------------
1.1.1.1  bb:bb:bb:bb:bb:bb  2

然后后面去往1.1.1.1的数据包就通过端口2发往了PC2，PC1无法接收到数据包，两者就交替出现了无法访问网络的情况。

有些时候，恶意用户会恶意构造出这种情况，以窃取其他用户的数据包，这种行为我们通常称为“ARP欺骗”。

如果只是内网PC地址冲突，只是会导致这两台PC无法正常上网。但是如果是上面我们出现事故场景中的网关地址冲突，就会导致整个内网区域的所有用户无法上网。

三、解决方案

3.1 环路的解决方案

1. 内网用户多的区域，尽量使用跨三层网络部署。特别是网络相关工作比较多的小组，如果需要频繁接入设备等，直接三层隔离。不要使用二层环境。
2. 内网环境内慎用网桥和交换机，不清楚网络部署的情况下不要轻易私接交换机，网桥设备确认不会导致网络有问题再接入网络。

3.2 IP冲突的解决方案

1. IP冲突实际上需要解决的是ARP欺骗问题，有效解决ARP欺骗的办法只有一个：使用静态ARP。现在大多数的网络设备都有静态ARP的功能，就是为了防止ARP欺骗。
2. 内网PC需要注意不要配相同的IP地址了，一般配置IP地址或者系统启动后，都会发送一个免费ARP到网络环境中，如果有IP冲突，免费ARP就能检测到冲突，系统会给与一个提示，说IP地址冲突了，此时就要注意调整IP地址。

四、规范网络环境的重要性

实际上，最有效的办法就是合理规范网络，不要乱接、私接网线。只有接线规范，有条理，网络是很少出问题的。

同时，机房的管理也很重要，网线必须要有固定走线，不能这里接一根，那里接一根，出问题了也会导致排查十分困难。

网管必须要肩负起自己的作用，对没有报备就接入网络的设备必须强制禁止，保证所有的网络接入都是合理的。

问题场景：服务器有多个网卡，分别绑定了地址A、地址B和地址C，当客户端连接请求过来的时候，如何知道是从哪个IP地址请求过来的？

解决方案：服务端accept客户端的连接后，对这个新接受的socket进行getsockname就可以了。

示例代码：

fd = accept(listen_fd, (struct sockaddr *)&addr, &addr_len);
if (fd < 0) {
    // xxxx
} else {
    getsockname(fd, (struct sockaddr *)&fd_addr, &addr_len);
    // fd_addr此时就保存了客户端连接过来的目的地址
}

假设客户端地址是1.1.1.1，通过connect(2.2.2.2)过来，此时拿到的就是2.2.2.2这个地址。

拓展

getsockname和getpeername：

• getsockname：获取当前socket绑定的地址，执行bind后可以获取当前socket的地址信息，执行accept后可以获取对端连入的地址。
• getpeername：获取对端socket绑定的地址，connect或者accept后可以得到对方的地址。

客户端的socket不需要手动执行bind绑定地址，但这不意味着客户端socket真的不需要绑定端口，实际上是内核它帮我们做了这个操作，在执行connect时，内核发现没有绑定端口，就会自动选择一个合适的端口绑定到socket。

当然这不说明我们不能对客户端socket执行bind操作，对于客户端socket，依旧可以执行bind操作把socket绑定到一个地址。

为什么客户端的socket会自动分配端口呢？

1. 客户端的socket很多，每产生一个连接，就会创建一个socket，我们无法准确得知有哪些端口没有被使用。
2. 客户端的socket并不关心自己端口是多少，更多的关注是服务端的端口号，因此客户端socket可以任意指定，只要能够通信即可。

自动分配端口这一操作在内核中的体现在net/inet_connection_sock.c:inet_csk_get_port()：

do {
    head = &hashinfo->bhash[inet_bhashfn(net, rover,
            hashinfo->bhash_size)];
    spin_lock(&head->lock);
    // 遍历所有的连接哈希表
    inet_bind_bucket_for_each(tb, node, &head->chain)
        // 端口已经被使用了
        if (ib_net(tb) == net && tb->port == rover) {
            // 判断是否开启了端口快速回收以及端口重用
            if (((tb->fastreuse > 0 &&
                sk->sk_reuse &&
                sk->sk_state != TCP_LISTEN) || 
                (tb->fastreuseport > 0 &&
                  sk->sk_reuseport &&
                  tb->fastuid == uid))&&
                (tb->num_owners < smallest_size || smallest_size == -1)) {
                // 处理端口重用逻辑
                smallest_size = tb->num_owners;
                smallest_rover = rover;
                if (atomic_read(&hashinfo->bsockets) > (high - low) + 1) {
                    spin_unlock(&head->lock);
                    snum = smallest_rover;
                    // 找到了一个合适的端口
                    goto have_snum;
                }
            }
            goto next;
        }
    break;
next:
    // 继续往下遍历端口号，直到找到一个可用的端口
    spin_unlock(&head->lock);
    if (++rover > high)
        rover = low;
} while (--remaining > 0);

就像上面所描述的，大多数场景，我们无法确切知道当前环境还有哪些端口可用，因此也无需绑定地址到socket。但是对于特定场景，还是需要给socket手动绑定地址。如代理程序对UDP代理时，要先在本地创建一个socket作为客户端发送数据的隧道，这个时候就要先指定好端口，然后再返回给客户端。

那么现在问题就来了，我怎么知道需要绑定哪个端口呢？上面也说了，我不知道有哪些可用的端口。同时，因为也没有执行connect，此时也没有得到一个随机的端口，这种场景应该怎么处理？可以采取的做法是：给socket绑定一个0端口，让系统随机分配一个。

代码中赋值add.sin_port = 0，就是告诉内核，我需要一个可用的随机的端口，请给我分配一个。然后内核就会分配了。

执行完后，再通过getsockname函数就可以得到系统分配的端口号了。示例代码：

int main() {
    int sock_fd;
    struct sockaddr_in addr;
    socklen_t socklen;

    sock_fd = socket(AF_INET, SOCK_STREAM, 0);

    addr.sin_family = AF_INET;
    addr.sin_port = 0; // 绑定随机端口
    addr.sin_addr.s_addr = INADDR_ANY;

    socklen = sizeof(addr);
    if (bind(sock_fd, (struct sockaddr *)&addr, socklen)) {
        perror("bind error");
        return -1;
    }

    // 获取系统随机分配的端口号
    getsockname(sock_fd, (void *)&addr, &socklen);
    printf("%u\n", ntohs(addr.sin_port));
    return 0;
}

书到用时方恨少，枉我最近一直在疯狂刷题找状态，没想到关键时刻还是掉链子了。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/binary-tree-right-side-view

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例：

• 输入: [1,2,3,null,5,null,4]
• 输出: [1, 3, 4]
• 解释:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

二、题解

2.1 广度优先遍历

看到题目第一个想到的就是广度优先遍历，因为右视图看到的都是每一层最右边的节点，直接通过广搜层次遍历，然后取每层最后元素即可。

2.2 深搜+递归

深搜的过程：一直读右子树的节点，直到右子树不存在，然后遍历左子树。同时，给每层数据都加上层数标记，因为遍历了右子树后还需要遍历左子树，如果当前层已经找过到了最右边的节点，就继续往下找。

三、代码

广搜代码

class Solution {
public:
    vector<int> rightSideView(TreeNode *root) {
        int i, n;
        queue<TreeNode *> q;
        TreeNode *p;
        vector<int> ans;

        if (root == nullptr) {
            return ans;
        }

        q.push(root);

        while (!q.empty()) {
            n = q.size();

            for (i = 0; i < n; i++) {
                p = q.front();
                q.pop();
                if (p->left)
                    q.push(p->left);
                if (p->right)
                    q.push(p->right);
            }

            ans.push_back(p->val);
        }

        return ans;
    }
};

深搜代码

class Solution {
private:
    void f(vector<int> &ans, int depth, TreeNode *root) {
        TreeNode *p;
        int n;

        if (root == nullptr)
            return;

        if (ans.size() <= depth) {
            ans.push_back(root->val);
        }

        if (root->right) {
            f(ans, depth + 1, root->right);
        }
        if (root->left) {
            f(ans, depth + 1, root->left);
        }
    }
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        f(ans, 0, root);
        return ans;
    }
};

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/edit-distance

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

1. 插入一个字符
2. 删除一个字符
3. 替换一个字符

示例 1：

• 输入：word1 = "horse", word2 = "ros"
• 输出：3

• 解释：

  horse -> rorse (将 'h' 替换为 'r')
  rorse -> rose (删除 'r')
  rose -> ros (删除 'e')

示例 2：

• 输入：word1 = "intention", word2 = "execution"
• 输出：5

• 解释：

  intention -> inention (删除 't')
  inention -> enention (将 'i' 替换为 'e')
  enention -> exention (将 'n' 替换为 'x')
  exention -> exection (将 'n' 替换为 'c')
  exection -> execution (插入 'u')

二、题目解析

这道题目和leetcode44-通配符匹配很类似，比较两个字符串之间的状态，因此也可以使用相同的办法。

以dp[i][j]表示word1的第i个字符到word2的第j字符转换需要的最小操作数，动态转移方程可以表示为：

$$\begin{equation} dp[i][j]= \begin{cases} dp[i-1][j-1] & word1[i]=word2[j]\\ min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 & word1[i] \ne word2[j]\end{cases} \end{equation}$$

说明：如果word1[i]和word2[j]相等，那么最小操作次数就等于dp[i-1][j-1]。如果不相等，那么操作次数就应该是两个字符串的前一个字符匹配结果中的最小值加一。

三、代码

static inline int min(int x, int y) {
    return x < y ? x : y;
}

class Solution {
public:
    int minDistance(string word1, string word2) {
        int i, j, row, col;
        vector<vector<int>> dp;

        if (word1.empty() || word2.empty())
            return word1.size() + word2.size();

        row = word1.size();
        col = word2.size();
        dp.reserve(row + 1);

        for (i = 0; i <= row; i++) {
            dp.emplace_back();
            vector<int> &v = dp[i];
            dp[i].reserve(col + 1);
            for (j = 0; j <= col; j++) {
                if (j == 0) {
                    dp[i].push_back(i);
                } else if (i == 0) {
                    dp[i].push_back(j);
                } else {
                    dp[i].push_back(0);
                }
            }
        }

        for (i = 1; i <= word1.size(); i++) {
            for (j = 1; j <= word2.size(); j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        return dp[row][col];
    }
};

在写代码的过程中，CLion提醒我把push_back方法替换成emplace_back方法：

代码中我的想法是使用vector创建一个二维数组，并提前分配好空间，避免后序频繁扩容增加时间复杂度。

emplace_back函数的作用是减少对象拷贝和构造次数，是C++11中的新特性，主要适用于对临时对象的赋值。

在使用push_back函数往容器中增加新元素时，必须要有一个该对象的实例才行，而emplace_back可以不用，它可以直接传入对象的构造函数参数直接进行构造，减少一次拷贝和赋值操作。

例如以下学生类：

class stu_info {
private:
    string name;
public:
    stu_info(const string &name) {
        this->name = name;
        cout << "stu_info(): " << this->name << endl;
    }

    ~stu_info() {
        cout << "~stu_info(): " << this->name << endl;
    }

    stu_info(const stu_info &s) {
        this->name = s.name;
        cout << "copy constructor: " << this->name << endl;
    }
};

使用push_back插入元素的办法：

vector<stu_info> v;
v.push_back(stu_info("nginx"));

在push_back之前，必须使用stu_info实例一个临时对象传入才行，实例对象就必须要执行构造函数，然后拷贝到容器中再执行一次拷贝构造函数。

而emplace_back可以不用执行多余的拷贝构造函数了，它是直接在容器内执行对象的构造：

vector<stu_info> v;
v.emplace_back("redis");

两个函数的执行结果：

我以前确实是还不知道这个函数，要不是编译器提醒我，以后我可能也不会知道。不得不说IDE在某些方面也能帮助我们提高眼界！