LeetCode 684 중복 연결
1961 단어 알고리즘
이 문제 에서 나 무 는 연결 되 고 고리 가 없 는 무방 향 도 를 가리킨다.
그림 을 입력 하 십시오. 이 그림 은 N 개의 노드 (노드 값 은 1, 2,..., N) 가 있 는 트 리 와 추가 적 인 변 으로 구성 되 어 있 습 니 다.추 가 된 변 의 두 정점 은 1 에서 N 사이 에 포함 되 어 있 으 며, 이 추 가 된 변 은 나무 에 존재 하 는 변 에 속 하지 않 습 니 다.
결과 도 는
로 구 성 된 2 차원 배열 이다.각 의 원 소 는 한 쌍 [u, v] 이다. ，만족시켰어 u < v, 연결 정점 표시 u v 의 무방 향도 변.삭제 할 수 있 는 가장 자 리 를 되 돌려 결과 그림 은 N 개의 노드 가 있 는 나무 입 니 다.여러 개의 답 이 있 으 면 2 차원 배열 에서 마지막 으로 나타 난 변 으로 돌아간다.답안 변
[u, v] 같은 격식 을 만족 시 켜 야 한다. u < v 。 예시 1:
: [[1,2], [1,3], [2,3]]
: [2,3]
: :
1
/ \
2 - 3
예시 2:
: [[1,2], [2,3], [3,4], [1,4], [1,5]]
: [1,4]
: :
5 - 1 - 2
| |
4 - 3
주의:
업데이트 (2017 - 09 - 26): 우 리 는 문제 설명 과 테스트 사례 를 재 검 사 했 습 니 다. 명확 한 그림 은 방향 이 없습니다. 그림.그림 에 대한 자세 한 내용 은 중복 연결 II 참조.어떠한 불편 을 초래 한 것 에 대해 우 리 는 깊 은 사과 의 뜻 을 느낀다.
분석 하 다.
그리고 집합 을 찾 습 니 다. new 한 배열 은 각 노드 의 뿌리 노드 (여기 (1, 2) 는 2 가 1 의 뿌리 노드 라 고 합 니 다) 를 저장 하고 edges 배열 을 옮 겨 다 닐 때 두 배열 의 뿌리 노드 가 같 는 지 찾 습 니 다. 같 으 면 고리 가 있 음 을 증명 하고 현재 배열 로 돌아 갑 니 다.
코드
class Solution {
public int[] findRedundantConnection(int[][] edges) {
int[] nums = new int[2000];
for(int[] i : edges){
int root1 = find(i[0],nums);
int root2 = find(i[1],nums);
if (root1 == root2)
return i;
else {
nums[root1] = root2;
}
}
return null;
}
public static int find(int x, int[] nums){
while (nums[x] != 0){
x = nums[x];
}
return x;
}
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
