Leetcode 섬 문제 모음 - 그림 의 옮 겨 다 니 기
5232 단어 Leetcode 문제 풀이 노트
leetcode 의 섬 문 제 는 본질 적 으로 그림 의 옮 겨 다 니 는 문제 이기 때문에 우 리 는 먼저 어떤 그림 의 옮 겨 다 니 는 지, 그리고 일반적인 옮 겨 다 니 는 방법 을 알 아야 한다.
그림 의 편력
그림 의 옮 겨 다 니 는 것 은 데이터 구조의 내용 에 속한다.그림 의 어느 정점 에서 출발 하여 그림 의 모든 정점 을 한 번 방문 하고 한 번 만 방문 하 는 것 을 말한다.그림 의 옮 겨 다 니 기 동작 은 나무의 옮 겨 다 니 기 동작 기능 과 비슷 하 다.그림 의 옮 겨 다 니 는 것 은 그림 의 기본 적 인 조작 이 고 그림 의 많은 다른 조작 은 옮 겨 다 니 는 작업 의 기초 위 에 세 워 져 있다.
그림 의 옮 겨 다 니 기 는 범위 우선 검색 (Breadth First Search, BFS) 과 깊이 우선 검색 (Depth First Search, DFS) 두 가지 로 나 뉜 다.
범위 우선 검색
나무의 층 차 를 옮 겨 다 니 는 것 과 유사 하 다.
V0 에서 출발
1) V0 방문 하기;
2) V0 의 모든 인접 지점 V1, V2,..., Vt 를 차례로 방문 합 니 다.
3) V1 의 모든 인접 점 을 순서대로 방문한다.
V2 의 모든 인접 점 에 순서대로 접근 하기;
．．．．．．
Vt 의 모든 인접 점 에 순서대로 접근 하기;
모든 정점 에 접근 할 때 까지.
메모: 중복 접근 할 수 없습니다.
알고리즘 에 대한 설명 에 따 르 면 우 리 는 대기 열 을 사용 하여 BFS 를 실현 하 는 것 을 쉽게 연상 할 수 있 습 니 다.
(1) 1 개의 정점 을 방문 할 때마다 이 정점 의 번 호 를 대열 에 넣 습 니 다.
(2) 그리고 팀 이 앞장 서서 방문 하지 않 은 인접 점 을 방문 한 후에 순서대로 팀 에 들어간다.
．．．．．．
팀 이 비 어 있 을 때 까지
의사 코드 구현:
public void BFS(Vnode[] G, int v) // G v ， BFS
{
int u;
qtype Q;
ClearQueue(Q); // Q
visit(G,v);
visited[v] = true; // , “ ”
EnQueue(Q, v); //v
while (!EmptyQueue(Q)) { //
v = DeQueue(Q); // , v
u = FirstAdj(G, v); // v
while (u >= 0) {
if (visited[u] == false) { //u
visit(G, u); visited[u] = true;
EnQueue(Q, u);
}
u = NextAdj(G, v, u); // v u
}
}
}
깊이 우선 검색
나무의 앞 순 서 를 옮 겨 다 니 는 것 과 유사 하 다.
어떤 정점 에서 출발 하여 그림 의 한 가 지 를 따라 머리 까지 검색 한 다음 에 거 슬러 올 라 가서 다른 가 지 를 따라 검색 합 니 다.
메모: 중복 접근 할 수 없습니다 (그림 에 회로 가 있 을 수 있 습 니 다. 순환 에 빠 지지 않도록 합 니 다)
의사 코드 구현 (재 귀적):
public void DFS(Vnode[] G, int v) // G v ， DFS
{
int u;
visit(G, v); // v
visited[v] = true; // ” ”
u = FirstAdj(G, v); // v u
while (u >= 0) { // u
if (visited[u] == false)
DFS(G, u); // u
u = NextAdj(G, v, u); // v u
}
}
이 외 에 도 스 택 을 사용 하여 실현 할 수 있 습 니 다:
public void BFS(Vnode[] G, int v) // G v ， BFS
{
int u;
Stack s;
ClearStack(s); // s
visit(G,v);
visited[v] = true; // , “ ”
s.push(v); //v
while (!s.isEmpty) { //
v = s.pop(); //
u = FirstAdj(G, v); // v
while (u >= 0) {
if (visited[u] == false) { //u
visit(G, u); visited[u] = true;
s.push(u.nextNode());//u
s.push(u);//u
}
}
}
} leetcode 의 섬 문 제 는 기본적으로 그림 깊이 우선 검색 애플 리 케 이 션 입 니 다.
Leetcode 섬 문제 집계
섬 수
이 유 를 정 하 다 '1 '(육지) 와' 0 '(물) 으로 구 성 된 2 차원 격자 로 섬의 수량 을 계산한다.한 섬 은 물 에 둘러싸 여 있 으 며 수평 방향 이나 수직 방향 으로 인접 한 육 지 를 통 해 연결 되 어 있다.너 는 격자 의 네 변 이 모두 물 에 둘러싸 여 있다 고 가정 할 수 있다.
예시 1:
입력:
11110
11010
11000
00000출력: 1
예시 2:
입력:
11000
11000
00100
00011출력: 3
출처: 스냅 백 (LeetCode) 링크:https://leetcode-cn.com/problems/number-of-islands 저작권 은 인터넷 에 귀속 된다.상업 전 재 는 정부 에 연락 하여 권한 을 부여 해 주 십시오. 비 상업 전 재 는 출처 를 밝 혀 주 십시오.
육 지 를 위 한 섬 마다 깊이 있 게 옮 겨 다 니 며 연 결 된 육 지 를 모두 방문한다.코드 는 다음 과 같 습 니 다:
class Solution {
public int numIslands(char[][] grid) {
int res=0;
for(int i=0;i=0 && i=0 && j 695. 섬의 최대 면적
0 과 1 을 포함 하 는 비 공 2 차원 배열 을 지정 합 니 다. grid , 한 개 섬. 네 방향 (수평 또는 수직) 입 니 다. 1 (토 지 를 대표 하 는) 구 성 된 조합.너 는 2 차원 행렬 의 네 가장자리 가 모두 물 에 둘러싸 여 있다 고 가정 할 수 있다.
주어진 2 차원 배열 중 가장 큰 섬 면적 을 찾 아 라.(섬 이 없 으 면 귀환 면적 은 0 이다.)
예시 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]위 에 주어진 행렬 을 되 돌려 야 합 니 다. 6。주의해 야 할 답 은 11 이 아니다. 섬 은 수평 이나 수직 네 방향의 '1' 만 포함 할 수 있 기 때문이다.
예시 2:
[[0,0,0,0,0,0,0,0]]위 에 주어진 행렬 을 되 돌려 줍 니 다. 0。
주의: 주어진 매트릭스 grid 길이 와 너비 모두 50 을 넘 지 않 습 니 다.
출처: 스냅 백 (LeetCode) 링크:https://leetcode-cn.com/problems/max-area-of-island 저작권 은 인터넷 에 귀속 된다.상업 전 재 는 정부 에 연락 하여 권한 을 부여 해 주 십시오. 비 상업 전 재 는 출처 를 밝 혀 주 십시오.
코드 해결:
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int max=0;
for(int i=0;i=0 && i=0 && j 좋은 웹페이지 즐겨찾기
