A. Minimum Cost of Buying Candies With Discount (opens new window)

Greedy, sort items by descending price. Purchase every two of three items and get the third one for free. If there are one or two items left, purchase them all.

DETAILS

def minimumCost(self, A: List[int]) -> int:
        A.sort(reverse = True)
        n, ans = len(A), 0
        for i in range(n // 3):
            ans += A[3 * i] + A[3 * i + 1]
        res = n % 3

        return ans if n % 3 == 0 else ans + sum(A[-(n % 3):])

B. Count the Hidden Sequences (opens new window)

Calculate the difference of the upper-bound and lower-bound of array A. If such difference is larger than upper-lower, then there is no such array.

DETAILS

def numberOfArrays(self, A: List[int], lower: int, upper: int) -> int:
        acc = [0] + list(itertools.accumulate(A))
        lo, up = min(acc), max(acc)
        if up - lo > upper - lower:
            return 0
        return upper - lower - (up - lo) + 1

C. K Highest Ranked Items Within a Price Range (opens new window)

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

BFS法，从出发点开始，搜索所有未被访问的邻居（这个邻居可以是商品，也可以是empty cell），记录下该邻居与出发点的距离。如果某个商品的值介于price之间，说明这个商品有可能是答案之一，我们把它放到备选列表里。因为最终选定前K个商品要参考四个条件:距离，价格，行数，列数。所以我们储存每一个备选商品时，储存的就是这四个条件：([距离，价格，行数，列数])。遍历完所有可能的商品后，按照上述四个条件，对备选商品列表排序，取出前K个的坐标值即可

DETAILS

def highestRankedKItems(self, A: List[List[int]], price: List[int], start: List[int], k: int) -> List[List[int]]:
        ans = []
        dq = collections.deque([(start[0], start[1], 0)])
        seen = set([(start[0], start[1])])
        
        dirs = ((1, 0), (0, 1), (-1, 0), (0, -1))
        m, n = len(A), len(A[0])

        while dq:
            cx, cy, dist = dq.popleft()
            if price[0] <= A[cx][cy] <= price[1]:
                ans.append([dist, A[cx][cy], cx, cy])
            for dx, dy in dirs:
                nx, ny = cx + dx, cy + dy
                if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in seen and A[nx][ny] > 0:
                    seen.add((nx, ny))
                    dq.append((nx, ny, dist + 1))
                    
        ans.sort()
        
        return [x[2:] for x in ans[:k]]

D. Number of Ways to Divide a Long Corridor (opens new window)

Greedy, find the number of plants within every two adjacent coaches. If there are N planets, meaning we have N + 1 ways to put in the bar. Get the product of all the number of ways, mod by 1E9+7.

DETAILS

def numberOfWays(self, A: str) -> int:
        c = collections.Counter(A)
        if c['S'] == 0 or c['S'] % 2: 
            return 0

        pos = [i for i, x in enumerate(A) if x == 'S']
        room, cur, mod = len(pos) // 2, 1, 10 ** 9 + 7

        for i in range(room - 1):
            cur *= (pos[2 * i + 2] - pos[2 * i + 1])
            cur %= mod
        return cur