+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2019-08(47)

2019-09(90)

2019-10(13)

2019-11(9)

2019-12(19)

LeetCode 332. 重新安排行程20200827

发布于2020-08-28 21:10     阅读(58)     评论(0)     点赞(13)     收藏(1)


0

1

2

3

4

5

6

7

8

题目描述

给定一个机票的字符串二维数组 [from, to],子数组中的两个成员分别表示飞机出发和降落的机场地点,对该行程进行重新规划排序。所有这些机票都属于一个从 JFK(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK 开始。
 
说明:
如果存在多种有效的行程,你可以按字符自然排序返回最小的行程组合。例如,行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小,排序更靠前
所有的机场都用三个大写字母表示(机场代码)。
假定所有机票至少存在一种合理的行程。
 
示例 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 Hierholzer 算法

前言

我们化简本题题意:给定一个n个点 m 条边的图,要求从指定的顶点出发,经过所有的边恰好一次(可以理解为给定起点的「一笔画」问题),使得路径的字典序最小。
 
这种「一笔画」问题与欧拉图或者半欧拉图有着紧密的联系,下面给出定义:

  • 通过图中所有边恰好一次且行遍所有顶点的通路称为欧拉通路
  • 通过图中所有边恰好一次且行遍所有顶点的回路称为欧拉回路
  • 具有欧拉回路的无向图称为欧拉图
  • 具有欧拉通路但不具有欧拉回路的无向图称为半欧拉图
     

因为本题保证至少存在一种合理的路径,也就告诉了我们,这张图是一个欧拉图或者半欧拉图。我们只需要输出这条欧拉通路的路径即可。
如果没有保证至少存在一种合理的路径,我们需要判别这张图是否是欧拉图或者半欧拉图,具体地:

  • 对于无向图 G,G 是欧拉图当且仅当 G 是连通的且没有奇度顶点。
  • 对于无向图 G,G 是半欧拉图当且仅当 G 是连通的且 G 中恰有 2 个奇度顶点。
  • 对于有向图 G,G 是欧拉图当且仅当 G 的所有顶点属于同一个强连通分量且每个顶点的入度和出度相同。
  • 对于有向图 G,G 是半欧拉图当且仅当 G 的所有顶点属于同一个强连通分量且恰有一个顶点的出度与入度差为 1;恰有一个顶点的入度与出度差为 1;所有其他顶点的入度和出度相同。

 
作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/reconstruct-itinerary/solution/zhong-xin-an-pai-xing-cheng-by-leetcode-solution/
来源:力扣(LeetCode)

Hierholzer 算法: 用于求欧拉回路/路径

Hierholzer 算法过程:

  1. 选择任一顶点为起点,遍历所有相邻边。
  2. 深度搜索,访问相邻顶点。将经过的边都删除。
  3. 如果当前顶点没有相邻边,则将顶点入栈。
  4. 栈中的顶点倒序输出,就是从起点出发的欧拉回路。

为了证明该算法的有效性,下说明两条性质。
 

性质一
如果该图为欧拉图,则栈底的必定为起点。如果该图为半欧拉图,则栈底部存储的是与起点不同的另外一个奇度数顶点。
证明
当顶点入栈时,说明当前所在顶点没有相邻边。
考虑到从起点出发到当前结点的路径中,除了起点和当前顶点外,其他的顶点都失去了偶数度数(入度与出度一一对应)。

  • 欧拉回路–>当前结点与起点相同:
    如果起点和当前顶点不同,那么两者都失去了奇数度数。
    如果图中包含欧拉回路,意味着所有顶点的初始度数都是偶数,而当前顶点的当前度数为0,表示当前顶点的初始度数必定是奇数,产生矛盾,因此假设不成立,当前顶点就是起点。
  • 同样地,对于欧拉路径,当前顶点不可能是起点,否则起点的度数就是偶数,而欧拉路径中起点和终点的度数一定是奇数。
    因此,当前顶点不是起点,但是度数也是数,所以一定是终点。

 

性质二
如果该图为欧拉图(/半欧拉图),则栈中的自底到顶第 n个顶点就是欧拉回路(/欧拉路径)上的第 n个顶点。
证明
在此只证明栈中相邻顶点在图中也为相邻顶点。因为模拟 Hierholzer 算法过程,可知该算法实际上就是在模拟“一笔画”过程,并且沿着画完的轨迹,从终点倒着逐一添加顶点到栈中。
并且主要以 n=2 的情况为例,后面的情况可以此类推。并且为了不用纠结于区分欧拉回路和欧拉路径,不妨以半欧拉图为例。
假设图中存在相邻的两顶点 V1,V2 ,并且深度搜索过程中,先访问 V2 随后访问了 V1,并且 V1 成为第一个入栈的顶点。由性质一可知,V1 就是欧拉路径上的起点(两个奇度数顶点任一可看作起点)。
根据 Hierholzer 算法,在遍历过程中,删除了途径的边,所以此时所有顶点的度数都为偶数。当然 deg(V2) 也是偶数,接下来就分类讨论。
如果 deg(V2)=0,也就是说当前顶点 V2 成为第二个入栈的顶点,那么 n=2 的情况就证毕了。
如果 deg(V2)>0 ,那么考虑当前包含 V2 的子图 G ,显然 G 是一个欧拉图,那么当前以 V2 为起点继续实施 Hierholzer 算法遍历剩下的相邻边,根据性质一V2 将会是 G 中第一个入栈的顶点。也就是,V2 是原图中第二个入栈的顶点。
综上所述,以此类推,Vn1 入栈前最后接触过的 Vn 将会是第 n 个入栈的顶点,再结合直观理解, Vn 就是路径上的第 n 个顶点。
作者:上进的z君
链接:https://zhuanlan.zhihu.com/p/108411618
来源:知乎

复杂度分析

时间复杂度:O(mlogm),其中m 是边的数量。对于每一条边我们需要 O(logm) 地删除它,最终的答案序列长度为 m+1,而与 n 无关。
 
空间复杂度:O(m),其中 m 是边的数量。我们需要存储每一条边。
作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/reconstruct-itinerary/solution/zhong-xin-an-pai-xing-cheng-by-leetcode-solution/
来源:力扣(LeetCode)

代码

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        A = {}
        for t in tickets:
            if t[0] in A:
                A[t[0]].append(t[1])
            else:
                A[t[0]] = [t[1]]
        for k in A:
            A[k].sort()
        ans = []
        def dfs(start):
            while start in A and len(A[start]):
                tmp = A[start].pop(0)
                dfs(tmp)
            ans.append(start)
        dfs('JFK')
        return ans[::-1]

解法1运行结果
简化代码

  1. 使用 collections 模块的 defaultdict类代替普通的dict,传入list参数,将value值初始为空的list,省去判断ticket‘s 起点是否在dict的key中。
  2. 调用heapq模快来对dict中的value进行排序。
    参考自力扣
import collections
import heapq


class Solution:
    def findItinerary(self, tickets):
        A = collections.defaultdict(list)
        ans = []
        for start, end in tickets:
            A[start].append(end)
        for k in A:
            heapq.heapify(A[k])
        def dfs(start):
            while len(A[start]):
                tmp = heapq.heappop(A[start])
                dfs(tmp)
            ans.append(start)
        dfs('JFK')
        return ans[::-1]

second result of first solution

原文链接:https://blog.csdn.net/silenceagle/article/details/108267979

0

1

2

3

4



所属网站分类: 技术文章 > 博客

作者:dfh8374

链接: https://www.pythonheidong.com/blog/article/496880/fde0aaf7a9df0578936c/

来源: python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

13 0
收藏该文
已收藏

评论内容:(最多支持255个字符)