leetCode 문제 풀이 보고서 의 Clone Graph

제목:
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors .
OJ's undirected graph serialization:
Nodes are labeled uniquely. We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2} .
The graph has a total of three nodes, and therefore contains three parts as separated by # .
First node is labeled as 0 . Connect node 0 to both nodes 1 and 2 .
Second node is labeled as 1 . Connect node 1 to node 2 .
Third node is labeled as 2 . Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:

분석:
이 문 제 는 우리 에 게 이미 알 고 있 는 무방 향 도 를 제공 합 니 다. 그림 의 결점 은 모두 자신의 값 (label) 과 다른 결점 과 의 관계 (다른 결점 과 의 연결 관 계 를 포함 하고 자신 과 관련 되 어 링 을 형성 할 수 있 습 니 다) 가 있 습 니 다. 이 이미 알 고 있 는 그림 에 대해 '복제' 를 하 라 고 요구 합 니 다.
그림 의 노드 데이터 구조:
class UndirectedGraphNode {
int label;
ArrayList neighbors;
UndirectedGraphNode(int x) {
label = x;
neighbors = new ArrayList();
}
};
문제 풀이 방향:
우선, 우 리 는 당신 에 게 그림 의 결점, 예 를 들 어 결점 0 을 주면 결점 1 과 결점 2 가 모두 관련 이 있다 고 생각 할 것 입 니 다. 만약 에 우리 가 결점 0 과 관련 된 관계 의 List 집합 을 설정 하려 면 결점 1 과 결점 2 가 이미 존재 한다 면 우 리 는 이미 존재 하 는 결점 을 다시 만 들 수 없 을 것 입 니 다.
종합 하 다
1. 우 리 는 HashMap < UndirectedGraphNode, UndirectedGraphNode > map 를 사용 하여 우리 new 가 나 온 그림 의 결산 점 을 저장 합 니 다.
2. 그림 에 있 는 모든 결점 을 순조롭게 만 들 고 그들의 관련 관 계 를 확정 하기 위해 서 는 하나의 대열 이 필요 합 니 다. 먼저 우리 에 게 제 공 된 그림 에 있 는 결점 을 quue 에 넣 고 순환 한 다음 에 대열 에 있 는 '머리 결점' (tempNode) 을 꺼 내야 합 니 다. 만약 에 결점 이 다른 결점 과 의 관계 List 가 있다 면 관 계 를 옮 겨 다 니 며 List 의 결점 을 결합 합 니 다.만약 에 결점 이 맵 에 포함 되 지 않 는 다 면 이 결점 이 아직 만 들 어 지지 않 았 다 는 것 을 증명 합 니 다. 이때 우 리 는 이 그림 의 결점 을 복사 한 다음 에 map. put (OldNode, NewNode);그리고 이 결점 을 새로운 결점 의 관계 집합 List 에 넣 으 세 요.
3. '고리 가 있다' (자신 이 자신의 결점 에 연결 되 어 있다) 는 상황 이 계속 반복 되 는 것 을 피하 기 위해 서 우 리 는 하나의 Set 집합 으로 처 리 된 모든 그림 의 결점 을 저장 해 야 합 니 다!
[말 이 좀 복잡 하 니 코드 를 구체 적 으로 살 펴 보 자!]
AC 코드:

package cn.xym.leetcode.copygraph;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;


class UndirectedGraphNode {
	int label;
	ArrayList<UndirectedGraphNode> neighbors;

	UndirectedGraphNode(int x) {
		label = x;
		neighbors = new ArrayList<UndirectedGraphNode>();
	}
};

public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null)
            return null;
        
        //   copy   ,    entry key     node, 
        //value    node("copy  node   ").
        HashMap<UndirectedGraphNode,UndirectedGraphNode> map 
                       = new HashMap<UndirectedGraphNode,UndirectedGraphNode>();
        map.put(node, new UndirectedGraphNode(node.label));	//   ， copy       node
        Set<UndirectedGraphNode> visitedSet 
                       = new HashSet<UndirectedGraphNode>(); //          
        Queue<UndirectedGraphNode> queue 
                       = new LinkedList<UndirectedGraphNode>(); //         
        queue.add(node);	//          node
        
        while (!queue.isEmpty()){
                //      
        	UndirectedGraphNode tempNode = queue.remove();	
                //               （  “ ”）
        	if (visitedSet.contains(tempNode))		
        		continue;
        	visitedSet.add(tempNode); //          
        	/*           List*/
        	for (UndirectedGraphNode i : tempNode.neighbors){
        		if (!map.containsKey(i)){
	        		UndirectedGraphNode copy = new UndirectedGraphNode(i.label);
	        		map.put(i, copy);
	        		map.get(tempNode).neighbors.add(copy);
        		}else{
        			map.get(tempNode).neighbors.add(map.get(i));
        		}
        		queue.add(i);
        	}
        }
        return map.get(node);
    }
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)

이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

leetCode 문제 풀이 보고서 의 Clone Graph

좋은 웹페이지 즐겨찾기