Leetcode 第 373 场周赛题解

Leetcode 第 373 场周赛题解

题目1：2946. 循环移位后的矩阵相似检查

思路

设矩阵的行数和列数分别为 m 和 n。

由于循环左移 n 次等价于循环左移 0 次，循环左移 n+1 次等价于循环左移 1 次，…，可以让 k = k%n，结果一样。

如果此时 k=0，那么操作不会影响矩阵，直接返回 true。

否则，直接按题意模拟即可。

代码

/*
 * @lc app=leetcode.cn id=2946 lang=cpp
 *
 * [2946] 循环移位后的矩阵相似检查
 */

// @lc code=start
class Solution
{
public:
    bool areSimilar(vector<vector<int>> &mat, int k)
    {
        if (mat.empty())
            return false;
        int m = mat.size(), n = m ? mat[0].size() : 0;
        k = k % n;
        if (k == 0)
            return true;
        for (int i = 0; i < m; i++)
        {
            if (i % 2)
            {
                for (int j = 0; j < n; j++)
                    if (mat[i][(j + k) % n] != mat[i][j])
                        return false;
            }
            else
            {
                for (int j = 0; j < n; j++)
                    if (mat[i][(j + n - k) % n] != mat[i][j])
                        return false;
            }
        }
        return true;
    }
};
// @lc code=end

复杂度分析

时间复杂度：O(m*n)其中 m 和 n 分别是矩阵 mat 的行数和列数。

空间复杂度：O(1)。

题目2：2947. 统计美丽子字符串 I

思路

暴力枚举每个子字符串的开头 i，令 j=i 并一路直达字符串 s 的末尾。

在这个过程中，设当前字符为 c = s[i]，设置 vowels 和 consonants 统计元音字符和非元音字符的个数。

每当满足 vowels == consonants && (vowels * consonants) % k == 0 条件，说明 s[i…j] 是一个非空美丽子字符串，计数器 count 自增 1。

最后返回 count 即为答案。

代码

/*
 * @lc app=leetcode.cn id=2947 lang=cpp
 *
 * [2947] 统计美丽子字符串 I
 */

// @lc code=start
class Solution
{
public:
    int beautifulSubstrings(string s, int k)
    {
        int len = s.length(), count = 0;
        for (int i = 0; i < len; i++)
        {
            int vowels = 0, consonants = 0;
            for (int j = i; j < len; j++)
            {
                if (isVowels(s[j]))
                    vowels++;
                else
                    consonants++;
                if (vowels == consonants && (vowels * consonants) % k == 0)
                    count++;
            }
        }
        return count;
    }
    // 辅函数 - 判断字符 c 是否是元音字母
    bool isVowels(const char &c)
    {
        if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
            return true;
        return false;
    }
};
// @lc code=end

复杂度分析

时间复杂度：O(len²)，其中 len 是字符串 s 的长度。

空间复杂度：O(1)。

题目3：

思路

代码

在这里插入代码片

复杂度分析

时间复杂度：O()。

空间复杂度：O()。

题目4：

思路

代码

在这里插入代码片

复杂度分析

时间复杂度：O()。

空间复杂度：O()。