LeetCode第69场双周赛

5960. 将标题首字母大写

题目描述：将给定的句子按照题意格式化

思路：根据题意描述即可

时间复杂度：\(O(n)\)

参考代码：

class Solution {
public:
    string capitalizeTitle(string title) {
        stringstream text(title);
        string t, res;
        while(text >> t){
            if(t.size() <= 2){
                for(int i = 0 ; i < t.size() ; ++i) {
                    if(t[i] >= 'a' && t[i] <= 'z') continue;
                    else t[i] = t[i] - 'A' + 'a';
                }
            }
            else{
                int n = t.size();
                if(t[0] >= 'a' && t[0] <= 'z') t[0] = t[0] - 'a' + 'A';
                for(int i = 1 ; i < n ; ++ i){
                    if(t[i] >= 'a' && t[i] <= 'z') continue;
                    else t[i] = t[i] - 'A' + 'a';
                }
            }
            if(res.size() == 0) res += t;
            else res += ' ' + t;
        }
        return res;
    }
};
           

5961. 链表最大孪生和

题目描述：给你一个链表，其对应的数组为\(A\)，其长度为\(n\)，保证\(n\)为偶数，下标从\(0\)开始，求：

\[\mathop{max}\limits_{i = 0}^{\frac{n}{2} - 1} \{A[i] + A[n - i - 1]\}

\]

思路：将链表转化成数组，然后根据题意模拟即可

空间复杂度：\(O(n)\)

class Solution {
public:
    int pairSum(ListNode* head) {
       vector<int> arr;
        while(head != nullptr){
            arr.push_back(head->val);
            head = head->next;
        }
        int res = 0, n = arr.size();
        for(int i = 0 ; i < n / 2 ; ++i){
            res = max(res , arr[i] + arr[n - i - 1]);
        }
        return res;
    }
};
           

5962. 连接两字母单词得到的最长回文串

题目描述：给你\(n\)个长度为\(2\)的字符串从中选择任意个组成回文串，求组成的回文串的最大长度。

思路：使用\(map\)存储一下前面未使用的字符串，对于当前枚举的字符串，若它的翻转字符串在\(map\)中，就对答案\(+4\)并将其翻转字符串对应的键值减一，否则将其加入\(map\)中，注意若最后还剩余长度为\(2\)且两个字符相同的串，则最终答案还应该\(+2\)。

时间复杂度：\(O(nlogn)\)

class Solution {
public:
    int longestPalindrome(vector<string>& words) {
        vector<int>cnt(27 , 0);
        int res = 0;
        string t;
        map<string , int>mp;
        for(auto s : words){
            if(s[0] == s[1]){
                cnt[s[0] - 'a'] ++;
                res += (cnt[s[0] - 'a'] / 2) * 4;
                cnt[s[0] - 'a'] %= 2;
            }
            else{
                t = s;
                reverse(t.begin() , t.end());
                if(mp.count(t) && mp[t] > 0) res += 4 , mp[t]--;
                else mp[s]++;
            }
        }
        for(auto ct : cnt){
            if(ct == 0) continue;
            res += 2;
            break;
        }
        return res;
    }
};
           

5931. 用邮票贴满网格图

题目描述：给你一个二进制矩阵，每个格子要么是\(0\)表示空， 要么为\(1\)表示占据，你需要在讲邮票贴在二进制矩阵中，且满足以下限制和要求：

• 覆盖所有空格子。
• 不覆盖任何被占据的格子。
• 我们可以放入任意数目的邮票。
• 邮票可以相互有重叠的部分。
• 邮票不能旋转。
• 邮票必须完全在矩阵内。

若存在一个放置方案满足上述条件返回true，否则返回false。

思路：首先可以使用二维前缀和用于快速判断一个矩形中是否存在被占据的格子，我们枚举邮票的左上角的位置，若将该邮票放在此处不会产生冲突，则就将该位置置\(1\)（使用一个新的数组保存）。接下来枚举每一个空格\((i , j)\)，查询其所在的位置是否被某张邮票覆盖，也即判断子矩阵\((max(1 , i - h + 1) , max(1 , j - w + 1)) \to (i , j)\) 内是否存在标记为\(1\)的点。此时只需对刚刚的标记数组再做一遍二维前缀和就可以对于每一个空格进行\(O(1)\)判断。

时间复杂度：\(O(nm)\)

空间复杂度：\(O(nm)\)

class Solution {
public:
    bool possibleToStamp(vector<vector<int>>& grid, int h, int w) {
        int n = grid.size() , m = grid[0].size();
        vector<vector<int>>a(n + 1 , vector<int>(m + 1 , 0));
        vector<vector<int>>b(n + 1 , vector<int>(m + 1 , 0));
        for(int i = 1 ; i <= n ; ++i){
            for(int j = 1 ; j <= m ; ++j){
                a[i][j] = grid[i - 1][j - 1];
                a[i][j] += a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1];
            }
        }
        //枚举邮票的左上角，因为只是问可行，不要求使用最少的 ，所以若当前左上角可以贴就贴上，否则不贴
        for(int i = 1 ; i <= n ; ++i){
            for(int j = 1 ; j <= m ; ++j){
                int up = i + h - 1 , low = j + w - 1;
                if(up > n || low > m) break;
                int dx = a[up][low] - a[up][j - 1] - a[i - 1][low] + a[i - 1][j - 1];
                if(dx > 0) continue;
                b[i][j] = 1;
            }
           for(int j = 1 ; j <= m ; ++j) b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
        }
        for(int i = 1 ; i <= n ; ++i){
            for(int j = 1 ; j <= m ; ++j){
                if(grid[i - 1][j - 1] == 1) continue;
                int up = max(i - h + 1 , 1) , low = max(j - w + 1 , 1);
                int dx = b[i][j] - b[i][low - 1] - b[up - 1][j] + b[up - 1][low - 1];
                if(dx == 0) return false;
            }
        }
        return true;
    }
};