2018 字节跳动 第三次 在线笔试题（2）
（代码通过率100%）
题目描述：
本公司有很多团队，现在要将关系紧密的团队放到同一个部门。给定一个M*M的二维数组，如：
4
0 1 1 0
1 0 0 0
1 0 0 1
0 0 1 1
其中4表示二维数组的大小，1代表一个团队，上下或左右相连的1（团队）表示其关系紧密，求最后分出的部门数。
输入描述：
第一行第一个整数表示M（M<1000），
后面每一行表示团队之间的关系分布，如上所示的数阵
输出描述：
一个整数
示例：
输入：
4
0 1 1 0
1 0 0 0
1 0 0 1
0 0 1 1
输出：
3
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
public class Main3 { private static List<String> list = new ArrayList<String>();//记录容器，记录矩阵中，每一个1的位置
public static void main(String[] args) { Scanner sc = new Scanner(System.in); int M = sc.nextInt();//初始化二维数组 int[][] arr = new int[M][M]; for (int i = 0; i < arr.length; i++) {//从上到下，从左到右 一个一个写 for (int j = 0; j < arr.length; j++) { arr[i][j] = sc.nextInt(); } } System.out.println(getResult(arr));
}
private static int getResult(int[][] arr){ int num = 0;//部门数 for (int i = 0; i < arr.length; i++) {//从上到下，从左到右 一个一个读 for (int j = 0; j < arr.length; j++) { //如果当前元素的值为1 且 记录容器中不存当前元素的坐标记录，就递归收索以当前坐标为基准的 //所有值为1的元素，并记录坐标，部门数加1 if(arr[i][j] == 1 && !list.contains(i+","+j)){ digui(i, j, arr); num++; } } } return num;
}
//从i和j开始，对数组进行递归收索，找出所有相连的1,并记录坐标
private static void digui(int i, int j, int[][] arr){ if(list.contains(i+","+j))//递归终止条件 return; list.add(i+","+j);//记录坐标值 //向下收索 if(i+1<arr.length){//先判断坐标值是否可能越界 if(arr[i+1][j] == 1){//再判断当前元素下移一位的元素值是否为一 digui(i+1, j, arr); } } //向右收索 if(j+1<arr.length){ if(arr[i][j+1] == 1){ digui(i, j+1, arr); } } //向左收索 if(j-1>=0){ if(arr[i][j-1] == 1){ digui(i, j-1, arr); } }
}
}
#笔试题目##字节跳动#
查看19道真题和解析