Python描述資料結構之圖實戰篇

前言

??本篇章所涉及到的題目均來源于力扣(LeetCode)，著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
??LeetCode中有關圖的題目，

1. LeetCode684：冗余連接

??LeetCode第684題：冗余連接，

??題目 在本問題中, 樹指的是一個連通且無環的無向圖，
??輸入一個圖，該圖由一個有著 N N N個節點 ( ( (節點值不重復 1 , 2 , . . . , N ) 1, 2, ..., N) 1,2,...,N)的樹及一條附加的邊構成，附加的邊的兩個頂點包含在 1 1 1到 N N N中間，這條附加的邊不屬于樹中已存在的邊，
??結果圖是一個以邊組成的二維陣列，每一個邊的元素是一對 [ u , v ] [u, v] [u,v]，滿足 u < v u < v u<v，表示連接頂點 u u u和 v v v的無向圖的邊，
??回傳一條可以刪去的邊，使得結果圖是一個有著 N N N個節點的樹，如果有多個答案，則回傳二維陣列中最后出現的邊，答案邊 [ u , v ] [u, v] [u,v]應滿足相同的格式 u < v u < v u<v，
??注意
??(1) 輸入的二維陣列大小在 3 3 3到 1000 1000 1000，
??(2) 二維陣列中的整數在 1 1 1到 N N N之間，其中 N N N是輸入陣列的大小，
??解題思路 這個題可以當做并查集來做，思路就是檢查每一條邊上兩個頂點是否在一個集合中，如果在，那么加入這條邊之后圖中就會構成環；如果不在，就讓它并入集合中，

??有關并查集的知識及操作請參閱這篇博客，

??代碼實作如下：

    def Find(self, S, x):
        while S[x] != -1:
            x = S[x]
        return x

    def Union(self, S, root1, root2, result):
        # 這里的減一是因為我設定的S是從0開始的
        x = self.Find(S, root1-1)
        y = self.Find(S, root2-1)
        if x != y:
            S[y] = x
        else:
            result.append([root1, root2])

    def findRedundantConnection(self, edges):
        length = len(edges)
        S = [-1] * length
        result = []
        for i, j in edges:
            self.Union(S, i, j, result)
        return result[-1]

??運行結果如下：

2. LeetCode841：鑰匙和房間

??LeetCode第841題：鑰匙和房間，

??題目 有 N N N個房間，開始時你位于 0 0 0號房間，每個房間有不同的號碼： 0 ， 1 ， 2 ， . . . ， N ? 1 0，1，2，...，N-1 0，1，2，...，N?1，并且房間里可能有一些鑰匙能使你進入下一個房間，在形式上，對于每個房間 i i i都有一個鑰匙串列 r o o m s [ i ] rooms[i] rooms[i]，每個鑰匙 r o o m s [ i ] [ j ] rooms[i][j] rooms[i][j]由 [ 0 , 1 ， . . . ， N ? 1 ] [0,1，...，N-1] [0,1，...，N?1]中的一個整數表示，其中 N = r o o m s . l e n g t h N = rooms.length N=rooms.length， 鑰匙 r o o m s [ i ] [ j ] = v rooms[i][j] = v rooms[i][j]=v可以打開編號為 v v v的房間，
??最初，除 0 號房間外的其余所有房間都被鎖住，你可以自由地在房間之間來回走動，如果能進入每個房間回傳 t r u e true true，否則回傳 f a l s e false false，
??提示

1.	1 <= rooms.length <= 1000
2.	0 <= rooms[i].length <= 1000
3.	所有房間中的鑰匙數量總計不超過 3000，

??解題思路 這個題可以將房間看成圖中的頂點，而房間里的鑰匙則是連接另個一個頂點的弧，沒錯，是個有向圖，所以這個問題的本質就是圖的遍歷，如果遍歷一次結束，頂點全部被訪問過，即能進入每個房間，回傳 t r u e true true，否則就回傳 f a l s e false false，

??有關圖遍歷的操作，請參閱我的這篇博客，

??深度優先遍歷代碼實作如下：

    def canVisitAllRooms(self, rooms):
        self.rooms = rooms
        length = len(rooms)
        visited = [False] * length
        self.DFS(visited, v=0)
        if len(set(visited)) == 1:
            return True
        else:
            return False

    def DFS(self, visited, v):
        visited[v] = True
        for k in self.rooms[v]:
            # k是房間v里面的鑰匙
            if not visited[k]:
                self.DFS(visited, k)

??運行結果如下：

??廣度優先遍歷代碼實作如下：

    def canVisitAllRooms(self, rooms):
        import collections

        self.rooms = rooms
        length = len(rooms)
        visited = [False] * length
        visited[0] = True
        # 把房間0加入佇列
        queue = collections.deque(iterable=[0])
        self.BFS(visited, queue)
        if len(set(visited)) == 1:
            return True
        else:
            return False

    def BFS(self, visited, queue):
        while queue:
            v = queue.popleft()
            for k in self.rooms[v]:
                # k是房間v里面的鑰匙
                if not visited[k]:
                    visited[k] = True
                    queue.append(k)

??運行結果如下：

3. LeetCode1387：將整數按權重排序

??LeetCode第1387題：將整數按權重排序，

??題目 我們將整數 x x x 的 權重 定義為按照下述規則將 x x x 變成 1 1 1 所需要的步數：
??如果 x x x 是偶數，那么 x = x / 2 x = x / 2 x=x/2
??如果 x x x 是奇數，那么 x = 3 ? x + 1 x = 3 * x + 1 x=3?x+1
??比方說， x = 3 x=3 x=3 的權重為 7 7 7 ，因為 3 3 3 需要 7 7 7 步變成 1 ( 3 ? ? > 10 ? ? > 5 ? ? > 16 ? ? > 8 ? ? > 4 ? ? > 2 ? ? > 1 ) 1 (3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1) 1(3??>10??>5??>16??>8??>4??>2??>1)，
??給你三個整數 l o lo lo， h i hi hi 和 k k k ，你的任務是將區間 [ l o , h i ] [lo, hi] [lo,hi] 之間的整數按照它們的權重 升序排序 ，如果大于等于 2 2 2 個整數有 相同 的權重，那么按照數字自身的數值 升序排序 ，
??請你回傳區間 [ l o , h i ] [lo, hi] [lo,hi] 之間的整數按權重排序后的第 k k k 個數，
??注意題目保證對于任意整數 x ( l o < = x < = h i ) x (lo <= x <= hi) x(lo<=x<=hi) ，它變成 1 1 1 所需要的步數是一個 32 32 32 位有符號整數，
??提示

1.	1 <= lo <= hi <= 1000
2.	1 <= k <= hi - lo + 1

??解題思路 這個題可以把它當做圖，用深度優先遍歷來做，就是把區間里的整數看成圖中的頂點，用 R R R表示吧，計算每個 R R R的權重的程序又可以看成遍歷圖的程序，我舉個栗子，就是下面這張圖，對應著示例 1：

??大致就是這么個意思，哈哈哈哈(ﾉ′▽｀)ﾉ?
??代碼實作如下：

    def DFS(self, x):
        if x == 1:
            # 遞回結束條件
            return 0
        # 統計步數
        elif x % 2 == 0:
            # 偶數
            return self.DFS(x / 2) + 1
        elif x % 2 != 0:
            # 奇數
            return self.DFS(3 * x + 1) + 1

    def getKth(self, lo, hi, k):
        result = []
        for x in range(lo, hi+1):
            count = self.DFS(x)
            result.append([x, count])
        result = sorted(result, key=lambda item: item[1])
        return result[k-1][0]

??運行結果如下：

??時間消耗較多，勉強算是跑完了ヾ(@^▽^@)ノ

4. LeetCode997：找到小鎮的法官

??LeetCode第997題：找到小鎮的法官，

??題目 在一個小鎮里，按從 1 1 1 到 N N N 標記了 N N N 個人，傳言稱，這些人中有一個是小鎮上的秘密法官，
??如果小鎮的法官真的存在，那么：

• 小鎮的法官不相信任何人，
• 每個人（除了小鎮法官外）都信任小鎮的法官，
• 只有一個人同時滿足屬性 1 1 1 和屬性 2 2 2，

??給定陣列 t r u s t trust trust，該陣列由信任對 t r u s t [ i ] = [ a , b ] trust[i] = [a, b] trust[i]=[a,b] 組成，表示標記為 a a a 的人信任標記為 b b b 的人，
??如果小鎮存在秘密法官并且可以確定他的身份，請回傳該法官的標記，否則，回傳 ? 1 -1 ?1，
??提示

1.	1 <= N <= 1000
2.	trust.length <= 10000
3.	trust[i] 是完全不同的
4.	trust[i][0] != trust[i][1]
5.	1 <= trust[i][0], trust[i][1] <= N

??解題思路 畫了一個圖可以發現，這個題可以用有向圖來做，即把每個人當做圖中的頂點，如果 P e r s o n 1 Person1 Person1信任 P e r s o n 2 Person2 Person2，則 P e r s o n 1 Person1 Person1是弧尾， P e r s o n 2 Person2 Person2是弧頭，由題目可知，所有人都信任法官，即法官所在頂點的入度為 N ? 1 N-1 N?1，法官不信任任何人，即法官所在頂點的出度為 0 0 0，
??代碼實作如下：

    def findJudge(self, N, trust):
        indegree = [0] * N
        outdegree = [0] * N
        for i, j in trust:
            outdegree[i-1] += 1
            indegree[j-1] += 1
        for index in range(N):
            if indegree[index] == N-1 and outdegree[index] == 0:
                return index + 1
        return -1

??運行結果如下：