leetcode277周赛

竞赛链接

T1: 5989. 元素计数

---

思路

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

Code

class Solution {
public:
    int countElements(vector<int>& nums) {
        int sum=0,mi=INT_MAX,ma=INT_MIN;
        sort(nums.begin(),nums.end());
        for(auto& i:nums){
            mi=min(mi,i);
            ma=max(ma,i);
        }
        for(auto& i:nums){
            if(i!=mi&&i!=ma)
                sum++;
        }
        return sum;
    }
};

复杂度分析

时间复杂度：O((N))
空间复杂度：O((1))

T2: 5991. 按符号重排数组

---

思路

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

Code

class Solution {
public:
    vector<int> rearrangeArray(vector<int>& nums) {
        vector<int>a,b;
        int n=nums.size()/2;
        for(auto& i:nums){
            if(i>0)
                a.emplace_back(i);
            else
                b.emplace_back(i);
        }
        vector<int>ans;
        int l=0,r=0;
        while(r<n){
            ans.emplace_back(a[l++]);
            ans.emplace_back(b[r++]);
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：O((N))
• 空间复杂度：O((N))

T3: 5990. 找出数组中的所有孤独数字

---

思路

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

Code

class Solution {
public:
    unordered_map<int,int>ha;
    vector<int> findLonely(vector<int>& nums) {
        for(auto& i:nums){
            ha[i]++;
        }
        vector<int>ans;
        for(auto& i:nums){
            if(!ha.count(i-1)&&!ha.count(i+1)&&ha[i]==1)
                ans.emplace_back(i);
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：O((N))
• 空间复杂度：O((N))

T4: 5992. 基于陈述统计最多好人数

---

思路

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

Code

class Solution {
public:
    int maximumGood(vector<vector<int>> &statements) {
        int ans = 0, n = statements.size();
        for (int i = 1; i < 1 << n; ++i) {    //二进制枚举-枚举每一个状态
            int cnt = 0;   // i 中好人个数
            for (int j = 0; j < n; ++j) {
                if ((i >> j) & 1) { // 枚举 i 中的好人j （//枚举该状态下二进制的每一位数值）
                    for (int k = 0; k < n; ++k) { // 枚举 j 的所有陈述
                        if (statements[j][k] < 2 && statements[j][k] != ((i >> k) & 1)) { // 该j的陈述与i的实际情况矛盾
                            goto next;  //跳出循环
                        }
                    }
                    ++cnt;
                }
            }
            ans = max(ans, cnt);
            next:;
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：O(
  (2^N*N^2))
• 空间复杂度：O((1))

额外拓展

二进制枚举

个人总结

---

本次周赛，t1 t2 t3全是大水题，t4一直在暴力，但没有从二进制枚举的角度考虑，吸取教训