Week 269 race

The topic is very simple. There are only three questions, and the fourth one is a little short.

I'm still too good. I'll continue to work hard to train my thinking and speed.

5938. Find the target subscript after array sorting

class Solution(object):
    def targetIndices(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        ans = []
        nums.sort()
        for i, w in enumerate(nums):
            if w == target:
                ans.append(i)
        return ans

I forgot to save the previous and wrote it again, mainly to deepen the newly learned sentences:

for i, w in enumerate(nums):
# i indicates array subscript
# w represents the value corresponding to the array subscript
# enumerate enumeration

5939. Average value of subarray with radius k

class Solution(object):
    def getAverages(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        ans = [0] * len(nums)
        
        # Traversal nums
        for i, w in enumerate(nums):
            if i - k < 0 or i + k >= len(nums):
                ans[i] = -1
            else:
                ans[i] = sum(nums[i - k : i + k + 1]) // (2 * k + 1)
        return ans

A = Solution()
print(A.getAverages([7,4,3,9,1,8,5,2,6], 3)) # [-1,-1,-1,5,4,4,-1,-1,-1]
print(A.getAverages([1000], 0)) #1000
print(A.getAverages([8], 10000))

This is my first edition. It obviously times out and unnecessarily repeats the summation calculation

The abuse of division in the second edition leads to a difference of one

Lessons learned: if you need to divide or round down these things, try to use them only once, that is, when obtaining the final result
W n e w = W o l d − L e f t + R i g h t a n s = [ W n e w 2 × k + 1 ] W_{new} = W_{old} - Left + Right \\ ans = [\frac{W_{new}}{2\times k + 1}] Wnew​=Wold​−Left+Rightans=[2×k+1Wnew​​]
Left represents the leftmost number of the last time, and Right represents the rightmost number of this time

class Solution(object):
    def getAverages(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        ans = [0] * len(nums)
        temp = -1  # Store last value
        num = 0 # Last left boundary point
        # Traversal nums
        for i, w in enumerate(nums):
            if i - k < 0 or i + k >= len(nums):
                ans[i] = -1
            elif temp == -1:
                temp = sum(nums[i - k : i + k + 1])
                num = nums[i - k]
                ans[i] = temp // (2 * k + 1)
            else:
                temp = temp + nums[i + k] - num
                ans[i] = temp // (2 * k + 1)
                num = nums[i - k]
        return ans

A = Solution()
print(A.getAverages([7,4,3,9,1,8,5,2,6], 3)) # [-1,-1,-1,5,4,4,-1,-1,-1]
print(A.getAverages([1000], 0)) #1000
print(A.getAverages([56725,48784,74934,6772,98570,96847,46483,6592,62552], 1))
print(A.getAverages([40527,53696,10730,66491,62141,83909,78635,18560], 2))

5940. Remove the maximum and minimum values from the array

What I did myself was traversal about twice without saving, but I don't want to review it again, because it was written blindly, although it passed

I look at the thinking of the big guys. I look at Lingcha mountain AI house

The reason why a big man is a big man is to think and speed up his hands~

Greedy Algorithm

• Delete them together in the front. Delete them once
• Delete them together later. Delete them once
• One at the front and one at the back. Delete them separately and add up the steps

The difficulty is how to express it in code

It needs to be expressed in mathematical language before doing the problem

Assume that the array length is n n n. Minimum at i i i. Maximum at j j j. And i < = j i<=j If I < = J, delete them respectively according to the above three cases

• j + 1 j+1 j+1
• n − i n-i n−i
• i + 1 + n − j i + 1 + n - j i+1+n−j

Take the minimum of the three

class Solution(object):
    def minimumDeletions(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # Extract extreme value and its index
        Min = min(nums)
        Max = max(nums)
        minIndex = nums.index(Min)
        maxIndex = nums.index(Max)
        
        # Exchange two values if necessary in order to be consistent with the mathematical language
        if minIndex > maxIndex:
            maxIndex, minIndex = minIndex, maxIndex
            
        # Calculate the values of the three strategies
        step = [0, 0, 0]
        step[0] = maxIndex + 1
        step[1] = len(nums) - minIndex
        step[2] = minIndex + 1 + len(nums) - maxIndex
        return min(step)

Lessons learned: the first question is usually given points and written directly. The best thing for question 23 is to think clearly about the mathematical principle, then think about how to express it in program language, and finally move the handwritten code.

5941. Identify all experts who know the secret

class Solution(object):
    def findAllPeople(self, n, meetings, firstPerson):
        """
        :type n: int
        :type meetings: List[List[int]]
        :type firstPerson: int
        :rtype: List[int]
        """
        ans = []
        def takeThird(elem):
            return elem[2]
        meetings.sort(key = takeThird)
        isKnow = [0] * n
        isKnow[0] = 1
        isKnow[firstPerson] = 1
        for lis in meetings:
            if isKnow[lis[0]] == 1 or isKnow[lis[1]] == 1:
                isKnow[lis[0]] = 1
                isKnow[lis[1]] = 1
        for i, w in enumerate(isKnow):
            if w == 1:
                ans.append(i)
        return ans

Only 37 / 42 passed, without considering simultaneity

def takeThird(elem):
    return elem[2]
meetings.sort(key = takeThird)
# Indicates sorting in ascending order by the third column of the 2D list

Leave it empty until I learn and check the collection and BFS