Day 2 - BFS

[tech-cow]

No description provided.

[tech-cow]

普通BFS

399 Currency Exchange

出错1： 应该先Pop在写exit condition.....
出错2：set([]) set takes iterable.....

第一次尝试: 2 Bugs

from collections import deque, defaultdict

class Solution(object):
    def calcEquation(self, equations, values, queries):
        if not equations or not values or not queries: return -1.0
        graph = self.make_graph(equations, values)
        res = []
        for start, end in queries:
            res.append(self.bfs(graph, start, end))
        return res
            
    
    def make_graph(self, equations, values):
        dic = defaultdict(list)
        for pair, val in zip(equations, values):
            div_a, div_b = pair
            dic[div_a].append((div_b, val)) 
            dic[div_b].append((div_a, 1.0 / val)) 
        return dic    
    
    def bfs(self, graph, start, end):    
        if start not in graph or end not in graph: return -1.0
        
        queue = deque([(start, 1.0)])
        visited = set(start)    # bug 2
        
        while queue:
            size = len(queue)
            for i in range(size):
                if node == end:       # bug 1
                    return cur_val
                
                node, cur_val = queue.popleft()
                
                for neighbor_node, val in graph[node]:
                    if neighbor_node not in visited:
                        queue.append((neighbor_node, val * cur_val))
                        visited.add(neighbor_node)        
        return -1.0

正确代码

from collections import deque, defaultdict

class Solution(object):
    def calcEquation(self, equations, values, queries):
        if not equations or not values or not queries: return -1.0
        graph = self.make_graph(equations, values)
        res = []
        for start, end in queries:
            res.append(self.bfs(graph, start, end))
        return res
            
    
    def make_graph(self, equations, values):
        dic = defaultdict(list)
        for pair, val in zip(equations, values):
            div_a, div_b = pair
            dic[div_a].append((div_b, val)) 
            dic[div_b].append((div_a, 1.0 / val)) 
        return dic    
    
    def bfs(self, graph, start, end):    
        if start not in graph or end not in graph: return -1.0
        
        queue = deque([(start, 1.0)])
        visited = set([start])
        
        while queue:
            node, cur_val = queue.popleft()

            if node == end:
                return cur_val

            for neighbor_node, val in graph[node]:
                if neighbor_node not in visited:
                    queue.append((neighbor_node, val * cur_val))
                    visited.add(neighbor_node)  
        return -1.0

[tech-cow]

BFS + Topological

207. Course Schedule

出错1： deque([i for i in range(numCourses) if indegree[i] == 0]), 第一次的时候没有call deque，然后用了popleft

正确代码

from collections import deque, defaultdict
class Solution(object):
    def canFinish(self, numCourses, courses):
        graph, indegree = self.make_graph(courses)
        return self.bfs(numCourses, graph, indegree)
    
    def make_graph(self, courses):
        graph = defaultdict(set)
        indegree = defaultdict(int)
        
        for course, prereq in courses:
            graph[prereq].add(course)
            indegree[course] += 1
        return graph, indegree
    
    
    def bfs(self, numCourses, graph, indegree):
        count = 0
        queue = deque([i for i in range(numCourses) if indegree[i] == 0])
        
        while queue:
            count += 1
            node = queue.popleft()
            for neighbor_node in graph[node]:
                indegree[neighbor_node] -= 1
                if indegree[neighbor_node] == 0:
                    queue.append(neighbor_node)
        
        return count == numCourses