【题目】
班里N个小朋友，每个人都有自己最崇拜的一个小朋友（也可以是自己）
在一个游戏中，需要小朋友坐一个圈
每个小朋友都有自己最崇拜的小朋友在他的右手边
求满足条件的圈最大多少人？
小朋友编号为1,2,3,…N
输入第一行，一个整数N（3<N<100000）
接下来一行N个整数，由空格分开
要求输出一个整数，表示满足条件的最大圈的人数。
例如：
输入：
9
3 4 2 5 3 8 4 6 9
则程序应该输出：
4
解释：
如图所示，崇拜关系用箭头表示，红色表示不在圈中。
显然，最大圈是[2 4 5 3] 构成的圈
再例如：
输入：
30
22 28 16 6 27 21 30 1 29 10 9 14 24 11 7 2 8 5 26 4 12 3 25 18 20 19 23 17 13 15
程序应该输出：
16
【分析】
可以使用数组来储存小朋友们的崇拜对象，然后下标+1就是对应的小朋友座号，写一个方法找出每一个小朋友的崇拜圈大小，然后找出最大的崇拜圈即可
【代码演示】
我要评论import java.util.Scanner;
class Main {
// 储存最大崇拜圈数量
static int max = 0;
public static void main(String[] args) {
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
// 储存小朋友们的崇拜对象
int[] boy = new int[n];
// 将崇拜对象填入数组
for (int i = 0; i < boy.length; i++) {
boy[i] = sr.nextInt();
}
// 查找每个小朋友的崇拜圈大小，找出最大的
for (int i = 0; i < boy.length; i++) {
int k = helper(boy, i, 0, "",i);
max = max < k ? k : max;
}
System.out.println(max);
}
private static int helper(int[] boy, int index, int inpunt, String str,int num) {
//因为提前预测了崇拜圈的结束，所以少了一次，结束的时候加上
if (num+1 == boy[index]) {
inpunt++;
return inpunt;
}
// 查看是否崇拜圈进入死循环了，如果是直接结束
for (int i = 0; i < str.length(); i++) {
if ((str.charAt(i) + "").equals("" + boy[index])) {
return 0;
}
}
str += boy[index];
index = boy[index] - 1;
inpunt++;
return helper(boy, index, inpunt, str,num);
}
}
问：index、inpunt、str、num分别是是什么？
答：index是每次崇拜对象的下标，找出下一个崇拜对象；
inpunt是临时的崇拜圈数，通过返回值返回出去；
str是储存已经出现过的崇拜者，如果这次又出现了出现过的，那就说明崇拜圈死循环了；
num是保存每次初始小朋友的座号，等到若干次崇拜之后，再次崇拜到初始小朋友，那么崇拜圈就形成了
本文地址：https://blog.csdn.net/our1624204500/article/details/107144382
如对本文有疑问， 点击进行留言回复！！
网友评论