[LeetCode]133. 克隆图（java实现）dfs+哈希表

1. 题目

2. 读题（需要重点注意的东西）

思路（dfs+哈希表）：
用哈希表来存储映射关系
① 复制所有点 dfs

复制的点用哈希表进行映射 — key(原来的节点) ：value(复制出来的节点)

② 复制所有边

枚举原节点key的所有邻接点，找到它们在value中的值，加到res链表中，然后再将这个res链表赋值给复制出来的节点的neighbors即完成了复制节点的边的连接。

3. 解法

---------------------------------------------------解法---------------------------------------------------：

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {
    Map<Node,Node> map = new HashMap<>();
    public Node cloneGraph(Node node) {
        if(node == null) return null;
        dfs(node); // 将所有节点复制到哈希表中

        // 遍历哈希表,复制边
        for(var entry : map.entrySet()){
            // 原节点为a
            Node a = entry.getKey();
            // 复制出来的节点为b
            Node b = entry.getValue();

            // 用res存储b的边
            List<Node> res = new ArrayList<>();
            // 找到a的边
            // 将a的所有邻接点的映射点加到res中
            for(int i = 0;i < a.neighbors.size();i++)
                res.add(map.get(a.neighbors.get(i)));

            // 将res加到b的邻接表中
            b.neighbors = res;
        }
        return map.get(node);
    }

    // 复制所有节点到哈希表中
    public void dfs(Node node){
        map.put(node,new Node(node.val));
        for(int i = 0;i < node.neighbors.size();i++){
            Node p = node.neighbors.get(i);
            if(!map.containsKey(p))
                dfs(p);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

---

可能存在的问题：

4. 可能有帮助的前置习题

5. 所用到的数据结构与算法思想

• Java数据结构—HashMap（哈希表及其基本操作）（含hashset）

6. 总结

entrySet() 方法可以与 for-each 循环一起使用，用来遍历迭代 HashMap 中每一个映射项

// foreach循环
for(var entry : map.entrySet()){
    // 获得key
    int key = entry.getKey();
	// 获得value
	int value = entry.getValue();
}
1
2
3
4
5
6
7