LeetCode笔记：Biweekly Contest 71
LeetCode笔记：Biweekly Contest 71
codename_cys
发布于 2022-04-13 16:25:15
发布于 2022-04-13 16:25:15
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题由于可以允许0在开头的情况，因此整体思路上还是比较简单的，只需要把4个数字取出来，然后把两个较小的数字放在十位数上，剩下的两个较大的数字放在个位数上即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def minimumSum(self, num: int) -> int:
digits = []
while num != 0:
digits.append(num % 10)
num = num // 10
digits = sorted(digits)
return 10*sum(digits[:2]) + sum(digits[2:])提交代码评测得到：耗时43ms，占用内存13.8MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题我的思路比较暴力就是了，直接把数据根据pivot分成三堆，然后重新组合即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
less = [x for x in nums if x < pivot]
equal = [x for x in nums if x == pivot]
large = [x for x in nums if x > pivot]
return less + equal + large提交代码评测得到：耗时2373ms，占用内存31.6MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题其实比较直接，按照题意进行计算即可，唯一需要注意的是，由于秒钟可以达到99，因此有的时间可以有多种设置方式，需要比较一下两者的大小。
2. 代码实现
给出python代码实现如下：
class Solution:
def minCostSetTime(self, startAt: int, moveCost: int, pushCost: int, targetSeconds: int) -> int:
minute, second = targetSeconds // 60, targetSeconds % 60
def get_cost(minute, second):
digits = (f"{minute:02d}" + f"{second:02d}").lstrip("0")
res, pre = 0, str(startAt)
for ch in digits:
res += pushCost
if ch != pre:
res += moveCost
pre = ch
return res
res = get_cost(minute, second) if minute < 100 else math.inf
if minute > 0 and second + 60 < 100:
res = min(res, get_cost(minute-1, second+60))
return res提交代码评测得到：耗时59ms，占用内存13.9MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题的思路其实就是在中段选择一个分隔点，左侧选取n个最小的元素，右侧选取n个最大的元素，然后求差值即可。
因此，我们就是遍历中段的分隔点，然后分别统计左右的前n个最大或者最小的元素之和，然后进行求差即可。而前者这个数组的维护则可以通过堆排进行高效的实现。
2. 代码实现
给出python代码实现如下：
class Solution:
def minimumDifference(self, nums: List[int]) -> int:
n = len(nums) // 3
left = [-x for x in nums[:n]]
right = nums[-n:]
ls, rs = sum(left), sum(right)
heapq.heapify(left)
heapq.heapify(right)
cnt = [[ls, rs] for _ in range(n+1)]
for i in range(n):
heapq.heappush(left, -nums[n+i])
lpop = heapq.heappop(left)
cnt[i+1][0] = cnt[i][0] - nums[n+i] - lpop
heapq.heappush(right, nums[2*n-1-i])
rpop = heapq.heappop(right)
cnt[n-1-i][1] = cnt[n-i][1] + nums[2*n-1-i] - rpop
return -max(sum(x) for x in cnt) 提交代码评测得到：耗时3545ms，占用内存46.3MB。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022/02/06 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
