Leetcode notes: Weekly contest 277

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

• 2148. Count Elements With Strictly Smaller and Greater Elements

1. Their thinking

This question is actually simple , Let's first merge the same elements , Then on unique The elements are sorted , Then take the middle elements and calculate the sum of their occurrence times .

2. Code implementation

give python The code implementation is as follows ：

class Solution:
    def countElements(self, nums: List[int]) -> int:
        cnt = Counter(nums)
        vals = sorted(cnt.items())
        return 0 if len(vals) <= 2 else sum(x[1] for x in vals[1:-1])

The submitted code was evaluated ： Time consuming 94ms, Take up memory 14.3MB.

2. Topic two

The link to question 2 is as follows ：

• 2149. Rearrange Array Elements by Sign

1. Their thinking

Our thinking on this question is very violent , Take out the positive and negative elements respectively and then merge them again .

However, a more elegant way can follow the example of fast sorting, and continuously sort elements with two pointers , But not here .

2. Code implementation

give python The code implementation is as follows ：

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        pos = [x for x in nums if x > 0]
        neg = [x for x in nums if x < 0]
        n = len(pos)
        res = [0 for _ in range(2*n)]
        for i in range(n):
            res[2*i] = pos[i]
            res[2*i+1] = neg[i]
        return res

The submitted code was evaluated ： Time consuming 1576ms, Take up memory 45.8MB.

3. Topic three

The link to question 3 is as follows ：

• 2150. Find All Lonely Numbers in the Array

1. Their thinking

Similarly, we only need to sort the original array to get our answer quickly .

2. Code implementation

give python The code implementation is as follows ：

class Solution:
    def findLonely(self, nums: List[int]) -> List[int]:
        n = len(nums)
        nums = [-2] + sorted(nums) + [10**7]
        res = []
        for i in range(1, n+1):
            if nums[i] - nums[i-1] <= 1 or nums[i+1] - nums[i] <= 1:
                continue
            res.append(nums[i])
        return res

The submitted code was evaluated ： Time consuming 1424ms, Take up memory 30.3MB.

4. Topic four

The link to question 4 is as follows ：

• 2151. Maximum Good People Based on Statements

1. Their thinking

Our idea of this problem is a violent depth first traversal , Examine each person's telling the truth and falsehood , Then investigate separately .

2. Code implementation

give python The code implementation is as follows ：

class Solution:
    def maximumGood(self, statements: List[List[int]]) -> int:
        n = len(statements)
        
        def dfs(idx, status):
            if idx >= n:
                return len([x for x in status if x >= 1])
            
            if status[idx] != 1:
                s = deepcopy(status)
                s[idx] = 0
                s1 = dfs(idx+1, s)
            else:
                s1 = 0
                
            def have_conflict(idx):
                return any(statements[idx][i] != 2 and status[i] != 2 and statements[idx][i] != status[i] for i in range(n))
            
            if status[idx] != 0:
                if have_conflict(idx):
                    return s1
                s = deepcopy(status)
                s[idx] = 1
                for i in range(n):
                    if statements[idx][i] != 2:
                        s[i] = statements[idx][i]
                s2 = dfs(idx+1, s)
            else:
                s2 = 0
            return max(s1, s2)
        
        res = dfs(0, [2 for _ in range(n)])
        return res              

The submitted code was evaluated ： Time consuming 2252ms, Take up memory 14.6MB.