跳到主要内容

第 277 场周赛

Problem A - 元素计数​

方法一：模拟​

只要不是最小值或最大值，就是符合要求的数。

  • 时间复杂度 O(N)\mathcal{O}(N)。
  • 空间复杂度 O(N)\mathcal{O}(N)。
参考代码（Python 3）
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])

Problem B - 按符号重排数组​

方法一：模拟​

将正数和负数分为两组，然后构造结果即可。

  • 时间复杂度 O(N)\mathcal{O}(N)。
  • 空间复杂度 O(N)\mathcal{O}(N)。
参考代码（Python 3）
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)]))

Problem C - 找出数组中的所有孤独数字​

方法一：哈希表​

哈希表计数之后逐个判断即可。

  • 时间复杂度 O(N)\mathcal{O}(N)。
  • 空间复杂度 O(N)\mathcal{O}(N)。
参考代码（Python 3）
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]

Problem D - 基于陈述统计最多好人数​

方法一：枚举​

二进制枚举哪几个是好人，之后判断是否存在矛盾。

  • 时间复杂度O(N2⋅2N)\mathcal{O}(N^2\cdot2^N)
  • 空间复杂度O(1)\mathcal{O}(1)
参考代码（C++）
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;
    }
};