LeetCode周赛384 题解

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; 
    }
};