认真刷题的打卡

每周设定周目标（会根据tag难度+已经刷了的数量定速度）

#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)
            
        

44. Wildcard Matching


class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        """
        j->     0   1   2   3   4   5   6
     i          ''  a   c   d   c   b   b 到s[j]为止可得的
               ---------------------------
     0          T   F   F   F   F   F   F
     1  p[0] a  F   T   F   F   F   F   F         
     2  p[1] *  [F] [T] []
     3  p[2] c  F   
     4  p[3] ?  F   
     5  p[4] b  F   
     
     
     =============================================
     if p[i-1] == '*':
        # take as '' or|| take this char as match 都行 || or 到此为止都要
        dp[i][j] = dp[i-1][j-1] or dp[i-i][j]
        
     elif p[i-1] == '?' or p[i-1]==s[j-1]:
        # match 看上个s p的match
        dp[i][j] == dp[i-1][j-1]

     else:
        dp[i][j] == False
  ======================================================      
        """

        #  初始化
        lens, lenp = len(s), len(p)
        dp = [[ True for j in range(lens+1) ] for i in range(lenp+1)]
        
        for j in range(1, lens+1):
            dp[0][j] = False
        
        for i in range(1, lenp+1):
            if p[i-1] == '*':
                dp[i][0] = dp[i-1][0]
            else:
                dp[i][0] = False
        
        
        for i in range(1, lenp+1):
            for j in range(1, lens+1):
                if p[i-1] == '*':
                    dp[i][j] = dp[i-1][j-1] or dp[i-1][j] or dp[i][j-1]
                elif p[i-1] == '?' or p[i-1] == s[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = False
        
        return dp[-1][-1]

323. Number of Connected Components in an Undirected Graph
class Solution(object):
    def countComponents(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: int
        """
        # union find
        """
            5
            [[0, 1], [1, 2], [3, 4],[2,4]]
        """
        
        root = [i for i in range(n)]
        
        def find(n):
            if root[n] == n:
                return n
            root[n] = find(root[n])
            return root[n]
        
        def union(a,b):
            pa = find(a)
            pb = find(b)
            if pa==pb:
                return True
            if pa<pb:
                root[pb] = pa
            else:
                root[pa] = pb
            return False
        
        for a,b in edges:
            union(a,b)

        m = set()   
        for i in range(n):
            m.add(find(i))
        return len(m)

这周刷Greedy 跟 Heap

周一：252,253,621  EMM   Greedy
周二：763,767,134   MMM   Greedy
周三：125,23    HE   

周四: 406,1616,238  MMM   Greedy

周五: 295   H   Heap
周六: 347,692,239   MMH   Heap

周日: 435,316,215   MMM   Greedy/Heap

cat110 发表于 2021-2-8 12:15
周日: 435,316,215   MMM   Greedy/Heap

本周18题

207. Course Schedule
# https://leetcode.com/problems/co ... for-cycle-detection

# 7# [[1,0],[1,2],[2,3],[3,0],[2,4],[4,5],[4,6],[5,6]]

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        
        # visited = 1, not visited = 0, visiting = -1
        status = [0 for i in range(numCourses)]
        
        edgedict = collections.defaultdict(list)
        for p, i in prerequisites:
            edgedict.append(p)
      
        ret = []
   
        def dfs(i):
            if status == 1:
                return
            if status == -1:
                return "cycle"
            status = -1
            for neibor in edgedict:
                if dfs(neibor) == "cycle":
                    return "cycle"
            status = 1
            ret.append(i)
        
        for i in range(numCourses):
            if dfs(i) == "cycle":
                return False
        ret.reverse()
        
        return True

332. Reconstruct Itinerary
# https://leetcode.com/problems/re ... uler-Path-Finding-O(E-log-E)-explained.

# [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]
class Solution:
   
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        self.ans = []
        self.edges = collections.defaultdict(list)
        
        for ticket in tickets:
            self.edges[ticket[0]].append(ticket[1])
        for key in self.edges:
            self.edges[key] = sorted(self.edges[key])
        #print(self.edges)
        def dfs(city):
            while self.edges[city]:
                nextcity = self.edges[city].pop(0)
                dfs(nextcity)
            # Important
            self.ans.append(city)
               
        dfs("JFK")
        
        return self.ans[::-1]