东莞网站建设 钢结构,发布网站免费空间,网页生成应用工具,如何创建一个app平台文章目录小朋友崇拜圈正则问题小朋友崇拜圈
小朋友崇拜圈 - 蓝桥云课 (lanqiao.cn) 拿到这道题要先把题目读懂。 下面的一行是表示#xff1a;编号为i的小朋友#xff0c;崇拜的对象为编号为path[i]的小朋友。 本题应该使用DFS#xff0c;深度优先遍历找到可以成环的崇拜圈…
文章目录小朋友崇拜圈正则问题小朋友崇拜圈
小朋友崇拜圈 - 蓝桥云课 (lanqiao.cn) 拿到这道题要先把题目读懂。 下面的一行是表示编号为i的小朋友崇拜的对象为编号为path[i]的小朋友。 本题应该使用DFS深度优先遍历找到可以成环的崇拜圈。
如果用通俗的话来说就是
每次传入小朋友最崇拜的人和自己如果找不到就继续找他崇拜的人所崇拜的人。刚开始传入path[i](x)后来传入path[x]。
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {static int N;// 第i个小朋友最崇拜的人就是path[i]。static int [] path;static int ans;public static void main(String[] args) {Scanner s new Scanner(System.in);N s.nextInt();path new int [N 1];for(int i 1 ; i N ; i ){path[i] s.nextInt();}for(int i 1 ; i N ; i ){//每次传入当前小朋友和他最崇拜的人dfs(path[i],i,1);}System.out.println(ans);}/**** param x 被 i 崇拜的小朋友* param ll 最找DFS要找回这个小朋友* param cnt 返回圈数答案*/static void dfs(int x,int ll , int cnt){if(cnt N) return ;//if(x ll){ans Math.max(ans , cnt);return;}dfs(path[x],ll,cnt 1);}
}正则问题
正则问题 - 蓝桥云课 (lanqiao.cn) 该题只需要掌握一个规律
遇到左括号进入DFS递归栈。遇到右括号退出DFS递归。但是返回的结果要加入current继续统计当前正则串长度。遇到 | 就比较current和max最大的一方即可。
最后返回结果时也要比较一次current和max因为可能最后一次current没有被统计。
DFS函数定义计算当前() 中的最长正则串。
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {static String str;static char [] ch;static int idx -1;public static void main(String[] args) {Scanner s new Scanner(System.in);str s.nextLine();ch str.toCharArray();System.out.println(dfs());}static int dfs(){int current 0;int max 0;while(idx ch.length - 1){idx ;if(ch[idx] (){current dfs();}else if(ch[idx] x){current ;}else if(ch[idx] |){max Math.max(current , max);current 0;}else{break;}}return Math.max(max , current);}
}
