LeetCode笔记：Weekly Contest 279_2165. smallest value of the rearranged number

• LeetCode笔记：Weekly Contest 279
  • 1. 题目一
    • 1. 解题思路
    • 2. 代码实现
  • 2. 题目二
    • 1. 解题思路
    • 2. 代码实现
  • 3. 题目三
    • 1. 解题思路
    • 2. 代码实现
  • 4. 题目四
    • 1. 解题思路
    • 2. 代码实现

1. 题目一

给出题目一的试题链接如下：

• 2164. Sort Even and Odd Indices Independently

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
1
2
3
4
5
6
7
8
9
10

提交代码评测得到：耗时48ms，占用内存13.8MB。

2. 题目二

给出题目二的试题链接如下：

• 2165. Smallest Value of the Rearranged Number

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

提交代码评测得到：耗时61ms，占用内存13.9MB。

3. 题目三

给出题目三的试题链接如下：

• 2166. Design Bitset

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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

提交代码评测得到：耗时1069ms，占用内存45.7MB。

4. 题目四

给出题目四的试题链接如下：

• 2167. Minimum Time to Remove All Cars Containing Illegal Goods

1. 解题思路

这一题的解题思路的话我的想法是说首先假设所有的元素都是属于中间位置的，那么耗时就是1的个数乘上2，然后考察两侧删除的情况。

此时，某一侧删除的元素是0，那么较之之前的情况就会增加一个耗时，反之就会减少一个耗时，然后对于某一个位置，我们要找的就是左侧最优的删除状况加上右侧最优的删除状况，然后对原来的结果进行修正即可。

整体而言，代码的算法复杂度是$O(N)$。

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

提交代码评测得到：耗时7526ms，占用内存39.7MB。