AI刷题-最小替换子串长度、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
3
样例 2
INPUT
5 2
1 0 1 0 2
1 2
1 5
2 4
3 5
OUTPUT
0
解题思路：
问题理解
你需要将一棵树划分为多个连通分块，每个分块中只包含一种礼物（或者没有礼物）。树的节点数 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;
}
运行结果：
原文地址：https://blog.csdn.net/m0_73302939/article/details/145233253
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！