Leetcode notes: biweekly contest 70

• LeetCode note ：Biweekly Contest 70
  • 1. Topic 1
    • 1. Their thinking
    • 2. Code implementation
  • 2. Topic two
    • 1. Their thinking
    • 2. Code implementation
  • 3. Topic three
    • 1. Their thinking
    • 2. Code implementation
  • 4. Topic four
    • 1. Their thinking
    • 2. Code implementation

1. Topic 1

The link to question 1 is as follows ：

• 2144. Minimum Cost of Buying Candies With Discount

1. Their thinking

This problem can be realized by using greedy algorithm directly .

First, we sort the prices , Then the two biggest prices must be at their own expense , Then we can get the third highest price candy for free , Repeat the above operation to the final answer .

2. Code implementation

give python The code implementation is as follows ：

class Solution:
    def minimumCost(self, cost: List[int]) -> int:
        cost = sorted(cost, reverse=True)
        cost = [c for i, c in enumerate(cost) if i % 3 != 2]
        return sum(cost)

The submitted code was evaluated ： Time consuming 40ms, Take up memory 14.4MB.

2. Topic two

The link to question 2 is as follows ：

• 2145. Count the Hidden Sequences

1. Their thinking

First of all, we assume that the first element is 0, So obviously we can recover the complete sequence .

here , We can get the difference between the largest element and the smallest element in this sequence , The difference between the range we give and the difference is our answer .

2. Code implementation

give python The code implementation is as follows ：

class Solution:
    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
        n = len(differences)
        nums = [0 for _ in range(n+1)]
        for i in range(n):
            nums[i+1] = nums[i] + differences[i]
        _min, _max = min(nums), max(nums)
        delta = _max - _min
        res = upper - lower - delta + 1
        return res if res >= 0 else 0

The submitted code was evaluated ： Time consuming 1943ms, Take up memory 28.8MB.

3. Topic three

The link to question 3 is as follows ：

• 2146. K Highest Ranked Items Within a Price Range

1. Their thinking

This question only needs to pass one bfs You can get all the grids you can reach , Then we sort them according to the sorting rules and take the first k Just one element .

2. Code implementation

give python The code implementation is as follows ：

class Solution:
    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:
        n, m = len(grid), len(grid[0])
        i, j = start
        q = [start + [0]]
        reachable = []
        seen = set([(i, j)])
        while q:
            i, j, s = q.pop(0)
            if pricing[0] <= grid[i][j] <= pricing[1]:
                reachable.append([s, grid[i][j], i, j])
            if i-1 >= 0 and grid[i-1][j] != 0 and (i-1, j) not in seen:
                q.append((i-1, j, s+1))
                seen.add((i-1, j))
            if i+1 < n and grid[i+1][j] != 0 and (i+1, j) not in seen:
                q.append((i+1, j, s+1))
                seen.add((i+1, j))
            if j-1 >= 0 and grid[i][j-1] != 0 and (i, j-1) not in seen:
                q.append((i, j-1, s+1))
                seen.add((i, j-1))
            if j+1 < m and grid[i][j+1] != 0 and (i, j+1) not in seen:
                q.append((i, j+1, s+1))
                seen.add((i, j+1))
        
        reachable = sorted(reachable)[:k]
        return [x[2:] for x in reachable] 

The submitted code was evaluated ： Time consuming 3336ms, Take up memory 68.3MB.

4. Topic four

The link to question 4 is as follows ：

• 2147. Number of Ways to Divide a Long Corridor

1. Their thinking

This question is actually simpler than the previous one , We just need to take every two seats as the boundary , Investigate two room Between plant number （ It might as well be k）, Then between the two there is $k+1$ A method of setting up wall panels , And we multiply all the possibilities to get our final answer .

2. Code implementation

give python The code implementation is as follows ：

class Solution:
    def numberOfWays(self, corridor: str) -> int:
        MOD = 10**9 + 7
        corridor = corridor.strip("P")
        seat_num = len([ch for ch in corridor if ch == "S"])
        if seat_num == 0 or seat_num % 2 != 0:
            return 0
        i, cnt, n = 0, 0, len(corridor)
        res = 1
        while i < n:
            if corridor[i] == "P":
                i += 1
                continue
            cnt += 1
            if cnt % 2 == 0:
                j = i+1
                while j < n and corridor[j] == "P":
                    j += 1
                res = res * (j-i) % MOD
                i = j
            else:
                i += 1
        return res

The submitted code was evaluated ： Time consuming 1355ms, Take up memory 16MB.