面试题116：
解决方案：
一个班级可以包含一个或多个朋友圈，对应的图中可能包含一个或多个子图，每个朋友圈对应一个子图。因此，这个问题可以转化为如何求图中子图的数目。图的搜索算法可以用来计算图中子图的数目。扫描图中所有的节点。如果某个节点v之前没有访问过，就搜索它所在的子图。当所有节点都访问完之后，就可以知道图中有多少个子图。
源代码（使用图的搜索）：
class Solution {
public int findCircleNum(int[][] isConnected) {
boolean[] visited = new boolean[isConnected.length];
int result = 0;
for(int i = 0;i < isConnected.length;i++){
if(!visited[i]){
findCircle(isConnected,visited,i);
result++;
}
}
return result;
}
//遍历同学i的朋友
private void findCircle(int[][] isConnected,boolean[] visited,int i){
Queue<Integer> queue = new LinkedList<>();
queue.add(i);
visited[i] = true;
while(!queue.isEmpty()){
int t = queue.remove();
for(int friend = 0;friend < isConnected.length;friend++){
if(isConnected[t][friend] == 1 && !visited[friend]){
queue.add(friend);
visited[friend] = true;
}
}
}
}
}
源代码（并查集）：
class Solution {
public int findCircleNum(int[][] isConnected) {
int[] fathers = new int[isConnected.length];
for(int i = 0;i < fathers.length;i++){
fathers[i] = i;
}
int count = fathers.length;
for(int i = 0;i < isConnected.length;i++){
for(int j = i+1;j < isConnected.length;j++){
if(isConnected[i][j] == 1 && union(fathers,i,j)){
count--;
}
}
}
return count;
}
//如果它们的根节点不相同，那么合并他们的朋友圈，如果相同，那么直接返回false
private boolean union(int[] fathers,int i,int j){
int fatherOfI = findFather(fathers,i);
int fatherOfJ = findFather(fathers,j);
if(fatherOfI != fatherOfJ){
fathers[fatherOfI] = fatherOfJ;
return true;
}
return false;
}
//压缩路径，使fathers[i]保存的是子集的根节点
private int findFather(int[] fathers,int i){
if(fathers[i] != i){
fathers[i] = findFather(fathers,fathers[i]);
}
return fathers[i];
}
}
面试题117：
解决方案：
把输入数组中的每个字符串看成图中的一个节点。如果两个字符串相似，那么它们对应的节点之间有一条边相连，也就属于同一个子图。例如，字符串[“tars”，“rats”，“arts”，“star”]根据相似性分别属于两个子图。
源代码：
class Solution {
public int numSimilarGroups(String[] strs) {
int[] fathers = new int[strs.length];
for(int i = 0;i < fathers.length;i++){
fathers[i] = i;
}
int groups = strs.length;
for(int i = 0;i < strs.length;i++){
for(int j = i + 1;j < strs.length;j++){
if(similar(strs[i],strs[j]) && union(fathers,i,j)){
groups--;
}
}
}
return groups;
}
private boolean similar(String str1,String str2){
int diffCount = 0;
for(int i = 0;i < str1.length();i++){
if(str1.charAt(i) != str2.charAt(i)){
diffCount++;
}
}
return diffCount <= 2;
}
//如果它们的根节点不相同，那么合并子集，如果相同，那么直接返回false
private boolean union(int[] fathers,int i,int j){
int fatherOfI = findFather(fathers,i);
int fatherOfJ = findFather(fathers,j);
if(fatherOfI != fatherOfJ){
fathers[fatherOfI] = fatherOfJ;
return true;
}
return false;
}
//压缩路径，使fathers[i]保存的是子集的根节点
private int findFather(int[] fathers,int i){
if(fathers[i] != i){
fathers[i] = findFather(fathers,fathers[i]);
}
return fathers[i];
}
}
面试题118：
解决方案：
- 逐步在图中添加5条边以便找出形成环的条件。最开始的时候图中的5个节点是离散的，任意两个节点都没有边相连。也就是说，图被分割成5个子图，每个子图只有一个节点。
- 通过一步步在图中添加边可以发现判断一条边会不会导致环的规律。如果两个节点分别属于两个不同的子图，添加一条边连接这两个节点，会将它们所在的子图连在一起，但不会形成环。如果两个节点属于同一个子图，添加一条边连接这两个节点就会形成一个环。
源代码：
class Solution {
public int[] findRedundantConnection(int[][] edges) {
int maxVertex = 0;
//找出节点个数
for(int[] edge:edges){
maxVertex = Math.max(maxVertex,edge[0]);
maxVertex = Math.max(maxVertex,edge[1]);
}
int[] fathers = new int[maxVertex+1];
//将n个节点初始化为n个子集，每个节点的根节点都指向它自己
for(int i = 1;i <= maxVertex;i++){
fathers[i] = i;
}
for(int[] edge:edges){
if(!union(fathers,edge[0],edge[1])){
return edge;
}
}
return new int[2];
}
//合并子集
private boolean union(int[] fathers,int i,int j){
int fatherOfI = findFather(fathers,i);
int fatherOfJ = findFather(fathers,j);
if(fatherOfI != fatherOfJ){
fathers[fatherOfI] = fatherOfJ;
return true;
}
return false;
}
//压缩路径，使fathers[i]保存的是子集的根节点
private int findFather(int[] fathers,int i){
if(fathers[i] != i){
fathers[i] = findFather(fathers,fathers[i]);
}
return fathers[i];
}
}
面试题119：
解决方案：
这个题目是关于整数的连续性的。如果将每个整数看成图中的一个节点，相邻的（数值大小相差1）两个整数有一条边相连，那么这些整数将形成若干子图，每个连续数值序列对应一个子图。计算最长连续序列的长度就转变成求最大子图的大小。
源代码（使用广度优先搜索）：
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for(int num:nums){
set.add(num);
}
int longest = 0;
while(!set.isEmpty()){
Iterator<Integer> iter = set.iterator();
longest = Math.max(longest,bfs(set,iter.next()));
}
return longest;
}
//搜索最长数字连续的最长序列
private int bfs(Set<Integer> set,int num){
Queue<Integer> queue = new LinkedList<>();
queue.offer(num);
set.remove(num);
int length = 1;
while(!queue.isEmpty()){
int i = queue.poll();
int[] neighbors = new int[]{i-1,i+1};
for(int neighbor:neighbors){
if(set.contains(neighbor)){
queue.offer(neighbor);
set.remove(neighbor);
length++;
}
}
}
return length;
}
}
源代码（使用并查集）：
class Solution {
public int longestConsecutive(int[] nums) {
Map<Integer,Integer> fathers = new HashMap<>();
//保存每个数字的最长数字序列
Map<Integer,Integer> counts = new HashMap<>();
Set<Integer> all = new HashSet<>();
for(int num:nums){
fathers.put(num,num);
counts.put(num,1);
all.add(num);
}
for(int num:nums){
//如果数组中存在num + 1的数字，那就两个子集合并
if(all.contains(num + 1)){
union(fathers,counts,num,num+1);
}
//如果数组中存在num - 1的数字，那就两个子集合并
if(all.contains(num-1)){
union(fathers,counts,num,num-1);
}
}
int longest = 0;
for(int length:counts.values()){
longest = Math.max(longest,length);
}
return longest;
}
private int findFather(Map<Integer,Integer> fathers,int i){
if(fathers.get(i) != i){
fathers.put(i,findFather(fathers,fathers.get(i)));
}
return fathers.get(i);
}
private void union(Map<Integer,Integer> fathers,Map<Integer,Integer> counts,int i,int j){
int fatherOfI = findFather(fathers,i);
int fatherOfJ = findFather(fathers,j);
if(fatherOfI != fatherOfJ){
fathers.put(fatherOfI,fatherOfJ);
int countOfI = counts.get(fatherOfI);
int countOfJ = counts.get(fatherOfJ);
//合并后，长度也叠加
counts.put(fatherOfJ,countOfI + countOfJ);
}
}
}
