Leetcode 384场周赛

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：

1
2
3

输入：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
测试用例中生成的输入满足每列至少包含一个非负整数。

思路

三层循环暴力修改一下即可。

代码

function modifiedMatrix(matrix: number[][]): number[][] {
	for (let i = 0, n = matrix.length; i < n; i++) {
		for (let j = 0, m = matrix[i].length; j < m; j++) {
			if (matrix[i][j] === -1) {
				for (let k = 0; k < n; k++) {
					matrix[i][j] = Math.max(matrix[i][j], matrix[k][j]);
				}
			}
		}
	}
	return matrix;
}

复杂度分析

时间：O(n * m * m)。
空间：O(1)。

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] 仅由小写英文字母组成。

思路

每次执行可以选择 words[i]和 words[j]中任意两个字符进行交换（i!=j）
每次执行可以选择 words[i]中任意两个字符进行位置交换
由于操作可执行任意次，则所有的字符都可以重新进行排列。
这样只需要统计字符的数量，依次进行回文串构造就可以。
需要先对字符串进行排序，优先构造最短的回文串。

代码

class Solution {
   public:
    int maxPalindromesAfterOperations(vector<string>& words) {
        int n = words.size(), ans = 0;
        // 贪心：优先从长度较短的字符串开始构造
        sort(words.begin(), words.end(), [](string& a, string& b) {
            return a.size() < b.size();
        });
        vector<int> cnt(26, 0);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < words[i].size(); j++) {
                cnt[words[i][j] - 'a']++;
            }
        }
        for (int i = 0; i < n; i++) {
            int s = words[i].size();
            // 先构造成对的字符：每次消耗两个相同字符
            for (int j = 0; j < 26 && s >= 2; j++) {
                int minv = min(s, cnt[j]);
                if (minv % 2 == 1) minv--;
                cnt[j] -= minv;
                s -= minv;
            }
            // 如果还剩一个字符：优先消耗奇数个字符
            for (int i = 0; i < 26 && s == 1; i++) {
                if (cnt[i] % 2 == 1){
                    cnt[i]--;
                    s--;
                }
            }
            // 如果还剩一个字符并且没有奇数个字符：随便选一个
            for (int i = 0; i < 26 && s == 1; i++) {
                if (cnt[i] > 0){
                    cnt[i]--;
                    s--;
                }
            }
            // 贪心构造：如果当前已经构造不出回文串，那么比它还长的肯定也构造不出
            if (s == 0) ans++;
            else break;
        }
        return ans;
    }
};

复杂度分析

时间：O(n*m)。
空间：O(1)。

100186. 匹配模式数组的子数组数目

给你一个下标从 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 <= 10^6
1 <= nums[i] <= 10^9
1 <= m == pattern.length < n
-1 <= pattern[i] <= 1

思路

首先我们可以根据题意将原数组都变成 1，0，-1 的形式
下面就是找出与 pattern 相同的子数组=>经典 KMP 匹配问题

(有一说一，知识点和上周的重了)

代码

class Solution {
   public:
    // 获取next数组
    vector<int> calcLSP(vector<int>& s) {
        int n = s.size();
        vector<int> next(n, 0);
        for (int i = 1, j = 0; i < n; i++) {
            while (j && s[i] != s[j]) j = next[j - 1];
            if (s[i] == s[j]) j++;
            next[i] = j;
        }
        return next;
    }
    int countMatchingSubarrays(vector<int>& nums, vector<int>& pattern) {
        vector<int> next = calcLSP(pattern);
        int n = nums.size(), m = pattern.size(), count = 0;
        // 做一下转换
        for (int i = 0; i < n - 1; i++) {
            if (nums[i + 1] > nums[i]) nums[i] = 1;
            else if (nums[i + 1] < nums[i]) nums[i] = -1;
            else nums[i] = 0;
        }
        // 进行匹配计数
        for (int i = 0, j = 0; i < n; i++) {
            while (j && nums[i] != pattern[j]) j = next[j - 1];
            if (nums[i] == pattern[j]) j++;
            if (j == m) {
                count++;
                j = next[j - 1];
            }
        }
        return count;
    }
};

复杂度分析

时间：O(n+m)。
空间：O(m)。