LeetCode算法题整理（图篇）Graph

Posted on 2019-02-10 | Updated on 2022-11-23 | In 算法 | | Visitors

990. Satisfiability of Equality Equations

满足所有方程式，判断是否存在变量的值满足所有的等式与不等式。原题

解析：所有的相等的点，在图中是联通的。

Input: ["a==b","b!=a"]
Output: false
Explanation: If we assign say, a = 1 and b = 1, then the first equation is satisfied, but not the second.  There is no way to assign the variables to satisfy both equations.

Input: ["a==b","b==c","a==c"]
Output: true

Input: ["a==b","b!=c","c==a"]
Output: false

方法一：set.

def equationsPossible(self, equations: 'List[str]') -> 'bool':
    equals = []
    equations.sort(key=operator.itemgetter(1), reverse=True)
    # print(equations)
    for x, e, _, y  in equations:
        if e == '=':
            for i, eq in enumerate(equals):
                if x in eq or y in eq:
                    equals[i].update({x, y})
                    break
            else:
                equals.append({x, y})
        else:
            if x == y:
                return False
            for eq in equals:
                if x in eq and y in eq:
                    return False
        # print(equals)
    return True

方法二：union find. 并查集。find方法可以想象成一个链表，返回的是链表末尾key,val相等的元素。同时建立连接关系。如a==b, b==c时fc={'a': 'b', 'b': 'c', 'c': 'c'}比较a!=c时就会最终找到fc['a'] == 'c'；如a==b, c==a时，fc={'a': 'b', 'b': 'b', 'c': 'b'}。

def equationsPossible(self, equations: 'List[str]') -> 'bool':
    equations.sort(key=lambda e: e[1] == '!')
    uf = {a: a for a in string.ascii_lowercase}

    def find(x):
        if x != uf[x]: 
            uf[x] = find(uf[x])
        return uf[x]

    for a, e, _, b in equations:
        if e == "=":
            uf[find(a)] = find(b)
        else:
            if find(a) == find(b):
                return False
    return True

997. Find the Town Judge

找到小镇审判长。审判长被除自己以外的所有人信任，并且不信任任何人。根据信任列表找出审判长。原题

Input: N = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
Output: 3
Input: N = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1
Input: N = 3, trust = [[1,3],[2,3]]
Output: 3

方法一：brute force.

def findJudge(self, N: int, trust: List[List[int]]) -> int:
    if not trust:
        return N
    a, b = zip(*trust)           
    candidates = collections.Counter(b)
    villages = set(a)
    for c, votes in candidates.most_common():
        if votes < N - 1:
            return -1
        if c not in villages:
            return c
    return -1

方法二：定向图。

def findJudge(self, N: int, trust: List[List[int]]) -> int:
    count = [0] * (N + 1)
    for i, j in trust:
        count[i] -= 1
        count[j] += 1
        print(count)
    for i in range(1, N + 1):
        if count[i] == N - 1:
            return i
    return -1

133. Clone Graph

深拷贝一个简单环。原题

def cloneGraph(self, node: 'Node') -> 'Node':
    cp = collections.defaultdict(lambda: Node(0, []))
    nodes = [node]
    seen = set()
    while nodes:
        n = nodes.pop()
        cp[n].val = n.val
        cp[n].neighbors = [cp[x] for x in n.neighbors]
        nodes.extend(x for x in n.neighbors if x not in seen)
        seen.add(n)
    return cp[node]

1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

找到距离范围内邻居最少的城市。原题

Input: n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
Output: 3
Explanation: The figure above describes the graph. 
The neighboring cities at a distanceThreshold = 4 for each city are:
City 0 -> [City 1, City 2] 
City 1 -> [City 0, City 2, City 3] 
City 2 -> [City 0, City 1, City 3] 
City 3 -> [City 1, City 2] 
Cities 0 and 3 have 2 neighboring cities at a distanceThreshold = 4, but we have to return city 3 since it has the greatest number.

方法一：狄克斯特拉算法。这里没想到用一个堆来维持最小的距离。

def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
    g = collections.defaultdict(list)
    for u, v, w in edges:
        g[u].append((v, w))
        g[v].append((u, w))
        
    def count_neighbor(city):
        heap = [(0, city)]
        dist = {}
        
        while heap:
            cur_w, u = heapq.heappop(heap)
            if u in dist:
                continue
            if u != city:
                dist[u] = cur_w
            for v, w in g[u]:
                if v in dist:
                    continue
                if cur_w + w <= distanceThreshold:
                    heapq.heappush(heap, (cur_w+w, v))
        return len(dist)
    
    return min(range(n), key=lambda x: (count_neighbor(x), -x))

方法二：弗洛伊德算法，这个时间复杂度为O(N^3)，space: O(N^2)但是代码简单。把每个节点当成中转点k，如果dis[i][j] > dis[i][k] + dis[k][j]说明从k走，i, j距离更短。

def findTheCity(self, n: int, edges: List[List[int]], maxd: int) -> int:
    dis = [[float('inf')] * n for _ in range(n)]
    for i, j, w in edges:
        dis[i][j] = dis[j][i] = w
    for i in range(n):
        dis[i][i] = 0
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j])
    ans = {sum(d<=maxd for d in dis[i]): i for i in range(n)}  # 这里id大的会将小的覆盖
    return ans[min(ans)]

1267. Count Servers that Communicate

找到2个以上的服务器连接个数，服务器可以在一行或是一列算是连接上。原题

1
2
3

Input: grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
Output: 4
Explanation: The two servers in the first row can communicate with each other. The two servers in the third column can communicate with each other. The server at right bottom corner can't communicate with any other server.

方法一：和小岛问题不同，这个服务器可以隔空连接，AC时用的dfs方法，效率非常慢。实际上只需要记录横纵左边即可，遍历两次

def countServers(self, g: List[List[int]]) -> int:
    X, Y = [0]*300, [0]*300
    m, n = len(g), len(g[0])
    for i in range(m):
        for j in range(n):
            X[i] += g[i][j]
            Y[j] += g[i][j]
    ans = 0
    for i in range(m):
        for j in range(n):
            if g[i][j]==1 and (X[i]>1 or Y[j]>1):
                ans += 1
    return ans

方法二：行列累计求和，但是只是用来判断而不是累加，然后遍历所有的元素。

1
2
3

def countServers(self, g: List[List[int]]) -> int:
    X, Y = tuple(map(sum, g)), tuple(map(sum, zip(*g)))
    return sum(X[i]+Y[j]>2 for i in range(len(g)) for j in range(len(g[0])) if g[i][j])

886. Possible Bipartition

将不喜欢的人放在两组中，根据关系是否能将其分为2组。原题

Input: N = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: group1 [1,4], group2 [2,3]

Input: N = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false

方法一：dfs。此题想了半个多点才想明白，等同于在一个无向图中，寻找一个奇数边的环。

def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
    g = [[] for _ in range(N+1)]
    for a, b in dislikes:
        g[a].append(b)
        g[b].append(a)

    seen = set()
    def dfs(i, p, p_len):
        seen.add(i)
        p[i] = p_len
        for nxt in g[i]:
            if nxt not in seen:
                if dfs(nxt, p, p_len+1):
                    return True
            elif nxt in p and (p_len-p[nxt])&1==0:
                return True
        p.pop(i)
        return False

    p = {}
    for i in range(1, N+1):
        if i not in seen and dfs(i, p, 0):
            return False
    return True

方法二：染色思想。0代表红色，1代表蓝色，每次将其不喜欢的人染成另一种颜色。这个代码比较简洁，不过稍微慢了一丢丢，50ms左右。

def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
    g = [[] for _ in range(N+1)]
    for a, b in dislikes:
        g[a].append(b)
        g[b].append(a)
    
    color = {}
    def dfs(i, c=0):
        if i in color:
            return color[i]==c
        color[i] = c
        return all(dfs(j, c^1) for j in g[i])
    
    return all(dfs(i) for i in range(1, N+1) 
               if i not in color)

207. Course Schedule

课程调度，课程有依赖关系，问是否能完成所有的课程。原题

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.

方法一：dfs。注意这里状态要用3中，1表示遍历过，-1表示正在遍历，0表未遍历。这样可以避免重复的遍历。

def canFinish(self, n: int, prerequisites: List[List[int]]) -> bool:
    g = [[] for _ in range(n)]
    for a, b in prerequisites:
        g[a].append(b)
        
    seen = [0] * n
    
    def dfs(i):
        if seen[i] in {1, -1}: return seen[i]==1
        seen[i] = -1
        if any(not dfs(j) for j in g[i]): return False
        seen[i] = 1
        return True

方法二：这个方法优雅一点，来自Lee215. BFS Topological Sorting.

def canFinish(self, n: int, prerequisites: List[List[int]]) -> bool:
    g = collections.defaultdict(list)
    degree = [0] * n
    for u, v in prerequisites:
        g[v].append(u)
        degree[u] -= 1
    bfs = [i for i in range(n) if degree[i]==0]    
    for i in bfs:
        for j in g[i]:
            degree[j] += 1
            if degree[j] == 0:
                bfs.append(j)
    return len(bfs)==n

1462. Course Schedule IV

和上题差不多，问题不一样，问的是根据给定的依赖关系，判断两节课是否有依赖。原题

方法一：dfs. 这个方法想了超出比赛时间限制了。但是也没过多久就优化出来了。

def checkIfPrerequisite(self, n: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
    g = [[] for _ in range(n)]
    q = [set() for _ in range(n)]         
    for u, v in prerequisites:
        g[u].append(v)

    def dfs(i):
        if q[i]:
            return q[i]
        q[i].update(g[i])
        for j in g[i]:
            q[i].update(dfs(j))
        return q[i]

    for i in range(n):
        dfs(i)
    return [b in q[a] for a, b in queries]

方法二：弗洛伊德算法，和求城市最小距离一样。时间复杂度是O(n3)

def checkIfPrerequisite(self, n: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
    g = [[False]*n for _ in range(n)]
    for u, v in prerequisites:
        g[u][v] = True
        
    for k in range(n):
        for i in range(n):
            for j in range(n):
                g[i][j] = g[i][j] or (g[i][k] and g[k][j])
    return [g[i][j] for i, j in queries]

方法三：bfs. 拓扑排序。

def checkIfPrerequisite(self, n: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
    g = collections.defaultdict(list)
    degree = [0] * n
    pres = [set() for _ in range(n)]
    for u, v in prerequisites:
        g[u].append(v)
        degree[v] -= 1
        pres[v].add(u)
    bfs = [i for i in range(n) if degree[i]==0]
    for i in bfs:
        for j in g[i]:
            degree[j] += 1
            pres[j] |= pres[i]
            if degree[j] == 0:
                bfs.append(j)
    return [a in pres[b] for a, b in queries]

1466. Reorder Routes to Make All Paths Lead to the City Zero

有一个有向图，两个节点之间只有一条边，要求所有的边指向0，需要改多少条边的方向。原题

1
2
3

Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

方法一：此题竞赛时未作出。一个效率不是很高的方法。用父节点去重。set记录原始顺序，遍历无向图。

def minReorder(self, n: int, connections: List[List[int]]) -> int:
    self.ans = 0
    g = collections.defaultdict(list)
    roads = set()
    for u, v in connections:
        g[u].append(v)
        g[v].append(u)
        roads.add((u, v))
    
    def dfs(i, parent):
        self.ans += (parent, i) in roads
        for j in g[i]:
            if j == parent:
                continue
            dfs(j, i)
    
    dfs(0, -1)
    return self.ans

方法二：比赛时想的思路，dfs内容未想出来。

def minReorder(self, n: int, connections: List[List[int]]) -> int:
    g1 = collections.defaultdict(list)
    g2 = collections.defaultdict(list)
    for u, v in connections:
        g1[u].append(v)
        g2[v].append(u)
    
    seen = set()
    def dfs(i):
        seen.add(i)
        ans = 0
        for j in g1[i]:
            if j not in seen:
                ans += 1 + dfs(j)
                
        for k in g2[i]:
            if k not in seen:
                ans += dfs(k)
                
        return ans
    return dfs(0)

1210. Minimum Moves to Reach Target with Rotations

一个占位2格的蛇，从左上走到右下需要最少的步数，可以旋转。原题

Input: grid = [[0,0,0,0,0,1],
               [1,1,0,0,1,0],
               [0,0,0,0,1,1],
               [0,0,1,0,1,0],
               [0,1,1,0,0,0],
               [0,1,1,0,0,0]]
Output: 11
Explanation:
One possible solution is [right, right, rotate clockwise, right, down, down, down, down, rotate counterclockwise, right, down].

方法一：这题没想到在写完还有10分钟，其实思路很简单，就是拿两个点当成一个点。一个点的bfs就很容易了。

def minimumMoves(self, g: List[List[int]]) -> int:
    n = len(g)
    q = collections.deque([((0, 0), (0, 1), 0)])
    seen = set(((0, 0), (0, 1)))
    while q:
        tail, head, step = q.popleft()
        if tail[0] == head[0] == head[1] == n-1 and tail[1]==n-2:
            return step
        if tail[0] == head[0] and tail[0]!=n-1: # horizontal
            d_tail, d_head = (tail[0]+1, tail[1]), (head[0]+1, head[1])
            if g[d_tail[0]][d_tail[1]] == g[d_head[0]][d_head[1]] == 0:
                if (tail, d_tail) not in seen:
                    q.append((tail, d_tail, step+1))
                    seen.add((tail, d_tail))
        if tail[1] == head[1] and tail[1]!=n-1: # vertical
            r_tail, r_head = (tail[0], tail[1]+1), (head[0], head[1]+1)
            if g[r_tail[0]][r_tail[1]] == g[r_head[0]][r_head[1]] == 0:
                if (tail, r_tail) not in seen:
                    q.append((tail, r_tail, step+1))
                    seen.add((tail, r_tail))
        if head[1] != n-1:
            r_head = head[0], head[1]+1
            r_tail = tail[0], tail[1]+1
            if g[r_head[0]][r_head[1]] == g[r_tail[0]][r_tail[1]] == 0:
                if (r_tail, r_head) not in seen:
                    q.append((r_tail, r_head, step+1))                    
                    seen.add((r_tail, r_head))
        if head[0] != n-1:
            d_head = head[0]+1, head[1]
            d_tail = tail[0]+1, tail[1]
            if g[d_head[0]][d_head[1]] == g[d_tail[0]][d_tail[1]] == 0:
                if (d_tail, d_head) not in seen:
                    q.append((d_tail, d_head, step+1))
                    seen.add((d_tail, d_head))
        
    return -1

方法二：另一种思路将蛇的横竖状态记录，这样一个点也能表示。

def minimumMoves(self, g: List[List[int]]) -> int:
    n = len(g)
    q, seen, target = [(0, 0, 0, 0)], set(), (n-1, n-2, 0)
    for r, c, dr, step in q:
        if (r, c, dr) == target: return step
        if (r, c, dr) not in seen:
            seen.add((r, c, dr))
            if dr:
                if c+1<n and g[r][c+1]==g[r+1][c+1]==0:
                    q += [(r, c+1, 1, step+1), (r, c, 0, step+1)]
                if r+2<n and g[r+2][c]==0:
                    q += [(r+1, c, 1, step+1)]
            else:
                if r+1<n and g[r+1][c]==g[r+1][c+1]==0:
                    q += [(r+1, c, 0, step+1), (r, c, 1, step+1)]
                if c+2<n and g[r][c+2]==0:
                    q += [(r, c+1, 0, step+1)]
    return -1

1202. Smallest String With Swaps

给定一组pairs表明索引对可以互换，求这个字符串能换的最小值时多少，同一对可以进行多次互换。原题

Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"
Explaination: 
Swap s[0] and s[3], s = "bcad"
Swap s[1] and s[2], s = "bacd"

方法一：看了几个例子想一想就明白了，实际上是一道连通器的题，将连通的索引单独排序就是最小的值。

竞赛时ac的方法用的是dfs. 内存用的有点多。

def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
    g = [[] for _ in range(len(s))]
    ans = [''] * len(s)
    for a, b in pairs:
        g[a].append(b)
        g[b].append(a)
    
    seen = [False] * len(s)
    def dfs(i, p):
        if not seen[i]:
            seen[i] = True
            p.append(i)
            for j in g[i]:
                dfs(j, p)
            return p
    
    groups = []
    for i in range(len(s)):
        tmp = dfs(i, [])
        if tmp:
            groups.append(tmp)
    for idx in groups:
        letters = iter(sorted(s[i] for i in idx))
        for i in sorted(idx):
            ans[i] = next(letters)
    return ''.join(ans)

方法二：做了一点优化。

def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
    g = [[] for _ in range(len(s))]
    ans = [''] * len(s)
    for a, b in pairs:
        g[a].append(b)
        g[b].append(a)
    
    seen = [False] * len(s)
    def dfs(i):
        seen[i] = True
        p.append(i)
        for j in g[i]:
            if not seen[j]:
                dfs(j)
    
    for i in range(len(s)):
        p = []
        if not seen[i]:
            dfs(i)
        letters = iter(sorted(s[i] for i in p))
        for i in sorted(p):
            ans[i] = next(letters)
    return ''.join(ans)

方法三：union-find。这个评论区里看到的方法写得很标准。

def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
    class UF:
        def __init__(self, n):
            self.p = list(range(n))
        def union(self, x, y):
            self.p[self.find(x)] = self.find(y)
        def find(self, x):
            if x!=self.p[x]:
                self.p[x] = self.find(self.p[x])
            return self.p[x]
    uf, res, m = UF(len(s)), [], defaultdict(list)
    for x, y in pairs:
        uf.union(x, y)
    for i in range(len(s)):
        m[uf.find(i)].append(s[i])
    for comp_id in m.keys(): 
        m[comp_id].sort(reverse=True)
    for i in range(len(s)): 
        res.append(m[uf.find(i)].pop())
    return ''.join(res)

方法四：我自己的Union-Find。

def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
    N = len(s)
    res = [''] * N

    def union(x, y):
        uf[find(x)] = find(y)

    def find(x):
        if uf[x] != x:
            uf[x] = find(uf[x])
        return uf[x]

    uf = list(range(N))

    for u, v in pairs:
        union(u, v)

    g = defaultdict(list)
    for i in range(N):
        g[find(i)].append(i)

    for indexes in g.values():
        for i, c in zip(sorted(indexes), sorted(map(s.__getitem__, indexes))):
            res[i] = c
    return ''.join(res)

787. Cheapest Flights Within K Stops

经过K个站点的最便宜的航班。原题

方法一：狄克斯特拉算法，只不过多了一个条件，经过K个站点。不需要用seen记录已经去过的点，因为该点可能有更少步数的到达方式。

def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
    g = collections.defaultdict(list)
    for u, v, w in flights:
        g[u].append((v, w))
    
    q = [(0, src, 0)]
    heapq.heapify(q)
    while q:
        p, city, step = heapq.heappop(q)
        if city == dst:
            return p
        for v, w in g[city]:
            if step < K+1:
                heapq.heappush(q, (p+w, v, step+1))
    return -1

332. Reconstruct Itinerary

重建行程，根据火车票来寻找行程，答案不唯一。原题

1 2	Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]] Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]

方法一：首次ac的方法，直接修改g。

def findItinerary(self, tickets: List[List[str]]) -> List[str]:
    g = collections.defaultdict(list)
    for u, v in tickets:
        g[u].append(v)
    for u in g.keys():
        g[u].sort()
    
    def dfs(city, p):  
        # print(city, p, g)
        p.append(city)
        if not g:
            return p
        org = g[city]
        for i, nxt in enumerate(g[city]):
            g[city] = g[city][:i] + g[city][i+1:]
            if not g[city]:
                del g[city]
            if dfs(nxt, p):
                return p
            g[city] = org
        if not org:
            del g[city]
        p.pop()
    return dfs('JFK', [])

方法二：用两个倒序可以解决

def findItinerary(self, tickets: List[List[str]]) -> List[str]:
    g = collections.defaultdict(list)
    for u, v in sorted(tickets, reverse=True):
        g[u].append(v)
        
    ans = []
    def dfs(city):
        while g[city]:
            dfs(g[city].pop())
        ans.append(city)
        
    dfs('JFK')
    return ans[::-1]

1519. Number of Nodes in the Sub-Tree With the Same Label

有一个数的图，每个节点有个字母，返回每个节点的子树中包含这个字母的总个数。原题

方法一：这个题作为竞赛的第二题是在是太恶心了，结束后我想了很长时间才想出来。dfs + counter, 每个节点都有它独立的一个counter。因为字母不同、

def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:
    g = collections.defaultdict(list)
    for u, v in edges:
        g[u].append(v)
        g[v].append(u)

    seen = [False] * n
    c = Counter()
    def dfs(node):
        cur = Counter()
        seen[node] = True
        for nxt in g[node]:
            if not seen[nxt]:
                cur += dfs(nxt)
        label = labels[node]
        cur[label] += 1
        ans[node] = cur[label]
        return cur
        
    ans = [0] * n
    dfs(0)
    return ans

方法二：优化方法一

def countSubTrees(self, n: int, edges: List[List[int]], labels: str) -> List[int]:
    g = collections.defaultdict(list)
    for u, v in edges:
        g[u].append(v)
        g[v].append(u)

    def dfs(node, p):
        cur = Counter(labels[node])
        for nxt in g[node]:
            if nxt != p:
                cur += dfs(nxt, node)
        ans[node] = cur[labels[node]]
        return cur
        
    ans = [0] * n
    dfs(0, -1)
    return ans

478. Generate Random Point in a Circle

在给定圆的范围内随机生成点。原题

方法一：严格来说这是一道几何题，为什么要将其开方，因为如果没有开方，对于一个圆来说，半径越小的地方点就越密集，因为在该周长上所有的点分布是一样的。开方可以让半径小的点降低分布。

class Solution:

    def __init__(self, radius: float, x_center: float, y_center: float):
        self.r = radius
        self.x = x_center
        self.y = y_center

    def randPoint(self) -> List[float]:
        import random
        edge = math.sqrt(random.random()) * self.r
        deg = random.random()*2*math.pi
        x = self.x + edge*math.cos(deg)
        y = self.y + edge*math.sin(deg)
        return x, y

1559. Detect Cycles in 2D Grid

2D 矩阵中判断是否有环。原题

方法一：这个题就差一点没想出来，就是怎么避免重复的路径，那就是需要和前一个点比对。看了这个提示后瞬间就完成了。时间空间待优化。

def containsCycle(self, g: List[List[str]]) -> bool:
    m, n = len(g), len(g[0])
    
    visited = [[False] * n for _ in range(m)]
    
    def spread(x, y, c, a, b):
        if visited[x][y]:
            return True
        visited[x][y] = True
        for i, j in ((x-1, y), (x+1, y), (x, y-1), (x, y+1)):
            if 0<=i<m and 0<=j<n and c==g[i][j] and (i, j)!=(a, b):
                if spread(i, j, c, x, y):
                    return True
        return False
    
    for i in range(m):
        for j in range(n):
            if not visited[i][j] and spread(i, j, g[i][j], i, j):
                return True
    return False

310. Minimum Height Trees

有一个无向图，0~n-1这些节点，每两个节点只有一条边，找出这种节点，当以节点为根时，组成的树有最小的高度。原题

Input: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

     0  1  2
      \ | /
        3
        |
        4
        |
        5 

Output: [3, 4]

方法一：这个解法很棒，评论区的解法，以前看这种题的时候，想到的是bfs，这个解法的核心思想是剪枝。每次将叶子节点剪去。最后剩下的一个或者2个节点就是最小高度的根节点。

def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
    if n == 1: return [0]
    g = collections.defaultdict(set)
    for u, v in edges:
        g[u].add(v)
        g[v].add(u)
        
    leaves = [i for i in range(n) if len(g[i])==1]
    while n > 2:
        n -= len(leaves)
        new_leaves = []
        for i in leaves:
            j = g[i].pop()
            g[j].remove(i)
            if len(g[j])==1: new_leaves.append(j)
        leaves = new_leaves
    return leaves

127. Word Ladder

每次可以改变单词中的一个字母，但必须在wordList中，问最少需要多少次能达到目标单词。原题

Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

方法一：BFS很好想，但是要想如何去重，wordList可能非常大，所以不能遍历，因为只有26个字母可以变，所以可以变换完比较。

def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
    q = [(beginWord, 1)]
    words_set = set(wordList)
    letters = string.ascii_lowercase
    for w, step in q:
        if w == endWord: return step
        for i in range(len(w)):
            for c in letters:
                nw = w[:i] + c + w[i+1:]
                if nw in words_set:
                    q.append((nw, step+1))
                    words_set.remove(nw)
    return 0

547. Friend Circles

朋友圈，一堆人拉帮结伙，朋友关系可以传递。通过二维数组表示i, j两个人是否是朋友。问N个人有多少个帮派。原题

Input: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
Output: 2
Explanation:The 0th and 1st students are direct friends, so they are in a friend circle. 
The 2nd student himself is in a friend circle. So return 2.

方法一：典型的Union-Find。最后结果还要遍历一下，才是最终结果。[[1,0,0,1],[0,1,1,0],[0,1,1,1],[1,0,1,1]]这个case在union之后，是[3,2,3,3]因为2的朋友在1计算之后变成了3。最终点更新了。所以遍历之后是[3,3,3,3]

def findCircleNum(self, M: List[List[int]]) -> int:
    
    def union(x, y):
        uf[find(x)] = find(y)
        
    def find(x):
        if x != uf[x]:
            uf[x] = find(uf[x])
        return uf[x] 
    
    N = len(M)
    uf = list(range(N))
    for i in range(N):
        for j in range(N):
            if M[i][j]:
                union(i, j)
                
    return len({find(i) for i in range(N)})

方法二：评论中有个dfs 也不错，行列循环分开了。

def findCircleNum(self, M: List[List[int]]) -> int:
    ans, N = 0, len(M)
    seen = set()
    
    def dfs(i):
        for j, r in enumerate(M[i]):
            if r and j not in seen:
                seen.add(j)
                dfs(j)
                
    for i in range(N):
        if i not in seen:
            ans += 1
            dfs(i)
            
    return ans

方法三：stefan的科学库和numpy写法。

import scipy.sparse

class Solution(object):
    def findCircleNum(self, M):
        return scipy.sparse.csgraph.connected_components(M)[0]
        
import numpy as np

class Solution(object):
    def findCircleNum(self, M):
        return len(set(map(tuple, (np.matrix(M, dtype='bool')**len(M)).A)))

1584. Min Cost to Connect All Points

所有点最小的曼哈顿距离|xi - xj| + |yi - yj|和为多少。原题

方法一：贪心法。这题有很多方法，然而比赛时一种也没写出来。首先贪心可以，由于是n^2的复杂度，所以没有敢写。

毕竟n=1000。评论区的做法，为什么贪心可行，想象一下，最后所有的点相连，每2点只有一条边，而且是最小的边。

def minCostConnectPoints(self, points: List[List[int]]) -> int:
    n, ans = len(points), 0
    seen = set()
    dis = [float('inf')] * n
    cur = 0
    # n-1 edges
    for i in range(n-1):
        x, y = points[cur]
        seen.add(cur)
        for j, (nx, ny) in enumerate(points):
            if j in seen: continue
            dis[j] = min(dis[j], abs(nx-x)+abs(ny-y))
        s, cur = min((d, j) for j, d in enumerate(dis))
        dis[cur] = float('inf')
        ans += s
        
    return ans

方法二：最小生成树。这是经典的最小生成树问题，有两种实现的方式，一种是Prim算法。一种是Kruskal算法。比贪心法慢了400ms，花费1580ms，还以为是我实现的问题，结果看评论区中的要2s多。空间则是贪心的5倍多。因为此题需要找到各个边的权重，所以即使是Prim算法，时间复杂度也是O(n^2)。Prim算法是每次以新的顶点找到最小的权重边。

def minCostConnectPoints(self, p: List[List[int]]) -> int:

    def manhattan(x, y):
        return abs(x[0]-y[0]) + abs(x[1]-y[1])

    ans, n = 0, len(p)
    seen = set()
    vertices = [(0, (0, 0))]

    while len(seen) < n:
        # print(vertices, seen)
        w, (u, v) = heapq.heappop(vertices)            
        if v in seen: continue
        ans += w
        seen.add(v)
        for j in range(n):
            if j not in seen and j!=v:
                heapq.heappush(vertices, (manhattan(p[j], p[v]), (v, j)))

    return ans

方法三：Kruskal，克鲁斯卡尔算法。原理是Union-Find。按照所有的权重看，每次产生一条边，但不一定和已有的边构成环。理论上来说比Prim算法要慢。实际运行却比prim快了1、200ms。

def minCostConnectPoints(self, p: List[List[int]]) -> int:
    edges, n, cnt, ans = [], len(p), 1, 0

    def manhattan(x, y):
        return abs(p[x][0]-p[y][0]) + abs(p[x][1]-p[y][1])

    edges = [(manhattan(i, j), (i, j)) 
             for i in range(n) for j in range(i+1, n)]
    heapq.heapify(edges)

    def union(x, y):
        uf[find(x)] = find(y)

    def find(x):
        if x != uf[x]:
            uf[x] = find(uf[x])
        return uf[x]

    uf = list(range(n))
    while cnt < n:
        d, (u, v) = heapq.heappop(edges)
        if find(u) != find(v):
            ans += d
            cnt += 1
            union(u, v)
    return ans

684. Redundant Connection

多余的边，有一个无向图有N个节点，和N个边，对于一个连通器来说，刚好多了一条边。找到这条多余的边，所有的边给的[u, v]均满足u<v。原题

Input: [[1,2], [1,3], [2,3]]
Output: [2,3]
Explanation: The given undirected graph will be like this:
  1
 / \
2 - 3

方法一：使用传统的Union-Find。

def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
    
    def union(x, y):
        uf[find(x)] = find(y)
        
    def find(x):
        if x != uf[x]:
            uf[x] = find(uf[x])
        return uf[x]
    
    n = len(edges)
    uf = list(range(n+1))
    for u, v in edges:
        if find(u)==find(v):
            return u, v
        union(u, v)

方法二：stefan. 考虑没用上的条件 u<v。可以利用字符串的replace。将所有出现的点，替换成最大的。

def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
    tree = ''.join(map(chr, range(1001)))
    for u, v in edges:
        if tree[u] == tree[v]:
            return u, v
        tree = tree.replace(tree[u], tree[v])

685. Redundant Connection II

同684一样，区别在于有向图，也是多出一条边，但这条边是最后一条无用的边。也就是说。删除这条边后，还是一个N个节点的有向图。并且图中只能有一个根节点。

方法一：花了不到2小时做出来，感觉方法很笨。因为有这样的例子，[[2,1],[3,1],[4,2],[1,4]]这时不能删除[1,4]，而是要删除[2,1]因为4和3会成为2个根节点。如果我们找到了一个点有两个父节点，那么删除的一定是这两条边中的一条。所以此时我没有将其加入到联通图中；另一种情况，没有两个父节点的点时，就像684一样判断是否联通就好了，最后判断，如果所有节点都联通了，我删除第2次遇见的相同父节点的边就行了，如果没有，那么应该删除第一次的边，这里用了一个pare来记录关系。

def findRedundantDirectedConnection(self, edges: List[List[int]]) -> List[int]:

    def union(x, y):
        uf[find(x)] = find(y)

    def find(x):
        if x != uf[x]:
            uf[x] = find(uf[x])
        return uf[x]
      
    ans, N, pare = None, len(edges), {}
    uf = list(range(N+1))
    for u, v in edges:
        if v in pare:
            ans = (u, v)
            continue
        if find(u)==find(v) and not ans:
            ans = (u, v)
        union(u, v)
        pare[v] = u
    return ans if len(set(map(find, range(1, N+1))))==1 else (pare[ans[1]], ans[1])

743. Network Delay Time

网络延迟，有N个网络节点，给出一个加权有向图，问从K点出发，遍历所有点需要多少时间，如果不可能返回-1。原题

1 2	Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2 Output: 2

方法一：bfs。首次AC，960ms。效率不算很高吧，因为可能遍历到重复的节点更新值。

def networkDelayTime(self, times, N, K):
    seen, ans = {}, 0
    g = collections.defaultdict(list)
    for u, v , w in times:
        g[u].append((v, w))
    q = collections.deque([(K, 0)])
    while q:
        u, t = q.popleft()
        seen[u] = min(seen.get(u, float('inf')), t)
        for v, nt in g[u]:
            if v not in seen or seen[v]>nt+t:
                q.append((v, t+nt))
    return max(seen.values()) if len(seen)==N else -1

方法二：堆实现了一个优先级队列，500ms左右。

def networkDelayTime(self, times, N, K):
    seen, t = set(), 0
    g = collections.defaultdict(list)
    for u, v , w in times:
        g[u].append((v, w))
    heap = [(0, K)]
    while heap:
        t, u = heapq.heappop(heap)
        if u in seen: continue
        seen.add(u)
        if len(seen) == N: break
        for v, nt in g[u]:
            heapq.heappush(heap, (t+nt, v))
    return t if len(seen)==N else -1

721. Accounts Merge

账号合并，一个人可能有多个账号，将具有相同账号的人合并到一起，返回所有的用户的所有的账号

方法一：做的时候想到了union-find，不过以开始的思路用集合暴力也解出来了。只要有一个账号相同，就是一个人。

def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
    users = collections.defaultdict(list)
    for name, *mails in accounts:
        old_mails = users[name]
        mails = set(mails)
        to_rm = []
        n = len(old_mails)
        j = n - 1
        while j >= 0:
            if old_mails[j] & mails:
                mails |= old_mails[j]
                old_mails.pop(j)
            j -= 1
        old_mails.append(mails)
    return [[name] + sorted(act_lst) 
            for name, acts in users.items() for act_lst in acts]

方法二：dfs，需要遍历两次。先记录一下每个邮箱出现的索引，

def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
    mail_occurs = collections.defaultdict(list)
    ans = []
    for i, (_, *mails) in enumerate(accounts):
        for mail in mails:
            mail_occurs[mail].append(i)
    visited = [False] * len(accounts)
    
    def dfs(i, mails):
        if visited[i]: return             
        visited[i] = True
        for other in accounts[i][1:]:
            mails.add(other)
            for j in mail_occurs[other]:
                dfs(j, mails)
    
    for i, (name, *mails) in enumerate(accounts):
        if visited[i]: continue
        acts = set()
        dfs(i, acts)
        ans.append([name] + sorted(acts))
    return ans

方法三：Union-FInd，这里要选出一个标准，不如每个首个出现的账号，将其它账号连到这个账号上。第二步需要遍历一遍，把相同的账号放到一个列表中，遍历过程中记录账号对应的姓名，方便我们构建最终的答案。

def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
    uf = {}
    mail_to_name = {}
    
    def union(x, y):
        uf.setdefault(x, x)
        uf.setdefault(y, y)
        uf[find(x)] = find(y)
        
    def find(x):
        if x != uf[x]:
            uf[x] = find(uf[x])
        return uf[x]
    
    for name, *mails in accounts:
        first = mails[0]
        for mail in mails:
            union(mail, first)
            mail_to_name[mail] = name
        
    g = collections.defaultdict(list)
    for mail in uf.keys():
        g[find(mail)].append(mail)
        
    return [[mail_to_name[first]] + sorted(mails) for first, mails in g.items()]

面试题 17.07. 婴儿名字

找到相同名字的数量，和721一样，也是合并婴儿。names中可能包含synonyms中没有的，synonyms中也可能包含names没有的。

1 2	输入：names = ["John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"], synonyms = ["(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"] 输出：["John(27)","Chris(36)"]

方法一：Union-Find。改进，这里修改了union方法，将较小的直接作为索引键。因为后续也不需要再使用了。360ms, 35M.

class Solution:
def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:
    # RE_NAME_CNT = re.compile(r'\w+|\d+')
    # RE_SAME_NAME = re.compile(r'\w+')

    def union(x, y):
        uf.setdefault(x, x)
        uf.setdefault(y, y)
        ax, ay = find(x), find(y)
        if ax < ay: ay, ax = ax, ay
        uf[ax] = ay

    def find(x):
        if x != uf[x]:
            uf[x] = find(uf[x])
        return uf[x]

    uf, cnt = {}, {}
    for person in names:
        # name, c = re.findall(RE_NAME_CNT, person)
        # name, c = re.match(r'(\w+)\((\d+)\)', person).groups()
        name, c = person.strip(')').split('(')
        uf.setdefault(name, name)
        cnt[name] = int(c)

    for con in synonyms:
        # n1, n2 = re.findall(RE_SAME_NAME, con)
        # n1, n2 = re.match(r'\((\w+),(\w+)\)', con).groups()
        n1, n2 = con.strip('()').split(',')
        union(n1, n2)

    total = collections.defaultdict(int)
    for name, c in cnt.items():
        total[find(name)] += c

    return [f'{p}({t})' for p, t in total.items()]

方法二：dfs 方法。cnt 不能使用defaultdict，因为循环cnt的时候会发生改变报错。因为会存在cnt中没有的key，也就是说不在names中的名字。448ms, 40M.

def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:
    cnt, seen, g = {}, defaultdict(int), defaultdict(list)
    for person in names:
        name, c = person.strip(')').split('(')
        cnt[name] = int(c)
    for con in synonyms:
        n1, n2 = con.strip('()').split(',')
        g[n1].append(n2)
        g[n2].append(n1)

    def dfs(n):
        seen[n], min_name = 1, n
        total = cnt.get(n, 0)
        for other in g[n]:
            if not seen[other]:
                p, s = dfs(other)
                total += s
                min_name = min(min_name, p)
        return min_name, total

    ans = []
    for name in cnt:
        if seen[name]: continue
        n, s = dfs(name)
        ans.append('{}({})'.format(n, s))
    return ans

方法三：评论区大神的写法。292ms, 17M，比我的快了好多。它这里的p比我的g要节省空间和时间，我试了更改方法二的这里平均快了40ms和10M的内存。

def trulyMostPopular(self, names: List[str], synonyms: List[str]) -> List[str]:
    p, d, q = {}, {}, collections.defaultdict(int)
    for s in synonyms:
        a, b = s.strip('()').split(',')
        pa, pb = p.setdefault(a, [a]), p.setdefault(b, [b])
        pa.extend(pb)
        for c in pb:
            p[c] = pa

    for name in p:
        d.setdefault(id(p[name]), min(p[name]))
    for s in names:
        name, count = s.strip(')').split('(')
        q[name in p and d[id(p[name])] or name] += int(count)
    return [f'{name}({count})' for name, count in q.items()]

851. Loud and Rich

啰里啰嗦一大堆，就是找到比当前人有钱的所有人中最低调的一个，quiet值最小，quiet没有重复值。

Input: richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
Output: [5,5,2,5,4,5,6,7]
Explanation: 
answer[0] = 5.
Person 5 has more money than 3, which has more money than 1, which has more money than 0.
The only person who is quieter (has lower quiet[x]) is person 7, but
it isn't clear if they have more money than person 0.

方法一：dfs. 首次AC，算比较简单。

def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
    N = len(quiet)
    rich = collections.defaultdict(list)
    for a, b in richer:
        rich[b].append(a)
    q_to_p = {q: i for i, q in enumerate(quiet)}

    @lru_cache(None)
    def dfs(i):
        q = quiet[i]
        for j in rich[i]:
            q = min(q, dfs(j))
        return q

    return [q_to_p[dfs(i)] for i in range(N)]

方法二：Lee的方法，比方法一节省一些空间。

def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
    N = len(quiet)
    rich = collections.defaultdict(list)
    for a, b in richer:
        rich[b].append(a)
    ans = [-1] * N

    def dfs(i):
        if ans[i] >= 0: return ans[i]
        ans[i] = i
        for j in rich[i]:
            if quiet[dfs(j)] < quiet[ans[i]]:
                ans[i] = dfs(j)
        return ans[i]

    for i in range(N):
        dfs(i) 
    return ans

399. Evaluate Division

通过已知的除法，计算带有这些变量的除法。

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation: 
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]

方法一：DFS。这题一开始想的是Union-Find方法，但是实现起来发现有点麻烦。需要注意一个问题，在遍历后未找到目标值时，需要添加-1。

def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
    g = defaultdict(list)  
    for (u, v), w in zip(equations, values):
        g[u].append((v, w))
        g[v].append((u, 1/w))
    
    def dfs(i, t, p=1):
        if i == t:
            ans.append(p)
        seen.add(i)
        for j, w in g[i]:
            if j not in seen:
                dfs(j, t, p*w)
    
    ans, seen = [], set()
    for i, (a, b) in enumerate(queries):
        if g[a] and g[b]:
            dfs(a, b)
            if i == len(ans):
                ans.append(-1)
            seen.clear()
        else:
            ans.append(-1)
    return ans

方法二：BFS方法也很优雅。

def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
    g = defaultdict(list)
    for (u, v), w in zip(equations, values):
        g[u].append((v, w))
        g[v].append((u, 1/w))
    
    def bfs(s, e):
        if not g[s] or not g[e]: return -1
        q, seen = [(s, 1)], set()
        for cur, p in q:
            if cur == e: return p
            seen.add(cur)
            for nei, np in g[cur]:
                if nei not in seen:
                    q.append((nei, p*np))
        return -1
    return (bfs(s, e) for s, e in queries)

方法三：Union-Find，自己想了个七八，也是用tuple返回一个比率，最后写着写着给自己绕蒙了，实现起来还是没有另两个方法简单。union方法其实融合了两个功能。然后就是将ratio添加到模板方法中。

def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
    uf = {}
    
    def find(x):
        p, xr = uf.setdefault(x, (x, 1.0))
        if x != p:
            r, pr = find(p)
            uf[x] = (r, xr * pr)
        return uf[x]
    
    def union(x, y, ratio):
        px, xr, py, yr = *find(x), *find(y)
        if not ratio:
            return xr / yr if px == py else -1.0
        if px != py:
            uf[px] = (py, yr/xr*ratio)

    for (u, v), w in zip(equations, values):
        union(u, v, w)
        
    return [union(x, y, 0) if x in root and y in root else -1.0 for x, y in queries]

方法四：Stefan的弗洛伊德算法。这个没有想到。

def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
    quot = collections.defaultdict(dict)
    for (num, den), val in zip(equations, values):
        quot[num][num] = quot[den][den] = 1
        quot[num][den] = val
        quot[den][num] = 1 / val
    for k, i, j in itertools.permutations(quot, 3):
        if k in quot[i] and j in quot[k]:
            quot[i][j] = quot[i][k] * quot[k][j]        
    return [quot[num].get(den, -1) for num, den in queries]

1617. Count Subtrees With Max Distance Between Cities

给你一颗树，求任意子树中节点最大距离1~n-1的分别有多少个。最多有15个节点。

输入：n = 4, edges = [[1,2],[2,3],[2,4]]
输出：[3,4,0]
解释：
子树 {1,2}, {2,3} 和 {2,4} 最大距离都是 1 。
子树 {1,2,3}, {1,2,4}, {2,3,4} 和 {1,2,3,4} 最大距离都为 2 。
不存在城市间最大距离为 3 的子树

方法一：比赛时没有时间做，虽然hard但是比较简单，看了题解后写上了。就是暴力的枚举所有的子树，然后再bfs求最大距离，同时判断一下是否构成了子树（这个组合所有节点都出现了）。这里根据Lee215的竞赛写法做了一些调整。时间复杂度为2**15。

def countSubgraphsForEachDiameter(self, n: int, edges: List[List[int]]) -> List[int]:
    g = [[] for _ in range(n)]
    for u, v in edges:
        u, v = u-1, v-1
        g[u].append(v)
        g[v].append(u)

    def max_d(comb):
        ans = 0
        for i in range(n):
            mask = comb
            if (1<<i) & comb:
                bfs = deque([(i, 0)])
                d = 0
                while bfs:
                    k, d = bfs.popleft()
                    mask ^= (1<<k)  # 标记k被取出此时为0
                    for j in g[k]:
                        if (1<<j) & mask:   # 为1的是剩下的
                            bfs.append((j, d+1))
                if mask: return 0       # 不是0说明没有构成子树
                ans = max(ans, d)
        return ans

    res = [0] * (n-1)
    for comb in range(1<<n):
        if comb & (comb-1) == 0: continue
        d = max_d(comb)
        res[d-1] += d>0
    return res

1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

二维矩阵中，每次翻拍“十”字，最小步数翻成0.原题

1
2
3

Input: mat = [[0,0],[0,1]]
Output: 3
Explanation: One possible solution is to flip (1, 0) then (0, 1) and finally (1, 1) as shown.

方法一：看了答案才做出来，看到提示bfs，但是没有想到可以将这个二维矩阵转成一个二进制是它的数。

def minFlips(self, mat: List[List[int]]) -> int:
    m, n = len(mat), len(mat[0])
    start = sum(cell<<(i*n+j) for i, row in enumerate(mat) for j, cell in enumerate(row))
    q = collections.deque([(start, 0)])
    seen = {start}
    while q:
        cur, step = q.popleft()
        if not cur:
            return step
        for x in range(m):
            for y in range(n):
                nxt = cur
                for i, j in ((0, 1), (1, 0), (-1, 0), (0, -1), (0, 0)):
                    if m > x+i >= 0 <= y+j < n:
                        nxt ^= 1 << ((x+i)*n + y+j) # 0 ^ 0 = 0, 1 ^ 0 = 1
                if nxt not in seen:
                    q.append((nxt, step+1))
                    seen.add(nxt)
    return -1

1293. Shortest Path in a Grid with Obstacles Elimination

最短路径，可以打通障碍k次。原题

Input: 
grid = 
[[0,0,0],
 [1,1,0],
 [0,0,0],
 [0,1,1],
 [0,0,0]], 
k = 1
Output: 6
Explanation: 
The shortest path without eliminating any obstacle is 10. 
The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2).

方法一：一开始想到了正确思路，但是想错了最小步骤怎么求，其实不用求，第一个到达的就是最小的步数。

def shortestPath(self, g: List[List[int]], k: int) -> int:
    m, n = len(g), len(g[0])
    q = collections.deque([(0, 0, k, 0)])
    seen = {(0, 0, k)}
    while q:
        x, y, r, s = q.popleft()
        if x==m-1 and y==n-1:
            return s
        # 如果可以直接直角边走到末尾，那么直接过去，优化快了700ms+.
        if r >= m + n - 3 - x - y:
            return s + m + n - 2 - x - y
        for i, j in ((0, 1), (1, 0), (-1, 0), (0, -1)):
            if 0<=x+i<m and 0<=y+j<n:
                nr = r-(g[x+i][y+j]==1)
                if (x+i, y+j, nr) not in seen and nr>=0:
                    q.append((x+i, y+j, nr, s+1))
                    seen.add((x+i, y+j, nr))
    return -1

1298. Maximum Candies You Can Get from Boxes

最多从盒子中拿到的糖果。从初始的盒子中往外取，盒子能嵌套盒子，盒子如果上锁还需要钥匙打开。原题

方法一：有一点没有想到，就是如果前面的盒子被拿出来，但是没有钥匙，知道后面的盒子才获取到钥匙。这种情况需要如何处理？这里参考了lee215的方式。q来表示所有已经打开的盒子，seen表示所有可见的盒子，这样当拿到钥匙时，其实需要做两个操作，如果这个盒子可见，将其放入q，如果盒子没见，将其锁打开（虽不符常理），这样在遇见盒子时可以直接将其添加到队列。

def maxCandies(self, status: List[int], candies: List[int], keys: List[List[int]], containedBoxes: List[List[int]], initialBoxes: List[int]) -> int:
    ans = 0
    q = collections.deque(b for b in initialBoxes if status[b])
    seen = set(initialBoxes)
    while q:
        b = q.popleft()
        ans += candies[b]
        for new_box in containedBoxes[b]:
            seen.add(new_box)
            if status[new_box]:
                q.append(new_box)
        for key in keys[b]:
            if status[key] == 0 and key in seen:
                q.append(key)
            status[key] = 1
    return ans

1345. Jump Game IV

跳到末尾最小步数，可以向前向后或者跳到一样的值。原题

1
2
3

Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.

方法一：bfs。需要注意num_seen记录所有的同值，否则会超时。

def minJumps(self, arr: List[int]) -> int:
    equal = collections.defaultdict(list)
    for i, a in enumerate(arr):
        equal[a].append(i)
        
    q = collections.deque([(0, 0)])
    pos_seen, num_seen = set(), set()
    while q:
        p, s = q.popleft()
        pos_seen.add(p)
        num = arr[p]
        if p == len(arr)-1:
            return s
        for nxt in [p-1, p+1] + equal[num] * (num not in num_seen):
            if nxt in pos_seen or not 0<=nxt<len(arr): continue
            q.append((nxt, s+1))
        num_seen.add(num)

1391. Check if There is a Valid Path in a Grid

判断是否能到达右下点。原题

1
2
3

Input: grid = [[2,4,3],[6,5,2]]
Output: true
Explanation: As shown you can start at cell (0, 0) and visit all the cells of the grid to reach (m - 1, n - 1).

方法一：dfs。需要注意的是(-x, -y) in directions[grid[ni][nj]])是用来判断该块和下一块是否是联通的。

def hasValidPath(self, grid: List[List[int]]) -> bool:
    directions = {
        1: ((0, 1), (0, -1)),
        2: ((1, 0), (-1, 0)),
        3: ((1, 0), (0, -1)),
        4: ((0, 1), (1, 0)),
        5: ((-1, 0), (0, -1)),
        6: ((0, 1), (-1, 0))
    }
    m, n = len(grid), len(grid[0])
    seen = set()
    
    def dfs(i, j):
        seen.add((i, j))
        if (i, j) == (m-1, n-1):
            return True
        block = grid[i][j]
        for x, y in directions[block]:
            ni, nj = i+x, j+y
            if 0<=ni<m and 0<=nj<n and (ni, nj) not in seen and (
                (-x, -y) in directions[grid[ni][nj]]):
                if dfs(ni, nj):
                    return True
        return False
        
    return dfs(0, 0)

1162. As Far from Land as Possible

离陆地最远的点的距离。原题

Input: [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: 
The cell (1, 1) is as far as possible from all the land with distance 2.

方法一：bfs. 此题竞赛时想到了解法，但是出发点有点问题，是从水找陆地，这样的话有很多重复的循环，导致超时。正确的思路是从陆地遍历水。

def maxDistance(self, grid: List[List[int]]) -> int:
    
    R, C = len(grid), len(grid[0])
    q = collections.deque([(i, j, 0) for i in range(R) for j in range(C)
                           if grid[i][j] == 1])
    d = -1
    while q:
        x, y, d = q.popleft()
        if grid[x][y] == 0:
            return d
        surrounds = ((x-1, y), (x+1, y), (x, y-1), (x, y+1))
        for i, j in surrounds:
            if 0<=i<R and 0<=j<C and grid[i][j]==0:
                q.append((i, j, d+1))
                grid[i][j] = 1
    return d or -1

1091. Shortest Path in Binary Matrix

从左上到右下，只能走0，求最短路径长度，可以斜着走。原题

方法一：核心思想为，BFS，到终点的深度，使用两个数组。

def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
    n = len(grid)
    if not grid[0][0] == grid[-1][-1] == 0:
        return -1
    
    def spread(i, j):
        di = (1, 0, -1)
        dj = (1, 0, -1)
        for k in di:
            for m in dj:
                x, y = i+k, j+m
                if 0<=x<n and 0<=y<n and grid[x][y]==0:
                    yield x, y
    
    d = 0
    bfs = [(0, 0)]
    seen = set()
    while bfs:
        d += 1
        bfs2 = []
        for (x, y) in bfs:
            if x==n-1 and y==n-1:
                return d
            if (x, y) not in seen:
                bfs2.extend([(i, j) for i, j in spread(x, y)])
                seen.add((x, y))
        bfs = bfs2
    return -1

方法二：使用双端队列。为了避免起点为1，所以从-1开始，深度为0.

def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
    n = len(grid)
    q = collections.deque([(-1, -1, 0)])
    seen = set()
    while q:
        x, y, d = q.popleft()
        if x==n-1 and y==n-1:
            return d
        for i, j in ((x-1, y-1), (x-1, y), (x-1, y+1), (x, y-1), (x, y+1), (x+1, y-1), (x+1, y), (x+1, y+1)):
            if 0<=i<n and 0<=j<n and grid[i][j]==0 and (i, j) not in seen:
                q.append((i, j, d+1))
                seen.add((i, j))
    return -1

1034. Coloring A Border

给边界染色，此题和733.flood fill很像，区别在于，那个是将所有区域染色，这个是只将边界染色。原题

方法一：写法稍作修改，将判断移到前面。四个方向只要有一个返回False就说明是边界的点。

def colorBorder(self, grid: List[List[int]], r0: int, c0: int, color: int) -> List[List[int]]:
    def dfs(x, y):
        if (x, y) in seen:
            return True
        if not (0<=x<R and 0<=y<C and grid[x][y]==grid[r0][c0]):
            return False
        seen.add((x, y))
        if dfs(x+1, y) + dfs(x-1, y) + dfs(x, y-1) + dfs(x, y+1) < 4:
            grid[x][y] = color
        return True
        
    seen, R, C = set(), len(grid), len(grid[0])
    dfs(r0, c0)
    return grid

1031. Number of Enclaves

求被困的地点个数。1表示陆地，不能够走到边界的陆地称为被困的陆地。原题

方法一：简单的DFS

def numEnclaves(self, A: List[List[int]]) -> int:
    if not A:
        return 0
    R, C = len(A), len(A[0])
    
    def spread(i, j):
        A[i][j] = 0
        for x, y in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)):
            if 0<=x<R and 0<=y<C and A[x][y] == 1:
                spread(x, y)
    
    for i in range(R):
        if A[i][0]==1:
            spread(i, 0)
        if A[i][C-1] == 1:
            spread(i, C-1)
    
    for j in range(C):
        if A[0][j] == 1:
            spread(0, j)
        if A[R-1][j] == 1:
            spread(R-1, j)
    return sum(sum(row) for row in A)

695. Max Area of Island

最大的岛屿面积。原题

方法一：dfs.

def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
    R, C = len(grid), len(grid[0])
    area, seen = 0, set()
    
    def spread(i, j):
        if not (0<=i<R and 0<=j<C and (i, j) not in seen and
                grid[i][j]):
            return 0
        seen.add((i, j))
        surrounds = ((i-1, j), (i+1, j), (i, j-1), (i, j+1))
        # return 1 + sum(map(lambda x: dfs(*x), surrounds))   
        return 1 + sum(starmap(dfs, surrounds))
    
    return max(spread(i, j) 
               for i in range(R) for j in range(C))

994. Rotting Oranges

腐烂的橘子，1表示新鲜，2表示腐烂，每分钟腐烂的会传染给四周上下左右的橘子，问所有的橘子腐烂最少需要几分钟。原题

方法一：竞赛时虽然做出来了，但有些点没想出来，其实是BFS，这样一想退出条件就很清楚了。

def orangesRotting(self, g: 'List[List[int]]') -> 'int':
    R, C = len(g), len(g[0])
    rotted = ((x, y, 0) for x in range(R) for y in range(C) if g[x][y]==2)
    q = collections.deque(rotted)

    def to_rot(x, y):
        for x, y in ((x-1, y), (x, y-1), (x+1, y), (x, y+1)):
            if 0<=x<R and 0<=y<C and g[x][y]==1:
                yield x, y
    d = 0
    while q:
        r, c, d = q.popleft()
        for sr, sc in to_rot(r, c):
            g[sr][sc] = 2
            q.append((sr, sc, d+1))

    if 1 in sum(g, []):
        return -1

733. Flood Fill

“洪水填充”，给定一个二维数组表示一张图片的像素，然后指定一个点和一个颜色，将这个点和上下左右四个点使用新的颜色填充，和这个点原来相同的颜色的点也受到影响，依次扩散，返回新的图片数组。原题

Input: 
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation: 
From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected 
by a path of the same color as the starting pixel are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected
to the starting pixel.

方法一：dfs. 需要注意的是，如果目标点与颜色相同，则原图不变。

def floodFill(self, image, sr, sc, newColor):
    rows, cols = len(image), len(image[0])
    old_val = image[sr][sc]
    def spread(x, y):
        if old_val == image[x][y]:
            image[x][y] = newColor
            if x-1 >= 0:
                spread(x-1, y)
            if x+1 < rows:
                spread(x+1, y)
            if y-1 >= 0:
                spread(x, y-1)
            if y+1 < cols:
                spread(x, y+1)
    if old_val != newColor:
        spread(sr, sc)
    return image

方法二：上述方法的变形。看起来更优雅。

def floodFill(self, image, sr, sc, newColor):
    def dfs(x, y):
        image[x][y] = newColor
        for x, y in ((x-1, y), (x+1, y), (x, y+1), (x, y-1)):
            if 0<=x<rows and 0<=y<cols and image[x][y]==old_val:
                dfs(x, y)
        
    old_val, rows, cols = image[sr][sc], len(image), len(image[0])
    if old_val != newColor:
        dfs(sr, sc)
    return image

1625. Lexicographically Smallest String After Applying Operations

给你一个字符串 s 以及两个整数 a 和 b 。其中，字符串 s 的长度为偶数，且仅由数字 0 到 9 组成。

你可以在 s 上按任意顺序多次执行下面两个操作之一：

累加：将 a 加到 s 中所有下标为奇数的元素上（下标从 0 开始）。数字一旦超过 9 就会变成 0，如此循环往复。例如，s = “3456” 且 a = 5，则执行此操作后 s 变成 “3951”。
轮转：将 s 向右轮转 b 位。例如，s = “3456” 且 b = 1，则执行此操作后 s 变成 “6345”。
请你返回在 s 上执行上述操作任意次后可以得到的字典序最小的字符串。

输入：s = "5525", a = 9, b = 2
输出："2050"
解释：执行操作如下：
初态："5525"
轮转："2555"
累加："2454"
累加："2353"
轮转："5323"
累加："5222"
累加："5121"
轮转："2151"
累加："2050"
无法获得字典序小于 "2050" 的字符串。

方法一：这题比较难想，作为竞赛第二题一直卡住了，实际没有3题简单。BFS，暴力去做就行，但是比赛时写得有一点问题TLE了。

但是还是想到一些规律，如果b是偶数时，累加的位数只有奇数位；如果b是奇数，那么通过旋转每一位都可能累加，但是累加和旋转的顺序其实是不想关的，可以单独地操作。时间1700ms。

def findLexSmallestString(self, s: str, a: int, b: int) -> str:
    q, seen, ans = deque([s]), {s}, s
    while q:
        cur = q.popleft()
        ans = min(ans, cur)
        nxt = ''.join(str(n if i&1==0 else (int(n)+a)%10) for i, n in enumerate(cur))
        if nxt not in seen:
            seen.add(nxt)
            q.append(nxt)
        rot = nxt[-b:] + nxt[:-b]
        if rot not in seen:
            seen.add(rot)
            q.append(rot)
    return ans

方法二：dfs，也是可以，向BFS那样去重就行了。速度比方法一慢了一点2400ms。

def findLexSmallestString(self, s: str, a: int, b: int) -> str:
    
    def op_1(s):
        return ''.join(str((int(c)+a)%10) if i&1 else c for i, c in enumerate(s))
    
    def op_2(s):
        return s[-b:] + s[:-b]
    
    seen = set()
    stack = [s]
            
    while stack:
        s = stack.pop()
        seen.add(s)
        if (ss := op_1(s)) not in seen: stack.append(ss)
        if (ss := op_2(s)) not in seen: stack.append(ss)
        
    return min(seen)

1627. Graph Connectivity With Threshold

给你1~n个点，如果两个点有一个约数大于Threshold，那么表明两点之间有边。问给你一些点对，判断这两个点是否相连。

方法一：简单的并查集问题，比赛可惜没时间做。这题的问题在于如何建图。枚举两个点一定会超时，所以从逆向考虑，枚举所有的约数，将这些点相连。

def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:

    def union(x, y):
        uf[find(x)] = find(y)

    def find(x):
        if x != uf[x]:
            uf[x] = find(uf[x])
        return uf[x]

    uf = list(range(0, n+1))

    for d in range(threshold+1, n+1):
        for j in range(d, n+1, d):
            union(j, d)

    return [find(u)==find(v) for u, v in queries]

947. Most Stones Removed with Same Row or Column

最多可以移除多少块石头，每次移除时，下一块找到同行或者同列的进行移除。

1 2	Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]] Output: 5

方法一：Union-Find，并查集方法。从一块石头开始，每次找同行或者同列的作为下一次石头。这些石头连通形成一个集合。

def removeStones(self, stones: List[List[int]]) -> int:

    def union(x, y):
        uf[find(x)] = find(y)

    def find(x):
        uf.setdefault(x, x)
        if x != uf[x]:
            uf[x] = find(uf[x])
        return uf[x]

    uf = {}

    for x, y in stones:
        union(x, y+10000)

    return len(stones) - len({find(x) for x, y in stones})

1654. Minimum Jumps to Reach Home

最少需要多少步能到达x，从坐标0点开始，每次可以向右跳`a`步，或者向左跳`b`步，但是不能连着两次向左跳。除此之外有些点不可达。

1
2
3

Input: forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
Output: 3
Explanation: 3 jumps forward (0 -> 3 -> 6 -> 9) will get the bug home.

方法一：BFS，还是很直观可以想到的，比赛时忽略了forbidden错了一次。需要注意的点如果当前点大于最大范围后，就跳不回来了，这个终止条件。这里用一个bool控制了是否可以回跳。

def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:
    f = set(forbidden)
    bfs = [(0, True, 0)]
    for cur, back, step in bfs:
        if cur == x:
            return step
        if cur+a <= 4000 and cur+a not in f:
            bfs.append((cur+a, True, step+1))
            f.add(cur+a)
        if back and cur-b>=0 and cur-b not in f:
            bfs.append((cur-b, False, step+1))
            f.add(cur-a)
    return -1

1203. Sort Items by Groups Respecting Dependencies

公司共有 n 个项目和 m 个小组，每个项目要不无人接手，要不就由 m 个小组之一负责。group[i] 表示第 i 个项目所属的小组，如果这个项目目前无人接手，那么 group[i] 就等于 -1。（项目和小组都是从零开始编号的）小组可能存在没有接手任何项目的情况。请你帮忙按要求安排这些项目的进度，并返回排序后的项目列表：

同一小组的项目，排序后在列表中彼此相邻。
项目之间存在一定的依赖关系，我们用一个列表 beforeItems 来表示，其中 beforeItems[i] 表示在进行第 i 个项目前（位于第 i 个项目左侧）应该完成的所有项目。

如果存在多个解决方案，只需要返回其中任意一个即可。如果没有合适的解决方案，就请返回一个空列表。

1 2	Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]] Output: [6,3,4,1,5,2,0,7]

方法一：拓扑排序，hard题，首先以项目为拓扑排序很容易想到，这里还需要对组间进行拓扑排序。然后再进行一次组内排序。最后合并结果。需要注意的点比较多。

def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
    def get_top_order(g, degree):
        bfs = [i for i in range(len(g)) if degree[i]==0]
        res = []
        for i in bfs:
            res.append(i)
            for j in g[i]:
                degree[j] += 1
                if degree[j] == 0:
                    bfs.append(j)
        return res if len(res)==len(degree) else []

    # 未分配组定义为新组
    it = count(m)
    group = [g if g!=-1 else next(it) for g in group]
    m = next(it)        # m 增加了
    g_graph, p_graph = [[] for _ in range(m)], [[] for _ in range(n)]
    g_degree, p_degree = [0] * m, [0] * n
    for u in range(n):
        for v in beforeItems[u]:
            p_degree[u] -= 1
            p_graph[v].append(u)
            if group[u] != group[v]:    # 只比较不同组
                g_degree[group[u]] -= 1
                g_graph[group[v]].append(group[u])

    projects = get_top_order(p_graph, p_degree)
    groups = get_top_order(g_graph, g_degree)
    if not projects or not groups: return []

    # 组内排序
    order_within_group = defaultdict(list)
    for p in projects:
        order_within_group[group[p]].append(p)

    res = []
    for g in groups:
        res += order_within_group[g]
    return res

803. Bricks Falling When Hit

有一个 m x n 的二元网格，其中 1 表示砖块，0 表示空白。砖块稳定（不会掉落）的前提是：

一块砖直接连接到网格的顶部，或者至少有一块相邻（4 个方向之一）砖块稳定不会掉落时给你一个数组 hits ，这是需要依次消除砖块的位置。

每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失，然后其他的砖块可能因为这一消除操作而掉落。一旦砖块掉落，它会立即从网格中消失（即，它不会落在其他稳定的砖块上）。返回一个数组 result ，其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。注意，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。

Input: grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
Output: [2]
Explanation: Starting with the grid:
[[1,0,0,0],
 [1,1,1,0]]
We erase the underlined brick at (1,0), resulting in the grid:
[[1,0,0,0],
 [0,1,1,0]]
The two underlined bricks are no longer stable as they are no longer connected to the top nor adjacent to another stable brick, so they will fall. The resulting grid is:
[[1,0,0,0],
 [0,0,0,0]]
Hence the result is [2].

方法一：逆向思维+dfs。逆向思维还是挺难想的。总共流程可以分为4步。

按照hits顺序，将砖块敲掉，如果没有，需要敲成-1，为了将其周围的砖块分开。
对首行每个单元格进行dfs，统计每个点能够挂住的砖块个数，然后将这些砖块标记为2.
然后按照hits倒序，敲掉的砖块补回来，如果补回来的块能和2的砖块相连，则表示，这些砖块是掉落的。
统计每次敲击的结果。

def hitBricks(self, grid: List[List[int]], hits: List[List[int]]) -> List[int]:
    M, N = len(grid), len(grid[0])

    # Connect unconnected bricks and 
    def dfs(i, j):
        if not (0<=i<M and 0<=j<N) or grid[i][j]!=1:
            return 0
        ret = 1
        grid[i][j] = 2
        ret += sum(dfs(x, y) for x, y in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)))
        return ret

    # Check whether (i, j) is connected to Not Falling Bricks
    def is_connected(i, j):
        return i==0 or any(0<=x<M and 0<=y<N and grid[x][y]==2 
                           for x, y in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)))

    # Mark whether there is a brick at the each hit
    for x, y in hits:
        grid[x][y] -= 1

    # Get grid after all hits
    for j in range(N):
        dfs(0, j)

    # Reversely add the block of each hits and get count of newly add bricks
    ret = [0] * len(hits)
    for k, (i, j) in enumerate(reversed(hits)):
        grid[i][j] += 1
        if grid[i][j]==1 and is_connected(i, j):
            ret[~k] = dfs(i, j) - 1
    return ret

1766. Tree of Coprimes

找到每个节点的最小祖先，并且祖先节点和其节点值互质。

Input: nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]]
Output: [-1,0,0,1]
Explanation: In the above figure, each node's value is in parentheses.
- Node 0 has no coprime ancestors.
- Node 1 has only one ancestor, node 0. Their values are coprime (gcd(2,3) == 1).
- Node 2 has two ancestors, nodes 1 and 0. Node 1's value is not coprime (gcd(3,3) == 3), but node 0's
  value is (gcd(2,3) == 1), so node 0 is the closest valid ancestor.
- Node 3 has two ancestors, nodes 1 and 0. It is coprime with node 1 (gcd(3,2) == 1), so node 1 is its
  closest valid ancestor.

方法一：dfs。比赛时没有时间看题。范围比较小节点值在1~50之间，所以可以将每个值互质的节点和深度放到一个列表中。

def getCoprimes(self, nums: List[int], edges: List[List[int]]) -> List[int]:
    N = len(nums)
    res = [-1] * N
    g = defaultdict(list)
    path = [[] for _ in range(51)]  
    seen = set()
    for u, v in edges:
        g[u].append(v)
        g[v].append(u)

    def dfs(node, depth):
        if node in seen: return
        seen.add(node)
        longest_depth = -1
        for x in range(1, 51):
            if gcd(x, nums[node]) == 1 and len(path[x])>0:
                pnode, pdepth = path[x][-1]
                if pdepth > longest_depth:
                    longest_depth = pdepth
                    res[node] = pnode
        path[nums[node]].append((node, depth))
        for nei in g[node]:
            dfs(nei, depth+1)
        path[nums[node]].pop()

    dfs(0, 0)
    return res

1368. Minimum Cost to Make at Least One Valid Path in a Grid

修改箭头方向最少次数能够到达右下角的点。

Input: grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]]
Output: 3
Explanation: You will start at point (0, 0).
The path to (3, 3) is as follows. (0, 0) --> (0, 1) --> (0, 2) --> (0, 3) change the arrow to down with cost = 1 --> (1, 3) --> (1, 2) --> (1, 1) --> (1, 0) change the arrow to down with cost = 1 --> (2, 0) --> (2, 1) --> (2, 2) --> (2, 3) change the arrow to down with cost = 1 --> (3, 3)
The total cost = 3.

方法一：狄克斯特拉，有点慢，4600ms。

def minCost(self, grid: List[List[int]]) -> int:
    heap = [(0, 0, 0)]
    M, N = len(grid), len(grid[0])
    seen = {(0, 0, 0)}
    d = {1: (0, 1), 2: (0, -1), 3: (1, 0), 4: (-1, 0)}
    while True:
        cost, x, y = heapq.heappop(heap)
        if x == M-1 and y == N-1:
            return cost
        for x0, y0 in d.values():
            i = x + x0
            j = y + y0
            if 0<=i<M and 0<=j<N:
                new_cost = cost + (d[grid[x][y]]!=(x0, y0))
                if (new_cost, i, j) not in seen:
                    heapq.heappush(heap, (new_cost, i, j))
                    seen.add((new_cost, i, j))

方法二：BFS+DFS. @lee215的方法，328ms。

def minCost(self, grid: List[List[int]]) -> int:
    M, N, k = len(grid), len(grid[0]), 0
    cost = [[inf] * N for _ in range(M)]
    dire = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    bfs = []

    def dfs(i, j):
        if not (0<=i<M and 0<=j<N and cost[i][j]==inf): return
        cost[i][j] = k
        bfs.append((i, j))
        dfs(i+dire[grid[i][j]-1][0], j+dire[grid[i][j]-1][1])

    dfs(0, 0)
    while bfs:
        k += 1
        bfs, bfs2 = [], bfs
        [dfs(x+i, y+j) for x, y in bfs2 for i, j in dire]

    return cost[-1][-1]

1786. Number of Restricted Paths From First to Last Node

从头节点到尾节点的限制路径是多少个，限制路径指每次节点到尾节点的最短路径要递减。

Input: n = 5, edges = [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]
Output: 3
Explanation: Each circle contains the node number in black and its distanceToLastNode value in blue. The three restricted paths are:
1) 1 --> 2 --> 5
2) 1 --> 2 --> 3 --> 5
3) 1 --> 3 --> 5

方法一：比赛时差一点做出来，最后一步没有想明白。首先肯定是需要求每个节点到尾节点的最短路径，利用狄克斯特拉算法简单求出。

然后使用记忆化，本质上是个动态规划来累加路径和。dfs方法没有想出来。

def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:
    MOD = 10**9 + 7
    g = defaultdict(list)
    for u, v, w in edges:
        g[u].append((v, w))
        g[v].append((u, w))

    dist = [-1] * (n+1)  # distance
    dist[-1] = 0
    heap = [(w, u) for u, w in g[n]]
    heapq.heapify(heap)
    cnt = 0
    while cnt < n-1:
        w, u = heapq.heappop(heap)
        if dist[u] == -1:
            dist[u] = w
            cnt += 1
            for v, w2 in g[u]:
                if dist[v]==-1:
                    heapq.heappush(heap, (w+w2, v))

    @lru_cache(None)
    def dfs(i):
        if i == n: return 1
        ans = 0
        for nei, _ in g[i]:
            if dist[i] > dist[nei]:
                ans = (ans+dfs(nei)) % MOD
        return ans

    return dfs(1)

331. Verify Preorder Serialization of a Binary Tree

判断一个字符串序列是否是前序遍历。

1 2	Input: "9,3,4,#,#,1,#,#,2,#,6,#,#" Output: true

方法一：栈。一开始想递归，发现递归并不好找条件return False。这个方法有点像不断地剪枝，当一个叶子节点满足子节点都是#的时候，它也变成#。

def isValidSerialization(self, preorder: str) -> bool:
    stack = []
    for node in preorder.split(","):
        stack.append(node)
        while len(stack)>=3 and stack[-1]==stack[-2]=="#" and stack[-3]!="#":
            stack.pop()
            stack.pop()
            stack.pop()
            stack.append("#")
    return stack == ["#"]

func isValidSerialization(preorder string) bool {
    var stack []string
    for _, node := range strings.Split(preorder, ",") {
        stack = append(stack, node)
        for ;len(stack)>=3 && stack[len(stack)-1]=="#" && stack[len(stack)-2]=="#" && stack[len(stack)-3]!="#"; {
            stack = stack[:len(stack)-3]
            stack = append(stack, "#")
        }
    }
    return len(stack)==1 && stack[0]=="#"
}

方法二：槽。代码简单，思想不简单。把树中的节点想象成槽，当出现一个非空节点，就需要左右孩子节点2个槽。如果是一个#表示消耗掉一个槽。全程槽的数不能为0，最后才能是0

def isValidSerialization(self, preorder: str) -> bool:
    slot = 1
    for node in preorder.split(","):
        if slot == 0: return False
        if node == "#":
            slot -= 1
        else:
            slot += 1
    return slot == 0

func isValidSerialization(preorder string) bool {
    slot := 1
    for _, node := range strings.Split(preorder, ",") {
        if slot == 0 {
            return false
        }
        if node == "#" {
            slot--
        } else {
            slot++
        }
    }
    return slot == 0
}

1857. Largest Color Value in a Directed Graph

有向图中包含颜色最多的路径，颜色的最大值是多少。

1
2
3

Input: colors = "abaca", edges = [[0,1],[0,2],[2,3],[3,4]]
Output: 3
Explanation: The path 0 -> 2 -> 3 -> 4 contains 3 nodes that are colored "a" (red in the above image).

方法一：拓扑排序+DP，比较难的一道题。两个都没有想到，首先为什么要拓扑排序，因为对于一个路径来说，从入度为0的点开始，才会让节点越多，颜色才可能最大。dp[i][j]表示以i为终点的路径，j颜色最大有多少个

def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
    g = defaultdict(list)
    N = len(colors)
    degree = [0] * N
    for u, v in edges:
        g[u].append(v)
        degree[v] -= 1
    dp = defaultdict(lambda: defaultdict(int))

    bfs = [i for i in range(N) if degree[i]==0]

    cnt = 0
    for i in bfs:
        cnt += 1
        dp[i][colors[i]] += 1
        for j in g[i]:
            degree[j] += 1
            for c in string.ascii_lowercase:
                dp[j][c] = max(dp[j][c], dp[i][c])
            if degree[j] == 0:
                bfs.append(j)

    if cnt != N:
        return -1
    return max(max(dp[i].values()) for i in range(N))

1871. Jump Game VII

跳跃游戏，0位首的数组，每次跳跃步伐在mi,ma之间，且只能跳到0的位置，问是否能够跳到最后一个位置。

Input: s = "011010", minJump = 2, maxJump = 3
Output: true
Explanation:
In the first step, move from index 0 to index 3. 
In the second step, move from index 3 to index 5.

方法一：比赛期间用了堆+无数次剪枝和TLE勉强通过。

def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
    if s[-1] != "0":
        return False
    max_one, max_zero = 0, 0
    one, zero = 0, 0
    for i in range(len(s)):
        if s[i] == "1":
            one += 1
            zero = 0
            max_one = max(max_one, one)
        else:
            zero += 1
            one = 0
            max_zero = max(max_zero, zero)
    if max_one >= maxJump:
        return False
    N = len(s)
    heap = [0]
    seen = {i for i, c in enumerate(s) if c == '1'}
    seen.add(0)

    while heap:
        i = heapq.heappop(heap)
        i = -i
        # if i + maxJump >= N-1 and s[-1]=="0":
        #     return True
        if i == N-1:
            return True
        for j in set(range(i+minJump, min(i+maxJump+1, N))) - seen:
        # for j, c in enumerate(islice(s, i+minJump, i+maxJump+1), i+minJump):
            # print(j, c)
            heapq.heappush(heap, -j)
            seen.add(j)
    return False

方法二：bfs。没想到能用bfs。

def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
    queue = collections.deque([0])
    visited, mx = set([0]), 0
    while queue:
        i = queue.popleft()
        for j in range(max(i + minJump, mx + 1), min(i + maxJump + 1, len(s))):
            if s[j] == '0' and j not in visited:
                if j == len(s) - 1: return True
                queue.append(j)
                visited.add(j)
        # mx = max(mx, i + maxJump)  # 去重重复的区间判断，对于"0000000", 1, 6这种case，没有的话可能会超时
        mx = i + maxJump             # i + maxJump一定会大于mx，因为是拓扑排序
    return False

1905. Count Sub Islands

找到图2中子岛屿的个数，如果图2的岛屿都在图一的同一个岛中，那么久叫作子岛屿。

Input: grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
Output: 3
Explanation: In the picture above, the grid on the left is grid1 and the grid on the right is grid2.
The 1s colored red in grid2 are those considered to be part of a sub-island. There are three sub-islands.

方法一：这题竞赛居然没做出来，想着先把图一的所有岛屿都求出来然后再遍历图2算。其实可以同时进行的。

def countSubIslands(self, g1: List[List[int]], g2: List[List[int]]) -> int:

    M, N = len(g1), len(g1[0])
    def dfs(i, j):
        if not (0<=i<M and 0<=j<N and g2[i][j]==1):
            # 如果越界或者g2[i][j]==0（即不是岛屿，不需要判断），则算作是子岛屿
            return 1
        res = g1[i][j]
        g2[i][j] = 0
        for x, y in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):
            res &= dfs(x, y)
        return res

    return sum(dfs(i, j) for i in range(M) for j in range(N) if g2[i][j])

2092. Find All People With Secret

找到知道秘密的人，一个人可以同时开多个会，而且同一时间点的事件同时发生。

方法一：比赛的时候想并查集，但是没有完全想出来。这里是答案的bfs方法。

def findAllPeople(self, n: int, meetings: List[List[int]], firstPerson: int) -> List[int]:
    can = {0, firstPerson}
    for _, group in groupby(sorted(meetings, key=operator.itemgetter(2)), key=operator.itemgetter(2)):
        g = defaultdict(list)
        queue = set()
        for x, y, t in group:
            g[x].append(y)
            g[y].append(x)
            if x in can: queue.add(x)
            if y in can: queue.add(y)
                
        q = deque(queue)
        while q:
            x = q.popleft()
            for y in g[x]:
                if y not in can:
                    q.append(y)
                    can.add(y)
        
    return list(can)

2097. Valid Arrangement of Pairs

找到一个有效的首位相连的路径，数组元素表示一条有向边。

Input: pairs = [[5,1],[4,5],[11,9],[9,4]]
Output: [[11,9],[9,4],[4,5],[5,1]]
Explanation:
This is a valid arrangement since endi-1 always equals starti.
end0 = 9 == 9 = start1 
end1 = 4 == 4 = start2
end2 = 5 == 5 = start3

方法一：和332题一样，是求欧拉路径的问题，区别在于要先找到开始的点。比赛的时候没有想出来

def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:
    g = defaultdict(list)
    din, dout = defaultdict(int), defaultdict(int)
    for s, e in pairs:
        g[s].append(e)
        dout[s] += 1
        din[e] += 1
        
    start = pairs[0][0]
    for p in dout:
        if dout[p] - din[p] == 1:
            start = p  # 欧拉环的尾
            break
    route = []
    
    def dfs(s):
        while g[s]:
            dfs(g[s].pop())
        route.append(s)
        
    dfs(start)
    route.reverse()
    # print(route)
    return [[a, b] for a, b in zip(route, route[1:])]

2360. Longest Cycle in a Graph

图中的最长环。每个节点最多只有一个出度。

Input: edges = [3,3,4,2,3]
Output: 3
Explanation: The longest cycle in the graph is the cycle: 2 -> 4 -> 3 -> 2.
The length of this cycle is 3, so 3 is returned.

方法一：常规方法，拓扑排序+bfs。逐渐删除入度为0的点，最后剩下所有的环。找出最大的环。

def longestCycle(self, edges: List[int]) -> int:
    N = len(edges)
    degree = [0] * N
    for u, v in enumerate(edges):
        if v == -1: continue
        degree[v] += 1
    stack = [n for n in range(N) if degree[n]==0]
    while stack:
        u = stack.pop()
        v = edges[u]
        if v == -1:
            continue
        degree[v] -= 1
        if degree[v] == 0:
            stack.append(v)

    # 无环，直接返回-1
    if max(degree) == 0:
        return -1

    def bfs(u):
        step = 0
        while u not in seen:
            step += 1
            seen.add(u)
            u = edges[u]
        return step

    ans = 0
    seen = set()
    for i in range(N):
        if degree[i]!=0 and i not in seen:
            ans = max(ans, bfs(i))
    return ans

方法二：时钟从0点找没有走过的点，如果有环的话，时差就是环长。

def longestCycle(self, edges: List[int]) -> int:
    time = [0] * len(edges)
    clock, ans = 1, -1
    for x, t in enumerate(time):
        if t: 
            continue
        start_time = clock
        while x != -1:
            if time[x]:  # 重复访问
                if time[x] >= start_time:  # 找到了一个新的环
                    print(x, time[x], start_time)
                    ans = max(ans, clock - time[x])
                break
            time[x] = clock
            clock += 1
            x = edges[x]
        # print(time)
    return ans

827. Making A Large Island

修改一个0变成1，最大的岛屿面积是多少？

1
2
3

输入: grid = [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。

方法一：首先用独立的编号标记每个岛屿，并记录岛屿面积。然后遍历0的地方，将上下左右的岛屿相连，计算面积。

def largestIsland(self, g: List[List[int]]) -> int:
    N = len(g)
    num = 2
    areas = Counter()

    def dfs(i, j):
        g[i][j] = num
        area = 1
        for x, y in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):
            if 0<=x<N and 0<=y<N and g[x][y]==1:
                area += dfs(x, y)
        return area

    for i in range(N):
        for j in range(N):
            if g[i][j] == 1:
                area = dfs(i, j)
                areas[num] = area
                num += 1
    res = max(areas.values(), default=0)

    for i in range(N):
        for j in range(N):
            if g[i][j] == 0:
                aroud = set()
                for x, y in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):
                    if 0<=x<N and 0<=y<N and g[x][y]!=0:
                        aroud.add(g[x][y])
                res = max(res, sum(areas[d] for d in aroud)+1)
    return res

934. Shortest Bridge

最短的桥，图中有两个岛屿，求两个岛屿间的最短距离。

方法一：首先用dfs将岛屿编号，并保存第一个岛屿的边。然后遍历其边使用bfs去找第二个岛屿。

def shortestBridge(self, grid: List[List[int]]) -> int:
    num = 2
    q = []
    M, N = len(grid), len(grid[0])

    def dfs(i, j):
        cnt = 0
        grid[i][j] = num
        for x, y in ((i+1, j), (i-1, j), (i, j-1), (i, j+1)):
            if 0<=x<M and 0<=y<N and grid[x][y]==1:
                cnt += 1
                dfs(x, y)
        if cnt != 4 and num == 2:
            q.append((i, j, 0))

    for x in range(M):
        for y in range(N):
            if grid[x][y] == 1:
                dfs(x, y)
                num += 1
    for x, y, s in q:
        for i, j in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):
            if 0<=i<M and 0<=j<N:
                if grid[i][j]==0:
                    q.append((i, j, s+1))
                    grid[i][j] = 1
                elif grid[i][j]==3:
                    return s

2477. Minimum Fuel Cost to Report to the Capital

给你一棵 n 个节点的树（一个无向、连通、无环图），每个节点表示一个城市，编号从 0 到 n - 1 ，且恰好有 n - 1 条路。0 是首都。给你一个二维整数数组 roads ，其中 roads[i] = [ai, bi] ，表示城市 ai 和 bi 之间有一条 双向路 。

每个城市里有一个代表，他们都要去首都参加一个会议。

每座城市里有一辆车。给你一个整数 seats 表示每辆车里面座位的数目。

城市里的代表可以选择乘坐所在城市的车，或者乘坐其他城市的车。相邻城市之间一辆车的油耗是一升汽油。

请你返回到达首都最少需要多少升汽油。

输入：roads = [[0,1],[0,2],[0,3]], seats = 5
输出：3
解释：
- 代表 1 直接到达首都，消耗 1 升汽油。
- 代表 2 直接到达首都，消耗 1 升汽油。
- 代表 3 直接到达首都，消耗 1 升汽油。
最少消耗 3 升汽油。

方法一：这题比赛时竟然没做出来，陷入了思维误区，老想用bfs。实际上需要dfs。首先需要将问题转化。

def minimumFuelCost(self, roads: List[List[int]], s: int) -> int:
    g = defaultdict(list)
    for u, v in roads:
        g[u].append(v)
        g[v].append(u)

    res = 0

    # 等价于车是无限的，因为每个节点都有车，即使s=1也是足够的
    # 等价于每走一条边，消耗一辆车
    # 求子树节点的大小

    # 表示从n到父节点需要多少辆车
    def dfs(n, p):
        size = 1
        for j in g[n]:
            if j != p:
                size += dfs(j, n)
        if n: # 0节点不需要计算，因为已经停止了
            nonlocal res
            res += ceil(size / s)
        return size

    dfs(0, -1)
    return res