LeetCode笔记：Weekly Contest 300

• LeetCode笔记：Weekly Contest 300
  • 1. 题目一
    • 1. 解题思路
    • 2. 代码实现
  • 2. 题目二
    • 1. 解题思路
    • 2. 代码实现
  • 3. 题目三
    • 1. 解题思路
    • 2. 代码实现
  • 4. 题目四
    • 1. 解题思路
    • 2. 代码实现

• 比赛链接：https://leetcode.com/contest/weekly-contest-300/

给出题目一的试题链接如下：

• 2325. Decode the Message

这一题其实就是题目有点长，思路倒是很直接，按照题意构建一个字符的映射对应关系，然后进行解码就行了。

给出python代码实现如下：

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)

提交代码评测得到：耗时49ms，占用内存13.9MB。

给出题目二的试题链接如下：

• 2326. Spiral Matrix IV

这一题倒是和一般的旋转矩阵的解法没啥太大的区别，不断地改变方向填充数据即可。

给出python代码实现如下：

# 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

提交代码评测得到：耗时2593ms，占用内存66.2MB。

给出题目三的试题链接如下：

• 2327. Number of People Aware of a Secret

这一题思路上其实还是蛮直接的，就是一个递推算法，然后用动态规划优化计算效率即可。

所以我们只需要写出递推公式，其递推关系其实也好计算，就是在前一天知道秘密的人数减去当天会忘掉秘密的人的数目，再加上当天会新知道秘密的人数。

而当天会忘记秘密的人的数目就是forget临界的那一天新增的知道咪咪的人数，然后当天新增的人数就是从当前日期往前delay天到forget临界的那一天之间所有新增的人的数目。

由此，我们即可写出最终的递推公式。

给出python代码实现如下：

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)

提交代码评测得到：耗时993ms，占用内存17.1MB。

给出题目四的试题链接如下：

• 2328. Number of Increasing Paths in a Grid

这一题其实较之上一题更加直接，就是一个动态规划就完事了。

每一个点的可以构成的路线数目就是1加上其邻接的所有大于这个点的路径数目。

由此，我们就可以快速地得到我们的最终答案。

给出python代码实现如下：

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

提交代码评测得到：耗时3547ms，占用内存107.4MB。