Java教程

【学习打卡】第21天 数据结构和算法

本文主要是介绍【学习打卡】第21天 数据结构和算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

克隆图(leetcode - 133)

给你无向 连通 图中一个节点的引用,请你返回该图的 深拷贝(克隆)。
图中的每个节点都包含它的值 val(int) 和其邻居的列表(list[Node])。

思路

  • 拷贝所有节点
  • 拷贝所有边

步骤

  1. 深度或者广度优先遍历所有节点
  2. 拷贝所有节点,存储起来
  3. 将拷贝的节点,按照原图的连接方式进行连接
深度优先遍历
/**
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function(node) {
    if(!node) return;
    const map = new Map()
    const bfs = (node) => {
        const nCopy = new Node(node.val);
        map.set(node, nCopy);
        (node.neighbors || []).forEach(n => {
            if(!map.has(n)) {
                bfs(n)
            }
            nCopy.neighbors.push(map.get(n))
            
        })
    }
    bfs(node)
    return map.get(node)
};

时间复杂度:O(n)
空间复杂度:O(n)

广度优先遍历
var cloneGraph = function(node) {
    if(!node) return;
    const map = new Map()
    const q = [node]
    map.set(node, new Node(node.val))
    while(q.length) {
        const n = q.shift();
        (n.neighbors || []).forEach(c => {
            if(!map.has(c)) {
                q.push(c)
                map.set(c, new Node(c.val))
            }
            
            map.get(n).neighbors.push(map.get(c))
            
        })
    }
    return map.get(node)
};

时间复杂度:O(n)
空间复杂度:O(n)

这篇关于【学习打卡】第21天 数据结构和算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!