字节后端笔试10.9
供大家参考，同时求大佬思路/答案。菜成狗，做一次打击一次，大厂属实不配
1、设计无向连通图
示例：
输入：
3
0 1 1
输出：
2
1 2
1 3
图之前心存侥幸，直接跳过，下去补补。
2、多叉树染色
示例：
输入：
6
1 2
6 3
5 2
2 4
3 1
输出
BBRBBB
个人认为这个题难在多叉树的建立（做的时候一直卡在这），下面是笔试完写的，不知道能不能过。 染色思路： 用递归，染色函数solution（TreeNode root）传入一棵染色前的树，返回染色后的树。 具体实现：取到根节点root，得到root的子节点列表，然后对各子节点树染色。若子节点数量为偶，由于染色后以子节点为顶点的树中蓝色节点数量为奇数，偶数个奇数相加，总蓝色节点个数为偶，要使root染色后仍为奇，则root节点必为蓝色；否则必为红色。返回染色后的树。
public class Main
{
public static void main(String[] args)
{
Scanner input=new Scanner(System.in);
int N=input.nextInt(); //节点个数
int[][] connect=new int[N][N];//临接矩阵
ArrayList<Integer> child_list=new ArrayList<>(); //根节点的子节点列表
for(int i=0;i<N-1;i++)
{
int a=input.nextInt();
int b=input.nextInt();
connect[a-1][b-1]=1;
connect[b-1][a-1]=1;
}
System.out.println("临接矩阵：");
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
System.out.print(connect[i][j]+" ");
System.out.println();
}
TreeNode root=new TreeNode('R',0);
pre_build(root,connect);
//层序遍历
System.out.println("染色前：");
bfs(root);
root=solution(root);
System.out.println("\n染色后：");
bfs(root);
}
public static void pre_build(TreeNode root,int[][] connect) //前序建树（多叉树）
{
if(root==null)
return;
int num= root.num;
for(int i=0;i<connect.length;i++)
{
if(connect[num][i]==1)
{
root.addNode(new TreeNode('R',i));
connect[i][num]=0;
}
}
ArrayList<TreeNode> child=root.children;
for(TreeNode o:child)
pre_build(o,connect);
}
public static TreeNode solution(TreeNode root) //输入染色前的树，返回染色后的树
{
ArrayList<TreeNode> list=root.children;
if(list.size()==0)
{
root.setColor('B');
return root;
}
else
{
for(TreeNode o:list)
o=solution(o); //子节点染色
if(list.size()%2==0) //子节点个数为偶 则根节点必为蓝色
root.setColor('B');
else
root.setColor('R'); //子节点个数为奇 则根节点必为红色
return root;
}
}
public static void bfs(TreeNode root) //层序遍历
{
LinkedList<TreeNode> list=new LinkedList<>();
list.add(root);
while(!list.isEmpty())
{
TreeNode tem=list.remove();
System.out.print("("+(tem.num+1)+","+tem.color+")");
ArrayList<TreeNode> child=tem.children;
if(child!=null)
{
for(TreeNode o:child)
list.add(o);
}
}
}
}
class TreeNode
{
public Character color; //颜色
public Integer num; //编号
public ArrayList<TreeNode> children=new ArrayList<>(); ///子节点列表
public TreeNode(Character color,Integer num)
{
this.color=color;
this.num=num;
}
public void addNode(TreeNode n)
{
children.add(n);
}
public void setColor(Character color)
{
this.color=color;
}
}
3、染色种类
示例：
输入:
5
1 2 1 2 2
BRRBB
输出：
5
说明：
和为1 的取法下标：B(0), R(2)
和为2的取法下标：B(3), R(1)或B(4), R(1)
和为3的取法下标：B(0,3), R(1,2)或B(0,4), R(1,2)
（这里下标从0开始）
