【编程题】一个只包含0和1的阵列,找到1的组的个数,每个组的定义是横向和纵向相邻的值都为1,如图中一共有4个组,用不同颜色的框分割(可以参见不同粗细勾画起来的框)。
def findGroup(nums_array): """ 先转为一维数组,遍历数组中的每个数,判断当前元素是否为1且元素的上下左右的数是否为1; 上为index-len(col),左为index-1,右为index+1,下为index+len(col);前提是不超过行、列范围; 将满足条件的index存入分组中; 检查当前元素的相邻元素是否在分组中,在则存入分组,不在则另存分组 :param nums_array: :return: """ n, m = len(nums_array[0]), len(nums_array) result, temp = [], [] nums_array = sum(nums_array, []) for index in range(len(nums_array)): if nums_array[index] == 1: temp.append(index) if index >= n: # 上 if nums_array[index - n] == 1: temp.append(index - n) if (index // n) < m - 1: # 下 if nums_array[index + n] == 1: temp.append(index + n) if (index % n) > 0: # 左 if nums_array[index - 1] == 1: temp.append(index - 1) if (index % n) < (n - 1): # 右 if nums_array[index + 1] == 1: temp.append(index + 1) if result and temp: count = 0 for index in range(len(result)): if (len(set(result[index])) + len(temp)) != len(set(result[index] + temp)): result[index] = result[index] + temp break count += 1 if count == len(result): result.append(temp) elif not result and temp: result.append(temp) temp = [] return len(result)
class Couples{ int data[][] = null; int count = 0; Couples(int data [][]){ this.data=data; } public Integer getCouples(){ for(int i=0; i<this.data.length; i++){ for(int j=0; j<this.data[i].length;j++){ if(this.data[i][j] == 1) { loop(i, j); this.count += 1; } } } return this.count; } // 递归置零 void loop(int i, int j){ if(this.data[i][j] == 1){ this.data[i][j] = 0; if (i != 0) { loop(i - 1, j); } if (i != this.data.length - 1) { loop(i + 1, j); } if (j != 0) { loop(i, j - 1); } if (j != this.data[i].length - 1) { loop(i, j + 1); } } } }