当前位置:网站首页>Leetcode notes: Weekly contest 300
Leetcode notes: Weekly contest 300
2022-07-05 17:59:00 【Espresso Macchiato】
- Match Links :https://leetcode.com/contest/weekly-contest-300/
1. Topic 1
The link to question 1 is as follows :
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 :
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 :
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 :
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.
边栏推荐
- Knowledge points of MySQL (7)
- Size_ T is unsigned
- Cartoon: looking for the best time to buy and sell stocks
- Compared with the loss of Wenxin, the performance is improved a lot
- 热通孔的有效放置如何改善PCB设计中的热管理?
- Cmake tutorial Step2 (add Library)
- Disorganized series
- Neural network self cognition model
- ITK Example
- 数据访问 - EntityFramework集成
猜你喜欢
Anaconda中配置PyTorch环境——win10系统(小白包会)
LeetCode每日一题:合并两个有序数组
神经网络自我认知模型
使用QT遍历Json文档及搜索子对象
ISPRS2022/雲檢測:Cloud detection with boundary nets基於邊界網的雲檢測
求解为啥all(())是True, 而any(())是FALSE?
Star ring technology data security management platform defender heavy release
How awesome is the architecture of "12306"?
ISPRS2020/云检测:Transferring deep learning models for cloud detection between Landsat-8 and Proba-V
Short the command line via jar manifest or via a classpath file and rerun
随机推荐
外盘黄金哪个平台正规安全,怎么辨别?
Operation before or after Teamcenter message registration
检查命名空间和类
Six bad safety habits in the development of enterprise digitalization, each of which is very dangerous!
[BeanShell] there are many ways to write data locally
Short the command line via jar manifest or via a classpath file and rerun
钉钉开放平台小程序API的缓存接口都有哪些内容?
GFS distributed file system
rsync
Leetcode daily question: merge two ordered arrays
删除数组中的某几个元素
Simple query cost estimation
leetcode每日一题:字符串中的第一个唯一字符
Knowledge points of MySQL (6)
读libco保存恢复现场汇编代码
Disabling and enabling inspections pycharm
ITK Example
Abnormal recovery of virtual machine Oracle -- Xi Fenfei
Teamcenter 消息注册前操作或后操作
Compared with the loss of Wenxin, the performance is improved a lot