Leetcode LC-Contest

Weekly Contest 269

Leetcode 2089, 2090, 2091, 2092

Sailorlqh
2021-11-28
3 min

# Weekly Contest 269

# 2089. Find Target Indices After Sorting Array

# Solution

class Solution:
    def targetIndices(self, nums: List[int], target: int) -> List[int]:
        nums.sort()
        res = []
        for i in range(len(nums)):
            if nums[i] > target:
                break
            if nums[i] == target:
                res.append(i)
        return res

# 2090. K Radius Subarray Averages

2090. K Radius Subarray Averages

class Solution:
    def getAverages(self, nums: List[int], k: int) -> List[int]:
        curSum = 0
        length = 2*k + 1
        if len(nums) < length:
            return [-1 for i in range(len(nums))]
        res = [0 for i in range(len(nums))]
        for i in range(length -1):
            curSum += nums[i]
            if i < k:
                res[i] = -1
        for i in range(k, len(nums) - k):
            curSum += nums[i+k]
            res[i] = curSum // length
            if i == len(nums) - k:
                break
            curSum -= nums[i-k]
        for i in range(len(nums) - k, len(nums)):
            res[i] = -1
        return res

# Leetcode 2091. Removing Minimum and Maximum From Array

2091. Removing Minimum and Maximum From Array

class Solution:
    def minimumDeletions(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 1
        minIndex, minValue = 0, 10**6
        maxIndex, maxValue = 0, -10**6
        length = len(nums)
        for i in range(len(nums)):
            if nums[i] < minValue:
                minValue = nums[i]
                minIndex = i
            if nums[i] > maxValue:
                maxValue = nums[i]
                maxIndex = i
        if minIndex > maxIndex:
            maxIndex, minIndex = minIndex, maxIndex
        print(minIndex, maxIndex, len(nums), maxIndex + 1, len(nums) - minIndex, minIndex + 1 + len(nums) - maxIndex)
        res = min(maxIndex + 1, len(nums) - minIndex, minIndex + 1 + len(nums) - maxIndex)
        return res
        

# Leetcode 2092 Find All People With Secret

2092. Find All People With Secret

Contruct and use union find to find the solution.

class Solution:
    def findAllPeople(self, n: int, meetings: List[List[int]], firstPerson: int) -> List[int]:
        group = [i for i in range(n)]
        meetings.append([0, firstPerson, 0])
        meetings.sort(key=lambda x: x[2])

        def union(p1, p2):
            g1 = find(p1)
            g2 = find(p2)
            group[g2] = g1


        def find(p):
            if group[p] == p: return group[p]
            else:
                g = find(group[p])
                group[p] = g
                return g

        i = 0
        while i < len(meetings):
            known = []
            in_queue = [meetings[i]]
            i += 1

            while i < len(meetings):
                if meetings[i][-1] == in_queue[-1][-1]:
                    in_queue.append(meetings[i])
                    i += 1
                else: break
            for m in in_queue:
                p1 = m[0]
                p2 = m[1]
                if find(p1) == 0:
                    union(p1, p2)
                elif find(p2) == 0:
                    union(p2, p1)
                else:
                    union(p1, p2)
                known.append(p1)
                known.append(p2)
            for p in known:
                if find(p) != 0:
                    group[p] = p

        return [i for i in range(n) if find(i) == 0]