Leetcode notes: Weekly contest 295

• LeetCode note ：Weekly Contest 295
  • 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

• Match Links ：https://leetcode.com/contest/weekly-contest-295/

1. Topic 1

The link to question 1 is as follows ：

• 2287. Rearrange Characters to Make Target String

1. Their thinking

This question only needs to be correct source String and target String for character statistics , And let's see target The characters are in source A few groups at most .

2. Code implementation

give python The code implementation is as follows ：

class Solution:
    def rearrangeCharacters(self, s: str, target: str) -> int:
        cnt = Counter(s)
        res = math.inf
        for k,v in Counter(target).items():
            res = min(cnt[k] // v, res)
        return res

The submitted code was evaluated ： Time consuming 31ms, Take up memory 13.8MB.

2. Topic two

The link to question 2 is as follows ：

• 2288. Apply Discount to Prices

1. Their thinking

This question only needs to identify the price part of the word , Then the price can be converted .

2. Code implementation

give python The code implementation is as follows ：

class Solution:
    def discountPrices(self, sentence: str, discount: int) -> str:
        def is_price(w):
            return re.match(r"^\$\d+\.?\d*$", w)
        
        def fn(w):
            if is_price(w):
                return "$" + "{:.2f}".format(float(w[1:]) * (100 - discount) / 100)
            else:
                return w
        
        s = [fn(w) for w in sentence.split()]
        return " ".join(s)

The submitted code was evaluated ： Time consuming 385ms, Take up memory 16.7MB.

3. Topic three

The link to question 3 is as follows ：

• 2289. Steps to Make Array Non-decreasing

1. Their thinking

Frankly speaking, I haven't solved this problem , In terms of ideas, there is no clear idea , As a whole, I know whether to use an ordered array , However, how to adaptively adjust to this problem has never been understood , So I won't explain more here , Just translated the words of the big men on the ranking list code.

2. Code implementation

Give the translated python The code is as follows ：

class Solution:
    def totalSteps(self, nums: List[int]) -> int:
        res = 0
        s = []
        n = len(nums)
        l = 0
        for i in nums[::-1]:
            depth = 0
            while s != [] and i > s[-1][0]:
                prev, prev_depth = s.pop()
                depth += 1 + max(prev_depth - depth - 1, 0)
            res = max(res, depth)
            s.append((i, depth))
        return res

The submitted code was evaluated ： Time consuming 1193ms, Take up memory 29.1MB.

4. Topic four

The link to question 4 is as follows ：

• 2290. Minimum Obstacle Removal to Reach Corner

1. Their thinking

The same question just translated the words of the top leaders on the ranking list code, So I won't teach others here , Interested readers can take a look at it for themselves code, This question code In fact, it is not difficult to understand ……

2. Code implementation

give python The code implementation is as follows ：

class Solution:
    def minimumObstacles(self, grid: List[List[int]]) -> int:
        n, m = len(grid), len(grid[0])
        distance = [[math.inf for _ in range(m)] for _ in range(n)]
        distance[0][0] = 0
        q = [(0, 0)]
        
        def inside(x, y):
            return 0 <= x < n and 0 <= y < m
        
        while q:
            x0, y0 = q.pop(0)
            for x, y in [(x0-1, y0), (x0+1, y0), (x0, y0-1), (x0, y0+1)]:
                if not inside(x, y):
                    continue
                if distance[x][y] > distance[x0][y0] + grid[x][y]:
                    distance[x][y] = distance[x0][y0] + grid[x][y]
                    if grid[x][y]:
                        q.append((x, y))
                    else:
                        q.insert(0, (x, y))
        return distance[-1][-1]

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