【学习打卡】第21天 数据结构和算法
2022/8/27 4:23:10
本文主要是介绍【学习打卡】第21天 数据结构和算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
图
克隆图(leetcode - 133)
给你无向 连通 图中一个节点的引用,请你返回该图的 深拷贝(克隆)。
图中的每个节点都包含它的值 val(int) 和其邻居的列表(list[Node])。
思路
- 拷贝所有节点
- 拷贝所有边
步骤
- 深度或者广度优先遍历所有节点
- 拷贝所有节点,存储起来
- 将拷贝的节点,按照原图的连接方式进行连接
深度优先遍历
/** * @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天 数据结构和算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型?
- 2024-05-29鸿蒙原生应用再新丁!新华社 入局鸿蒙
- 2024-05-29设计模式 之 迭代器模式(Iterator)