【4.3蓝桥备战】小朋友崇拜圈、正则问题

小朋友崇拜圈

• 小朋友崇拜圈 - 蓝桥云课 (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)
  该题只需要掌握一个规律：

1. 遇到左括号进入DFS递归栈。
2. 遇到右括号退出DFS递归。但是返回的结果要加入current，继续统计当前正则串长度。
3. 遇到 | 就比较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);}
}