Shinkai005

V1

2022/02/12阅读:29主题:红绯

【leetcode】133.克隆图

【leetcode】133.克隆图.md

image-20220212085245101
image-20220212085245101

==题目描述==

image-20211130130239606
image-20211130130239606

==题目思路==

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

==个人题解==

  1. 遍历所有的节点
  2. 拷贝所有节点存储起来
  3. 将拷贝的节点根据原图的方式进行链接
/**
 * // Definition for a Node.
 * function Node(val, neighbors) {
 *    this.val = val === undefined ? 0 : val;
 *    this.neighbors = neighbors === undefined ? [] : neighbors;
 * };
 */


/**
 * @param {Node} node
 * @return {Node}
 */

var cloneGraph = function (node{
    // 1.   遍历所有的节点
    // 2.   拷贝所有节点存储起来
    // 3.   将拷贝的节点根据原图的方式进行链接
    if (!node) return;
    // 用map主要是为了建立映射关系.n和nCopy 还有neighbor之间
    const visited = new Map();
    // 深度遍历
    const dfs = (n) => {
        const nCopy = new Node(n.val);
        visited.set(n, nCopy);
        // 这里判[],是为了不影响程序继续执行.
        (n.neighbors || []).forEach(ne => {
            if (!visited.has(ne)) {
                dfs(ne);
            }
            //当前遍历的是n.neighbors, 加入到nCopy数组中.
            // 这里需要注意,加入的是nCopy
            nCopy.neighbors.push(visited.get(ne));
        });
    };
    dfs(node);
    return visited.get(node);
};

==总结优化==

下面是广度遍历

/**
 * // Definition for a Node.
 * function Node(val, neighbors) {
 *    this.val = val === undefined ? 0 : val;
 *    this.neighbors = neighbors === undefined ? [] : neighbors;
 * };
 */


/**
 * @param {Node} node
 * @return {Node}
 */

var cloneGraph = function (node{

    if (!node) return;
    const visited = new Map();
    visited.set(node, new Node(node.val))
    const q = [node];
    while (q.length) {
        const n = q.shift();
        
        (n.neighbors || []).forEach(ne => {
            if (!visited.has(ne)) {
                q.push(ne);
                visited.set(ne, new Node(ne.val));
            }
            visited.get(n).neighbors.push(visited.get(ne));
        })
    }
    return visited.get(node);
};

==时间复杂度(time complexity)==

O(n)

==空间复杂度(space complexity)==

O(n) map数据结构

  • 为什么不看递归的空间复杂度呢?

    • 如果两个结构前后排列,就返回更大的那个.

分类:

前端

标签:

JavaScript

作者介绍

Shinkai005
V1

公众号:深海笔记Shinkai