Leetcode notes: Weekly contest 300

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

1. Topic 1

The link to question 1 is as follows ：

• 2325. Decode the Message

1. Their thinking

This question is actually a little long , The idea is very direct , Build a character mapping correspondence according to the meaning of the topic , Then decode it .

2. Code implementation

give python The code implementation is as follows ：

class Solution:
    def decodeMessage(self, key: str, message: str) -> str:
        cipher = {
    " ": " "}
        idx = 0
        for ch in key:
            if ch != " " and ch not in cipher.keys():
                cipher[ch] = chr(ord('a') + idx)
                idx += 1
        res = [cipher[ch] for ch in message]
        return "".join(res)

The submitted code was evaluated ： Time consuming 49ms, Take up memory 13.9MB.

2. Topic two

The link to question 2 is as follows ：

• 2326. Spiral Matrix IV

1. Their thinking

This problem is not much different from the general solution of rotation matrix , Just fill in the data by constantly changing the direction .

2. Code implementation

give python The code implementation is as follows ：

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:
        res = [[-1 for _ in range(n)] for _ in range(m)]
        direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        x, y, idx = 0, 0, 0
        while head:
            res[x][y] = head.val
            nx, ny = x + direction[idx][0], y + direction[idx][1]
            if not(0 <= nx < m and 0 <= ny < n and res[nx][ny] == -1):
                idx = (idx+1) % 4
                nx, ny = x + direction[idx][0], y + direction[idx][1]
            x, y = nx, ny
            head = head.next
        return res

The submitted code was evaluated ： Time consuming 2593ms, Take up memory 66.2MB.

3. Topic three

The link to question 3 is as follows ：

• 2327. Number of People Aware of a Secret

1. Their thinking

In fact, the idea of this question is quite direct , It's a recursive algorithm , Then use dynamic programming to optimize the calculation efficiency .

So we just need to write a recursive formula , Its recurrence relation is actually easy to calculate , That is, the number of people who knew the secret the day before minus the number of people who would forget the secret that day , Plus the number of new people who will know the secret that day .

And the number of people who will forget the secret that day is forget On the critical day, the new number of people who know Mimi , Then the number of people added on that day is from the current date delay Day to forget The number of all new people between the critical day .

thus , We can write the final recursive formula .

2. Code implementation

give python The code implementation is as follows ：

class Solution:
    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:
        MOD = 10**9 + 7
        
        @lru_cache(None)
        def fp(idx):
            return np(idx-forget) 
        
        @lru_cache(None)
        def np(idx):
            if idx == 1:
                return 1
            elif idx <= delay:
                return 0
            res = 0
            for i in range(idx-forget+1, idx-delay+1):
                res += np(i)
            return res % MOD
        
        @lru_cache(None)
        def dp(idx):
            if idx <= 0:
                return 0
            elif idx <= delay:
                return 1
            return (dp(idx-1) - fp(idx) + np(idx)) % MOD
        
        return dp(n)

The submitted code was evaluated ： Time consuming 993ms, Take up memory 17.1MB.

4. Topic four

The link to question 4 is as follows ：

• 2328. Number of Increasing Paths in a Grid

1. Their thinking

This question is actually more direct than the previous one , It's just a dynamic planning .

The number of routes that can be formed by each point is 1 Add the number of adjacent paths greater than this point .

thus , We can get our final answer quickly .

2. Code implementation

give python The code implementation is as follows ：

class Solution:
    def countPaths(self, grid: List[List[int]]) -> int:
        MOD = 10**9 + 7
        n, m = len(grid), len(grid[0])
        
        @lru_cache(None)
        def dp(i, j):
            res = 1
            for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
                if 0 <= x < n and 0 <= y < m and grid[x][y] > grid[i][j]:
                    res += dp(x, y)
            return res % MOD
        
        s = sum(dp(i, j) for i in range(n) for j in range(m))
        return s % MOD

The submitted code was evaluated ： Time consuming 3547ms, Take up memory 107.4MB.