LeetCode笔记：Weekly Contest 283
LeetCode笔记：Weekly Contest 283
codename_cys
发布于 2022-04-13 16:32:51
发布于 2022-04-13 16:32:51
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题没啥好说的，找到横轴和纵轴的范围然后遍历一下就可以了。
2. 代码实现
给出python代码实现如下：
class Solution:
def cellsInRange(self, s: str) -> List[str]:
res = []
alphabets = string.ascii_uppercase
digits = string.digits
cs, ce = alphabets.find(s[0]), alphabets.find(s[3]) + 1
rs, re = digits.find(s[1]), digits.find(s[4]) + 1
for col in alphabets[cs:ce]:
for row in digits[rs:re]:
res.append(col+row)
return res提交代码评测得到：耗时40ms，占用内存13.8MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题同样没啥难度，只需要先对数字进行一下排序，然后依次看一下两两之间可以填充多少数字，然后填充直至k个数字被全部填满为止。
2. 代码实现
给出python代码实现如下：
class Solution:
def minimalKSum(self, nums: List[int], k: int) -> int:
nums = sorted(nums)
pre = 0
res = 0
for x in nums:
if x <= pre+1:
pre = x
continue
elif x > pre + k:
res += k * (pre+1 + pre+k) // 2
k = 0
break
else:
t = x - pre - 1
res += t * (pre+1 + pre+t) // 2
k -= t
pre = x
if k > 0:
res += k * (pre+1 + pre+k) // 2
return res提交代码评测得到：耗时995ms，占用内存28.8MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题倒是没啥难度，找到入度为0的节点就是根节点，然后用递归构造一下树即可。
2. 代码实现
给出python代码实现如下：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def createBinaryTree(self, descriptions: List[List[int]]) -> Optional[TreeNode]:
graph = defaultdict(list)
deg = defaultdict(int)
for u, v, s in descriptions:
graph[u].append((v, s))
deg[v] += 1
def dfs(u):
root = TreeNode(u)
for v, s in graph[u]:
if s == 0:
root.right = dfs(v)
else:
root.left = dfs(v)
return root
root = [u for u in graph if deg[u] == 0][0]
return dfs(root)提交代码评测得到：耗时3408ms，占用内存35.9MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
显然，如果两个数不互质，那么这两个数的倍数也不可能互质，因此，我们只需要用一个贪婪算法即可完成这道题。
只需要在填入每一个数字的时候不断地去考察其和上一个填入的数字的关系，如果不互质，那么就将其合并成最小公倍数，然后继续考察再前一个数，直至无法合并为止。
重复上述操作即可得到最终的答案。
2. 代码实现
给出python代码实现如下：
class Solution:
def replaceNonCoprimes(self, nums: List[int]) -> List[int]:
res = []
for x in nums:
while res != []:
y = res[-1]
z = gcd(x, y)
if z == 1:
break
else:
res.pop()
x = x * y // z
res.append(x)
return res提交代码评测得到：耗时1907ms，占用内存30.5MB。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022/03/06 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
