A. Longest Subsequence With Limited Sum (opens new window)

Get prefix sum array P of the input array A, use binary search over P to find the insert position for each query in Q.

DETAILS

def answerQueries(self, A: List[int], Q: List[int]) -> List[int]:
        P = list(itertools.accumulate(sorted(A)))
        return [bisect.bisect_right(P, q) for q in Q]

B. Removing Stars From a String (opens new window)

Iterate over string backward, if we meet a star "*", we will ignore the next character.

DETAILS

def removeStars(self, s: str) -> str:
        d, ans = 0, ""
        for ch in reversed(s):
            if ch == "*":
                d += 1
            elif d:
                d -= 1
            else:
                ans += ch
        return ans[::-1]

C. Minimum Amount of Time to Collect Garbage (opens new window)

The key is that the car for garbage G will stop by the station where G appears last.

Therefore, we just need to find out the last station for each trash, then get the travelling time for each car. Finally add the total number of garbages to the time.

DETAILS

def garbageCollection(self, G: List[str], T: List[int]) -> int:
        T = list(itertools.accumulate(T, initial = 0))
        ans, n = sum(len(g) for g in G), len(G)
        for trash in "MPG":
            for i in range(n - 1, -1, -1):
                if G[i].find(trash) != -1:
                    ans += T[i]
                    break
        
        return ans

D. Build a Matrix With Conditions (opens new window)

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

本质是一个判断有向图中是否存在环的问题，这里提供BFS解法：关键是记录每个点的入度，把入度为0的点压入双向队列，从这些点出发，每弹出一个点i，把这点i下家的入度减一。

如果最后所有的点都【入】+【出】队列，说明该图中无环，并且节点的弹出顺序代表了一种可能的排序。

如果图中有环，环上的节点入度永远大于零，这样最后出入队列的点数必小于k.

分别处理R和C，如果两个图中都无环，说明存在这样的矩阵。

DETAILS

def buildMatrix(self, k: int, R: List[List[int]], C: List[List[int]]) -> List[List[int]]:
        def helper(A):
            nxt, indegree = [set() for _ in range(k)], [0] * k
            dq, ans = collections.deque(), []
            A = set([tuple(a) for a in A])  
            for i, j in A:
                nxt[i - 1].add(j - 1)
                indegree[j - 1] += 1
            for i in range(k):
                if indegree[i] == 0:
                    dq.append(i)   
            while dq:
                cur = dq.popleft()
                ans.append(cur)
                for cand in nxt[cur]:
                    indegree[cand] -= 1
                    if indegree[cand] == 0:
                        dq.append(cand)       
            return ans if len(ans) == k else []
        
        ans1, ans2 = helper(R), helper(C)
        if not ans1 or not ans2: 
            return []

        A = [[0] * k for _ in range(k)]
        for i in range(k): 
            A[ans1.index(i)][ans2.index(i)] = i + 1
        return A