小朋友崇拜圈

• 小朋友崇拜圈 - 藍橋云課 (lanqiao.cn)
  拿到這道題要先把題目讀懂。
  下面的一行是表示：編號為i的小朋友，崇拜的對象為編號為path[i]的小朋友。
  本題應(yīng)該使用DFS，深度優(yōu)先遍歷找到可以成環(huán)的崇拜圈。

如果用通俗的話來說，就是：

• 每次傳入小朋友最崇拜的人和自己，如果找不到，就繼續(xù)找他崇拜的人所崇拜的人。（剛開始傳入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 ++){//每次傳入當(dāng)前小朋友和他最崇拜的人，dfs(path[i],i,1);}System.out.println(ans);}/**** @param x 被 i 崇拜的小朋友* @param ll 最找DFS要找回這個小朋友* @param cnt 返回圈數(shù)答案*/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)
  該題只需要掌握一個規(guī)律：

1. 遇到左括號進入DFS遞歸棧。
2. 遇到右括號退出DFS遞歸。但是返回的結(jié)果要加入current，繼續(xù)統(tǒng)計當(dāng)前正則串長度。
3. 遇到 | 就比較current和max最大的一方即可。

最后返回結(jié)果時，也要比較一次current和max，因為可能最后一次current沒有被統(tǒng)計。

DFS函數(shù)定義：計算當(dāng)前() 中的最長正則串。

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);}
}