携程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);
    }
}