A. Check Distances Between Same Letters (opens new window)

Record the index of the first occurrence of each character (pos[ch]), for the second occurrence of a character ch. Check if the distance between the two occurrences is valid.

DETAILS

def checkDistances(self, s: str, A: List[int]) -> bool:
        pos = [-1] * 26
        for i, ch in enumerate(s):
            k = ord(ch) - ord('a')
            if pos[k] != -1 and i - pos[k] != A[k] + 1:
                return False
            pos[k] = i
        return True

B. Number of Ways to Reach a Position After Exactly k Steps (opens new window)

杨辉三角通项公式。

It's just about the n's row, m's number in Pascal's Triangle.

DETAILS

def numberOfWays(self, A: int, B: int, k: int) -> int:
        mod, diff = 10 ** 9 + 7, abs(A - B)
        if abs(diff - k) % 2 or abs(A - B) > k: 
            return 0
        return math.comb(k, k - (k + diff) // 2) % mod

C. Longest Nice Subarray (opens new window)

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

我们用数组bits来表示数组中每一个数的二进制表示中1的位数。

滑动窗口。从右侧(j)向当前窗口加入数字，如果窗口AND值不等于0，说明当前加入的数字的二进制表示中某一位已经在窗口中出现过了。我们需要从左侧(i)移除数字，直到重复位都被移出窗口。

DETAILS

def longestNiceSubarray(self, A: List[int]) -> int:
        ans, cur, j = 1, 1, 0
        tmp = A[0]

        for i in range(1, len(A)):
            # If conflict by AND.
            while j < i and (tmp & A[i]):
                # Remove number from left side (i) using XOR.
                tmp ^= A[j]
                j += 1
                cur -= 1
                
            # Add number from right (j) using OR.
            tmp |= A[i]
            ans = max(ans, i - j + 1)
        
        return ans

D. Meeting Rooms III (opens new window)

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

因为我们要不断找出最小号码的空房间，和最早结束会议的满房间，所以用两个优先队列来放置空房间和满房间，两个队列排序的index分别是号码和会议结束时间。

我们按照会议开始时间来遍历每一个会议，对于每个会议，假设它的开始时间和结束时间分别是start, end：

• 先把会议结束时间早于start的满房间弹出，放到空房间里。
• 如果有空房间，从里面选出号码最小的房间，把这个任务分配给该房间。
• 如果当前没有空房间，说明我们需要推迟这个会议，直到满房间最早的会议结束。

DETAILS

def mostBooked(self, n: int, A: List[List[int]]) -> int:
        count, free, taken = [0] * n, list(range(n)), []
        heapq.heapify(free)    
        A.sort()
        prev = -1
        
        for start, end in A:
            # Reset start time.
            duration = end - start
            start = max(start, prev)
            end = start + duration
            
            # Free finished rooms 
            while taken and taken[0][0] <= start:
                _, i = heapq.heappop(taken)
                heapq.heappush(free, i)
            
            # Delay current meeting if there is no free room.
            if not free:
                start = taken[0][0]
                end = start + duration
                # Free finished rooms
                while taken and taken[0][0] <= start:
                    _, i = heapq.heappop(taken)
                    heapq.heappush(free, i)
            
            # Assign a room
            i = heapq.heappop(free)
            count[i] += 1
            heapq.heappush(taken, [end, i])
            
            # Reset previous time
            prev = start
            
        return count.index(max(count))