AK

第 384 场周赛 - 力扣（LeetCode）

---

前两题都是签到,      略。 

第三题: 回文字符串的最大数量 

1、题意:

给定一个字符串数组，总字符数量不超过1e6, 可以交换其中的任意两个字符，问能构造最多几个回文字符串。

2、题解:

首先我们要知道，无论怎么交换，字符数组内的各个字符串的长度不能发生改变，只是原来的字符布局发生了改变，那我们不妨先将所有的字符拿出来然后依次发出去，问题此时转化为了怎么分配字符使得回文字符串最多，考虑一个字符串，他需要的字符数量一定是len / 2对一样的字符，所以我们直接根据字符串长度对数组排序，优先分配给长度较小者，那如果它的长度是奇数呢，我们也直接借一位，将代价留给最后一个字符串，因为它的变成回文串最难，代价最高。
 

3、代码 (C++)：

class Solution {
public:int maxPalindromesAfterOperations(vector<string>& words) {map<char, int> mp; vector<int> us; for(int i = 0; i < words.size(); i ++ )     for(auto c : words[i]) mp[c] ++; int r = 0;for(auto t : mp) r += (t.second / 2); for(int i = 0; i < words.size(); i ++ ) us.push_back(words[i].size()); sort(us.begin(), us.end()); int ans = 0; for(int i = 0; i < us.size(); i ++ ) {int o = us[i] / 2;if(o <= r) r -= o, ans ++; }return ans; }
};

---

第四题：匹配模式的子数组数目2

1、题意:

 

2、题解:

数据范围相对于签到题变大了，我们不妨先预处理出来 i <= n - 1元素与前一个元素的大小关系划分1, -1, 0的，因为也就三种值，我们不妨规定一种映射，此时两个数组都变成了字符串，问题转化成了字符串匹配的问题，我们不妨对两个字符串进行哈希，边遍历i < n - m的位置边比较哈希值，最后得到答案。

3、代码(C++)
 

class Solution {
public:int countMatchingSubarrays(vector<int>& nums, vector<int>& pattern) {int n = nums.size(), m = pattern.size(); const int N = n + 2; unsigned long long p1[N], h1[N], p2[N], h2[N]; int P = 131; map<int, char> mp;mp[0] = 'a', mp[1] = 'b', mp[-1] = 'c'; string a, b; for(int i = 0; i < pattern.size(); i ++ ) a += mp[pattern[i]];for(int i = 0; i < n - 1; i ++ ) if(nums[i] < nums[i + 1]) b += mp[1]; else if(nums[i] > nums[i + 1]) b += mp[-1]; else b += mp[0]; p1[0] = 1; for(int i = 1; i <= n - 1; i++ ) {p1[i] = p1[i-1] * P;    h1[i] = h1[i-1] * P + b[i - 1]; }p2[0] = 1; for(int i = 1; i <= m; i++ ) {p2[i] = p2[i-1] * P;    h2[i] = h2[i-1] * P + a[i - 1];  }        int ans = 0; for(int i = 0; i < n - m; i ++ ) {int l = i + 1, r = i + m;unsigned long long x = h1[r] - h1[l - 1] * p1[r - l + 1];l = 1, r = m; unsigned long long y = h2[r] - h2[l - 1] * p2[r - l + 1];if(x == y) ++ ans; }return ans; }
};