AI刷题-最小替换子串长度、Bytedance Tree 问题

一、最小替换子串长度

问题描述

输入格式

输出格式

输入样例 1

输出样例 1

输入样例 2

输出样例 2

解题思路：

问题理解

数据结构选择

算法步骤

最终代码：

运行结果：

二、Bytedance Tree 问题

问题描述

输入格式

输出格式

数据范围

解题思路：

问题理解

数据结构选择

算法步骤

最终代码：

运行结果：

一、最小替换子串长度

问题描述

输入一个长度为 4 倍数的字符串，只有A、S、D、F四个字母构成，现要求替换其中一个子串，调整为词频一样的字符串。例如ADDF，只需要替换D到S，就可以得到四个字母词频一样的字符串ASDF。求满足要求的最小子串长度。

输入格式

第一行输入一个字符串

输出格式

输出 1 个整数，满足要求的最小子串长度

输入样例 1

ADDF

输出样例 1

1

样例说明：替换D为S，将ADDF转为ASDF

输入样例 2

ASAFASAFADDD

输出样例 2

输出：3

样例说明：替换AFA为SFF，将ASAFASAFADDD转成ASAFASSFFDDD

解题思路：

问题理解

题目要求我们找到一个最小的子串，通过替换这个子串，使得整个字符串中A、S、D、F四个字母的词频相等。输入字符串的长度是4的倍数，这意味着每个字母的理想词频应该是总长度的四分之一。

数据结构选择

我们可以使用一个数组来记录当前字符串中每个字母的词频。然后，我们可以通过滑动窗口的方式来找到一个最小的子串，使得替换这个子串后，所有字母的词频达到理想状态。

算法步骤

初始化词频数组：记录当前字符串中每个字母的词频。
计算理想词频：理想词频是总长度的四分之一。
滑动窗口：
- 从左到右遍历字符串，维护一个窗口，窗口内的字母词频与理想词频的差距最小。
- 当窗口内的字母词频与理想词频的差距达到最小值时，记录当前窗口的长度。
返回最小窗口长度：最终返回找到的最小窗口长度。

最终代码：

#include <iostream>
#include <string>
#include <unordered_map>
#include <algorithm>
#include <limits>  // 添加此行以包含 numeric_limits// 声明 isTrue 函数
bool isTrue(std::unordered_map<char, int>& temp, std::unordered_map<char, int>& map, int num);int solution(std::string input) {int length = input.length();int res = std::numeric_limits<int>::max();  // 使用 numeric_limits// 判断每个字符应该有几个int num = length / 4;// 记录当前字符情况std::unordered_map<char, int> map;for (int i = 0; i < length; i++) {map[input[i]]++;}// 遍历for (int i = 0; i < length; i++) {// 记录替换区字符情况std::unordered_map<char, int> temp;for (int j = i; j <= length; j++) {if (isTrue(temp, map, num)) {res = std::min(res, j - i);break;} else if (j < length) {temp[input[j]]++;}}}return res;
}bool isTrue(std::unordered_map<char, int>& temp, std::unordered_map<char, int>& map, int num) {for (auto& entry : map) {char key = entry.first;if (entry.second - temp[key] > num) {return false;}}return true;
}int main() {// 你可以添加更多测试用例std::cout << (solution("ADDF") == 1) << std::endl;std::cout << (solution("ASAFASAFADDD") == 3) << std::endl;std::cout << (solution("AFAFSSFDSFFF") == 3) << std::endl;return 0;
}

运行结果：

二、Bytedance Tree 问题

问题描述

众所周知，每两周的周三是字节跳动的活动日。作为活动组织者的小 A，在这次活动日上布置了一棵 Bytedance Tree。

Bytedance Tree 由 n 个结点构成，每个结点的编号分别为 1，2，3......n，有 n - 1 条边将它们连接起来，根结点为 1。而且为了观赏性，小 A 给 M 个结点挂上了 K 种礼物（0 ≤ K ≤ M ≤ N，且保证一个结点只有一个礼物)。

现在小 A 希望将 Bytedance Tree 划分为 K 个 Special 连通分块，送给参加活动日活动的同学们，请问热心肠的你能帮帮他，告诉小 A 一共有多少种划分方式吗？

一个 Special 连通分块应该具有以下特性：

Special 连通分块里只有一种礼物（该种类礼物的数量不限）
Special 连通分块可以包含任意数量的未挂上礼物的结点

由于方案数可能过大，对结果取模 998244353

输入格式

第一行输入两个整数 n 和 k，分别表示 n 个结点和 k 种装饰品。

接下来一行，输入 n 个整数 a0, a1,...an，表示第 i 个结点挂着的礼物种类为 ai（0 表示没有挂礼物）

接下来 n - 1 行，输入两个整数 u 和 v，分别表示结点 u 和结点 v 之间有一条边。

输出格式

一行

输出方案数即可

数据范围

2 ≤ n ≤ 1000000（1e6）

2 ≤ k ≤ n

样例 1

INPUT

7 3

1 0 0 0 0 2 3

1 7

3 7

2 1

3 5

5 6

6 4

OUTPUT

样例 2

INPUT

5 2

1 0 1 0 2

1 2

1 5

2 4

3 5

OUTPUT

解题思路：

问题理解

你需要将一棵树划分为多个连通分块，每个分块中只包含一种礼物（或者没有礼物）。树的节点数 n 和礼物种类数 k 都可能很大，因此需要一个高效的算法来解决这个问题。

数据结构选择

树的表示：由于树的节点数可能达到 1000000，使用邻接表来表示树是比较合适的。这样可以高效地进行遍历和查找。
礼物信息：可以使用一个数组来存储每个节点的礼物种类。

算法步骤

读取输入：首先读取节点数 n 和礼物种类数 k，然后读取每个节点的礼物种类，最后读取树的边信息。
构建树：使用邻接表来构建树。
DFS遍历：使用深度优先搜索（DFS）来遍历树，并计算每个礼物种类的连通分块数。具体步骤如下：
- 从根节点开始遍历树。
- 对于每个节点，记录其礼物种类。
- 如果当前节点的礼物种类与父节点的礼物种类不同，则说明进入了一个新的连通分块。
- 统计每个礼物种类的连通分块数。
计算方案数：根据每个礼物种类的连通分块数，计算总的划分方案数。由于方案数可能很大，需要对结果取模 998244353。

最终代码：

#include <iostream>
#include <vector>
#include <queue>using namespace std;const long long MOD = 998244353;int solution(int nodes, int decorations, vector<vector<int>>& tree) {// 模拟输入的第一行是礼物分布vector<int> decorationsList = tree[0];// 找到所有挂有礼物的结点vector<int> decorationNodes;for (int i = 0; i < decorationsList.size(); i++) {if (decorationsList[i] != 0) {decorationNodes.push_back(i + 1); // 1-based indexing}}// 检查礼物的数量是否与K一致if (decorationNodes.size() != decorations) {return 0;}// 检查每种礼物类型是否只对应一个结点vector<int> typeCount(decorations + 1, 0);for (int i = 0; i < decorationsList.size(); i++) {if (decorationsList[i] != 0) {typeCount[decorationsList[i]]++;}}for (int t = 1; t <= decorations; t++) {if (typeCount[t] != 1) {return 0;}}// 选择第一个礼物结点作为根结点int root = decorationNodes[0];// 构建树的邻接表vector<vector<int>> adj(nodes + 1);for (int i = 1; i < tree.size(); i++) {int u = tree[i][0];int v = tree[i][1];adj[u].push_back(v);adj[v].push_back(u);}// BFS 来确定每个结点的父结点vector<int> parent(nodes + 1, 0);vector<bool> isDecoration(nodes + 1, false);for (int node : decorationNodes) {isDecoration[node] = true;}parent[root] = -1;queue<int> q;q.push(root);while (!q.empty()) {int u = q.front();q.pop();for (int v : adj[u]) {if (parent[v] == 0 && v != root) {parent[v] = u;q.push(v);}}}// 计算方案数long long total = 1;for (int i = 1; i < decorationNodes.size(); i++) {int node = decorationNodes[i];int count = 0;int current = node;while (parent[current] != -1) {int p = parent[current];count++;if (isDecoration[p]) {break;}current = p;}total = (total * count) % MOD;}return total;
}