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