LeetCode第275场周赛

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

题目描述：给你一个\(n \times n\)的矩阵，判断是否其每一行和每一列都包含从\(1\sim n\)的全部整数，是返回true，否则返回false。

思路：直接根据题意模拟即可

时间复杂度：\(O(n^2)\)

参考代码：

class Solution {
public:
    bool checkValid(vector<vector<int>>& matrix) {
        int n = matrix.size();
        //检验行是否满足
        for(int i = 0 ; i < n ; ++i){
            vector<int> cnt(n , 1);
            for(int num : matrix[i]){
                if(--cnt[num - 1] < 0) return false;
            }
        }
        //检验列
        for(int j = 0 ; j < n ; ++j){
            vector<int>cnt(n , 1);
            for(int i = 0 ; i < n ; ++i){
                if(--cnt[matrix[i][j] - 1] < 0) return  false;
            }
        }
        return true;
    }
};
           

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

题目描述：交换定义为选中一个数组中的两个互不相同的位置并交换二者的值。环形 数组是一个数组，可以认为 第一个 元素和 最后一个 元素 相邻 。给你一个 二进制环形数组 \(nums\) ，返回在任意位置将数组中的所有\(1\)聚集在一起需要的最少交换次数。

思路：显然答案只有0011100和11000111两种形式，对于第二种相当于在非环形数组中将0聚合。对于非环形数组中的聚合，所需要的最小次数就是总的1的个数减去一个窗口内1的个数，这个窗口的长度为\(1\)的个数。

时间复杂度：\(O(n)\)

空间复杂度：\(O(n)\)

class Solution {
private:
    int solve(vector<int>& nums){
        int n = nums.size() , cnt = 0;
        for(auto num : nums) cnt += num == 1;
        int res = n, presum = 0;
        for(int i = 0 ; i < n ; ++i){
            presum += nums[i] == 1;
            if(i >= cnt) presum -= nums[i - cnt] == 1;
            if(i >= cnt - 1) res = min(res , cnt - presum);
        }
        return res;
    }
public:
    int minSwaps(vector<int>& nums) {
        int res = solve(nums);
        for(auto& num : nums) num^= 1;
        res = min(res, solve(nums));
        return res;
    }
};
           

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

题目描述：给你两个下标从 0 开始的字符串数组

startWords

和

targetWords

。每个字符串都仅由 小写英文字母 组成。对于

targetWords

中的每个字符串，检查是否能够从

startWords

中选出一个字符串，执行一次 转换操作 ，得到的结果与当前

targetWords

字符串相等。

转换操作为：添加一个当前未在该字符串中出现的字符，然后添加到其末尾。然后进行任意的重排。

找出

targetWords

中有多少字符串能够由

startWords

中的 任一 字符串执行上述转换操作获得。返回

targetWords

中这类 字符串的数目 。

思路：显然可以将

startWords

中的所有的字符串所能转换的字符串全部枚举出来，然后按照字符从小到大排序插入

set

中。然后遍历

targetWords

，将其中的字符串从小到大排序后去集合中查找，设字符集的大小为\(\sum\) 则此方法的时间复杂度为：\(O(26\sum log\sum)\) 且常数巨大，实测中超时最后一个点。考虑优化，注意到每个字符串中每个字符只出现了一次，且只有

26

种字符，所以考虑使用二进制表示每一个字符，一个字符串就是一个\(int\)类型的整数。假设有\(n\)个字符串，则这样做的时间复杂度为：\(O(\sum + 26\times nlogn)\) 可以通过此题。

时间复杂度：\(O(\sum + 26 \times nlogn)\)

class Solution {
public:
    int wordCount(vector<string>& startWords, vector<string>& targetWords) {
        set<int> s;
        for(auto& str : startWords){
            vector<int> cnt(26 , 0);
            for(auto c : str) cnt[c - 'a']++;
            int dx = 0;
            for(int i = 0 ; i < 26 ; ++i) if(cnt[i]) dx |= 1 << i;
            for(int i = 0 ; i < 26 ; ++i){
                if(cnt[i]) continue;
                int dy = dx + (1 << i);
                s.insert(dy);
            }
        }
        int res = 0;
        for(auto& str : targetWords){
            vector<int> cnt(26 , 0);
            for(auto c : str) cnt[c - 'a']++;
            int dx = 0;
            for(int i = 0 ; i < 26 ; ++i) if(cnt[i]) dx |= 1 << i;
            if(s.find(dx) != s.end()) ++res;
        }
        return res;
    }
};
           

未优化时的代码：

class Solution {
public:
    int wordCount(vector<string>& startWords, vector<string>& targetWords) {
        set<string> s;
        for(auto& str : startWords){
            vector<int> cnt(26 , 0);
            for(auto c : str) cnt[c - 'a']++;
            for(int i = 0 ; i < 26 ; ++i){
                if(cnt[i]) continue;
                string t = str;
                t += 'a' + i;
                sort(t.begin() , t.end());
                s.insert(t);
            }
        }
        int res = 0;
        for(auto& str : targetWords){
            sort(str.begin() , str.end());
            if(s.find(str) != s.end()) ++res;
        }
        return res;
    }
};
           

5979. 全部开花的最早一天

题目描述：给你\(n\) 枚种子。每枚种子必须先种下，才能开始生长、开花。播种需要时间，种子的生长也是如此。给你两个下标从\(0\)开始的整数数组

plantTime

growTime

，每个数组的长度都是 \(n\) ：

• plantTime[i]

  是 播种 第\(i\)枚种子所需的 完整天数 。每天，你只能为播种某一枚种子而劳作。无须 连续几天都在种同一枚种子，但是种子播种必须在你工作的天数达到

  plantTime[i]

  之后才算完成。

• growTime[i]

  是第

  i

  枚种子完全种下后生长所需的 完整天数 。在它生长的最后一天 之后 ，将会开花并且永远 绽放 。

从第\(0\)天开始，你可以按任意顺序播种种子，求所有种子都开花的最早的时间。

思路：显然要使时间尽量早，那么就需要让当前播种的种子的播种时间和前面已经完成播种的种子的生长时间尽可能多的重合。故应将生长时间长的种子放在前面，也即按照种子的生长时间从大到小排序，然后进行播种即可。

时间复杂度：\(O(nlogn)\)

class Solution {
public:
    int earliestFullBloom(vector<int>& plantTime, vector<int>& growTime) {
        vector<pair<int , int>> nums;
        int n = plantTime.size();
        for(int i = 0 ; i < n ; ++i){
            nums.push_back({plantTime[i] , growTime[i]});
        }
        std::sort(nums.begin() , nums.end() , [&](const pair<int , int>& a , const pair<int , int>& b){
            return a.second > b.second;
        });
        int res = 0, curTime = 0;
        for(auto& num : nums){
            res = max(res , curTime + num.first + num.second);
            curTime += num.first;
        }
        return res;
    }
};