# # Leetcode 第277场周赛题解

## # Problem A - 元素计数 (opens new window)

### # 方法一：模拟

• 时间复杂度 $\mathcal{O}(N)$
• 空间复杂度 $\mathcal{O}(N)$

class Solution:
def countElements(self, nums: List[int]) -> int:
lo, hi = min(nums), max(nums)
return len([num for num in nums if num != lo and num != hi])

1
2
3
4

## # Problem B - 按符号重排数组 (opens new window)

### # 方法一：模拟

• 时间复杂度 $\mathcal{O}(N)$
• 空间复杂度 $\mathcal{O}(N)$

class Solution:
def rearrangeArray(self, nums: List[int]) -> List[int]:
pos = [num for num in nums if num > 0]
neg = [num for num in nums if num < 0]
return list(itertools.chain(*[[p, n] for p, n in zip(pos, neg)]))

1
2
3
4
5

## # Problem C - 找出数组中的所有孤独数字 (opens new window)

### # 方法一：哈希表

• 时间复杂度 $\mathcal{O}(N)$
• 空间复杂度 $\mathcal{O}(N)$

class Solution:
def findLonely(self, nums: List[int]) -> List[int]:
cnt = collections.Counter(nums)
return [num for num in nums if cnt[num] == 1 and (num - 1) not in cnt and (num + 1) not in cnt]

1
2
3
4

## # Problem D - 基于陈述统计最多好人数 (opens new window)

### # 方法一：枚举

• 时间复杂度$\mathcal{O}(N^2\cdot2^N)$
• 空间复杂度$\mathcal{O}(1)$

class Solution {
public:
int maximumGood(vector<vector<int>>& s) {
int n = s.size();
int ans = 0;
for (int i = (1 << n) - 1; i >= 0; --i) {
int m = __builtin_popcount(i);
if (m < ans)
continue;
bool valid = true;
for (int j = 0; j < n; ++j) {
if (i & (1 << j)) {
for (int k = 0; k < n; ++k) {
if ((s[j][k] == 0 && ((i & (1 << k)) > 0)) || (s[j][k] == 1 && ((i & (1 << k)) == 0))) {
valid = false;
break;
}
}
}
if (!valid)
break;
}
if (valid)
ans = max(ans, m);
}
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28