Java小朋友崇拜圈
【题目】
班里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
上一篇: python 阶乘累加和的实例
下一篇: 年轻的秘密 女人有个不老穴经常按衰老减慢