leetcode contest 373

T4 题目没有做出来，竟然没有想出来，前三题确实是水题。T4 是个不错的题目，需要值得注意与思考的题目。

946. 循环移位后的矩阵相似检查

给你一个下标从 0 开始且大小为 m x n 的整数矩阵 mat 和一个整数 k 。请你将矩阵中的 奇数 行循环 右 移 k 次，偶数 行循环 左 移 k 次。

如果初始矩阵和最终矩阵完全相同，则返回 true ，否则返回 false 。

示例 1：

输入：mat = [[1,2,1,2],[5,5,5,5],[6,3,6,3]], k = 2
输出：true
解释：


初始矩阵如图一所示。
图二表示对奇数行右移一次且对偶数行左移一次后的矩阵状态。
图三是经过两次循环移位后的最终矩阵状态，与初始矩阵相同。
因此，返回 true 。

示例 2：

输入：mat = [[2,2],[2,2]], k = 3
输出：true
解释：由于矩阵中的所有值都相等，即使进行循环移位，矩阵仍然保持不变。因此，返回 true 。

示例 3：

输入：mat = [[1,2]], k = 1
输出：false
解释：循环移位一次后，mat = [[2,1]]，与初始矩阵不相等。因此，返回 false 。

提示：

• 1 <= mat.length <= 25
• 1 <= mat[i].length <= 25
• 1 <= mat[i][j] <= 25
• 1 <= k <= 50

地址

https://leetcode.cn/contest/weekly-contest-373/problems/matrix-similarity-after-cyclic-shifts/

题意

模拟

思路

1. 直接模拟即可，模拟移位即可。
2. 复杂度分析：

• 时间复杂度：$O(n^2)$，其中 $n$ 表示给定的矩阵的行数。
• 空间复杂度：$O(1)$。

代码

class Solution:
    def areSimilar(self, mat: List[List[int]], k: int) -> bool:
        k %= len(mat[0])
        return k == 0 or all(r == r[k:] + r[:k] for r in mat)

2947. 统计美丽子字符串 I

给你一个字符串 s 和一个正整数 k 。

用 vowels 和 consonants 分别表示字符串中元音字母和辅音字母的数量。

如果某个字符串满足以下条件，则称其为 美丽字符串 ：

• vowels == consonants，即元音字母和辅音字母的数量相等。
• (vowels * consonants) % k == 0，即元音字母和辅音字母的数量的乘积能被 k 整除。

返回字符串 s 中 非空美丽子字符串 的数量。

子字符串是字符串中的一个连续字符序列。

英语中的 元音字母 为 'a'、'e'、'i'、'o' 和 'u' 。

英语中的 辅音字母 为除了元音字母之外的所有字母。

示例 1：

输入：s = "baeyh", k = 2
输出：2
解释：字符串 s 中有 2 个美丽子字符串。
- 子字符串 "baeyh"，vowels = 2（["a","e"]），consonants = 2（["y","h"]）。
可以看出字符串 "aeyh" 是美丽字符串，因为 vowels == consonants 且 vowels * consonants % k == 0 。
- 子字符串 "baeyh"，vowels = 2（["a","e"]），consonants = 2（["b","y"]）。
可以看出字符串 "baey" 是美丽字符串，因为 vowels == consonants 且 vowels * consonants % k == 0 。
可以证明字符串 s 中只有 2 个美丽子字符串。

示例 2：

输入：s = "abba", k = 1
输出：3
解释：字符串 s 中有 3 个美丽子字符串。
- 子字符串 "abba"，vowels = 1（["a"]），consonants = 1（["b"]）。
- 子字符串 "abba"，vowels = 1（["a"]），consonants = 1（["b"]）。
- 子字符串 "abba"，vowels = 2（["a","a"]），consonants = 2（["b","b"]）。
可以证明字符串 s 中只有 3 个美丽子字符串。

示例 3：

输入：s = "bcdf", k = 1
输出：0
解释：字符串 s 中没有美丽子字符串。

提示：

• 1 <= s.length <= 1000
• 1 <= k <= 1000
• s 仅由小写英文字母组成。

地址

https://leetcode.cn/contest/weekly-contest-373/problems/count-beautiful-substrings-i/

题意

模拟

思路

1. 我们直接模拟遍历两个数组即可，计算区间 $[i,j]$ 的元音字母，计算区间内的元音字符的数目是否等于非元音字母的数目，且二者之积是否能被 $k$ 整除。
2. 复杂度分析：

• 时间复杂度：$O(n^2)$，其中 $n$ 表示给定的字符串的长度。
• 空间复杂度：$O(n)$，其中 $n$ 表示给定的字符串的长度。

代码

class Solution:
    def beautifulSubstrings(self, s: str, k: int) -> int:
        n = len(s)
        kdict = ['a', 'o', 'e', 'i', 'u']
        cnt = [0] * (n + 1)
        for i, ch in enumerate(s):
            cnt[i + 1] = cnt[i]
            if ch in kdict:
                cnt[i + 1] += 1
        res = 0
        for i in range(1, n + 1):
            for j in range(i - 1, -1, -1):
                x = cnt[i] - cnt[j]
                y = i - j - x
                if x == y and (x * y) % k == 0:
                    res += 1
        return res

2948. 交换得到字典序最小的数组

给你一个下标从 0 开始的 正整数 数组 nums 和一个 正整数 limit 。

在一次操作中，你可以选择任意两个下标 i 和 j，如果 满足 |nums[i] - nums[j]| <= limit ，则交换 nums[i] 和 nums[j] 。

返回执行任意次操作后能得到的 字典序最小的数组 。

如果在数组 a 和数组 b 第一个不同的位置上，数组 a 中的对应元素比数组 b 中的对应元素的字典序更小，则认为数组 a 就比数组 b 字典序更小。例如，数组 [2,10,3] 比数组 [10,2,3] 字典序更小，下标 0 处是两个数组第一个不同的位置，且 2 < 10 。

示例 1：

输入：nums = [1,5,3,9,8], limit = 2
输出：[1,3,5,8,9]
解释：执行 2 次操作：
- 交换 nums[1] 和 nums[2] 。数组变为 [1,3,5,9,8] 。
- 交换 nums[3] 和 nums[4] 。数组变为 [1,3,5,8,9] 。
即便执行更多次操作，也无法得到字典序更小的数组。
注意，执行不同的操作也可能会得到相同的结果。

示例 2：

输入：nums = [1,7,6,18,2,1], limit = 3
输出：[1,6,7,18,1,2]
解释：执行 3 次操作：
- 交换 nums[1] 和 nums[2] 。数组变为 [1,6,7,18,2,1] 。
- 交换 nums[0] 和 nums[4] 。数组变为 [2,6,7,18,1,1] 。
- 交换 nums[0] 和 nums[5] 。数组变为 [1,6,7,18,1,2] 。
即便执行更多次操作，也无法得到字典序更小的数组。

示例 3：

输入：nums = [1,7,28,19,10], limit = 3
输出：[1,7,28,19,10]
解释：[1,7,28,19,10] 是字典序最小的数组，因为不管怎么选择下标都无法执行操作。

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• 1 <= limit <= 109

地址

https://leetcode.cn/contest/weekly-contest-373/problems/make-lexicographically-smallest-array-by-swapping-elements/

题意

贪心

思路

1. 当然我们知道如果数组在不做限制的情况，肯定是按照数字大小从小到大排序所得到的序列的字典序最小，其次我们还需要探讨一下，如果给定限制的情况下，哪些数据可以进行交换。先说结论：

   • 对于已经排序的数组 $arr[i],arr[j],arr[k]$，如果满足 $arr[i]> arr[j] > arr[k]$, 且满足 $i < j < k$，此时我们可以通过交换一定可以使得其按照数字从小到大进行排序，比如上述的过程我们可以交换如下：

     • $arr[i], arr[j]$ 交换，然后得到 $arr[j], arr[i], arr[k]$;
     • $arr[k], arr[j]$ 交换，然后得到 $arr[k], arr[i], arr[j]$;
     • $arr[i], arr[j]$ 交换，然后得到 $arr[k], arr[j], arr[i]$;

   • 我们总能把所有相邻元素距离小于等于 $limit$ 的进行交换，根据上述推论，我们将数组按照从小到大进行排序，然后将相邻值小于等于 $limit$ 的序列中的元素按照从小到大进行重新排列，依次贪心得到字典序最小的序列返回即可。

• 时间复杂度：$O(n \log n)$，其中$n$ 表示给定数组的长度；
• 空间复杂度：$O(n)$，其中$n$ 表示给定数组的长度；

代码

class Solution:
    def lexicographicallySmallestArray(self, nums: List[int], limit: int) -> List[int]:
        n = len(nums)
        arr = [(x, i) for i, x in enumerate(nums)]
        arr.sort()
        
        i = 0
        ans = [0] * n
        while i < n:
            cnt, idx = [], []
            cnt.append(arr[i][0])
            idx.append(arr[i][1])
            if i + 1 < n and arr[i + 1][0] - arr[i][0] <= limit:
                while i + 1 < n and arr[i + 1][0] - arr[i][0] <= limit:
                    cnt.append(arr[i + 1][0])
                    idx.append(arr[i + 1][1])
                    i += 1
            i += 1
            idx.sort()
            cnt.sort()
            for j, x in enumerate(idx):
                ans[x] = cnt[j]
        
        return ans

2949. 统计美丽子字符串 II

显示英文描述

给你一个字符串 s 和一个正整数 k 。

用 vowels 和 consonants 分别表示字符串中元音字母和辅音字母的数量。

如果某个字符串满足以下条件，则称其为 美丽字符串 ：

• vowels == consonants，即元音字母和辅音字母的数量相等。
• (vowels * consonants) % k == 0，即元音字母和辅音字母的数量的乘积能被 k 整除。

返回字符串 s 中 非空美丽子字符串 的数量。

子字符串是字符串中的一个连续字符序列。

英语中的 元音字母 为 'a'、'e'、'i'、'o' 和 'u' 。

英语中的 辅音字母 为除了元音字母之外的所有字母。

示例 1：

输入：s = "baeyh", k = 2
输出：2
解释：字符串 s 中有 2 个美丽子字符串。
- 子字符串 "baeyh"，vowels = 2（["a","e"]），consonants = 2（["y","h"]）。
可以看出字符串 "aeyh" 是美丽字符串，因为 vowels == consonants 且 vowels * consonants % k == 0 。
- 子字符串 "baeyh"，vowels = 2（["a","e"]），consonants = 2（["b","y"]）。
可以看出字符串 "baey" 是美丽字符串，因为 vowels == consonants 且 vowels * consonants % k == 0 。
可以证明字符串 s 中只有 2 个美丽子字符串。

示例 2：

输入：s = "abba", k = 1
输出：3
解释：字符串 s 中有 3 个美丽子字符串。
- 子字符串 "abba"，vowels = 1（["a"]），consonants = 1（["b"]）。
- 子字符串 "abba"，vowels = 1（["a"]），consonants = 1（["b"]）。
- 子字符串 "abba"，vowels = 2（["a","a"]），consonants = 2（["b","b"]）。
可以证明字符串 s 中只有 3 个美丽子字符串。

示例 3：

输入：s = "bcdf", k = 1
输出：0
解释：字符串 s 中没有美丽子字符串。

提示：

• 1 <= s.length <= 5 * 104
• 1 <= k <= 1000
• s 仅由小写英文字母组成。

地址

https://leetcode.cn/contest/weekly-contest-373/problems/count-beautiful-substrings-ii/

题意

动态规划

思路

1. 题目的关键在于 $k$ 的值为 $1000$，当然本身题目还是非常难得题目，这个动态规划的定义还是挺难得题目，很少遇到这么好的题目。
   • 我们先思考一个问题，如何求出字符串中元音字母与辅音字符数目想等的字串的数目，这是个经典题目，此时我们使用动态规划，设 $x = v[i] - p[i]$, 其中 $v[i]$ 表示元音字母的数目，$p[i]$ 表示非元音字母的数目，我们每次记录二者的差值即可，只需要从字符串中截取区间 $[i,j]$，其中 $i,j$ 满足 $v[i] - p[i] = v[j] - p[j]$，这是个经典问题，力扣上已经出现过很多次的题目了，我们用 $dp[x]$ 记录元音字符与辅音字母差值为 $x$ 的索引的数目，当遍历到 $i$ 时，此时以 $i$ 为结尾满足要求的字符串数目即为 $dp[i]$;
   • 再思考另外一个问题，子字符串长度 $x$ 的平方可以被 $k$ 整除，假设 $x^2$ 能被 $k$ 整除，此时只需要满足 $(x \bmod k) ^ 2 \bmod k = 0$，此时如果需要求满足条件的子字符串的数量。这个问题如何求呢？首先我们需要找到哪些长度的平方能够被 $k$ 整除。假设当前字符串的长度为 $l$，此时 $p = l \bmod k$，此时如果满足 $p^2$ 能够被 $k$ 整除，则 $l^2$ 一定可以被 $k$ 整除。我们可以提前求出所有满足题目要求的集合 $E$，此时满足 $p \in E$ 时，$p^2 \bmod k = 0$。此时假设当前为第 $i$ 个字符，则此时 $p = i \bmod k$，对于任意的 $x \in E$ 长度之间的差值为 $p - x$ 的索引，此时满足要求的值即为 $\sum_{j = 0} ^ n dp[x_j], (p - x_j) \in E $。
   • 当然问题二描述的过于复杂，将二者要求结合起来即为题目所有需要求得数目，我们用哈希来存储不同的状态值即可。
2. 复杂度分析:

• 时间复杂度：$O(n \sqrt k)$，其中 $n$ 表示数组的长度，$k$ 表示数组中的最大长度；
• 空间复杂度：$O(n \sqrt k)$，其中 $n$ 表示数组的长度，$k$ 表示数组中的最大长度；

代码

class Solution:
    def beautifulSubstrings(self, s: str, k: int) -> int:
        kdict = ['a', 'o', 'e', 'i', 'u']
        arr = [i for i in range(k) if i * i % k == 0]
        n = len(s)
        ans = 0
        mp = Counter()
        mp[(0, 0)] = 1
        x, y = 0, 0

        for i, ch in enumerate(s):
            if ch in kdict:
                x += 1
            else:
                y += 1
            p = x % k
            for v in arr:
                z =  (p - v + k) % k
                ans += mp[(x - y, z)]
            mp[(x - y, p)] += 1
        return ans

欢迎关注和打赏，感谢支持！

• 关注我的博客: http://whistle-wind.com/
• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
• 关注我的微信公众号: 公务程序猿