Pythonデータ構造の図と二叉検索ツリー

23627 ワード

データ構造 LeetCode アルゴリズム#アルゴリズム#

1.図の基礎知識

図はアルゴリズムの中で最も強力なフレームワークの一つであり、ツリー構造は図の特殊な状況にすぎない.図は隣接テーブルと重み付け隣接辞書で表すことができる

2.図の深さ優先探索と幅優先探索

リファレンスhttps://www.cnblogs.com/yupeng/p/3414736.htmlこのブログ

2.1深さ優先アルゴリズム：

(1)初期頂点vにアクセスし、頂点vにアクセスしたことをマークする.(2)頂点vの最初の隣接頂点wを検索する.(3)頂点vの隣接頂点wが存在する場合、実行を継続する.そうでなければvに遡って、vのもう一つのアクセスされていない隣接点を探します.(4)頂点wがまだアクセスされていない場合、頂点wにアクセスし、頂点wがアクセスされたとマークする.(5)頂点wの次の隣接頂点wiの検索を続け、vが値wiを取った場合はステップ(3)に進む.連通図のすべての頂点がすべてアクセスされるまで.

2.2幅優先アルゴリズム：

(1)頂点vがキューに入る.(2)キューが空でない場合は実行を続け,そうでない場合はアルゴリズムが終了する.(3)キューを出てキューヘッダ頂点vを取得する.頂点vにアクセスし、頂点vがアクセスされたことをマークします.(4)頂点vの最初の隣接頂点colを検索する.(5)vの隣接頂点colがアクセスされていない場合,colはキューに入る.(6)頂点vの別の新しい隣接頂点colを検索し続け、ステップ(5)に進む.頂点vのすべてのアクセスされていない隣接点が処理されるまで.手順(2)に進みます.

3.カリキュラム(LeetCode 207210630)

3.1テーマ

LeetCode 207 Course Schedule There are a total of n courses you have to take, labeled from 0 to n - 1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1] Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses? For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

LeetCode 210 Course Schedule II There are a total of n courses you have to take, labeled from 0 to n - 1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1] Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses. There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array. For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

LeetCode 630 Course Schedule III There are n different online courses numbered from 1 to n. Each course has some duration(course length) t and closed on dth day. A course should be taken continuously for t days and must be finished before or on the dth day. You will start at the 1st day. Given n online courses represented by pairs (t,d), your task is to find the maximal number of courses that can be taken. Example:

Input: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
Output: 3
Explanation: 
There're totally 4 courses, but you can take 3 courses at most:
First, take the 1st course, it costs 100 days so you will finish it on the 100th day, and ready to take the next course on the 101st day.
Second, take the 3rd course, it costs 1000 days so you will finish it on the 1100th day, and ready to take the next course on the 1101st day. 
Third, take the 2nd course, it costs 200 days so you will finish it on the 1300th day. 
The 4th course cannot be taken now, since you will finish it on the 3300th day, which exceeds the closed date.

3.2考え方

LeetCode 207 Course Scheduleは、図中にループの有無を判定するループが存在する場合false

に戻ることに相当する.

LeetCode 210 Course Schedule IIすべてのレッスンを完了するには、すべてのレッスンの順序を返します(1)numCorsetサイズの配列grapを初期化します(2)図のノードの入度を配列に保存し、配列の最初の入度が0のノードを見つけて-1に設定します.配列のすべての頂点が入度である頂点の入度を1減らし、そのpushを結果配列の(3)に繰り返します(2)numCourse回、入力値が0の頂点が見つからない場合は、空に戻ります.

LeetCode 630 Course Schedule IIIは、カリキュラムの終了時間に基づいてカリキュラムをソートし、優先キュー(heapq)を使用して、現在最も遅い完了時間の制約を満たしているカリキュラムの時間を維持し、制約を満たしていないカリキュラムの時間をポップアップします(カリキュラムの実際の終了時間をできるだけ早くすることができます).制約:時間間隔≦end≦end

3.3コード

LeetCode 207 Course Schedule

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """
        node = [[] for i in range(numCourses)]
        visit = [0 for i in range(numCourses)]
        for x, y in prerequisites:
            node[x].append(y)
        def dfs(i):
            if visit[i] == -1:
                return False
            if visit[i] == 1:
                return True
            visit[i] = -1
            for j in node[i]:
                if not dfs(j):
                    return False
            visit[i] = 1
            return True
        for i in range(numCourses):
            if not dfs(i):
                return False
        return True

LeetCode 210 Course Schedule II

class Solution(object):
    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """
        grap = [0] * numCourses
        for pre in prerequisites:
            grap[pre[0]] += 1
        ans =[]
        for j in range(numCourses):
            for i in range(numCourses):
                if grap[i] == 0:
                    ans.append(i)
                    grap[i] = -1
                    for pre in prerequisites:
                        if pre[1] == i:
                            grap[pre[0]] -= 1
                    break
        if len(ans) != numCourses:
            return []
        else:
            return ans

LeetCode 630 Course Schedule III

import heapq
class Solution(object):
    def scheduleCourse(self, courses):
        """
        :type courses: List[List[int]]
        :rtype: int
        """
        heap = []
        start = 0
        courses = sorted(courses, key=lambda x: x[1])
        for t, end in courses:
            start += t
            heapq.heappush(heap, -t)
            while start > end:
                start += heapq.heappop(heap)
        return len(heap)

4.最小高さの木（LeetCode 310 Minimum Height Trees）

4.1テーマ

For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.
Format The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
Example 1:
Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]

return [1]
Example 2:
Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

return [3, 4]
Note:
(1) According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”
(2) The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

4.2考え方

まず各点の度を計算し、次に度1の点をlistまたはqueueに入れて計算し、これらの点をneighborから除去し、次にdegree=1の点を計算し、最後に1-2点(答えになる点は必ず葉結点の上の層にあるため)がrootである

4.3コード

class Solution(object):
    def findMinHeightTrees(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        if n == 1:
            return [0]
        edge_dict = {}
        degree = [0] * n
        for i, j in edges:
            edge_dict[i] = edge_dict.get(i, []) + [j]
            edge_dict[j] = edge_dict.get(j, []) + [i] 
            degree[i] += 1
            degree[j] += 1
        degree_1 = []
        for i in range(n):
            if degree[i] == 1:
                degree_1.append(i)
        while n > 2:
            n -= len(degree_1)
            dq = []
            for i in degree_1:
                out = edge_dict[i][0]
                edge_dict[out].remove(i)
                if len(edge_dict[out]) <= 1:
                    if out not in dq:
                        dq.append(out)
            degree_1 = dq[:]
        return degree_1

5.ツリーの基礎知識

二叉ソートツリーまたは空のツリー、または以下の性質を有する二叉ツリー:(1)左のサブツリーが空でない場合、左のサブツリー上のすべてのノードの値は、そのルートノードの値以下である.(2)右サブツリーが空でない場合、右サブツリー上のすべてのノードの値は、そのルートノードの値以上である.(3)左,右サブツリーもそれぞれ二叉ソートツリーである.

6.二叉ルックアップツリーのK番目の小さい数（LeetCode 230 Kth Smallest Element in a BST）

6.1テーマ

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
Note: You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

6.2考え方

ツリーの特徴に基づいて、k番目のノードまで巡回するまで、再帰メソッドを使用して、k番目のノードまで順次巡回する方法を使用します.

6.3コード

class Solution(object):
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        self.k = k
        self.ans = None
        self.solve(root)
        return self.ans

    def solve(self, root):
        if not root:
            return
        self.solve(root.left)
        self.k -= 1
        if self.k == 0:
            self.ans = root.val
            return 
        self.solve(root.right)

7.ツリー符号化と復号化（LeetCode 449 Serialize and Deserialize BST）

7.1テーマ

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.
The encoded string should be as compact as possible.

7.2考え方

シーケンス化:二叉検索ツリーをシーケンスし、カンマ区切り値文字列を出力逆シーケンス化:スタックとノードステーションを使用して二叉ツリーの再構築中のノードを保存し、最大値スタックrstackは現在のノードの右ノードが許可する最大値を保存し、シーケンス化列をループし、現在の数値をvalとし、新規ツリーノードnode=TreeNode(val)

7.3コード

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return ''
        left = self.serialize(root.left)
        right = self.serialize(root.right)
        ans = str(root.val)
        if left:
            ans += ',' + left
        if right:
            ans += ',' + right
        return ans


    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        if not data:
            return None
        nstack, rstack = [], [0x7FFFFFFF]
        for val in map(int, data.split(',')):
            node = TreeNode(val)
            if nstack:
                if val < nstack[-1].val:
                    nstack[-1].left = node
                    rstack.append(nstack[-1].val)
                else:
                    while val > rstack[-1]:
                        while nstack[-1].val > nstack[-2].val:
                            nstack.pop()
                        nstack.pop()
                        rstack.pop()
                    nstack[-1].right = node
            nstack.append(node)
        return nstack[0]

8.逆シーケンス（LeetCode 315 Count of Smaller Numbers After Self）

8.1テーマ

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

8.2考え方

ツリーを作成し、ルートノードから挿入し、自身の値より小さいノード数を計算します.

8.3コード

class BinarySearchTreeNode(object):
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.count = 1
        self.leftTreeSize = 0


class BinarySearchTree(object):
    def __init__(self):
        self.root = None

    def insert(self, val, root):
        if not root:
            self.root = BinarySearchTreeNode(val)
            return 0

        if val == root.val:
            root.count += 1
            return root.leftTreeSize

        if val < root.val:
            root.leftTreeSize += 1

            if not root.left:
                root.left = BinarySearchTreeNode(val)
                return 0
            return self.insert(val, root.left)

        if not root.right:
            root.right = BinarySearchTreeNode(val)
            return root.count + root.leftTreeSize

        return root.count + root.leftTreeSize + self.insert(
            val, root.right)

class Solution(object):
    def countSmaller(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        tree = BinarySearchTree()
        return [
            tree.insert(nums[i], tree.root)
            for i in xrange(len(nums) - 1, -1, -1)
        ][::-1]

コメント投稿機能

Windows 10でのLinux GUIアプリの実行