leetcode275周赛

竞赛链接

T1: 5976. 检查是否每一行每一列都包含全部整数

---

思路

模拟，按两种方式遍历数组，若都满足则返回true，否则返回false

Code

class Solution {
public:
    bool checkValid(vector<vector<int>>& ma) {
        int n=ma.size();

        for(int i=0;i<n;++i){  //从左到右遍历数组
            vector<bool>f(n+1,false);
            int cnt=0;
            for(int j=0;j<n;++j){
                if(f[ma[i][j]]==false)
                    cnt++,f[ma[i][j]]=true;
            }
            if(cnt!=n)
                return false;
        }

        for(int i=0;i<n;++i) {  //从上到下遍历数组
            vector<bool>f(n+1,false);
            int cnt=0;
            for(int j=0;j<n;++j){
                if(f[ma[j][i]]==false)
                    cnt++,f[ma[j][i]]=true;
            }
            if(cnt!=n)
                return false;
        }
        return true;
    }
};

复杂度分析

时间复杂度：O(n2)
空间复杂度：O(n)

T2: 5977. 最少交换次数来组合所有的 1 II

---

思路

前缀和或滑动窗口，窗口大小为数组中1的数量

Code

class Solution {
public:
    int minSwaps(vector<int>& nums) {
        int cnt=0,n=nums.size();
        int ma=-1;
        vector<int>ha(2*n+1,0);
        int len=2*n;
        vector<int>f=nums;
        for(auto& i:nums){   //因为首尾可以相连，所以这里将原数组*2
            f.emplace_back(i);
            if(i==1)
                cnt++;
        }
        for(int i=1;i<=2*n;++i)  //前缀和
            ha[i]=ha[i-1]+f[i-1];
        for(int i=0;i<=len-cnt;++i){
            ma=max(ma,ha[i+cnt]-ha[i]);
        }
        return abs(cnt-ma);
    }
};

复杂度分析

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

T3: 5978. 统计追加字母可以获得的单词数

---

思路

考虑 targetWords[i] 能否还原回 startWords 中的某个字符串。

由于可以任意重排，我们可以对 startWords 和 targetWords 的每个字符串都排序。

由于需要追加字符，且题目保证所有字符串都没有重复字符，因此我们可以枚举排序后的 targetWords[i] 的所有字符，将其去掉后去看看是否在每个字符串都排序后的 startWords 中存在。这可以用哈希表实现。

代码实现时，我们并不需要排序每个字符串，而是记录每个字符是否出现过，这可以用位运算实现。

Code

class Solution {
public:
    int wordCount(vector<string> &startWords, vector<string> &targetWords) {
        unordered_set<int> s;
        for (string &word : startWords) {
            int mask = 0;
            for (char ch : word) {
                mask |= 1 << (ch - 'a');
            }
            s.insert(mask);
        }
        int ans = 0;
        for (string &word : targetWords) {
            int mask = 0;
            for (char ch : word) {
                mask |= 1 << (ch - 'a');
            }
            for (int i = 0; i < 26; ++i) {
                if (mask & (1 << i) && s.count(mask ^ (1 << i))) { // 去掉这个字符
                    ++ans;
                    break;
                }
            }
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：O(m*n)，m为字符串中最多的字母类别数量
• 空间复杂度：O(n)

T4: 5979. 全部开花的最早一天

---

思路

贪心：先种生长时间长的，再种生长时间短的。

为什么这一贪心是正确的？

对于任意两盆花，假设第一盆的种植和生长时间为 (a, b)，第二盆的种植和生长时间为 (c,d)，且有 b>d。

暂时不考虑交错种植的情况。

• 先种一，再种二：总时间为 max(a+b,a+c+d)
• 先种二，再种一：总时间为 max(c+d,c+a+b)。因为 c+a+b>c+a+d>c+d，所以结果就为 c+a+b。
  二者对比，显然有 c+a+b>c+a+d 且 c+a+b>a+b。所以应该先种一。

下面考虑交错种植。我们可以发现，无论是几盆花发生交错，交错种植并不能让种植结束时间提前。所以在存在交错种植的情况下，我们总是可以按照种植结束时间的顺序，以无交错的方式进行种植，此时所有花的种植结束时间均不会比原来延后。在这样的情况下，结合上面的讨论，就说明我们的贪心策略确实是最优的。

Code

class Solution {
public:
    int earliestFullBloom(vector<int>& pl, vector<int>& gr) {
        vector<pair<int,int>>ha;
        int len=0,ma=INT_MIN,n=pl.size(),bo=-1;

        for(int i=0;i<n;++i){
            ha.emplace_back(make_pair(pl[i],gr[i]));
        }   
        sort(ha.begin(),ha.end(),[&](auto& a,auto& b){
            return a.second>b.second;
        });

        for(int i=0;i<n;++i){
            ma=max(ma,bo+ha[i].first+ha[i].second+1);
            bo+=ha[i].first;
        }
        return ma;
    }
};

复杂度分析

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

个人总结

---

本次周赛，前两题挺顺利的，t3的时候一整个卡住了，时候反思了下，题目没看完，给了很多提示点。。 t4还好，是一个贪心，大胆猜就完事了