A. Sort the People (opens new window)

Sort the tuple (height, name) then output names in the sorted order.

DETAILS

def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
        return [a[0] for a in sorted([(n, i) for n, i in zip(names, heights)], key = lambda x:-x[1])]

B. Longest Subarray With Maximum Bitwise AND (opens new window)

A & B <= min(A, B), thus we are actually looking for:

• The largest number a from array A.
• The longest subarray filled by a.

DETAILS

def longestSubarray(self, A: List[int]) -> int:
        max_a = max(A)
        return max(len(list(g)) for k, g in itertools.groupby(A) if k == max_a)

C. Find All Good Indices (opens new window)

Left and right DP. For each index i, we store the longest decreasing subarray length end by i - 1 and the longest increasing subarray length from i + 1.

DETAILS

def goodIndices(self, A: List[int], k: int) -> List[int]:
        n = len(A)
        dec, inc = [1] * n, [1] * n
        
        for i in range(n - 2, -1, -1):
            if A[i] <= A[i + 1]:
                inc[i] = inc[i + 1] + 1
        for i in range(1, n):
            if A[i] <= A[i - 1]:
                dec[i] = dec[i - 1] + 1
        
        return [i for i in range(1, n - 1) if dec[i - 1] >= k and inc[i + 1] >= k]

D. Number of Good Paths (opens new window)

Please refer to This LC Discussion (opens new window) for my solution in English.

并查集。 我们要找的路径上的点都要不大于两个端点的值，所以我们要从小到大地遍历每个点，找出以当前节点作为端点的路有多少条。

DETAILS

class UF:
    def __init__(self, n):
        self.root = list(range(n))
    def find(self, x):
        if self.root[x] != x: self.root[x] = self.find(self.root[x])
        return self.root[x]

class Solution:
    def numberOfGoodPaths(self, V: List[int], E: List[List[int]]) -> int:
        N  = collections.defaultdict(set)
        ans, uf = len(V), UF(len(V))
        for a, b in E:
            N[a].add(b)
            N[b].add(a)    
        dic = collections.defaultdict(dict)
        for i, v in enumerate(V):
            dic[i][v] = 1

        for val, cur in sorted([v, i] for i, v in enumerate(V)):
            for nxt in N[cur]:
                root_nxt, root_cur = uf.find(nxt), uf.find(cur)
                if V[nxt] <= val and root_nxt != root_cur:
                    uf.root[root_cur] = root_nxt
					ans += dic[root_cur][val] * dic[root_nxt].get(val, 0)
                    dic[root_nxt][val] = dic[root_nxt].get(val, 0) + dic[root_cur][val]
		
        return ans