Day 11 | 7/27

[tech-cow]

今日计划 | BFS

搜集BFS资源，以及针对经典题开刷。

Leetcode

• 102. Binary Tree Level Order Traversal
• 133. Clone Graph
• 127. Word Ladder
• 207. Course Schedule
• 210. Course Schedule II

Lintcode

• 127. Topological Sorting

Comeback Later：

• 297. Serialize and Deserialize Binary Tree
• 444. Sequence Reconstruction
• 611. Knight Shortest Path

[tech-cow]

Leetcode

102. Binary Tree Level Order Traversal

类型：BFS
Time Complexity O(n)
Space Complexity O(n)

BFS的题解思路。

这里new_q也可以命名成next_level，同样q可以命名为cur_level，但因为太长，我选择放弃。

通过一个temp的数组new_q来存储下一层的node，
每次迭代完成后，把temp数组的node更新到q里面用于下一次迭代，并存储至res

class Solution(object):
    def levelOrder(self, root):
        res = []
        if not root: 
            return res
        q = [root]
        while q :
            res.append([node.val for node in q])
            new_q = []
            for node in q:
                if node.left:
                    new_q.append(node.left)
                if node.right:
                    new_q.append(node.right)
            q = new_q
        return res

133. Clone Graph

类型：BFS
Time Complexity O(n)
Space Complexity O(n)

思路：

1. 找到所有的Nodes，并且储存到字典
2. 找到每个Node的Neighbor，并储存到字典

有了思路以后，写个Helper用来BFS遍历寻找所有的Node，具体参考getNodes()
然后要做的就是把所有的Nodes存储以及他们的Neighbor，参考以下

# Definition for a undirected graph node
# class UndirectedGraphNode:
#     def __init__(self, x):
#         self.label = x
#         self.neighbors = []

class Solution:
    def cloneGraph(self, node):
        if not node: return node
        root = node
        
        # Store Nodes      
        nodes = self.getNodes(node)
        dic = {}
        for node in nodes:
            dic[node] = UndirectedGraphNode(node.label)
            
        # Store Node's Neighbors
        for node in nodes:
            clone_node = dic[node]
            for neighbor in node.neighbors:
                clone_neighbor = dic[neighbor]
                clone_node.neighbors.append(clone_neighbor)
        return dic[root]
            

        
    def getNodes(self, node):
        q = collections.deque([node])
        res = set([node])
        while q:
            head = q.popleft()
            for neighbor in head.neighbors:
                if neighbor not in res:
                    res.add(neighbor)
                    q.append(neighbor)
        return res

127. Word Ladder

类型：BFS
Time Complexity O(n26^len) -> O(n26^len/2)
Space Complexity O(n)

每次只要对word里面任意字母进行更改以后，就将其放回queue里面。
对于是否访问这个问题，我的写法是写一个visted的set来统计，LC里面有一种直接删除wordList里面访问过的词，想法雷同。
至于记录深度，可以利用python里面tuple的小技巧，每次迭代的时候对tuple里面的计量单位增值即可:
q.append((new_word, length + 1))
最后一点就是开头的arr = set(arr) 用来解决TLE，LC里面有些特别大的重复List很尴尬。

class Solution(object):
    def ladderLength(self, start, end, arr):
        arr = set(arr) #avoid TLE
        q = collections.deque([(start, 1)])
        visted = set()
        alpha = string.ascii_lowercase  #'abcd...z'
        while q:
            word, length = q.popleft()
            if word == end:
                return length
            
            for i in range(len(word)):
                for ch in alpha:
                    new_word = word[:i] + ch + word[i+1:]
                    if new_word in arr and new_word not in visted:
                        q.append((new_word, length + 1))
                        visted.add(new_word)
        return 0

白板

写白板的时候忘记写 new_word not in visted

207. Course Schedule

类型：BFS
Time Complexity O(n)
Space Complexity O(n)

Topological Sorting题
首先构建一个图，因为题目没有提供。
然后创建一个入度数组。
把入度数组里面为0的课丢进Queue，表示这门课无需Pre-req，然后对这门课的所有邻居的入度减1。更新完邻居的入度后，如果发现邻居里面有入度为0，则将其丢进Queue继续迭代。

class Solution(object):
    def canFinish(self, n, edges):
        from collections import deque
        in_degrees = [0 for i in range(n)]   #入度记录一门课需要上几个pre_req
        graph = {i: set() for i in range(n)}   #画一幅图

        # 构建图以及入度
        for i, j in edges:
            in_degrees[i] += 1  
            graph[j].add(i) 

        # 如果课没有pre_req，扔到Queue里
        q = deque()
        for i, pre_req in enumerate(in_degrees):    
            if not pre_req:
                q.append(i)

        # 进行BFS操作
        visited = 0
        while q:
            node = q.popleft()
            visited += 1
            for neigh in graph[node]:
                in_degrees[neigh] -= 1
                if in_degrees[neigh] == 0:
                    q.append(neigh)
        return visited == n

210. Course Schedule II

类型：BFS
Time Complexity O(n)
Space Complexity O(n)

这种Follow up简直就是送分啊。就把每次pop出来的数存到一个数组返回即可。

class Solution(object):
    def findOrder(self, n , edges):
        from collections import deque
        in_degrees = [0 for i in range(n)]   #入度记录一门课需要上几个pre_req
        graph = {i: set() for i in range(n)}   #画一幅图

        # 构建图以及入度
        for i, j in edges:
            in_degrees[i] += 1  
            graph[j].add(i) 

        # 如果课没有pre_req，扔到Queue里
        q = deque()
        for i, pre_req in enumerate(in_degrees):    
            if not pre_req:
                q.append(i)

        # 进行BFS操作
        visited = 0
        res = []
        while q:
            node = q.popleft()
            visited += 1
            res.append(node)
            for neigh in graph[node]:
                in_degrees[neigh] -= 1
                if in_degrees[neigh] == 0:
                    q.append(neigh)
        return res if visited == n else []

[tech-cow]

Lintcode

127. Topological Sorting

类型：BFS
Time Complexity O(n)
Space Complexity O(n)

def topSortBFS(self, graph):
    indegree = {}
    ans = []
    for g in graph:
        for n in g.neighbors:
            if n not in indegree:
                indegree[n] = 1
            else:
                indegree[n] += 1
                
    q = []
    for g in graph:
        if g not in indegree:
            q.append(g)
    
    while q:
        temp = q.pop(0)
        ans.append(temp)
        for n in temp.neighbors:
            indegree[n] -= 1
            if indegree[n] == 0:
                q.append(n)
    return ans