133. 克隆图

题目描述 给定无向连通图中一个节点的引用,返回该图的深拷贝(克隆)。图中的每个节点都包含它的值 val(Int) 和其邻居的列表(list[Node])。 示例: 输入: {“$id”:”1″,”neighbors”:[{“$id”:”2″,”neighbors”:[{“$ref”:”1″},{“$id”:”3″,”neighbors”:[{“$ref”:”2″},{“$id”:”4″,”neighbors”:[{“$ref”:”3″},{“$ref”:”1″}],”val”:4}],”val”:3}],”val”:2},{“$ref”:”4″}],”val”:1} 解释: 节点 1 的值是 1,它有两个邻居:节点 2 和 4 。 节点 2 的值是 2,它有两个邻居:节点 1 和 3 。 节点 3 的值是 3,它有两个邻居:节点 2 和 4 。 节点 4 的值是 4,它有两个邻居:节点 1 和 3 。 提示: 节点数介于 1 到 100 之间。 无向图是一个简单图,这意味着图中没有重复的边,也没有自环。 由于图是无向的,如果节点 p 是节点 q 的邻居,那么节点 q 也必须是节点p 的邻居。 必须将给定节点的拷贝作为对克隆图的引用返回。 来源:力扣(LeetCode)…

Read more

684. 冗余连接

题目描述 在本问题中, 树指的是一个连通且无环的无向图。 输入一个图,该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间,这条附加的边不属于树中已存在的边。 结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ,满足 u < v,表示连接顶点u 和v的无向图的边。 返回一条可以删去的边,使得结果图是一个有着N个节点的树。如果有多个答案,则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。 示例 1: 输入: [[1,2], [1,3], [2,3]] 输出: [2,3] 解释: 给定的无向图为: 1 / \ 2 – 3 示例 2: 输入: [[1,2], [2,3], [3,4], [1,4], [1,5]] 输出: [1,4] 解释: 给定的无向图为: 5 – 1 – 2 | | 4 -…

Read more

332. 重新安排行程

题目描述 给定一个机票的字符串二维数组 [from, to],子数组中的两个成员分别表示飞机出发和降落的机场地点,对该行程进行重新规划排序。所有这些机票都属于一个从JFK(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK 出发。 说明: 1. 如果存在多种有效的行程,你可以按字符自然排序返回最小的行程组合。例如,行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小,排序更靠前 2. 所有的机场都用三个大写字母表示(机场代码)。 3. 假定所有机票至少存在一种合理的行程。 示例 1: 输入: [[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]] 输出: [“JFK”, “MUC”, “LHR”, “SFO”, “SJC”] 示例 2: 输入: [[“JFK”,”SFO”],[“JFK”,”ATL”],[“SFO”,”ATL”],[“ATL”,”JFK”],[“ATL”,”SFO”]] 输出: [“JFK”,”ATL”,”JFK”,”SFO”,”ATL”,”SFO”] 解释: 另一种有效的行程是 [“JFK”,”SFO”,”ATL”,”JFK”,”ATL”,”SFO”]。但是它自然排序更大更靠后。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/reconstruct-itinerary 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 首先,我们忽略按照字典顺序排列这一条件,那么这道题本质上求得的是有向图的欧拉路径。 严谨地说,一个连通有向图G有欧拉路径,指存在一个顶点,从它出发,沿着有向边的方向,可以不重复地遍历图中所有的边。 https://zh.wikipedia.org/wiki/%E4%B8%80%E7%AC%94%E7%94%BB%E9%97%AE%E9%A2%98 题目中给定的机场名称是图的顶点,行程是图的边。题目要求重新安排行程,从示例可以看出每个行程都必须用到且只用一次。对应到欧拉路径的定义,每条边都要走到,且不重复。那么,这道题就转化成了给定起点,求一条字典顺序最小的欧拉路径。为了引出解法,我们先放几个例子。 图1展示了一张顶点度数都为偶数的图,首先我们忽略掉按字典顺序输出的条件。我们可以看出,如果顶点度数为偶数,那么我们先从JFK到MUC再回JFK到ATL最后返回JFK,又或是JFK先到ATL再回JFK再去MUC再回JFK,都是合法的路径。如果按照字典顺序输出,我们优先访问字典顺序小的节点ATL即可。因此,我们使用贪心策略,优先访问字典顺序小的顶点。 图2这个例子可以看出,我们别无选择必须先从JFK到NRT再回JFK,最后到达KUL作为终点。如果我们按照字典顺序先到KUL,就进入了“死路”。但是上一个例子我们提到了,优先访问字典顺序小的顶点,那么我们第一次肯定是先到KUL,这就走不通了,那怎么解决呢?当我们采用DFS方式遍历图时,需要将访问到的节点逆序插入到结果集。因此第一个访问到的节点将出现在结果集最后面,而我们是以顺序的方式来查看结果。如果第一个访问的节点是“孤岛节点”,他会出现在结果集的最后。当我们顺序读取结果集时,这种“孤岛节点”是最后遇到的,是图遍历的终点,这样就没有问题了。 我们在图3绘制了算法执行过程,黑色实线表示图的边;红色实实线表示递归调用;绿色虚线表示递归调用返回;数字代表执行顺序;文字表示执行的操作,结果集的数字表示在第几步操作加入的。我们从JFK出发,沿着边到达KUL(因为KUL字典顺序比NRT小),然后KUL没有临接点,将它放入结果集(2),然后从KUL返回到达JFK,注意这个是通过调用栈返回而不是沿着边返回。然后从JFK出发沿着边到达NRT,因为NRT到JFK有返回边,沿着边再回到JFK。此时JFK的两个临接点都访问过了,我们将JFK加入结果集(6)。然后我们从JFK返回到NRT,这是从调用栈返回。然后NRT的临接点都访问过了,我们将NRT加入结果集(8),然后退栈回到JFK。JFK的所有临接点都访问过了,将JFK加入结果集(10),然后退栈,整个流程结束。…

Read more