LeetCode周赛——384

1.修改矩阵（模拟）

class Solution {
public:vector<vector<int>> modifiedMatrix(vector<vector<int>>& matrix) {int n = matrix.size();int m = matrix[0].size();vector<int> ans(m);for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)ans[i] = max(ans[i], matrix[j][i]);for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)if(matrix[j][i] == -1) matrix[j][i] = ans[i];return matrix;}
};

2.匹配模式数组的子数组数目 I（暴力）

class Solution {
public:int countMatchingSubarrays(vector<int>& nums, vector<int>& pattern) {int n = nums.size();int m = pattern.size();int ans = 0;//枚举numsfor(int i = 0; i < n - m; i++){int f = 1;//枚举patternfor(int j = 0; j < m; j++){如果不满足，那就跳到下一个if(nums[i + j + 1] > nums[i + j] && pattern[j] != 1) f = 0;if(nums[i + j + 1] == nums[i + j] && pattern[j] != 0) f = 0;if(nums[i + j + 1] < nums[i + j] && pattern[j] != -1) f = 0;}if(f) ans++;}return ans;}
};

3.回文字符串的最大数量（贪心）

class Solution {
public:int maxPalindromesAfterOperations(vector<string>& words) {int n = words.size();vector<int> cnt(26, 0);for(int i = 0; i < n; i++)for(char c : words[i])//统计每个字符有多少个cnt[c - 'a']++;int sum = 0, ans = 0;//统计有多少对字符for(int i : cnt) sum += i / 2;//从小到大排序，允许重复数字multiset<int> s;//插入每个字符串的长度for(int i = 0; i < n; i++) s.insert(words[i].size());for(int i : s){//计算剩余多少对字符int t = sum - i / 2;//如果剩余的对数大于等于0，那就更新答案和对数if(t >= 0){sum = t;ans++;}}return ans;}
};

4.匹配模式数组的子数组数目 II（KMP）

class Solution {
public:int countMatchingSubarrays(vector<int>& nums, vector<int>& pattern) {int n = nums.size();int m = pattern.size();vector<int> s(n), ne(n);//将匹配串转化为01串，用kmp匹配for(int i = 1; i < n; i++)s[i - 1] = nums[i] > nums[i - 1] ? 1 : nums[i] == nums[i - 1] ? 0 : -1;//求next模板串ne[0] = -1;for(int i = 1, j = -1; i < m; i++){while(j >= 0 && pattern[i] != pattern[j + 1]) j = ne[j];if(pattern[i] == pattern[j + 1]) j++;ne[i] = j;}int ans = 0;//kmp匹配，但是s里只有n-1个元素for(int i = 0, j = -1; i < n - 1; i++){while(j >= 0 && s[i] != pattern[j + 1]) j = ne[j];if(s[i] == pattern[j + 1]) j++;if(j == m - 1){ans++;j = ne[j];}}return ans;}
};