LeetCode day25

6 minutes read
LeetCode
#LeetCode
views 1078 words

Diffculty: Medium

207. Course Schedule

Topic: DFS, BFS, Graph, Topological sort

There are a total of numCourses courses you have to take, labeled from 0 to numCourses-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?

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: 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.

Constraints:

  • The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  • You may assume that there are no duplicate edges in the input prerequisites.
  • 1 <= numCourses <= 10^5

思路:

  • 本题可约化为： 课程安排图是否是 有向无环图(DAG)。即课程间规定了前置条件，但不能构成任何环路，否则课程前置条件将不成立。
  • 思路是通过 拓扑排序 判断此课程安排图是否是 有向无环图(DAG) 。 拓扑排序原理： 对 DAG 的顶点进行排序，使得对每一条有向边 (u, v)，均有 u（在排序记录中）比 v 先出现。亦可理解为对某点 v 而言，只有当 v 的所有源点均出现了，v 才能出现。
  • 通过课程前置条件列表 prerequisites 可以得到课程安排图的 邻接表 adjacency，以降低算法时间复杂度，以下两种方法都会用到邻接表。

Approach1

topo sort + BFS

def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
    #用拓扑排序，来判断图是否是有环图
    #首先定义两个表，一个入度表，一个图的邻接表
    indegrees = [0 for _ in range(numCourses)]
    adjacency = [[] for _ in range(numCourses)]

    #将题目给出的数据转换成入度表和邻接表
    for cur, pre in prerequisites:
        indegrees[cur] += 1
        adjacency[pre].append(cur)

    #然后开始用bfs进行，首先将入度为0的点入队
    quee_ = []
    for i in range(numCourses):
        if indegrees[i] == 0:
            quee_.append(i)

    #开始迭代
    while quee_:
        node = quee_.pop(0)
        numCourses-=1                    #学完一门课
        for c in adjacency[node]:
            indegrees[c] -= 1            #这个点入读减1
            if indegrees[c] == 0:        #入读变为0，意思已经学完了先到课程
                quee_.append(c)          #入队,循环
    
    return not numCourses                #判断时候课程都学完

时间复杂度 O(N + M)： 遍历一个图需要访问所有节点和所有临边，N 和 M 分别为节点数量和临边数量；

空间复杂度 O(N + M)： 为建立邻接表所需额外空间，adjacency 长度为 N ，并存储 M 条临边的数据

Approach2

DFS

def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
    def dfs(i, adjacency, flags):
        if flags[i] == -1: return True
        if flags[i] == 1: return False
        flags[i] = 1
        for j in adjacency[i]:
            if not dfs(j, adjacency, flags): return False
        flags[i] = -1
        return True

    adjacency = [[] for _ in range(numCourses)]
    flags = [0 for _ in range(numCourses)]
    for cur, pre in prerequisites:
        adjacency[pre].append(cur)
    for i in range(numCourses):
        if not dfs(i, adjacency, flags): return False
    return True

时间复杂度 O(N + M)： 遍历一个图需要访问所有节点和所有临边，N 和 M 分别为节点数量和临边数量；

空间复杂度 O(N + M)： 为建立邻接表所需额外空间，adjacency 长度为 N ，并存储 M 条临边的数据

208. Implement Trie (Prefix Tree)

Topic: Design, Trie

Implement a trie with insert, search, and startsWith methods.

Example:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");   
trie.search("app");     // returns true

Note:

  • You may assume that all inputs are consist of lowercase letters a-z.
  • All inputs are guaranteed to be non-empty strings.

Approach1

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.lookup = {}
        

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        tree = self.lookup
        for a in word:
            if a not in tree:
                tree[a] = {}
            print(self.lookup,'--------' ,tree)
            '''
{'a': {}} -------- {'a': {}}
{'a': {'p': {}}} -------- {'p': {}}
{'a': {'p': {'p': {}}}} -------- {'p': {}}
{'a': {'p': {'p': {'l': {}}}}} -------- {'l': {}}
{'a': {'p': {'p': {'l': {'e': {}}}}}} -------- {'e': {}}
            '''
            tree = tree[a]
        # 单词结束标志
        tree["#"] = "#"
        

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        tree = self.lookup
        for a in word:
            if a not in tree:
                return False
            tree = tree[a]
        if "#" in tree:
            return True
        return False
        

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        tree = self.lookup
        for a in prefix:
            if a not in tree:
                return False
            tree = tree[a]
        return True




# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

Approach2

210. Course Schedule II

Topic: DFS, BFS, Graph, Topological sort

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.

Example 1:

Input: 2, [[1,0]] 
Output: [0,1]
Explanation: 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] .

Example 2:

Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: 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] .

Note:

  1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  2. You may assume that there are no duplicate edges in the input prerequisites.

Approach1

Approach2

215. Kth Largest Element in an Array

Topic: Heap, Divide and Conquer

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note: You may assume k is always valid, 1 ≤ k ≤ array’s length.

Approach1

def findKthLargest(nums: List[int], k: int) -> int:
    nums = sorted(nums)
    return nums[-k]

Approach2

使用堆(heap, FIFO), 它比较列表的优势在于，它可以在插入数据时自动调整位置，使之符合堆特征，即nums[i]总是大于nums[i//2]

  1. heappush(heap, x) 将x压入堆中
  2. heappop(heap) 从堆中弹出最小的元素
  3. heapify(heap) 让列表具备堆特征
  4. heapreplace(heap, x) 弹出最小的元素，并将x压入堆中，返回弹出的元素
  5. nlargest(n, iter) 返回iter中n个最大的元素
  6. nsmallest(n, iter) 返回iter中n个最小的元素

采用nlargest直接获取答案:

def findKthLargest(nums: List[int], k: int) -> int:
    from heapq import heappush,heapreplace
    # 使用堆的nlargest(n,iter)返回前n个最大的数,倒序排练
    return nlargest(k,nums)[-1]

Approach3

利用最大堆，存储前k个最大的数，最后返回堆底元素就行了. 主要思路：

  1. 当i<k,压数据进堆
  2. 当i>=k，比较sums[i]和堆底元素，如果大于，则使用heapreplace进行替换，否则跳过

code:

def findKthLargest(nums: List[int], k: int) -> int:
    from heapq import heappush,heapreplace       
    # 使用小顶堆
    heap = []
    for i in range(len(nums)):
        if i < k:
            heappush(heap,nums[i])
        else:
            if nums[i] > heap[0]:
                m = heapreplace(heap,nums[i]) # 可以不用m，用来表示弹出的元素
    return heap[0]

Approach4