題：小朋友崇拜圈
班里N個小朋友，每個人都有自己最崇拜的一個小朋友（也可以是自己）。
在一個游戲中，需要小朋友坐一個圈，
每個小朋友都有自己最崇拜的小朋友在他的右手邊。
求滿足條件的圈最大多少人？
小朋友編號為1,2,3,...N
輸入第一行，一個整數N（3<N<100000）
接下來一行N個整數，由空格分開。
要求輸出一個整數，表示滿足條件的最大圈的人數。
例如：
輸入：
9
3 4 2 5 3 8 4 6 9
則程式應該輸出：
4
解釋：
如圖p1.png所示，崇拜關系用箭頭表示，紅色表示不在圈中。
顯然，最大圈是[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
uj5u.com熱心網友回復：
附圖
uj5u.com熱心網友回復：
public void run() {
int[] nums = {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};
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i< nums.length; i++) {
map.put(i, nums[i]);
}
Integer maxCircle = 0;
for (Integer v : map.values()) {
List<Integer> group = Lists.newArrayList();
int nodeCount = 0;
int i = v;
while (!group.contains(i)) {
group.add(i);
i = nums[i-1];
nodeCount ++;
if (nodeCount > maxCircle) {
maxCircle = nodeCount;
}
}
}
System.out.println(maxCircle);
}
uj5u.com熱心網友回復：
謝謝大佬~~~~~~~~~
uj5u.com熱心網友回復：
i = nums[i-1]; 為什么要這樣啊uj5u.com熱心網友回復：
i = nums[i-1]; 為什么要這樣做？
uj5u.com熱心網友回復：
找到這個人崇拜的小朋友啊。
這段代碼還可以精簡。map那段沒用，map.values()換成nums。
uj5u.com熱心網友回復：
那為什么非要是i-1呢 他右邊的不是都可以崇拜么
uj5u.com熱心網友回復：
看圖片，單箭頭的。
1號小朋友崇拜22號，那你就要去找下標21的。如果他寫了1號小朋友崇拜22號和20號 那應該就可以按你的思路寫。
uj5u.com熱心網友回復：
懂了，謝謝~~~~~~~
uj5u.com熱心網友回復：
#include <stdio.h>#include <malloc.h>
int n, *a, *flag, head, max, count;
void init() ;
void bfs(int temp) ;
int main() {
int i;
init();
for(i=0; i<n; i++) {
flag[i] = 1; //標記
head = i+1;
count = 0;
bfs(a[i]);
flag[i] = 0; //取消標記
}
printf("%d", max);
return 0;
}
void init() {
int i;
scanf("%d", &n);
a = (int *)malloc(sizeof(int)*n);
flag = (int *)malloc(sizeof(int)*n);
for(i=0; i<n; i++) {
scanf("%d", &a[i]);
flag[i] = 0;
}
head = 0; //標記開始的頭為0即不存在，以便最后一個找不到崇拜物件了
max = 0; //設定最大可以圍成圈的人數為0
}
void bfs(int temp) {
int i;
count++;
if(temp == head) {
max = max>count?max:count;
}
else if(flag[temp-1] == 1) { //防止進入無限遞回中
return;
}
else {
flag[temp-1] = 1;
bfs(a[temp-1]);
flag[temp-1] = 0;
}
}
uj5u.com熱心網友回復：
題目沒有說清楚的是，輸入表達的意思，第一個數，是有多少個小朋友，比較好理解，第二行有n個數，排列的規律為崇拜編號比如：
9
3 4 2 5 3 8 4 6 9
為一共9個小朋友，第一個小朋友仰慕3號，第二個小朋友仰慕4號，第三個小朋友仰慕2號，第四個小朋友仰慕5號，第五個小朋友仰慕3號，第六個小朋友仰慕8號，第七個小朋友仰慕4號，第八個小朋友仰慕6號，第九個小朋友仰慕9號自己。
uj5u.com熱心網友回復：
樓主的代碼在加入每個元素的時候，沒有考慮最后能不能形成一個圈，就直接加進去了，所以肯定是錯的，原題給的資料只是恰好能通過而已。可以測驗一下以下測驗資料：
4
2 3 4 4
即1崇拜2，2崇拜3，3崇拜4，4崇拜4自己。顯然，答案應該是1，只有4自己能形成一個圈。但是樓主的代碼輸出的是3，就是因為在加入每個數的時候，不考慮最后能不能形成一個圈，就直接加入了。
uj5u.com熱心網友回復：
這個就是找最大環，遍歷崇拜關系取下一個崇拜者的崇拜關系，一層層尋找，能形成環，取形成環的最大即可思路挺簡單的
加入LS說的測驗資料
public class Sample {
public static void main(String[] args) {
int [][]num = { //測驗資料
{3,4,2,5,3,8,4,6,9},
{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},
{2,3,4,4}
};
int max=-1, n;
List<Integer> tmp = new ArrayList<>(); //尋找用
List<Integer> res = new ArrayList<>(); //保存結果用
for (int j=0; j<num.length; j++) { //遍歷取測驗資料
max = -1;
res.clear();
for (int i=0; i<num[j].length; i++) { //此處以下是演算法的開始，遍歷崇拜關系
if (res.contains(i+1)) continue; //如果當前崇拜者被遍歷過則跳過（只是為了改善性能，不要這行代碼也沒關系）
tmp.clear();
n = i+1; //當前崇拜者編號
tmp.add(n); //當前崇拜者加入環
while (true) { //一層層查找崇拜關系
n = num[j][n-1]; //取下一個崇拜者
if (!tmp.contains(n)) { //如果不在環中則加入環
tmp.add(n);
if (tmp.size() > num[j].length) break; //為了防止崇拜關系不正確而死回圈(不存在環)，正常可以不要這行代碼
} else { //如果在環中（能形成環）
if (n!=i+1) {//如果最后一個崇拜者不是最開始的第一個崇拜者
tmp = tmp.subList(tmp.indexOf(n), tmp.size()); //則去掉不符合環的崇拜者
}
if (tmp.size()>max) { //如果環的人數大于max，則重新修改max，并保存環
max=tmp.size();
res.clear();
res.addAll(tmp);
}
break; //形成環則退出一層層查找崇拜關系
}
}
}
System.out.println(max); //列印最大環
System.out.println(res);
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/114722.html
標籤：Java相關
上一篇：專案創建問題，求解
下一篇：服務器回傳的cookie資訊不是用response這個物件來接受到嗎？為什么client并沒有接收到回應資訊，怎么會能獲取到cookie呢？