当前位置:网站首页>LeetCode笔记:Weekly Contest 300
LeetCode笔记:Weekly Contest 300
2022-07-05 17:46:00 【Espresso Macchiato】
1. 题目一
给出题目一的试题链接如下:
1. 解题思路
这一题其实就是题目有点长,思路倒是很直接,按照题意构建一个字符的映射对应关系,然后进行解码就行了。
2. 代码实现
给出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。
2. 题目二
给出题目二的试题链接如下:
1. 解题思路
这一题倒是和一般的旋转矩阵的解法没啥太大的区别,不断地改变方向填充数据即可。
2. 代码实现
给出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。
3. 题目三
给出题目三的试题链接如下:
1. 解题思路
这一题思路上其实还是蛮直接的,就是一个递推算法,然后用动态规划优化计算效率即可。
所以我们只需要写出递推公式,其递推关系其实也好计算,就是在前一天知道秘密的人数减去当天会忘掉秘密的人的数目,再加上当天会新知道秘密的人数。
而当天会忘记秘密的人的数目就是forget临界的那一天新增的知道咪咪的人数,然后当天新增的人数就是从当前日期往前delay天到forget临界的那一天之间所有新增的人的数目。
由此,我们即可写出最终的递推公式。
2. 代码实现
给出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。
4. 题目四
给出题目四的试题链接如下:
1. 解题思路
这一题其实较之上一题更加直接,就是一个动态规划就完事了。
每一个点的可以构成的路线数目就是1加上其邻接的所有大于这个点的路径数目。
由此,我们就可以快速地得到我们的最终答案。
2. 代码实现
给出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。
边栏推荐
- 得知女儿被猥亵,35岁男子将对方打至轻伤二级,法院作出不起诉决定
- Mask wearing detection based on yolov3
- 2022 information system management engineer examination outline
- Cmake tutorial step5 (add system self-test)
- “12306” 的架构到底有多牛逼?
- leetcode每日一题:字符串中的第一个唯一字符
- Use QT designer interface class to create two interfaces, and switch from interface 1 to interface 2 by pressing the key
- 开户复杂吗?网上开户安全么?
- 外盘黄金哪个平台正规安全,怎么辨别?
- 怎么选择外盘期货平台最正规安全?
猜你喜欢
「运维有小邓」用于云应用程序的单点登录解决方案
Vulnerability recurrence - 48. Command injection in airflow DAG (cve-2020-11978)
Abnormal recovery of virtual machine Oracle -- Xi Fenfei
Daily exercise: a series of dates
每日一练:关于日期的一系列
Ten top automation and orchestration tools
ISPRS2022/雲檢測:Cloud detection with boundary nets基於邊界網的雲檢測
论文阅读_医疗NLP模型_ EMBERT
使用QT遍历Json文档及搜索子对象
Leetcode daily question: the first unique character in the string
随机推荐
读libco保存恢复现场汇编代码
rsync
Vulnerability recurrence - 48. Command injection in airflow DAG (cve-2020-11978)
tkinter窗口预加载
flask接口响应中的中文乱码(unicode)处理
排错-关于clion not found visual studio 的问题
Cartoon: interesting [pirate] question
多线程(一) 进程与线程
Accuracy of BigDecimal Division
解决“双击pdf文件,弹出”请安装evernote程序
使用QT遍历Json文档及搜索子对象
Tencent music launched its new product "quyimai", which provides music commercial copyright authorization
How to modify MySQL fields as self growing fields
漏洞复现----48、Airflow dag中的命令注入(CVE-2020-11978)
This 17-year-old hacker genius cracked the first generation iPhone!
Which platform of outer disk gold is regular and safe, and how to distinguish it?
Size_ T is unsigned
Six bad safety habits in the development of enterprise digitalization, each of which is very dangerous!
How awesome is the architecture of "12306"?
Mask wearing detection based on yolov3