欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java小朋友崇拜圈

程序员文章站 2022-05-21 11:57:02
【题目】班里N个小朋友,每个人都有自己最崇拜的一个小朋友(也可以是自己)在一个游戏中,需要小朋友坐一个圈每个小朋友都有自己最崇拜的小朋友在他的右手边求满足条件的圈最大多少人?小朋友编号为1,2,3,…N输入第一行,一个整数N(3

【题目】
班里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] 构成的圈Java小朋友崇拜圈

再例如:
输入:
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