leetcode contest 384

最近周赛比较简单，双周赛难度有所上升，本周最难的题目是 t3, 其余的题目比较简单。

100230. 修改矩阵

给你一个下标从 0 开始、大小为 m x n 的整数矩阵 matrix ，新建一个下标从 0 开始、名为 answer 的矩阵。使 answer 与 matrix 相等，接着将其中每个值为 -1 的元素替换为所在列的 最大 元素。

返回矩阵 answer 。

示例 1：

输入：matrix = [[1,2,-1],[4,-1,6],[7,8,9]]
输出：[[1,2,9],[4,8,6],[7,8,9]]
解释：上图显示了发生替换的元素（蓝色区域）。
- 将单元格 [1][1] 中的值替换为列 1 中的最大值 8 。
- 将单元格 [0][2] 中的值替换为列 2 中的最大值 9 。

示例 2：

输入：matrix = [[3,-1],[5,2]]
输出：[[3,2],[5,2]]
解释：上图显示了发生替换的元素（蓝色区域）。

提示：

• m == matrix.length
• n == matrix[i].length
• 2 <= m, n <= 50
• -1 <= matrix[i][j] <= 100
• 测试用例中生成的输入满足每列至少包含一个非负整数。

地址

https://leetcode.cn/contest/weekly-contest-384/problems/modify-the-matrix/

题意

直接模拟即可

思路

1. 直接模拟即可，用每一列的最大值替换 -1 即可；
2. 复杂度分析：

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

代码

class Solution:
    def modifiedMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        m, n = len(matrix), len(matrix[0])
        cols = [0] * n
        for i in range(n):
            cols[i] = max([matrix[j][i] for j in range(m)])
        for i in range(m):
            for j in range(n):
                matrix[i][j] = cols[j] if matrix[i][j] == -1 else matrix[i][j]
        return matrix

3036. 匹配模式数组的子数组数目 II

给你一个下标从 0 开始长度为 n 的整数数组 nums ，和一个下标从 0 开始长度为 m 的整数数组 pattern ，pattern 数组只包含整数 -1 ，0 和 1 。

大小为 m + 1 的子数组 nums[i..j] 如果对于每个元素 pattern[k] 都满足以下条件，那么我们说这个子数组匹配模式数组 pattern ：

• 如果 pattern[k] == 1 ，那么 nums[i + k + 1] > nums[i + k]
• 如果 pattern[k] == 0 ，那么 nums[i + k + 1] == nums[i + k]
• 如果 pattern[k] == -1 ，那么 nums[i + k + 1] < nums[i + k]

请你返回匹配 pattern 的 nums 子数组的 数目 。

示例 1：

输入：nums = [1,2,3,4,5,6], pattern = [1,1]
输出：4
解释：模式 [1,1] 说明我们要找的子数组是长度为 3 且严格上升的。在数组 nums 中，子数组 [1,2,3] ，[2,3,4] ，[3,4,5] 和 [4,5,6] 都匹配这个模式。
所以 nums 中总共有 4 个子数组匹配这个模式。

示例 2：

输入：nums = [1,4,4,1,3,5,5,3], pattern = [1,0,-1]
输出：2
解释：这里，模式数组 [1,0,-1] 说明我们需要找的子数组中，第一个元素小于第二个元素，第二个元素等于第三个元素，第三个元素大于第四个元素。在 nums 中，子数组 [1,4,4,1] 和 [3,5,5,3] 都匹配这个模式。
所以 nums 中总共有 2 个子数组匹配这个模式。

提示：

• 2 <= n == nums.length <= 106
• 1 <= nums[i] <= 109
• 1 <= m == pattern.length < n
• -1 <= pattern[i] <= 1

地址

https://leetcode.cn/contest/weekly-contest-384/problems/number-of-subarrays-that-match-a-pattern-ii/

题意

字符串哈希算法，KMP

思路

1. 本题与上周的题目几乎一样的解法，最直接的办法就是字符串哈希 KR 算法或者 KMP, 由于给定的模式只关系到数组中两个相邻的元素，此时我们首先可以将数组转换为模式匹配的目标数，然后在该数组的模式匹配中查找 pattern 一共出现多少次即可。经典的解法就是字符串匹配即可，即匹配当前字符串在目标字符串中出现的次数即可，我们可以用KR 算法或者 KMP 算法即可。
2. 复杂度分析：

• 时间复杂度：$O(n)$, $n$ 表示给定字符串 $s$ 的长度；
• 空间复杂度：$O(n)$；

代码

class Solution:
    def countMatchingSubarrays(self, nums: List[int], pattern: List[int]) -> int:
        n, k = len(nums), len(pattern)
        arr = []
        for i in range(1, n):
            if nums[i] > nums[i - 1]:
                arr.append(2)
            elif nums[i] == nums[i - 1]:
                arr.append(1)
            else:
                arr.append(0)
        pattern = [v + 1 for v in pattern]
        
        mod, base = 10**9 + 7, 31
        h = base**(k - 1) % mod
        key = 0
        for v in pattern:
            key = (key * base + v) % mod
        ans, curr = 0, 0
        for i in range(len(arr)):
            curr = (curr * base + arr[i]) % mod;
            if i >= k - 1:
                if curr == key:
                    ans += 1
                curr = (curr - (arr[i - k + 1] * h % mod) + mod) % mod
        return ans;

100219. 回文字符串的最大数量

给你一个下标从 0 开始的字符串数组 words ，数组的长度为 n ，且包含下标从 0 开始的若干字符串。

你可以执行以下操作 任意 次数（包括零次）：

• 选择整数i、j、x和y，满足0 <= i, j < n，0 <= x < words[i].length，0 <= y < words[j].length，交换 字符 words[i][x] 和 words[j][y] 。

返回一个整数，表示在执行一些操作后，words 中可以包含的回文字符串的 最大 数量。

注意：在操作过程中，i 和 j 可以相等。

示例 1：

输入：words = ["abbb","ba","aa"]
输出：3
解释：在这个例子中，获得最多回文字符串的一种方式是：
选择 i = 0, j = 1, x = 0, y = 0，交换 words[0][0] 和 words[1][0] 。words 变成了 ["bbbb","aa","aa"] 。
words 中的所有字符串都是回文。
因此，可实现的回文字符串的最大数量是 3 。

示例 2：

输入：words = ["abc","ab"]
输出：2
解释：在这个例子中，获得最多回文字符串的一种方式是： 
选择 i = 0, j = 1, x = 1, y = 0，交换 words[0][1] 和 words[1][0] 。words 变成了 ["aac","bb"] 。
选择 i = 0, j = 0, x = 1, y = 2，交换 words[0][1] 和 words[0][2] 。words 变成了 ["aca","bb"] 。
两个字符串都是回文 。
因此，可实现的回文字符串的最大数量是 2。

示例 3：

输入：words = ["cd","ef","a"]
输出：1
解释：在这个例子中，没有必要执行任何操作。
words 中有一个回文 "a" 。
可以证明，在执行任何次数操作后，无法得到更多回文。
因此，答案是 1 。

提示：

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 100
• words[i] 仅由小写英文字母组成。

地址

https://leetcode.cn/contest/weekly-contest-384/problems/maximum-palindromes-after-operations/

题意

构造题目 + 贪心

思路

1. 题目比较有意思，首先我们看到任意两个字符串中的任意两个字符都可以交换，这其实意味着所有字符串中的所有字符都可以任意交换，包括同一个字符串本身的字符也可以任意交换，题目则转换成了给定不同字符的数目，最多可以构造指定长度的字符串的数目最多为多少。
2. 根据 $1$ 的分析我们可以贪心的来构造，首先我们可以知道对于长度为奇数的回文字符串，它最中间的字母可以填任意元素，此时我们只需要计算它的两边需要的成对的字符的数目即可，因此首先我们统计所有出现次数为偶数的字符的数目，然后我们贪心的从字符串长度从小到大开始构造，出现次数为偶数的总数为 $tot$
   • 首先构造长度最小的字符串，此时我们从 $tot$ 中减去需要构造的最长偶数对数；
   • 然后构造长度较长的字符串，此时我们还是依次构造，直到 $tot$ 小于 $0$ 为止，此时则无法构造。
3. 复杂度分析：

• 时间复杂度：$O(n\log n + |\Sigma|)$，其中 $n$ 表示给定字符串数组的长度， $|\Sigma|$ 表示字符集的大小。
• 空间复杂度：$O(|\Sigma|)$， $|\Sigma|$ 表示字符集的大小。

代码

class Solution:
    def maxPalindromesAfterOperations(self, words: List[str]) -> int:
        n = len(words)
        cnt = Counter(c for w in words for c in w)
        v = sum(x % 2 for x in cnt.values())
        tot = sum(len(w) for w in words)
        tot -= v

        words.sort(key = len)
        ans = 0
        for w in words:
            tot -= len(w) // 2 * 2
            if tot < 0:
                break
            ans += 1
        return ans
    

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

• 关注我的博客: https://mike-box.github.io/

• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu