LeetCode笔记：Weekly Contest 253（补发）
LeetCode笔记：Weekly Contest 253（补发）
codename_cys
发布于 2021-08-24 16:25:47
发布于 2021-08-24 16:25:47
代码可运行
运行总次数：0
代码可运行
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这题也还好，就是不断地取出头部的单词进行拼接，直到全部取用完成或者组合出目标单词。
2. 代码实现
给出python代码实现如下：
class Solution:
def isPrefixString(self, s: str, words: List[str]) -> bool:
t = ""
while words and s != t:
w = words.pop(0)
t = t + w
return s == t提交代码评测得到：耗时36ms，占用内存14.4MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题的思路也直接，维护一个堆排来确保每一次取用最大的元素，然后重复k次取用操作即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def minStoneSum(self, piles: List[int], k: int) -> int:
piles = [-x for x in piles]
heapq.heapify(piles)
for _ in range(k):
n = -heapq.heappop(piles)
heapq.heappush(piles, -n + n // 2)
return - sum(piles)提交代码评测得到：耗时1816ms，占用内存29MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题其实也挺直接的，我们先扣去本身就符合条件的括号，结果就变成了]]][[[这样的结果。
而没经过一次变换，我们就能减少2对括号，因此，我们可以快速地得到最终需要的变换次数。
2. 代码实现
给出python代码实现如下：
class Solution:
def minSwaps(self, s: str) -> int:
bra, ket = 0, 0
for c in s:
if c == "[":
bra += 1
else:
if bra == 0:
ket += 1
else:
bra -= 1
n = bra
return (n+1)//2提交代码评测得到：耗时367ms，占用内存25.3MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题自己没有搞定出来，然后看了答案之后简直惊呆了，因为曾经遇到过，而且当时的解法同样惊艳到我了，然后我依然忘了……
2. 代码实现
直接给出官方的代码实现如下，应该是一目了然的……
class Solution:
def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
d = list()
ans = list()
for ob in obstacles:
# 这里需要改成 >=
if not d or ob >= d[-1]:
d.append(ob)
ans.append(len(d))
else:
# 将 300 题解中的二分查找改为 API 调用使得代码更加直观
# 如果是最长严格递增子序列，这里是 bisect_left
# 如果是最长递增子序列，这里是 bisect_right
loc = bisect_right(d, ob)
ans.append(loc + 1)
d[loc] = ob
return ans本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/08/22 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
