LintCode 섬의 개수
1390 단어 LintCode
01 행렬을 주어 서로 다른 섬의 개수를 구하다.
0은 바다를 대표하고, 1은 섬을 대표하며, 만약 두 개의 1이 서로 인접한다면 이 두 개의 1은 같은 섬에 속한다.우리는 상하좌우를 인접으로만 고려한다.
예제
행렬:
[
[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[0, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 1]
]
중에는
3 개의 섬이 있다.생각:
일부 귀속적인 사상을 운용했는데 우선 이중 for순환이 하나하나 행렬을 반복하는 요소이다.
어떤 원소를 1로 찾았을 때 귀속적인 사상을 이용하여 이 원소의 상하좌우, 그것과 인접한true의 상하좌우원소, 인접한...이 원소들은false로 바뀐다
마지막 반환num
코드:
public static int numIslands(boolean[][] grid) {
// Write your code here
int num = 0;
if (grid == null)
return 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if (grid[i][j] == true) {
num++;
grid = change(grid, i, j);
}
}
}
return num;
}public static boolean[][] change(boolean[][] grid, int i, int j) {
// false
grid[i][j] = false;
if (i > 0 && grid[i - 1][j] == true) {
//
grid = change(grid, i - 1, j);
}
if (j < grid[i].length - 1 && grid[i][j + 1] == true) {
//
grid = change(grid, i, j + 1);
}
if (j > 0 && grid[i][j - 1] == true) {
//
grid = change(grid, i, j - 1);
}
if (i < grid.length - 1 && grid[i + 1][j] == true) {
//
grid = change(grid, i + 1, j);
}
return grid;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
lintcode--94. 두 갈래 나무의 최대 경로와두 갈래 트리를 제시하고 경로와 최대를 찾을 수 있습니다. 경로는 어느 노드에서 시작하고 끝낼 수 있습니다. (경로와 두 노드 사이에 있는 경로의 노드 값의 합) 두 갈래 나무 한 그루를 주시오. 되돌아오다 뒷순서에...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
