学校数据结构2022-03-11上机题

T1 手撕STL sort

问题描述

模拟实现C++中STL sort的功能。

设数组 $a$ 中有 $n$ 个元素，有三个要求。

1. 当递归区间小于设定值时，直接返回。
2. 当递归深度超过 $\lfloor 2 \cdot \log_{2}{n} \rfloor$ 时，转为堆排序。
3. 最后对整个数组进行直接插入排序。

题解

这题解法都已经给好了，就对着书上把相应的代码抄下来，然后按照题意组合就行了。注意若区间足够小，一定是先返回，只有当要求 $1$ 不满足时，才考虑堆排序。

T2 冬奥会接驳车

问题描述

一个 $n \times m$ 的矩阵，其中每个元素为，$0$ 空地，$1$ 障碍，$3$ 起点，$4$ 终点。

一个人从起点出发，只能上下左右移动，不能碰到障碍，求最少几步能够到终点。

$1 \le n,m \le 100$

题解

显而易见的 $BFS$ 问题，从起点开始，每次向四个方向扩展，走到的地方如果不是障碍且步数更少就入队，直到走到终点即可。如果所有元素出队后，终点仍未入队（没走到），则无解。

(X,Y) => 队列Q;   
dis(X,Y) = 0;   //起点入队，dis记录步数
while (head < tail)     //队列不空
{
    Q => (X,Y);
    for (int i = 0; i < 4; ++i)
    {
        (X,Y) + next[i] -> (x,y);   //向四个方向扩展
        if (x,y)未过边界 && (x,y)不是障碍 && (dis(X,Y) + 1 < dis(x,y))
        {
            dis(x,y) = dis(X,Y) + 1;
            (x,y) => Q;     //新点入队
        }
    }
}

时间复杂度 $O(n \cdot m)$ 。

T3 自动纠错

问题描述

两个字符串 $s1,s2$ 之间的距离 $dis$ 定义为，有三种操作：

1. 删去任意位置一个字符
2. 增加任意位置一个字符
3. 改变任意位置一个字符

$s1$ 改变为 $s2$ 所需要的最小的操作次数，为两者间的距离。如图所示的距离（上 $s1$ ，下 $s2$ ）为 $4$ 。

现有一个字典，其中有 $n$ 个元素，每个元素为字符串 $s$ 和其对应的频率 $p$ 。

给出 $m$ 个询问，每个询问为一个字符串 $q$ ，问字典中哪些字符串和 $q$ 的距离在 $d$ 之内，并输出其中频率最高的（频率相同时字典序更小）。

$n \le 10^4,m \le 10^3,d \le 2$

题解

数据结构

具体的数据结构题目已经很明显的给出了：

一种高效的处理方法是：结合各单词间的距离，将字典组织成一棵多叉树。在该树中，每个结点表示一个单词，对于每个结点 $p$ ，其第 $i$ 棵子树包含与 $p$ 的距离为 $i$ 的所有单词对应的结点。

树的创建过程如下：取字典中任意单词作为根结点，比如第一个单词。然后将剩余单词逐个插入到树中，插入一个新单词 $w$ 时，首先计算该单词与根结点的距离 $d$ 。若根结点的第 $d$ 个子树为空，则将单词 $w$ 对应的结点作为根结点的第 $d$ 个子结点。若根结点的第 $d$ 个子树非空，即根结点已有第 $d$ 个子结点 $p_d$ 。则按上述规则将单词 $w$ 递归插入以 $p_d$ 为根的子树，即计算 $w$ 与 $p_d$ 的距离…。

例如字典为 $help, hell, hello, shell, helper, sloop, helps, troop$ ，将 $help$ 作为根结点，然后将 $hell$ 插入，$hell$ 与 $help$ 的距离为 $1$ ，故 $hell$ 作为 $help$ 的第一个子结点。$hello$ 与 $help$ 的距离为 $2$ ，故 $hello$ 作为 $help$ 的第 $2$ 个子结点。如下图 $(a)$ 所示。

然后插入 $shell,shell$ 与 $help$ 的距离为 $2$ ，故应在 $help$ 的第 $2$ 个子树里，但 $help$ 已经有第 $2$ 个子结点 $hello$ 了，此时将 $shell$ 递归插入以 $hello$ 为根结点的子树：计算 $shell$ 与 $hello$ 的距离为 $2$ ，将 $shell$ 作为 $hello$ 的第 $2$ 个子结点，如上图 $(b)$ 所示。插入 $helper$ 时，$helper$ 与 $help$ 的距离为 $2$ ，将 $helper$ 递归插入以 $hello$ 为根结点的子树：计算 $helper$ 与 $hello$ 的距离为 $3$ ，将 $helper$ 作为 $hello$ 的第 $3$ 个子结点。以此类推，最终上述字典对应的树结构如上图 $(c)$ 所示。该树结构保证与任意结点距离为 $d$ 的单词都在该结点的第 $d$ 棵子树里。

假定我们需要向用户返回与错误单词距离不超过 $n$ 的单词，当用户输入一个单词 $w$ 时，在树中查询 $w$ ，计算 $w$ 与根结点 $T$ 的距离 $d$ ，接下来我们不必考察 $T$ 的所有子树中是否包含与 $w$ 距离不超过 $n$ 的结点/单词，而只需要递归考察根结点 $T$ 的第 $d-n$ 到第 $d+n$ 棵子树即可。例如 $n=1,d=5$ ，我们只需要递归考察根 $T$ 的第 $4$ 、第$5$、第$6$棵子树是否包含与$w$距离不超过$1$的结点/单词。其他子树无需考察，为什么呢？举个例子，我们考虑根$T$的第$3$棵子树的任意结点$P$。$w$与$T$的距离为$d=5$，即$w$最少经过$5$步操作才能转换为$T$，$T$与$P$的距离为$3$，$T$经过最少$3$步操作才能变为$P$，这意味着$w$至少需要$2$步操作才能变为$P$。不可能通过$1$步操作变为$P$。故第$3$棵子树的所有结点都不满足条件。

由于$n$通常很小，因此该方法在查询时往往可以排除很多子树，进而节省时间。当考察一个结点时，计算$w$与该结点的距离$d$；若$d=0$，意味着用户输入的单词$w$在字典中，是正确的单词；若$d > n$则该结点不是候选单词，继续递归考察该结点第$d-n$到$d+n$的子树。若$d ≤ n$则该结点就是候选单词之一，此时可有两种策略，一是将该单词直接返回给用户，二是继续向下考察子树，找出所有候选单词并选择用户历史使用频率最高的单词返回给用户。

以上为题目给出的算法，注意这个算法时间复杂度并不严格，只是能在某种程度上减少比较次数，但可以确保通过此题（需注意实现算法的常数）。

计算字符串距离

除此以外，还有一个重要的问题就是，如何计算两个字符串的距离。

可见每个位置都有三种操作，如果直接暴力比较，虽然字符串的长度只有 $15$ ，也仍然需要 $3^{15}$ 次比较，显然是无法接受的。

这里提出一种有效的解决方案，这个问题可以使用动态规划解决。

设 $dp[i][j]$ 为 $s1$ 考虑到 $i$ 位置，$s2$ 考虑到 $j$ 位置，$s1_{1 \cdots i},s2_{1 \cdots j} $ （前缀）的距离。显然对于 $i,j$ 有两种情况：

1. $s1[i]=s2[j]$ ，此时 $dp[i][j]=dp[i-1][j-1]$
2. $s1[i] \not = s2[j]$ ，此时 $dp[i][j]=min\{dp[i-1][j-1],dp[i-1][j],dp[i][j-1]\}+1$

对于 $1$ 很好理解，两个位置相同，就没必要操作，直接从之前的状态扩展即可。

对于 $2$ ，三个式子正好对应三种操作（改变，增加，减少），因为要次数最少，所以取三者最小值，再加上一次操作次数，拓展到新状态。

边界条件可根据状态得出：

1. $dp[i][0]=i$ 显然 $s2$ 是空，则 $s1$ 最少通过减 $i$ 个字符与其相同。
2. $dp[0][j]=j$ 同上。

int Dis(char *s1, char *s2)
{
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int dp[Max_len][Max_len] = {0};
    int len = max(len1, len2);
    for (register int i = 0; i <= len; ++i)
        dp[i][0] = dp[0][i] = i;       //边界条件
    for (register int i = 1; i <= len1; ++i)
        for (register int j = 1; j <= len2; ++j)
            if (s1[i - 1] == s2[j - 1])
                dp[i][j] = dp[i - 1][j - 1];    //情况1
            else
                dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;      //情况2
    return dp[len1][len2];
}

时间复杂度 $O(len^2)$ ，$len$ 为字符串长度。