IMPORTANT
第二题难度加倍，操作数有 6 种，黑科技过了。。第三题编辑距离，真离谱，都怀疑数据有问题了，我考完去力扣过了，但是笔试硬是没过！！！🤬
由于笔试不支持在 IDE 上编辑，因此暂不给出代码

第一题#

题意描述#

给你一个字符串，如果有连续的超过三个重复的字符，删掉至小于 3 个，且每次至少删除 3 个重复字符，如果删完之后依然有连续的超过三个重复的字符，则继续利用删除规则删掉至小于 3 个

数据范围#

无

解法#

栈#

时间复杂度 $O(n)$

设置两个栈，一个是字符栈，一个是对应字符数量栈

一次遍历字符串，如果 $s[i] != s[i - 1]$

如果 $3$ $3$ 整除栈顶字符数量，那么此时取出栈顶元素即可
- 如果此时的栈顶字符等于 $s[i]$ ，就将栈顶元素的数量加一即可
- 否则将 $s[i]$ 加入栈中即可
如果 3 不整数栈顶字符数量，直接将 $s[i]$ 加入栈中即可

最后注意判断栈顶字符数量是否大于等于 3 即可

代码如下

暂无

WARNING
下题暂未给出思路以及代码，等复习一手正则表达式

第二题#

题意描述#

正则表达式字符串匹配。给你一个字符串 $s$ 和一个字符匹配串 $p$ ，问 $p$ 是否匹配 $s$ ？

其中 $p$ 可能出现的字符为: ^,?,+,*, . ,$

NOTE
本场最难的一题

数据范围#

字符串长度小于等于 $100$

解法#

动态规划#

时间复杂度 $O(nm)$

在看了相关语法后，在此题中，字符 ^ 只能出现在第一个位置，且 ^ 的后面不能是 +, * , ?。那么剩下的还有 ^, ., $ 以及字母，无论 ^ 后面是什么，都以其后面的为主，因此最开头出现 ^ 直接删掉即可，如果中间或者末尾出现 ^ ，直接返回 false 即可。

同理，$ 也是一样，其只能出现在末尾位置，如果 $ 出现在中间位置，则直接返回 false；$ 前面同样也不能是 +, *, ?，剩下的^, ., $ 以及字母，都是以前一个字符为主，因此同样可以删掉最后一个 $ 即可

综上，经过处理后，字符匹配串里面只会有 ? + * . ，这其实就跟力扣的正则表达式差不多了，就是需要多判断两个字符和多一点转移。

代码如下

暂无

第三题#

题目大意#

有 $T$ 组数组，每个数据给你两个字符串 $s, p$

这两个字符串都是 DNA 链，也就是说只有 AGCT 四种字符。

$DNA$ 链有可能发生替换、删除和增加

换句话说，这题就是求编辑距离

NOTE
但是就是不对，我都怀疑他的三种操作根本不是编辑距离的三种操作了，或者题目数据有问题

数据范围#

字符串长度 $\le 100$

题解#

动态规则#

时间复杂度 $O(nm)$

设 $f(i,j)$ 为 $s[1-i]$ 和 $p[1-j]$ 的编辑距离，因此 $f(i,j)$ 的计算公式为

f(i,j)= \begin{cases} min\{f(i,j-1)+1, f(i-1,j)+1, f(i-1,j-1)+1\}, & \text{if } s[i]\neq p[j] \\ min\{f(i,j-1)+1, f(i-1,j)+1, f(i-1,j-1)\}, & \text{if } s[i]=p[j] \end{cases}

代码如下

暂无

第四题#

题目大意#

有 $T$ 个样例，对于每个样例：

有一个长度为 $n$ 的序列,接下来给你 $n$ 行数据，让你求这个序列

每行有两个整数，第一个整数为 $a$ ， $a$ 是反转序列中的一个数；第二个整数为 $b$ ，表示在反转序列中 $a$ 的下一个数在第 $b$ 行。如果在反转序列中， $a$ 是最后一个数，则 $b=0$

数据范围#

$T \le 10$
$n \le 10^6$

题解#

单链表#

$O(nT)$

由于在反转序列中，出了第一个数外，其他数都是上一个数指向其位置。

例如：

$n = 3$
序列为 $[2,4,1]$
反转序列为 $[1,4,2]$
$n$ 行输入数据为:
$4 \ \ 3$
$1 \ \ 1$
$2 \ \ 0$

可以发现除了第 $2$ 个数据，其余行的数都有指向的，因此，第 $2$ 行数据就是单链表的头结点， $a_i$ 表示数据域， $b_i$ 表示指针域， $b=0$ ，表示 NULL 值。

因此，只需要找到头结点，然后单链表遍历即可，最后输出反转后的链表。

代码如下

暂无

吐槽#

题目的确有的不是很规范。