Leetcode notes: Weekly contest 279

• LeetCode note ：Weekly Contest 279
  • 1. Topic 1
    • 1. Their thinking
    • 2. Code implementation
  • 2. Topic two
    • 1. Their thinking
    • 2. Code implementation
  • 3. Topic three
    • 1. Their thinking
    • 2. Code implementation
  • 4. Topic four
    • 1. Their thinking
    • 2. Code implementation

1. Topic 1

The link to question 1 is as follows ：

• 2164. Sort Even and Odd Indices Independently

1. Their thinking

This question is quite direct , Is to first take out the elements according to parity , Then sort them separately and reorganize them .

2. Code implementation

give python The code implementation is as follows ：

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

The submitted code was evaluated ： Time consuming 48ms, Take up memory 13.8MB.

2. Topic two

The link to question 2 is as follows ：

• 2165. Smallest Value of the Rearranged Number

1. Their thinking

The idea of this question is actually to take out the numbers in each digit , Then sort it , The only thing to note is that it needs to be based on the positive and negative conditions and whether the beginning is 0 Just deal with the boundary conditions .

2. Code implementation

give python The code implementation is as follows ：

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

The submitted code was evaluated ： Time consuming 61ms, Take up memory 13.9MB.

3. Topic three

The link to question 3 is as follows ：

• 2166. Design Bitset

1. Their thinking

This question is actually quite simple , Just record the length as size The string of , But here's the thing , Due to the existence count and flip operation , therefore , To optimize execution efficiency , Let's save the inverse sequence of the original sequence , And use cnt To record the sequence 1 Number of , This can optimize count and flip Efficiency of execution .

2. Code implementation

give python The code implementation is as follows ：

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)

The submitted code was evaluated ： Time consuming 1069ms, Take up memory 45.7MB.

4. Topic four

The link to question 4 is as follows ：

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

1. Their thinking

My idea is to first assume that all elements belong to the middle position , So time consuming is 1 Multiply the number of 2, Then examine the deletion on both sides .

here , The element deleted on one side is 0, Then it will be more time-consuming than before , On the contrary, it will reduce a time-consuming , Then for a certain location , What we are looking for is the optimal deletion condition on the left plus the optimal deletion condition on the right , Then correct the original result .

As a whole , The algorithm complexity of the code is $O(N)$.

2. Code implementation

give python The code implementation is as follows ：

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

The submitted code was evaluated ： Time consuming 7526ms, Take up memory 39.7MB.