Leetcode notes: Weekly contest 275

• LeetCode note ：Weekly Contest 275
  • 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 ：

• 2133. Check if Every Row and Column Contains All Numbers

1. Their thinking

There is nothing to say about this problem , Just check it according to the meaning of the topic .

2. Code implementation

give python The code implementation is as follows ：

class Solution:
    def checkValid(self, matrix: List[List[int]]) -> bool:
        n = len(matrix)
        if any(len(set(l)) != n for l in matrix):
            return False
        if any(len(set([matrix[j][i] for j in range(n)])) != n for i in range(n)):
            return False
        return True

The submitted code was evaluated ： Time consuming 854ms, Take up memory 14.7MB.

2. Topic two

The link to question 2 is as follows ：

• 2134. Minimum Swaps to Group All 1’s Together II

1. Their thinking

This question is more or less a clever one , Because the final exchange result must be a series of 1 And the rest 0, that , We just need to investigate 1 Total of （ Remember as l）, Then look at all the lengths l Among the continuous substrings of 0 The number of , The number is the number of times to exchange .

Then we go to a minimum value .

2. Code implementation

give python The code implementation is as follows ：

class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        n, s = len(nums), sum(nums)
        nums = [0] + nums + nums[:s]
        accum = list(accumulate(nums))
        return min(s - (accum[i+s] - accum[i]) for i in range(n))

The submitted code was evaluated ： Time consuming 1324ms, Take up memory 25.9MB.

3. Topic three

The link to question 3 is as follows ：

• 2135. Count Words Obtained After Adding a Letter

1. Their thinking

I don't have any good ideas for the time being , Just use one 26 An array of dimensions to express each word , Each dimension represents the number of times its corresponding letter appears , And let's see target Is the word that appears after deleting a character for each word in startwords among .

2. Code implementation

give python The code implementation is as follows ：

class Solution:
    def wordCount(self, startWords: List[str], targetWords: List[str]) -> int:
        starts = set()
        for w in startWords:
            s = [0 for _ in range(26)]
            for ch in w:
                s[ord(ch) - ord('a')] += 1
            starts.add(tuple(s))
        
        res = 0
        for w in targetWords:
            s = [0 for _ in range(26)]
            for ch in w:
                s[ord(ch) - ord('a')] += 1
            for i in range(26):
                if s[i] > 0:
                    s[i] -= 1
                    if tuple(s) in starts:
                        res += 1
                        break
                    s[i] += 1
        return res

The submitted code was evaluated ： Time consuming 2088ms, Take up memory 37.8MB.

4. Topic four

The link to question 4 is as follows ：

• 2136. Earliest Possible Day of Full Bloom

1. Their thinking

This question feels a little watery , I used a greedy algorithm , Obviously all the watering time is necessary , What can be reduced is the growth time , So we arrange them in reverse chronological order , Then plant in turn , After that, just look at the shortest time required for each flower to grow .

2. Code implementation

give python The code implementation is as follows ：

class Solution:
    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:
        times = sorted(zip(plantTime, growTime), key=lambda x: (x[1], -x[0]), reverse=True)
        
        res = 0
        used = 0
        for pt, gt in times:
            res = max(res, used + pt + gt)
            used += pt
        return res

The submitted code was evaluated ： Time consuming 1959ms, Take up memory 41.5MB.