认真刷题的打卡

743. Network Delay Time

https://leetcode.com/problems/ne ... -easy-to-understand

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        # https://brilliant.org/wiki/dijkstras-short-path-finder/
        """
        Dijkstra
        time O(E+VlogV)
        space O(E+V)
        """
        
        # https://leetcode.com/problems/ne ... -easy-to-understand
        
        # build graph
        weight = collections.defaultdict(dict)
        for u, v, w in times:
            weight[v] = w
        
        heap = [(0,k)]
        distance = {}
        while(heap):
            cost, i = heapq.heappop(heap)
            if i not in distance:
                distance = cost
                for j in weight:
                    heapq.heappush(heap,(cost+weight[j], j))
        
        if len(distance) == n:
            return max(distance.values())
        return -1
        

class Solution(object):
    def validTree(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: bool
        """
        # union find to solve this
        
        root = [i for i in range(n)]
        
        def find(i):
            if root[i]==i:
                return i
            root[i] = find(root[i])
            return root[i]
        
        def union(a, b):
            ra = find(a)
            rb = find(b)
            if ra == rb:
                return True
            
            root[ra] = rb
            root[a] = rb
            return False
        
        for edge in edges:
            if union(edge[0], edge[1]):
                print(root)
                return False
        ### ALWAYS
        for i in range(n):
            find(i)
            
        return len(set(root)) ==1
        
        

#269. Alien Dictionary
class Solution(object):
    def alienOrder(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        graph = collections.defaultdict(list)
        status = {}
        
        def buildGraph(w1,w2):
            if w1 == w2:
                return True
            minlen = min(len(w1),len(w2))
            # abcxyz, abc
            if w1[:minlen] == w2[:minlen] and len(w1)>len(w2):
                return False
            i = 0
            while i<minlen and w1[i]==w2[i]:
                i+=1
            
            if w1[min(i,len(w1)-1)] in graph[w2[min(i,len(w2)-1)]]:
                #conflict
                return False
            graph[w1[min(i,len(w1)-1)]].append(w2[min(i,len(w2)-1)])
            return True
               
        # build Graph
        pool = []
        pool.extend(words[0])
        for word1, word2 in zip(words[:-1],words[1:]):
            pool.extend(word1+word2)
            if not buildGraph(word1, word2):
                return ""
        for c in pool:  
            status[c] = 0
        #print(status)
        
        """
        0 = unvisited
        1 = visited
        -1 = visiting
        """
        ret_stack = []
        
        def dfs(c):
            #print(c, status)
            if status[c] != 0:
                # T if finished , F if cycle found
                return status[c] == 1
            status[c] = -1
            for nextc in graph[c]:
                if not dfs(nextc):
                    return False
            status[c] = 1
            ret_stack.append(c)
            return True
            
        #print(status)
        for i in status.keys():
            r = dfs(i)
            
            if not r:
                return ""
        ret_stack.reverse()   
        return "".join(ret_stack)
            
        

近期
2/14        301H, 236M, 105M 547M 98M       
2/15        721M 207M 210M        
2/16        332M,133M101E       
2/17        1153H,863M,684M       
2/18        399M,785M,323M       
2/19        886M,797M,743M       
2/20        1334M,128H,841M       
2/21        261M,1042M,57M,269H       
2/22        526M,131M,329H       
2/23        339M,364M,545M       
2/24        430M,417M,694M       
2/25        1087M,938E,114M       

一直在刷只是跟新频率不高。近期：
2/26        46M
2/27        112E,47M,113M,208M,211M
2/28        
3/1        39M,366M,77M
3/2        733E,494M,40M
3/3        257E,216M,41H
3/4        1192H,254M
3/5        
3/6        95M,116M,117M,78M
3/7        108E,90M,489H
3/8        320M
3/9        784M,109M
3/10        106M,542M,130M
3/11        934M,1254M,314M
3/12        
3/13        679H.38M,987H
3/14        99H
3/15        1110M,104E,490M

3/16        198M
3/17        213M,337M,256M,257E
3/18        529M,1026M
3/19        690E,979M,827H,968H
3/20        1161M,103M,515M,513M,429M

3/21        865M,834H
3/22        55M,45M,1306M
3/23        62M,63M,64M,980H
3/24        1239M,36M,37H
3/25        11M
3/26        92M,22M

3/27        221M,206E,25H
3/28        843M,121E,122E
3/29        123H,309M

3/30        152M,53E
3/31        10H,853M
4/1        72H
4/2        813M,1335H,312H,410H
4/3        139M,140H,846M,1235H
4/4        704E

4/5        4H
4/6        1326H,1024M,45M,50M
4/7        69E,981M
4/8       
4/9        153M,154H
4/10        81M,33M,162M,315H
4/11        74M,240M,528M,142M
4/12        287M,169E
4/13        801M