携程4.16笔试
第二道：三个数组abc，游游打算重排c数组，使得尽可能多的下标i满足ai+bi=ci。
思路：ai+bi的值是固定的 先用一个for循环算一遍 放到map里 ，key是值，value是个数，然后再用一个for循环 看看数组c里的值有没有在map里出现，有的话 计数+1，并且让map里相应的key 值-1 然后就好了。
第三题：给一个数组，每次操作可以把相邻的两个素数元素进行合并，合并后的新数为原来的两个数之和，并删除原来两个数。现在希望最终数组的元素数量尽可能少。
第一行输入n表示数组大小，第二行输入n个正整数，表示数组元素。
思路：
1.写一个检查是否是素数的函数
2.写一个合并函数：
2.1先判断2 这个特殊情况 因为素数2和相邻的素数合并 结果可能是素数也可能是非素数 别的素数合并都是非素数。所以要先判断存不存在2和相邻的一边的素数合并是素数 另一边合并不是素数的情况 比如数组7 2 3 后两个先合并和前两个先合并就不一样。
2.2再把其余素数合并
代码：
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class PrimeMerge {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
List<Integer> numbers = new ArrayList<>();
// 读取数组元素
for (int i = 0; i < n; i++) {
numbers.add(scanner.nextInt());
}
// 关闭Scanner
scanner.close();
// 合并素数，优先处理2
mergePrimesWithPriorityToTwo(numbers);
// 输出最终数组
for (int num : numbers) {
System.out.print(num + " ");
}
}
private static void mergePrimesWithPriorityToTwo(List<Integer> numbers) {
// 检查一个数是否是素数的辅助函数
boolean isPrime(int num) {
if (num <= 1) return false;
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
// 合并2与其相邻的素数
for (int i = 0; i < numbers.size(); ) {
if (numbers.get(i) == 2) {
// 检查左边是否有素数可以合并
if (i > 0 && isPrime(numbers.get(i - 1)) && isPrime(numbers.get(i - 1) + 2)) {
numbers.set(i - 1, numbers.get(i - 1) + 2);
numbers.remove(i);
} else if (i < numbers.size() - 1 && isPrime(numbers.get(i + 1)) && isPrime(numbers.get(i + 1) + 2)) {
// 检查右边是否有素数可以合并
numbers.set(i, numbers.get(i) + numbers.get(i + 1));
numbers.remove(i + 1);
} else {
// 没有可以合并的素数，继续下一个数
i++;
}
} else {
i++;
}
}
// 合并剩余的素数对
for (int i = 0; i < numbers.size() - 1; ) {
if (isPrime(numbers.get(i)) && isPrime(numbers.get(i + 1)))) {
numbers.set(i, numbers.get(i) + numbers.get(i + 1));
numbers.remove(i + 1);
} else {
i++;
}
}
}
}
第四题：定义一棵树的直径为：任意两个节点的距离的最大值。现在定义f(i)：对i号节点上再连接一个新的子叶节点后，树的直径长度。现在要求f(1)到f(n)的值。
输入描述：第一行输入一个正整数n，代表树的节点数量。
接下来的n-1行，每行输入两个正整数u和v，代表u号节点和v号节点之间有一条长度为1的边连接。
变量的范围：1≤n≤10的五次方，1≤u，v≤n。
思路：第四题说是树的直径，但其实就是图，但是可以用二叉树类比着来做。
1.写一个树类，val表示节点编号，children表示孩子链表。把每个节点创建处理并保存，把每个节点的孩子节点添加一下。
2.写一个for循环，针对每个f(i)，把新的子叶节点添加一下，然后调用dfs处理得到f(i)值。
3.dfs：二叉树求直径实际上是求子树的深度，然后左右子树深度相加就是直径，返回结果是左右子树深度的最大值+1。同样的道理，这里也是求所有子树的深度，记录最大深度和第二大深度，然后f(i)就是最大深度和第二大深度之和，返回结果就是最大深度+1。
代码：
import java.util.*;
class TreeNode {
int val;
List<TreeNode> children;
public TreeNode(int val) {
this.val = val;
children = new ArrayList<>();
}
}
public class TreeDiameter {
public static int[] f; // 存储每个节点的f(i)值
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 树的节点数量
f = new int[n + 1]; // 初始化f数组
// 构建树的数据结构
TreeNode[] nodes = new TreeNode[n + 1];
for (int i = 1; i <= n; i++) {
nodes[i] = new TreeNode(i);
}
// 连接节点之间的关系
for (int i = 0; i < n - 1; i++) {
int u = scanner.nextInt();
int v = scanner.nextInt();
nodes[u].children.add(nodes[v]);
nodes[v].children.add(nodes[u]);
}
// 遍历每个节点，添加一个新的子叶节点，计算f(i)
for (int i = 1; i <= n; i++) {
// 添加新的子叶节点
addLeafAndDFS(nodes[i], n + i);
// 计算f(i)
dfs(nodes[i], null, i);
}
// 输出结果
for (int i = 1; i <= n; i++) {
System.out.print(f[i] + " ");
}
}
// 添加新的子叶节点，并调用dfs计算f(i)
public static void addLeafAndDFS(TreeNode node, int newLeafValue) {
TreeNode newLeaf = new TreeNode(newLeafValue); // 创建新的子叶节点
node.children.add(newLeaf); // 添加到当前节点的子节点中
newLeaf.children.add(node); // 添加当前节点作为新的子叶节点的父节点
}
// 递归计算以当前节点为根的子树的直径
public static void dfs(TreeNode node, TreeNode parent, int i) {
int maxDepth1 = 0; // 最大深度
int maxDepth2 = 0; // 次大深度
// 遍历当前节点的子节点
for (TreeNode child : node.children) {
if (child == parent) continue; // 避免回溯
int childDepth = dfs(child, node, i); // 递归计算子节点的深度
if (childDepth > maxDepth1) {
maxDepth2 = maxDepth1;
maxDepth1 = childDepth;
} else if (childDepth > maxDepth2) {
maxDepth2 = childDepth;
}
}
// 更新f(i)
f[i] = Math.max(f[i], maxDepth1 + maxDepth2);
}
}
#我的实习求职记录#
投递字节跳动等公司10个岗位 >
