LeetCode Weekly Contest 232 Report

#232 Contest.

1790. Check if One String Swap Can Make Strings Equal

Account Login - LeetCode

Note the two indices not equal and check if a swap can make them equal.

class Solution:
    def areAlmostEqual(self, s1: str, s2: str) -> bool:
        if s1 == s2:
            return True
        i1, i2 = -1, -1
        for i in range(len(s1)):
            if s1[i] != s2[i]:
                if i1 == -1:
                    i1 = i
                elif i2 == -1:
                    i2 = i
                else:
                    return False
        
        return s1[i1] == s2[i2] and s1[i2] == s2[i1]

1791. Find Center of Star Graph

Account Login - LeetCode

Check the common node of any two edges.

class Solution:
    def findCenter(self, es: List[List[int]]) -> int:
        return list(set(es[0]) & set(es[1]))[0]

1792. Maximum Average Pass Ratio

Account Login - LeetCode

Sort the classes by their “contribution”s to the sum of their ratio. I failed several times at the beginning by sorting by their derivative:

Quotient rule

It is obvious that you should never think too much.

from queue import PriorityQueue
class Solution:
    def maxAverageRatio(self, cs: List[List[int]], e: int) -> float:
        if len(cs) == 1:
            return min((cs[0][0] + e) / (cs[0][1] + e), 1)
        
        pq = PriorityQueue()
        for a, b in cs:
            pq.put((-(a + 1) / (b + 1) + (a / b), a, b))
        
        for _ in range(e):
            _, a, b = pq.get()
            a, b = a + 1, b + 1
            pq.put((-(a + 1) / (b + 1) + (a / b), a, b))
        
        return sum(a / b for _, a, b in pq.queue) / len(pq.queue)

1793. Maximum Score of a Good Subarray

Account Login - LeetCode

Use two pointers. Each time try to broader the boundary and update the current result.

class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        i, j, res, curMin = k, k, nums[k], nums[k]
        while i > 0 or j < len(nums) - 1:
            if i == 0:
                j += 1
            elif j == len(nums) - 1:
                i -= 1
            elif nums[i - 1] < nums[j + 1]:
                j += 1
            else:
                i -= 1
            
            curMin = min(curMin, nums[i], nums[j])
            
            while i > 0 and nums[i - 1] >= curMin:
                i -= 1
            while j < len(nums) - 1 and nums[j + 1] >= curMin:
                j += 1
            
            res = max(res, curMin * (j - i + 1))
        
        return res