LeetCode Weekly Contest 236 Report

#236 Contest.

1822. Sign of the Product of an Array

Account Login - LeetCode

Not much to say, break if 0 else find negative.

class Solution:
    def arraySign(self, nums: List[int]) -> int:
        res = 1
        for num in nums:
            if num == 0:
                return 0
            res *= 1 if num > 0 else -1
        return res

1823. Find the Winner of the Circular Game

Account Login - LeetCode

This gives me a feeling the circle can be break into a line, and repeat itself, which may lead to a better solution…but I did not figure out one. So I thought about write a brutal force and optimize.

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        l, last = [i + 1 for i in range(n)], 0
        while n > 1:
            cur = (last + k - 1) % n
            l.pop(cur)
            last = cur
            n -= 1
        return l[0]

However LeetCode did not let me TLE…I move forwarded…

1824. Minimum Sideway Jumps

Account Login - LeetCode

The question itself is telling you a DP story. Depends on if there is obstacle, the step to a place can be the previous step or jump from another lane. Otherwise assign it a INF, we can use min to remove it after all.

INF = 6 * (10 ** 5)
class Solution:
    def minSideJumps(self, obs: List[int]) -> int:
        last = [1, 0, 1]
        for i in range(1, len(obs) - 1):
            ob = obs[i]
            cur = last[:]
            if ob == 0:
                cur = [min(last[0], last[1] + 1, last[2] + 1), min(last[1], last[0] + 1, last[2] + 1), min(last[1] + 1, last[2], last[0] + 1)]
            elif ob == 1:
                cur[0] = INF
                cur[1] = min(last[1], last[2] + 1)
                cur[2] = min(last[2], last[1] + 1)
            elif ob == 2:
                cur[1] = INF
                cur[0] = min(last[0], last[2] + 1)
                cur[2] = min(last[2], last[0] + 1)
            else:
                cur[2] = INF
                cur[0] = min(last[0], last[1] + 1)
                cur[1] = min(last[1], last[0] + 1)
            last = cur[:]
        return min(last)

1825. Finding MK Average

Account Login - LeetCode

I know there is are more elegant solutions, like using a queue, maybe, I still don’t know why this is a “hard” problem. I wrote as the problem described and it got accepted.

class MKAverage:
    def __init__(self, m: int, k: int):
        self.m, self.k = m, k
        self.l = []
    def addElement(self, num: int) -> None:
        self.l.append(num)
    def calculateMKAverage(self) -> int:
        if len(self.l) < self.m:
            return -1
        
        l1 = sorted(self.l[len(self.l) - self.m:])[self.k:self.m - self.k]
        return int(sum(l1) / len(l1))