LeetCode笔记：Weekly Contest 320
LeetCode笔记：Weekly Contest 320
codename_cys
发布于 2022-11-28 21:26:58
发布于 2022-11-28 21:26:58
文章被收录于专栏：我的充电站
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题我的思路非常暴力，就是一个三重循环，找到三个unique的元素之后看一下他们各自有多少重复个数，然后相乘求和即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def unequalTriplets(self, nums: List[int]) -> int:
cnt = Counter(nums)
nums = list(cnt.keys())
n = len(nums)
res = 0
for i in range(n-2):
for j in range(i+1, n-1):
for k in range(j+1, n):
res += cnt[nums[i]] * cnt[nums[j]] * cnt[nums[k]]
return res提交代码评测得到：耗时787ms，占用内存13.8MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题思路上其实还好，就是先遍历之后获取全部的元素，然后对每一个query，找到不大于这个query值的最大元素，以及不小于这个元素最小元素返回即可。
而后者通过二分搜索即可快速得到。
2. 代码实现
给出python代码实现如下：
class Solution:
def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:
vals = []
def dfs(root):
nonlocal vals
if root is None:
return
dfs(root.left)
vals.append(root.val)
dfs(root.right)
return
dfs(root)
def query(q):
idx = bisect.bisect_left(vals, q)
if idx == len(vals):
return [vals[-1], -1]
elif vals[idx] == q:
return [q, q]
elif idx == 0:
return [-1, vals[0]]
else:
return [vals[idx-1], vals[idx]]
return [query(q) for q in queries] 提交代码评测得到：耗时1540ms，占用内存157.6MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题的思路其实就是一个拓扑排序问题，只要找到每一个节点距离0节点的距离以及该节点后续子节点的个数即可。
则从该节点出发到上一个节点所需要的最小的最小的油量就是这个节点上的子节点个数对k的商的上取整。
2. 代码实现
给出python代码实现如下：
class Solution:
def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
def traverse(roads):
graph = defaultdict(list)
for u, v in roads:
graph[u].append(v)
graph[v].append(u)
s = [0]
parents = defaultdict(int)
children = defaultdict(list)
seen = set()
while s != []:
u = s.pop(0)
seen.add(u)
for v in graph[u]:
if v not in seen:
parents[v] = u
children[u].append(v)
s.append(v)
return parents, children
parents, children = traverse(roads)
cnt = defaultdict(int)
deg = {u:len(children[u]) for u in children}
s = [u for u in parents if u not in children]
while s != []:
u = s.pop(0)
cnt[u] += 1
cnt[parents[u]] += cnt[u]
deg[parents[u]] -= 1
if deg[parents[u]] == 0:
s.append(parents[u])
return sum([math.ceil(cnt[x]/seats) for x in cnt if x != 0])提交代码评测得到：耗时7909ms，占用内存78.1MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题思路上就是一个动态规划的题目，本质上来说，我们只要用一个k \times n 的矩阵进行动态规划即可。
其中，dp[r][i]表示s[i:]这个子串当中刚好存在r个满足条件的beautiful partition的个数。
而其他的思路就比较简单了，看看代码就行了，这里就不多做展开了。
2. 代码实现
给出python代码实现如下：
class Solution:
def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:
MOD = 10**9 + 7
n = len(s)
if s[0] not in "2357" or s[-1] in "2357":
return 0
elif k * minLength > n:
return 0
dp = [[0 for _ in range(n)] for _ in range(k+1)]
for i in range(1, n-minLength+1):
if s[i] in "2357" and s[i-1] not in "2357" :
dp[1][i] = 1
dp[1][0] = 1
for r in range(2, k+1):
cnt = deepcopy(dp[r-1])
for i in range(n-2, -1, -1):
cnt[i] = (cnt[i] + cnt[i+1]) % MOD
for i in range(n-1, 0, -1):
if s[i] in "2357" and s[i-1] not in "2357":
dp[r][i] = cnt[i+minLength] if i + minLength < n else 0
dp[r][0] = cnt[minLength]
return dp[k][0]提交代码评测得到：耗时7236ms，占用内存22.5MB。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-11-20，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
