2025.3.8 淘天笔试（个人整理，仅供参考）
第一题
小红拿到了一个01串，她可以进行最多一次操作：选择一个连续子串，将它们所有字符取反（0变1，1变0）。小红想知 道，最终1字符数量的最大值是多少？
输入描述
一个仅由0和1字符组成的字符串，长度不超过200000
输出描述
一个整数，代表'1′数量的最大值。
样例输入
101001001
样例输出
7
解法一
题目转化为找出含0最多的连续子串，这样翻转完后1才能最多。先求所有1的数量为sum，再求子串数位的和（使用前缀和），需要把所有的0当成-1，求与sum差值最大的子串。
import java.util.Scanner;
public class taotianT1 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
int sum = s.chars()
.map(c -> c - '0')
.sum();
int[] preSum = new int[s.length()];
preSum[0] = s.charAt(0) == '0' ? -1 : 1;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == '0') {
preSum[i] = preSum[i - 1] - 1;
} else {
preSum[i] = preSum[i - 1] + 1;
}
}
int max = sum;
for (int i = 0; i < s.length(); i++) {
for (int j = 0; j <= i; j++) {
int diff = preSum[i] - preSum[j];
max = Math.max(max, sum - diff);
}
}
System.out.println(max);
}
}
- 时间复杂度： O(n^2)
- 空间复杂度： O(n)
解法二
==类似力扣53==
这个问题可以用 Kadane’s Algorithm（最大子段和）变形来解决。思路如下：
- 计算原始的 1 的数量，即如果不做任何操作，有多少个 1。
- 转换数组：
- 0 变成 +1（因为反转它会增加 1 的数量）。
- 1 变成 -1（因为反转它会减少 1 的数量）。
- 使用 Kadane’s Algorithm 计算最大子数组和：
- 这个最大子数组和代表如果选择最优的子串进行翻转，能额外增加多少个 1。
- 计算最终答案：
- 最大1数量 = 原始1的数量 + 最大子数组和
- 需要注意的是，如果最大子数组和为负数，则不翻转，即结果仍然是原始 1 的数量。
import java.util.Scanner;
public class taotianT1 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.next();
scanner.close();
int originalOnes = 0; // 原始的 1 的数量
int maxGain = 0, currentGain = 0;
boolean hasZero = false; // 判断是否至少有一个 0
for (char c : s.toCharArray()) {
if (c == '1') {
originalOnes++;
currentGain -= 1; // 1 变 -1
} else {
hasZero = true;
currentGain += 1; // 0 变 +1
}
// Kadane’s Algorithm 维护最大子段和
if (currentGain < 0) {
currentGain = 0; // 重新开始计算子数组
}
maxGain = Math.max(maxGain, currentGain);
}
// 如果全是 1，那么翻转任何子串都会减少 1 的数量，所以只能少翻转一个 1
System.out.println(hasZero ? (originalOnes + maxGain) : (originalOnes - 1));
}
}
- 时间复杂度： O(n)
- 空间复杂度： O(1)
第二题
小红现在有每种小写字母若干个，她想把这些字母组成一个字符串s，使得字符串s任意两个相邻字母都不一样，请 你帮助她求出最长字符串的长度。
输入描述
每个测试文件均包含多组测试数。第一行输入一个整数 T（1≤T≤1000），代表数据组数，每组测试数据描述如下：对于每一组 测试数据，每行26个整数，依次表示a-z的字母数量x(0≤xi≤10)。
输出描述
每组数据输出一个整数，表示满足条件的最长字符串的长度。
示例1
输入
3
24个0 1 1
23个0 1 1 1
25个1 5
输出
2
3
30
解法
计算数量最多的那个字母的数量maxFreq，如果总数total大于等于2*maxFreq，那么怎么排列都可以满足题意，直接返回total；否则，取剩余字母的总数量，这些字母可以随意排列，数量最多的那个字母需要插空放到这些数字之间的空，共有total - maxFreq + 1个空，总数就是(total - maxFreq) * 2 + 1。
import java.util.Scanner;
public class taotianT2 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
for (int i = 0; i < n; i++) {
int[] freq = new int[26];
for (int j = 0; j < 26; j++) {
freq[i] = scanner.nextInt();
}
int maxFreq = 0, total = 0;
for (int num : freq) {
maxFreq = Math.max(maxFreq, num);
total += num;
}
if (total >= 2 * maxFreq) {
System.out.println(total);
} else {
System.out.println((total - maxFreq) * 2 + 1);
}
}
scanner.close();
}
}
第三题
小红拿到了一棵树，树上的每个节点被染色成了红色、绿色或蓝色。小红可以在两个不同颜色的相邻节点之间来回行走，但如果两个相邻节点的颜色相同，则不能行走。小红可以在开始行走之前选择任意一个点修改它的颜色（最多只能修改一次)，然后小红可以选择任意一个起始点开始行走。小红希望自己走过的节点数量尽可能多（一个节点走多次也只计算一次）。请你求出小红能走的最多节点数量。
输入描述
第一行输入一个正整数n，代表节点数量。
第二行输入一个长度为n的、仅由R、G、B三种字符组成的字符串，第i个字符为R代表i号节点被染成红色，G代表染成绿色，B代表染成蓝色。
接下来的n-1行，每行输入两个正整数u和v，代表节点u和节点v有一条边连接。1<=n<=100000，1<=u，V<=n
输出描述
一个正整数，代表小红最多可以走的节点数量。
示例1
5
RRRGB
1 2
1 3
1 4
1 5
输出
4
说明
将1号节点修改为蓝色，然后小红选择1号节点为起点，可以这样走：1 -> 2-> 1 -> 3 -> 1 -> 4，这样一共走到了4个节点。
示例2
输入
3
RRB
1 2
2 3
输出
3
解法
使用 DFS 计算最大可行走的节点数。思路如下：
- 建图：使用 邻接表 存储树结构。
- 模拟行走：
- 先尝试不修改颜色的情况下计算最大可行走的节点数。
- 枚举修改某个节点颜色后，计算新的最大可行走节点数。
- 优化 DFS 计算：
- 记录每个节点在原颜色下的最大可达节点数。
- 仅修改节点颜色后进行一次 DFS 重新计算，避免重复计算。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
public class taotianT3 {
static int n;
static char[] colors;
static List<Integer>[] tree;
static int maxNodes = 0;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
scanner.nextLine();
String colorStr = scanner.nextLine();
colors = new char[n + 1];
for (int i = 1; i <= n; i++) {
colors[i] = colorStr.charAt(i - 1);
}
tree = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) {
tree[i] = new ArrayList<>();
}
for (int i = 0; i < n - 1; i++) {
int u = scanner.nextInt();
int v = scanner.nextInt();
tree[u].add(v);
tree[v].add(u);
}
scanner.close();
// 计算原始最大可达节点数
maxNodes = getMaxReachableNodes();
// 枚举修改某个节点的颜色，尝试获取更优解
char[] originalColors = Arrays.copyOf(colors, n + 1);
for (int i = 1; i <= n; i++) {
for (char newColor : new char[]{'R', 'G', 'B'}) {
if (newColor != originalColors[i]) {
colors[i] = newColor;
maxNodes = Math.max(maxNodes, getMaxReachableNodes());
}
}
colors[i] = originalColors[i]; // 恢复原始颜色
}
System.out.println(maxNodes);
}
private static int getMaxReachableNodes() {
boolean[] visited = new boolean[n + 1];
int maxReach = 0;
for (int i = 1; i <= n; i++) {
Arrays.fill(visited, false);
maxReach = Math.max(maxReach, dfs(i, visited));
}
return maxReach;
}
private static int dfs(int node, boolean[] visited) {
visited[node] = true;
int count = 1;
for (int neighbor : tree[node]) {
if (!visited[neighbor] && colors[node] != colors[neighbor]) {
count += dfs(neighbor, visited);
}
}
return count;
}
}
哔哩哔哩公司福利 351人发布
查看26道真题和解析
投递阿里巴巴集团等公司10个岗位