LeetCode笔记：Weekly Contest 279
LeetCode笔记：Weekly Contest 279
codename_cys
发布于 2022-04-13 16:31:52
发布于 2022-04-13 16:31:52
文章被收录于专栏：我的充电站
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这题还是比较直接的，就是先按照奇偶性取出元素，然后分别进行排序之后进行重组即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def sortEvenOdd(self, nums: List[int]) -> List[int]:
n = len(nums)
odd = sorted(nums[1::2], reverse=True)
even = sorted(nums[::2])
for i, x in enumerate(even):
nums[2*i] = x
for i, x in enumerate(odd):
nums[2*i+1] = x
return nums提交代码评测得到：耗时48ms，占用内存13.8MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题的思路其实就是取出每一位上的数字，然后进行排序即可，唯一需要注意的是需要根据正负条件以及开头是否为0进行一下边界条件处理即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def smallestNumber(self, num: int) -> int:
is_positive = True
if num == 0:
return 0
elif num < 0:
num = -num
is_positive = False
digits = []
while num != 0:
digits.insert(0, num % 10)
num = num // 10
if is_positive:
digits = sorted(digits)
idx = 0
while digits[idx] == 0:
idx += 1
digits[idx], digits[0] = digits[0], digits[idx]
else:
digits = sorted(digits, reverse=True)
res = 0
for d in digits:
res = res*10 + d
return res if is_positive else -res提交代码评测得到：耗时61ms，占用内存13.9MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这题其实挺简单的，只需要记录一下长度为size的字符串即可，但是需要注意的是，由于存在count和flip操作，因此，为了优化执行效率，我们额外再保存一下原序列的逆序列，并用cnt来记录序列当中1的数目，从而可以优化count和flip的执行效率。
2. 代码实现
给出python代码实现如下：
class Bitset:
def __init__(self, size: int):
self.bits = ["0" for _ in range(size)]
self.rbits = ["1" for _ in range(size)]
self.cnt = 0
self.size = size
def fix(self, idx: int) -> None:
if self.bits[idx] == "0":
self.cnt += 1
self.bits[idx] = "1"
self.rbits[idx] = "0"
def unfix(self, idx: int) -> None:
if self.bits[idx] == "1":
self.cnt -= 1
self.bits[idx] = "0"
self.rbits[idx] = "1"
def flip(self) -> None:
self.bits, self.rbits = self.rbits, self.bits
self.cnt = self.size - self.cnt
def all(self) -> bool:
return self.cnt == self.size
def one(self) -> bool:
return self.cnt > 0
def count(self) -> int:
return self.cnt
def toString(self) -> str:
return "".join(self.bits)提交代码评测得到：耗时1069ms，占用内存45.7MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题的解题思路的话我的想法是说首先假设所有的元素都是属于中间位置的，那么耗时就是1的个数乘上2，然后考察两侧删除的情况。
此时，某一侧删除的元素是0，那么较之之前的情况就会增加一个耗时，反之就会减少一个耗时，然后对于某一个位置，我们要找的就是左侧最优的删除状况加上右侧最优的删除状况，然后对原来的结果进行修正即可。
整体而言，代码的算法复杂度是
。
2. 代码实现
给出python代码实现如下：
class Solution:
def minimumTime(self, s: str) -> int:
cnt = 0
for ch in s:
if ch == "1":
cnt += 1
tot = 2*cnt
n = len(s)
l2r = [0 for _ in range(n+1)]
for i in range(n):
l2r[i+1] = l2r[i] + 1 if s[i] == "0" else l2r[i] - 1
r2l = [0 for _ in range(n+1)]
for i in range(n-1, -1, -1):
r2l[i] = r2l[i+1] + 1 if s[i] == "0" else r2l[i+1] - 1
for i in range(n):
l2r[i+1] = min(l2r[i+1], l2r[i])
r2l[n-i-1] = min(r2l[n-i-1], r2l[n-i])
res = tot + min([x + y for x, y in zip(l2r, r2l)])
return res提交代码评测得到：耗时7526ms，占用内存39.7MB。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022/02/06 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
