题目：
思路：
找规律，这里很明显说只要返回其中一个就行，那么一般都是找规律的题了，根据条件，可以知道，每次D就拿剩余的最大数，I拿剩余的最小数。如此肯定满足条件！
?具体代码：
class Solution {
public int[] diStringMatch(String s) {
int n = s.length(), lo = 0, hi = n;
int[] perm = new int[n + 1];
for (int i = 0; i < n; ++i) {
//每次拿剩余的最大/最小
perm[i] = s.charAt(i) == 'I' ? lo++ : hi--;
}
// 最后剩下一个数，此时 lo == hi
perm[n] = lo;
return perm;
}
}
??其他题目：
?思路：
使用dfs/bfs或者并查集都行，dfs的思路：对每一行长度【也就是有多少个城市】进行入口进行遍历，然后dfs函数里面对他有关联的城市筛选出来。
并查集思路：
代码：
//使用dfs
class Solution {
public int findCircleNum(int[][] isConnected) {
int cities = isConnected.length;
boolean[] visited = new boolean[cities];
int provinces = 0;
for (int i = 0; i < cities; i++) {
if (!visited[i]) {
dfs(isConnected, visited, cities, i);
provinces++;
}
}
return provinces;
}
public void dfs(int[][] isConnected, boolean[] visited, int cities, int i) {
for (int j = 0; j < cities; j++) {
if (isConnected[i][j] == 1 && !visited[j]) {
visited[j] = true;
dfs(isConnected, visited, cities, j);
}
}
}
}
//使用并查集
class Solution {
int[] p = new int[200];
int find(int x){
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
void union(int x, int y){
p[find(x)] = find(y);
}
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
for(int i = 0; i < n; i++) p[i] = i;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(isConnected[i][j] == 1) union(i, j);
}
}
int res = 0;
for(int i = 0; i < n; i++){
if(p[i] == i) res++;
}
return res;
}
}
补充：如果想练手bfs/dfs可以做一做：
剑指 Offer 32 - I. 从上到下打印二叉树
https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/
?使用bfs的效果：
?
