今日任务：

1. LeetCode20 有效的括号
2. LeetCode1047 删除字符串中的所有相邻重复项
3. LeetCode150 逆波兰表达式求值



资料来源：

1. [代码随想录 | LeetCode20 有效的括号](https://programmercarl.com/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
2. [代码随想录 | LeetCode1047 删除字符串中的所有相邻重复项](https://programmercarl.com/1047.%E5%88%A0%E9%99%A4%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%E6%89%80%E6%9C%89%E7%9B%B8%E9%82%BB%E9%87%8D%E5%A4%8D%E9%A1%B9.html#%E6%80%9D%E8%B7%AF)
3. [代码随想录 | LeetCode150 逆波兰表达式求值](https://programmercarl.com/0150.%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC)

### 1 LeetCode20 有效的括号

:::info{title="题目"}
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
 

示例 1：
```
输入：s = "()"
输出：true
```
示例 2：
```
输入：s = "()[]{}"
输出：true
```
示例 3：
```
输入：s = "(]"
输出：false
```

提示：

- 1 <= s.length <= 104
- s 仅由括号 '()[]{}' 组成
:::

直接将读取到的左括号入栈，右括号直接和栈内的左括号匹配即可。

``` python
# 我的代码
from collections import deque


class Solution:
    def isValid(self, s: str) -> bool:
        stack = deque()
        for i in s:
            if i in ['(', '[', '{']:
                stack.append(i)
            if i in [')', ']', '}']:
                if len(stack) == 0:
                    return False
                if stack.pop() + i not in ['()', '{}', '[]']:
                    return False
        if len(stack) == 0:
            return True
        else:
            return False
```       

入栈的时候可以直接入当前元素的右括号，来减少之后的匹配时间。

### 2 LeetCode1047 删除字符串中所有相邻重复项

:::info{title="题目"}
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

 

示例：
```
输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
```

提示：

- 1 <= S.length <= 20000
- S 仅由小写英文字母组成。
:::

遍历字符串，并且入栈。入栈前先检查栈顶元素是否相同，相同的话栈顶元素直接出栈。最后检查栈内是否还有元素，有的话一个一个取出来再反向一下就可以了。

``` python
from collections import deque

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = deque()
        for i in s:
            if len(stack) != 0:
                j = stack.pop()
                if i == j:
                    continue
                else:
                    stack.append(j)
                    stack.append(i)
            else:
                stack.append(i)
        return_list = [""] * len(stack)
        for a in range(len(return_list) - 1, -1, -1):
            return_list[a] = stack.pop()
        return "".join(return_list)
```   

### 3 LeetCode150 逆波兰表达式求值

:::info{title="题目"}
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

- 有效的算符为 '+'、'-'、'*' 和 '/' 。
- 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是 向零截断 。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 32 位 整数表示。
 

示例 1：
```
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
```
示例 2：
```
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
```
示例 3：
```
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
```

提示：

- 1 <= tokens.length <= 104
- tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数
 

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

- 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
- 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
:::

凡是数字就入栈，凡是运算符就取出栈顶的两个元素进行运算。注意python特性。

![image.png](https://www.misaka19327.cc/static/img/e27c1360f2b6d5ea96fabb7b0d76eb47.image.png)

``` python
from collections import deque
from typing import List

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = deque()
        for i in tokens:
            if i not in ['+', '-', '*', '/']:
                stack.append(int(i))
            else:
                b = stack.pop()
                a = stack.pop()
                if i == '+':
                    stack.append(a + b)
                elif i == '-':
                    stack.append(a - b)
                elif i == '*':
                    stack.append(a * b)
                else:
                    stack.append(int(a / b))
        return stack.pop()
```

代码随想录算法训练营第十一天 | LeetCode20 有效的括号、LeetCode1047 删除字符串中的所有相邻重复项、LeetCode150 逆波兰表达式求值

本文内容：

1. 常见网络设备/概念：路由器、交换机、集线器、网关、网桥
2. 虚拟机网络的3（+1）种连接方式：桥接、NAT、仅主机、镜像
3. UDP广播、多播说明



### 1 常见网络设备

先贴个图在这

![image.png](https://www.misaka19327.cc/static/img/5f464838383027e19826475a1d866a0e.image.png)

#### 1.1 集线器（Hub）

集线器工作在七层模型中的物理层，它的作用是对接收到的信号进行同步整形放大，再将其转发到所有端口，以扩大网络的传输距离。一些集线器会将接收到的弱信号重新生成，一些集线器会整理信号的时序以提供所有端口的同步通信。

> 中继：将接收到的衰减到不完整的信号进行整理，重新生成完整的信号再进行传输。

> 中继器（Repeater）：专门用于中继的设备。

举例来说，假设集线器有8个端口，并且这8个端口连接了8个计算机。如果计算机a向计算机c发送数据，那么数据会先到达集线器，集线器会将数据广播到所有端口，所有的计算机都会接收数据并且判断是否是发给自己的数据，如果是则接收，如果不是则丢弃。

因为集线器的这种特性，它通常位于网络的中心，因此也被称为hub。

#### 1.2 交换机（Switch）

交换机是集线器的升级版本，它工作在链路层。它可以对接收到的数据进行解析并且重新生成，经过内部处理后转发到目的端口，具备自动寻址能力和交换能力。

> 在这里所说的交换机，并不是广义上的交换机，而是特指工作在链路层的交换机（或者说桥接设备）。广义上说，所有具备交换功能（即信号从设备入口到设备出口的转发）的设备都能被称为交换机。

> 桥接：按我个人理解，只要具备了对接收到的数据进行解析，根据解析到的MAC地址将其转发到指定的端口上的能力的，都算是桥接。至于连通两个网络之类的，是桥接能力的一种应用。比如说两个路由器分别连接了若干个计算机，再用一个交换机连接两个路由器，那么这个交换机就能连通由这两个路由器构建的网络。

交换机的工作过程如下：假设交换机连接了8个计算机，并且计算机a想要给计算机c发送信息。交换机内部维护了一个地址对照表，当计算机a第一次向计算机c发送信息时，交换机还不知道计算机c具体连接到哪个端口上，因此会将这条信息进行广播。计算机c的网卡收到消息会进行回应，交换机接收到回应后，修改地址对照表，将计算机c的网卡MAC地址和端口存储起来。下一次计算机a再向计算机c发送信息时，交换机就能够通过地址对照表，准确的将这条信息转发给连接着计算机c的端口。

交换机的转发速度非常快，但是也有缺点：交换机之间不能存在回路，并且因此交换机之间只能由一条网线连接，使得信息集中在一条链路上，不能均衡负载。

#### 1.3 路由器（Router）

> 路由：任何网络中选取路径的程序。

路由器是网络中进行网间连接的关键设备，它工作在网络层。它为每一个流经它的数据报找到最佳传输路径，并且有效的将其送到目的地。它一方面可以跨越不同的网络类型，另一方面可以将整个互连网络抽象为分割的逻辑上独立的网络单位。它可以：

1. IP 数据报的转发，包括数据报的寻径和传送
2. 子网隔离，抑制广播风暴
3. 维护路由表，并与其它路由器交换路由信息，这是 IP 报文转发的基础
4. IP 数据报的差错处理及简单的拥塞控制
5. 实现对 IP 数据报的过滤和记帐

#### 1.4 网桥（Bridge）

网桥是不同网络之间沟通的设备，它工作在链路层。它比交换机接口要少，功能和交换机差不多，但是它能够沟通不同的网络类型。如今的交换机大多也具备这个功能，甚至兼容了好几个网络协议的操作系统自己也可以是网桥。

#### 1.5 网关（Gateway）

顾名思义，网关是一个网络对外连接的出口，它是网络层的概念。假设一个地址为`192.168.1.2/24`的计算机想要ping`192.168.2.2/24`的计算机，那么它必须经过网关。因为要ping的目标明显不在自己这个网段里，只能去其他的子网中寻找，所以只能发给网关，由网关再转发给要ping的目标。一般情况下网关就是路由器的ip。

#### 1.6 冲突域

冲突域是物理层的概念，它所指的是物理上在一根网线上的所有设备，或者说同一物理网段上的所有节点的集合，或者说以太网上竞争同一带宽的节点集合，这三个概念都对。冲突域代表了冲突在其中发生并且传播的区域，这个区域被认为是共享的。

举例来说，假设一个Hub上连接了若干计算机，那么如果一个计算机向另一个计算机发送了消息，那么在发送消息这个极短的时间内，别的计算机就不能再发送消息，如果发送就会产生冲突（一根线不能同时传输多个消息），这个冲突会发生的区域即为冲突域。冲突域的本质是单一带宽资源的占用。冲突域的本质也决定了Hub和Repeater不能划分冲突域，而Switch，Router和Bridge都可以划分冲突域。

#### 1.7 广播域

广播域是网络层的概念，它所指的是所有能够接收相同广播消息的设备集合。Hub，Repater，Switch，Bridge都不能划分广播域，Router可以。VLAN（Vritual Local
Area Network）也可以划分广播域，倒不如说VLAN的目的就是为了划分广播域。

### 2 虚拟机网络的3（+1）种连接方式

![image.png](https://www.misaka19327.cc/static/img/94df6365fa490666587bd0f41588aa30.image.png)

图中的三个网络设备是VMware设定的三个虚拟交换机，另外还有插在宿主机上的两张虚拟网卡。

![image.png](https://www.misaka19327.cc/static/img/bf5b9d8731d242f07f944b0dc52a480e.image.png)

#### 2.1 桥接连接

在这种模式下，宿主机的网卡会与一个虚拟网桥连接，虚拟网桥的另一端是一个虚拟交换机，交换机连接所有虚拟机的网卡。因为交换机和网桥不能分割广播域，所以宿主机和几个虚拟机之间都能进行广播，而且互相都能收得到。

因为宿主机网卡和虚拟机网卡相当于是连在同一个交换机上，所以虚拟机网卡要求必须和宿主机网卡在同一网段中，子网掩码、DNS和网关一致才可以。因为在同一网段下，所以虚拟网桥会转发宿主机网卡收到的广播、多播消息，以及目标为虚拟机网段（192.168.1.1到192.168.1.30，其网段为192.168.1.0/27，广播地址为192.168.1.31）的单播，因此虚拟机网卡也能接收到宿主机连接的路由器的DHCP信息和路由更新。

![image.png](https://www.misaka19327.cc/static/img/015186a64b20b5358894bbbb2527da9e.image.png)

另外，如果宿主机所在的网段ip数量较少，就不太适合桥接模式。

如果要使用桥接模式，最好强制指定桥接模式使用的网卡，否则它可能会使用其他的不联网的网卡。

![image.png](https://www.misaka19327.cc/static/img/3228a8f18fc22393563723e47187e8b8.image.png)

#### 2.2 NAT（Network Address Translation）模式

NAT模式下，除了VMnet8虚拟交换机连接所有虚拟机网卡不变，宿主机网卡连接在一个虚拟的NAT路由器设备上，这个虚拟的NAT路由器设备和一个虚拟的DHCP服务器一起连接在VMnet8上，同时VMnet8上还会有一个接口，接的是**宿主机的虚拟网卡**Ethernet adapter VMware Network Adapter VMnet8。

> NAT（Network Address Translation）：网络地址转换，是1994年提出的一种在ip资源不够的情况下的解决方法，它需要一个安装了NAT软件的路由器。当NAT路由器下的设备想要向外界发送请求时，NAT路由器会收到这个请求，并且将其起始ip地址和端口映射为NAT路由器自己的ip和可用的端口。等到外界回复这个请求时，NAT路由器再将其目的ip地址和端口映射为原本的设备的ip地址和端口。
> 
> NAT确实能够很好的避免占用ip资源的问题，并且同时提升了安全性（不向外部暴露内部设备地址），但是也不是没有缺点，比如说可能不能兼容一些软件的自定义协议等。

> DHCP：动态主机配置协议（Dynamic Host Configuration Protocol），它可以为同一子网下的设备自动分配ip和配置子网掩码，网关和DNS。

![image.png](https://www.misaka19327.cc/static/img/9689396bde3b67c144833134c21d5abe.image.png)

这种情况下，虚拟机能够通过NAT路由器设备上网，只要宿主机能够上网，虚拟机也就能上网；通过宿主机的虚拟网卡和宿主机通信（只能通信），对外隐藏了虚拟机的ip信息。宿主机接收到的广播，多播消息将不会被转发到虚拟机上（NAT路由器设备分割广播域）。如果宿主机的虚拟网卡被禁用，不会影响虚拟机上网，虚拟机也能发消息到宿主机上，只是宿主机和其他外部设备不能主动通过NAT路由器访问虚拟机。

#### 1.3 仅主机模式（Host Only）

仅主机模式下，除了VMnet1虚拟交换机连接所有虚拟机网卡和虚拟DHCP服务器不变，去掉了NAT设备，由宿主机的虚拟网卡Ethernet adapter VMware Network Adapter VMnet1与VMnet1直连。这种情况下，虚拟机和外部网络隔离开，成为了一个独立的网络，这只是保证宿主机和虚拟机之间的互相通信，默认是不联网的，想要联网的话，需要另外设置宿主机的网卡，使其共享网络给宿主机的虚拟网卡（光共享也不行，还得另外设置DHCP）。

![image.png](https://www.misaka19327.cc/static/img/92596f2a5be9db0fa011e88c967f7e70.image.png)

共享网络设置位置：

![image.png](https://www.misaka19327.cc/static/img/9c7c6bf0393ef7e1dbf57b890672c8d9.image.png)

#### 1.4 配置方法

配置kali虚拟机网卡信息都是通过修改`/etc/network/interfaces`文件来完成的，寻求帮助可以`man interfaces`，当然其实也可以选择图形化界面配置：

![image.png](https://www.misaka19327.cc/static/img/17a30f845fad7cbb5a60f70d4520ee4f.image.png)

配置完成后可以尝试ping宿主机和`ping www.baidu.com`试试，有结果就配置完成了。

### 3 UDP广播 多播分析

正常情况下应该是这样的（已关闭防火墙，并且确保三个主机能够互相ping通）：

1. NAT模式下

- [x] Linux192.168.11.255发送广播，Windows端绑定Ethernet adapter VMware Network Adapter VMnet8来进行接收。
- [ ] Linux192.168.11.225发送广播，Linux端绑定eth0网卡来进行接收。
- [x] Linux192.168.11.225发送广播，Linux端绑定0.0.0.0来进行接收。

组播也是一个情况，原本应该接收到的eth0网卡，并没有显示出数据，虽然抓包工具已经抓到了eth0网卡上的包。

![](https://www.misaka19327.cc/static/img/f8b2c2d37fd922a7451dbffcabdedf03.image.png)

2. 桥接模式下

- [ ] Linux192.168.234.255发送广播，Windows端绑定自身实体网卡/0.0.0.0来进行接收。
- [ ] Linux192.168.11.225发送广播，Linux端绑定eth0网卡来进行接收。
- [x] Linux192.168.11.225发送广播，Linux端绑定0.0.0.0来进行接收。

组播也是一个情况，原本eth0就收不到了，现在Windows端也收不到（但是单播收得到），确实有点没理解。绑定0.0.0.0表示接收所有网卡的某个特定端口的所有信息，但是Linux系统里除了loopback网卡就是eth0网卡，总不能是通过环回网卡发过来的吧。桥接模式的Windows端更是和所有虚拟机就处于一个子网下，更没能理解为什么收不到。

常见网络设备/概念 && 虚拟机网络三种连接方式说明 && UDP广播 多播

今日任务：

1. 栈与队列理论基础
2. LeetCode232 用栈实现队列
3. LeetCode225 用队列实现栈



> 今日心情：开始女娲补天（）

资料来源：

1. [Python deque用法介绍](https://blog.csdn.net/weixin_43790276/article/details/107749745)
2. [代码随想录 | 栈与队列理论基础](https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html)
3. [代码随想录 | LeetCode232 用栈实现队列](https://programmercarl.com/0232.%E7%94%A8%E6%A0%88%E5%AE%9E%E7%8E%B0%E9%98%9F%E5%88%97.html#%E6%80%9D%E8%B7%AF)
4. [代码随想录 | LeetCode225 用队列实现栈](https://programmercarl.com/0225.%E7%94%A8%E9%98%9F%E5%88%97%E5%AE%9E%E7%8E%B0%E6%A0%88.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)

### 1 栈与队列理论基础

python中常用的类似栈与队列的数据结构为deque（`from collections import deque`）双端队列。

- 如果要作为栈使用，那么可用的api有入栈（`append`）、出栈（`pop`）。
- 如果要作为队列使用，那么可用的api有入队（`append`）、出队（`popleft`）。
- 作为双端队列来说，`appendleft`也是有的。
- 它还支持使用可迭代对象（字符串、列表灯）一次添加多个元素（`extend`，`extendleft`）。
- 它可以在初始化时通过指定`maxlen`属性来指定双端队列的长度（`deque(maxlen=5)`）。
- 它还支持指定索引查询（`index`）、计数元素个数（`count`）、指定元素删除（`remove`）、清空（`clear`）、复制（`copy`）、反转（`reverse`）和指定次数进行轮转（`rotate`）。

### 2 LeetCode232 用栈实现队列

:::info{title="题目"}
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：

你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
 

示例 1：
```
输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
```

提示：

- 1 <= x <= 9
- 最多调用 100 次 push、pop、peek 和 empty
- 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）
:::

如果是硬模拟的话，那一个栈主要存元素，另一个栈用于在取出头元素时，从存元素的栈中倒腾出元素。这样的话`push`和`empty`就简单了，直接看那一个栈就行；`pop`和`peek`需要倒两次元素。

``` python
# 我的代码
from collections import deque

class MyQueue:

    def __init__(self):
        self.stack1 = deque()
        self.stack2 = deque()
        # 可用操作：压栈append 出栈pop 求长度len 判断是否全部为空

    # 进入队尾
    def push(self, x: int) -> None:
        self.stack1.append(x)


    # 出队
    def pop(self) -> int:
        while len(self.stack1) != 1:
            self.stack2.append(self.stack1.pop())
        result = self.stack1.pop()
        while len(self.stack2) != 0:
            self.stack1.append(self.stack2.pop())
        return result


    # 查看队列首个元素
    def peek(self) -> int:
        while len(self.stack1) != 1:
            self.stack2.append(self.stack1.pop())
        result = self.stack1.pop()
        self.stack1.append(result)
        while len(self.stack2) != 0:
            self.stack1.append(self.stack2.pop())
        return result


    # 队列是否为空
    def empty(self) -> bool:
        if len(self.stack1) == 0:
            return True
        return False
```

正常模拟方法可以看成将两个栈底对底拼起来来模拟一个队列的所有行为。

![679ef34cf7939965f5042ebec86f1f2.jpg](https://www.misaka19327.cc/static/img/776fc1656d87c481bc24496d89504c19.679ef34cf7939965f5042ebec86f1f2.jpg)

:::tip{title="提示"}
一定要注意转移元素只有在out栈为空时才能进行。
:::

``` python
from collections import deque

class MyQueue:

    def __init__(self):
        self.stack_in = deque()
        self.stack_out = deque()
        # 可用操作：压栈append 出栈pop 求长度len 判断是否全部为空

    # 进入队尾
    def push(self, x: int) -> None:
        self.stack_in.append(x)

    # 出队
    def pop(self, out: bool = True) -> int:
        if len(self.stack_out) == 0:
            while len(self.stack_in) != 0:
                self.stack_out.append(self.stack_in.pop())
        if out:
            return self.stack_out.pop()
        else:
            num = self.stack_out.pop()
            self.stack_out.append(num)
            return num

    # 查看队列首个元素
    def peek(self) -> int:
        # 这里提醒我了 可以对pop进行抽象 用默认值来设置函数参数
        return self.pop(False)

    # 队列是否为空
    def empty(self) -> bool:
        if len(self.stack_in) == 0 and len(self.stack_out) == 0:
            return True
        return False
```  

### 3 LeetCode225 用队列实现栈

:::info{title="题目"}
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
 

注意：

你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
 

示例：
```
输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
```

提示：

- 1 <= x <= 9
- 最多调用100 次 push、pop、top 和 empty
- 每次调用 pop 和 top 都保证栈不为空
:::

任务文档提醒我了，队列可以只用一个，没这一句的话我还真的会用两个队列去写。入栈和判空不说了，主要是出栈。出栈的原理就是队列的轮转，出队的元素可以再入队回到队尾，将队列中的除了最后一个元素的其他元素进行轮转，下一个要出队的元素就是要出栈的元素了。

``` python
from collections import deque


class MyStack:

    def __init__(self):
        self.queue = deque()
        # 队列允许的操作：入队append 出队popleft 求队列长度

    def push(self, x: int) -> None:
        self.queue.append(x)

    def pop(self, out: bool = True) -> int:
        for _ in range(len(self.queue) - 1):
            self.queue.append(self.queue.popleft())
        if out is True:
            return self.queue.popleft()
        num = self.queue.popleft()
        self.queue.append(num)
        return num

    def top(self) -> int:
        return self.pop(False)

    def empty(self) -> bool:
        if len(self.queue) == 0:
            return True
        return False
```

代码随想录算法训练营第十天 | LeetCode232 用栈实现队列、LeetCode225 用队列实现栈

今日任务：

1. LeetCode28 找出字符串中第一个匹配项的下标
2. LeetCode459 重复的子字符串
3. 字符串总结
4. 双指针回顾



> 今日心情：意识到了写博客的重要性，能够快速帮我回溯记忆。

资料来源：

1. [代码随想录 | 字符串：总结篇](https://programmercarl.com/%E5%AD%97%E7%AC%A6%E4%B8%B2%E6%80%BB%E7%BB%93.html#%E4%BB%80%E4%B9%88%E6%98%AF%E5%AD%97%E7%AC%A6%E4%B8%B2)
2. [代码随想录 | 双指针总结篇](https://programmercarl.com/%E5%8F%8C%E6%8C%87%E9%92%88%E6%80%BB%E7%BB%93.html#%E6%95%B0%E7%BB%84%E7%AF%87)
3. [代码随想录 | 28. 实现 strStr()](https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
4. [代码随想录 | LeetCode459 重复的子字符串](https://programmercarl.com/0459.%E9%87%8D%E5%A4%8D%E7%9A%84%E5%AD%90%E5%AD%97%E7%AC%A6%E4%B8%B2.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)

### 1 KMP简述

#### 1.1 KMP是什么？

KMP是一种针对字符串的算法，因为发明者为Knuth，Morris和Pratt三位学者，所以取名KMP。它的作用是**当字符串匹配失败时，在下一次的匹配中能够获取部分已经匹配的字符串，从而避免再次从头开始匹配**。如果是用暴力来在字符串中寻找匹配字符串，那么显而易见就是两轮循环，KMP可以利用最长相等前后缀来减少循环次数。

#### 1.2 最长相同前后缀

- 前缀：字符串的必须包含第一个字符，必须不包含最后一个字符的所有子串。
- 后缀：字符串的必须包含最后一个字符，必须不包含第一个字符的所有子串。

以字符串`aabcdaa`为例，它的所有前缀包括：

1. a
2. aa
3. aab
4. aabc
5. aabcd
6. aabcda

同理，所有后缀包括：

1. a
2. aa
3. daa
4. cdaa
5. bcdaa
6. abcdaa

在这些前后缀中，最长相同前后缀即为`aa`，长度为2。

#### 1.3 前缀表

前缀表，即为字符串的所有前缀的下标和最长相同前后缀的长度组成的表，还是以字符串`aabcdaa`为例，它的前缀表是这样的：


| 字符 | a | a | b | c | d | a | a |
| --- | --- | --- | --- | --- | --- | --- | --- |
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 最长相同前后缀的长度 | 0 | 1 | 0 | 0 | 0 | 1 | 2 |


#### 1.4 KMP匹配过程

以在字符串`aabaabaafaab`（文本串，变量名一般是`haystack`）中匹配`aabaaf`（模式串，变量名一般是`needle`）为例。

1. 求模式串的前缀表
    
    | 字符 | a | a | b | a | a | f |
    | --- | --- | --- | --- | --- | --- | --- |
    | 下标 | 0 | 1 | 2 | 3 | 4 | 5 |
    | 最长相同前后缀的长度 | 0 | 1 | 0 | 1 | 2 | 0 |
    
2. 开始循环匹配，每次匹配失败后，文本串从匹配失败后的位置开始，模式串以匹配失败的位置的前一个元素在前缀表中存储的最长相同前后缀的长度为下标开始下次匹配，直到匹配成功。

![cc8e05d80c6e07d2fc0ad7be1d07617.jpg](https://www.misaka19327.cc/static/img/8307d5963593628b4da9f771d9300736.cc8e05d80c6e07d2fc0ad7be1d07617.jpg)

#### 1.5 为什么KMP能够提升速度 && 为什么是前缀表

KMP能提升速度的原因在于，比起暴力两层循环，KMP需要的是对模式串的一次循环和实际匹配过程中的一次循环。后一次循环还能靠前缀表来减少匹配次数。KMP的时间复杂度是$O(m+n)$，这比暴力的$O(m+n)$要快多了。

前缀表的含义是每一个字串前后相同字符的长度，它代表了KMP最根本的目的：**在下一次的匹配中能够获取部分已经匹配的字符串**。前缀表所存储的最长相同前后缀就是这句话中的“部分已经匹配的字符串”。因为最长相同前后缀的含义，下一次循环开始时，在这次匹配点之前的字符都不再需要匹配，只需要从上一次循环匹配失败的点再次开始即可。

![f10c7f5ed4c118c7f527995ff869a3f.jpg](https://www.misaka19327.cc/static/img/b06bfa6c5acf38440ad65ed9b75ea274.f10c7f5ed4c118c7f527995ff869a3f.jpg)



### 3 字符串总结

字符串，在大部分的语言中的底层实现都是基于类似字符数组的形式。在用python解题时，更应该将其转换为`List[str]`，一个字符一个字符组成的列表来处理。

:::note{title="注"}
预留Java字符串的底层机制
:::

:::note{title="注"}
预留Go字符串的底层机制
:::

1. **双指针法**：典型代表就是反转字符串，两头的指针交换并且向中间移动；或者各种形式的扩充字符串，一个指针从最后往前，一个指针从实际内容往前；或者**各种形式的删除内容，两个指针一起从头往后移动，遇到要删除的元素就快指针+1慢指针不动，遇到不是要删除的元素就交换元素然后两个指针一起+1**。
2. **反转法**：一个是要注意，反转的取值范围，如何控制边界条件；一个是可以**通过先反转全部再反转部分来达到保持部分顺序不变的同时整体顺序反转，或者两次反转顺序反过来也有奇效**。
3. **KMP**：KMP的特点是当字符串匹配时，可以获取一部分上次的匹配信息，以避免这次次匹配时从头开始。它是字符串类题目的重点。

### 4 双指针回顾

双指针是个极其广泛的解法类型，它的最终目标是利用好两个指针，在一次循环内完成两次循环要做的事情。

1. **数组**：典型就是删除元素，两个指针一起从头往后移动，遇到要删除的元素就快指针+1慢指针不动，遇到不是要删除的元素就交换元素然后两个指针一起+1。如果暴力解法就是两次循环，利用双指针就是一次循环足矣。
2. **字符串**：见上。
3. **链表**：一个典型应用是反抓链表（那题我记得好像是三个指针来着？），另一个就是**利用步长不同的两个指针来探测是否存在环以及寻找环的入口**。
4. **N数之和**：

基本上粗体的就是我一开始想不到，并且预感自己绝对会忘的东西😂

代码随想录算法训练营第九天 | LeetCode28 找出字符串中第一个匹配项的下标、LeetCode459 重复的子字符串

今日任务：

1. LeetCode344 反转字符串
2. LeetCode541 反转字符串 Ⅱ
3. 卡码网54 替换数字
4. LeetCode151 反转字符串中的单词
5. 卡码网55 右旋字符串



> 今日心情：在先翻转全部，然后翻转部分这个思路上踩了两次坑，这个要记住。

资料来源：

1. [代码随想录 | LeetCode344 反转字符串](https://programmercarl.com/0344.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
2. [代码随想录 | LeetCode541 反转字符串 Ⅱ](https://programmercarl.com/0541.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2II.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
3. [代码随想录 | 卡码网54 替换数字](https://programmercarl.com/kama54.%E6%9B%BF%E6%8D%A2%E6%95%B0%E5%AD%97.html#%E6%80%9D%E8%B7%AF)
4. [代码随想录 | LeetCode151 反转字符串中的单词](https://programmercarl.com/0151.%E7%BF%BB%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%87%8C%E7%9A%84%E5%8D%95%E8%AF%8D.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)
5. [代码随想录 | 卡码网55 右旋字符串](https://programmercarl.com/kama55.%E5%8F%B3%E6%97%8B%E5%AD%97%E7%AC%A6%E4%B8%B2.html)

### 1 LeetCode344 反转字符串

:::info{title="题目"}
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。


示例 1：
```
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]
```
示例 2：
```
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
```

提示：

* 1 <= s.length <= 105
* s[i] 都是 ASCII 码表中的可打印字符
:::

大体思路就是前后两个指针，从头尾往中间去，一边走一边交换，这说是双指针我觉得也行。

另外就是文档里写到的：**如果题目的关键部分用了库函数就能解决，那么就不要用库函数；如果库函数只是这个题目考察重点的一部分，且已经了解库函数的实现原理，那么可以使用库函数。**

``` python
class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        first, last, temp = 0, len(s) - 1, 0
        while first < last:
            temp = s[first]
            s[first] = s[last]
            s[last] = temp
            first += 1
            last -= 1
```          

### 2 LeetCode541 反转字符串 Ⅱ

:::info{title="题目"}
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
 

示例 1：
```
输入：s = "abcdefg", k = 2
输出："bacdfeg"
```
示例 2：
```
输入：s = "abcd", k = 2
输出："bacd"
```

提示：

* 1 <= s.length <= 104
* s 仅由小写英文组成
* 1 <= k <= 104
:::

大体思路就是先计算要翻转的次数，按照次数进行翻转。翻转完成后，如果剩下的是k到2k的部分，就不处理直接加入数组；如果是0到k的部分，就翻转。

踩坑：

![image.png](https://www.misaka19327.cc/static/img/6aa3a6708d955912f6d8bda5afb5e0c5.image.png)

另外注意代码里的列表转字符串写法：`''.join(list)`。

``` python
# 我的代码
class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        return_str = []
        reverse_count = int(len(s) / k)
        if reverse_count % 2 == 0:
            reverse_count = int(reverse_count / 2)
        else:
            reverse_count = int(reverse_count / 2) + 1
        print(reverse_count)
        pointer = -1
        for _ in range(reverse_count):
            pointer += k
            for i in range(k):
                return_str.append(s[pointer - i])
            for i in range(k):
                if pointer + i + 1 < len(s):
                    return_str.append(s[pointer + i + 1])
            pointer += k
        if pointer < len(s):
            for i in range(len(s) - pointer - 1):
                return_str.append(s[len(s) - 1 - i])
        return ''.join(return_str)
``` 

### 3 卡码网54 替换数字

:::info{title="题目"}
题目描述
> 给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。 例如，对于输入字符串 "a1b2c3"，函数应该将其转换为 "anumberbnumbercnumber"。

输入描述

> 输入一个字符串 s,s 仅包含小写字母和数字字符。

输出描述

> 打印一个新的字符串，其中每个数字字符都被替换为了number

输入示例

> a1b2c3

输出示例

> anumberbnumbercnumber

提示信息

> 数据范围：
1 <= s.length < 10000。

:::

:::tip{title="提示"}
一点小技巧：大多数数组填充类的题，可以先扩充数组到目标长度，然后从最后往前开始填充试试。
:::

先遍历所有字符，找到数字，计算扩充后应有的长度，然后扩展数组，并且按从后往前的顺序开始从字符串的最后填充到数组的最后。

``` python
a = input()
first_pointer = len(a) - 1
str_list = list(a)
more_number_len = 0
for i in a:
    if 48 <= ord(i) <= 57:
        more_number_len += 5
str_list += ['0'] * more_number_len
last_pointer = len(str_list) - 1

for first_pointer in range(first_pointer, -1, -1):
    if 48 <= ord(str_list[first_pointer]) <= 57:
        str_list[last_pointer] = "r"
        last_pointer -= 1
        str_list[last_pointer] = "e"
        last_pointer -= 1
        str_list[last_pointer] = "b"
        last_pointer -= 1
        str_list[last_pointer] = "m"
        last_pointer -= 1
        str_list[last_pointer] = "u"
        last_pointer -= 1
        str_list[last_pointer] = "n"
        last_pointer -= 1
    else:
        str_list[last_pointer] = str_list[first_pointer]
        last_pointer -= 1
print("".join(str_list))
```

### 4 LeetCode151 反转字符串中的单词

:::info{title="题目"}
给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

 

示例 1：
```
输入：s = "the sky is blue"
输出："blue is sky the"
```
示例 2：
```
输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。
```
示例 3：
```
输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。
```

提示：

* 1 <= s.length <= 104
* s 包含英文大小写字母、数字和空格 ' '
* s 中 至少存在一个 单词
:::

删空格部分不提，大致的思路就是先翻转所有的字符，然后按照单词一个一个翻转，就能把单词顺序翻转的同时，不改变单词内字符的顺序。

只是，在删空格部分被爆杀。

``` python
class Solution:
    def reverseWords(self, s: str) -> str:
        str_list = list(s)
        i = 0
        while True:
            i += 1
            if i >= len(str_list): # 因为是边查边删 for容易越界
                break
            if ord(str_list[i]) == 32:
                if ord(str_list[i - 1]) != 32: # 单词之后的一个空格可以留
                    continue
                str_list.pop(i)
                i -= 1
        if ord(str_list[0]) == 32: # 检查开头
            str_list.pop(0)
        if ord(str_list[len(str_list) - 1]) == 32: # 检查结尾
            str_list.pop(len(str_list) - 1)

        first_pointer = 0
        last_pointer = len(str_list) - 1
        while first_pointer < last_pointer:
            temp = str_list[first_pointer]
            str_list[first_pointer] = str_list[last_pointer]
            str_list[last_pointer] = temp
            first_pointer += 1
            last_pointer -= 1

        first_pointer, last_pointer = 0, 0
        while first_pointer < len(str_list) - 1:
            # 先让后指针找到要翻转的词的末尾
            for last_pointer in range(last_pointer, len(str_list)):
                if last_pointer == len(str_list) - 1:
                    break
                if ord(str_list[last_pointer]) == 32:
                    last_pointer -= 1
                    break
            temp2 = last_pointer

            # 翻转词
            while first_pointer < last_pointer:
                temp = str_list[first_pointer]
                str_list[first_pointer] = str_list[last_pointer]
                str_list[last_pointer] = temp
                first_pointer += 1
                last_pointer -= 1

            # 再找到下一个词
            if temp2 == len(str_list) - 1:
                first_pointer = temp2
            else:
                first_pointer = temp2 + 2
                last_pointer = temp2 + 2

        return "".join(str_list)
```

### 5 卡码网55 右旋字符串

:::info{title="题目"}
题目描述
字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。 

例如，对于输入字符串 "abcdefg" 和整数 2，函数应该将其转换为 "fgabcde"。

输入描述
> 输入共包含两行，第一行为一个正整数 k，代表右旋转的位数。第二行为字符串 s，代表需要旋转的字符串。

输出描述
> 输出共一行，为进行了右旋转操作后的字符串。

输入示例
> 2
> 
> abcdefg

输出示例
> fgabcde

提示信息
数据范围：
* 1 <= k < 10000,
* 1 <= s.length < 10000;
:::

属于是刷过前几题之后应该想到的，失算了，然后在错误的思路上狂奔。我的思路还是太过欠考虑，最后还是没做出来。实际上正确的解法和LeetCode151是一致的，先翻转所有，再按段翻转。

另，该思路也可活用于左旋，道理是差不多的。

``` python
# 我的代码
num = int(input())
str_list = list(input())

sub_num = len(str_list) - num
first_pointer, last_pointer = 0, 0 

if sub_num >= num:
    first_pointer = len(str_list) - 1
    last_pointer = sub_num - 1
    while first_pointer > 0:
        temp = str_list[first_pointer]
        str_list[first_pointer] = str_list[last_pointer]
        str_list[last_pointer] = temp
        print(str_list)
        if last_pointer > 0:
            last_pointer -= 1
        elif last_pointer == 0 and sub_num == num:
            break
        first_pointer -= 1
elif sub_num < num:
    first_pointer = sub_num
    last_pointer = 0
    while last_pointer != len(str_list) - 1:
        temp = str_list[first_pointer]
        str_list[first_pointer] = str_list[last_pointer]
        str_list[last_pointer] = temp
        if first_pointer < len(str_list) - 1:
            first_pointer += 1
        last_pointer += 1

print("".join(str_list))
```

``` python
num = int(input())
str_list = list(input())

first_pointer = 0
last_pointer = len(str_list) - 1
while first_pointer < last_pointer:
    temp = str_list[first_pointer]
    str_list[first_pointer] = str_list[last_pointer]
    str_list[last_pointer] = temp
    first_pointer += 1
    last_pointer -= 1
    
first_pointer = 0
last_pointer = num - 1
while first_pointer < last_pointer:
    temp = str_list[first_pointer]
    str_list[first_pointer] = str_list[last_pointer]
    str_list[last_pointer] = temp
    first_pointer += 1
    last_pointer -= 1
    
first_pointer = num
last_pointer = len(str_list) - 1
while first_pointer < last_pointer:
    temp = str_list[first_pointer]
    str_list[first_pointer] = str_list[last_pointer]
    str_list[last_pointer] = temp
    first_pointer += 1
    last_pointer -= 1

print("".join(str_list))
```