百度2023暑期实习第一场笔试编程题Java版

1.

题目内容
小红拿到了一个字符串，她想知道这个字符串能否通过重新排列组成 Baidu 字符串？注：必须大小写完全相同。 共有 t 组询问。

输入描述
第一行输入一个正整数 t ，代表询问次数。
接下来的 t 行，每行输入一个仅包含英文字母的字符串。
所有字符串的长度之和保证不超过 200000

输出描述
对于每次询问，输出一行答案。如果可以通过重新排列组成 Baidu，则输出 Yes ，否则输出 No 。

思路
字符串长度必须为5，且必须包含Baidu5个char。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        char[] chars = "Baidu".toCharArray();
        for (int i = 0; i < n; i++) {
            String s = in.next();
            if(s.length()!=5||!s.contains("B")||!s.contains("a")||!s.contains("i")||!s.contains("d")||!s.contains("u"))
                System.out.println("No");
            else System.out.println("Yes");
        }
    }
}

2.

题目内容：
给定一个整数x，请你构造一个仅由’r’,‘e’,'d’三种字符组成的字符串，其中回文子串的数量恰好为x

输入描述
一个正整数x. 1≤x≤10^9

输出描述
回文子串的数量恰好为x的字符串

思路
d包含1个回文子串，dd包含3个回文子串，ddd包含6个，dddd包含10个，依次累加求。
比如x=14，那么14-10-3-1=0；依次构建10个r，3个e，1个d。
因为10>3>1，所以不会有其他多余的回文子串。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int x = in.nextInt();
        int temp=0,index=0,c=1;
        StringBuilder builder = new StringBuilder("");
        while(x>0){
            temp=0;
            for (int i = 1; i < 1000000; i++) {
                temp+=i;
                if(temp>x){
                    temp-=i;
                    index=i-1;
                    break;
                }
            }// 这段可以用（n+1）*n/2替换
            if(c==1){
                for (int i = 0; i < index; i++) {
                    builder.append("r");
                }
                c++;
            }else if(c==2){
                for (int i = 0; i < index; i++) {
                    builder.append("e");
                }
                c++;
            }else {
                for (int i = 0; i < index; i++) {
                    builder.append("d");
                }
                c=1;
            }
            x=x-temp;
        }
        System.out.println(builder.toString());
    }
}

3.

题目内容
小红拿到了一棵树，每个节点被染成了红色或者蓝色。
小红定义每条边的权值为：删除这条边时，形成的两个子树的同色连通块数量之差的绝对值。
小红想知道，所有边的权值之和是多少？

输入描述
第一行输入一个正整数 n ,代表节点的数量。
第二行输入一个长度为 n 且仅由 R 和 B 两种字符组成的字符串。
第 i 个字符为 R 代表 i 号节点被染成红色，为 B 则被染成蓝色。
接下来的 n−1 行，每行输入两个正整数 u 和 v ，代表节点 u 和节点 v 有一条边相连。

输出描述
一个正整数，代表所有节点的权值之和。

思路
关键在于构建无向图，取每个节点，记录其父节点的位置，之后从当前节点往下dfs，
sum=1+Σ儿子节点的同色联通块数量
同时需要考虑父子之间的数量
如果子节点的颜色和当前节点的颜色是否相同，子节点所在子树的数量需要-1，
比如R-R，右边R的同色连通块数量为1，但因为父子相同色，就是1+（1-0）
如果不同，儿子节点的同色联通块数量不需要-1。
比如B-R，右边R的同色连通块数量为1，但因为父子不同色，就是1+（1）
最后对所有边遍历一遍即可。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

//4
//BBRR
//1 2
//3 2
//4 1
//答案为2

//        7
//        RRBRRRB
//        1 2
//        1 3
//        1 4
//        3 5
//        3 6
//        4 7
//        答案为16
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int x = in.nextInt();
        TreeNode[] treeNodes = new TreeNode[x];
        char[] colors = in.next().toCharArray();
        for (int i = 0; i < x; i++) {
            treeNodes[i] = new TreeNode(colors[i]);
        }
        int[][] ints = new int[x - 1][2];
        for (int i = 1; i < x; i++) {
            int a = in.nextInt() - 1;
            int b = in.nextInt() - 1;
            ints[i - 1] = new int[]{a, b};
            // 构建无向图，选取每个节点dfs
            treeNodes[a].setFriend(treeNodes[b]);
            treeNodes[b].setFriend(treeNodes[a]);
        }
        int sum = 0;
        for (int i = 0; i < ints.length; i++) {
            int num1 = dfs(treeNodes[ints[i][0]], treeNodes[ints[i][1]]);
            int num2 = dfs(treeNodes[ints[i][1]], treeNodes[ints[i][0]]);
            sum += num1 > num2 ? num1 - num2 : num2 - num1;
        }
        System.out.println(sum);
    }

    static int dfs(TreeNode node, TreeNode pre) {
        int sum = 1;
        for (TreeNode friend : node.friends) {
            if (friend != pre) {
                int dfs = dfs(friend, node);
                if (friend.color != node.color)
                    sum += dfs;
                else sum += dfs - 1;
            }
        }
        return sum;
    }

    static class TreeNode {
        char color;
        List<TreeNode> friends;

        public TreeNode(char color) {
            this.color = color;
            friends = new ArrayList<>();
        }

        void setFriend(TreeNode node) {
            friends.add(node);
        }
    }
}