LeetCode笔记：Weekly Contest 295
LeetCode笔记：Weekly Contest 295
codename_cys
发布于 2022-05-30 08:02:32
发布于 2022-05-30 08:02:32
文章被收录于专栏：我的充电站
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题只需要对source字符串以及target字符串进行一下字符统计，然后看一下target当中的字符分别在source当中最多有几组即可。
2. 代码实现
给出python代码实现如下：
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提交代码评测得到：耗时31ms，占用内存13.8MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题只需要对单词当中价格的部分进行识别，然后进行价格转换即可。
2. 代码实现
给出python代码实现如下：
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)提交代码评测得到：耗时385ms，占用内存16.7MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题坦率地说我没有搞定，思路上来说也没有一个很清晰的思路，整体来说知道是要用一个有序数组这个还是知道的，不过具体怎么自适应的调整到这道题当中却始终想不明白，所以这里就不多做说明了，仅仅是翻译了一下排行榜上的大佬的code。
2. 代码实现
给出翻译后的python代码如下：
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提交代码评测得到：耗时1193ms，占用内存29.1MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题同样的只是翻译了一下排行榜上面大佬的code，所以就不在这里班门弄斧了，有兴趣的读者可以自行看一下code，这题的code事实上倒是不难懂……
2. 代码实现
给出python代码实现如下：
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]提交代码评测得到：耗时8747ms，占用内存40MB。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-05-29，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
