Leetcode 第 384 場周賽題解

題目1：3033. 修改矩陣

思路

模擬。

代碼

/** @lc app=leetcode.cn id=3033 lang=cpp** [3033] 修改矩陣*/// @lc code=start
class Solution
{
public:vector<vector<int>> modifiedMatrix(vector<vector<int>> &matrix){if (matrix.empty())return {};int m = matrix.size(), n = m ? matrix[0].size() : 0;auto answer = matrix;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++){// 每個值為 -1 的元素需要替換if (matrix[i][j] == -1){// 找到列最大值int col_max = -1;for (int k = 0; k < m; k++)col_max = max(col_max, matrix[k][j]);// 修改 answer 數組answer[i][j] = col_max;}}return answer;}
};
// @lc code=end

復雜度分析

時間復雜度：O(m²*n)，其中 m 和 n 分別是矩陣 matrix 的行數和列數。

空間復雜度：O(m*n)，其中 m 和 n 分別是矩陣 matrix 的行數和列數。

題目2：3034. 匹配模式數組的子數組數目 I

思路

暴力。

設數組 nums 的長度為 m，數組 pattern 的長度為 n。

遍歷數組 nums 的每個長度是 n+1 的子數組并計算子數組的模式，然后與數組 pattern 比較，如果相等則找到一個匹配模式數組的子數組。遍歷結束之后即可得到匹配模式數組的子數組數目。

代碼

/** @lc app=leetcode.cn id=3034 lang=cpp** [3034] 匹配模式數組的子數組數目 I*/// @lc code=start
class Solution
{
public:int countMatchingSubarrays(vector<int> &nums, vector<int> &pattern){// 特判if (nums.empty() || pattern.empty())return 0;if (nums.size() <= pattern.size())return 0;int count = 0;int m = nums.size(), n = pattern.size();for (int i = 0; i < m - n; i++){bool flag = true;for (int k = 0; k < n && flag; k++){int diff = nums[i + k + 1] - nums[i + k];int p = getPattern(diff);if (p != pattern[k])flag = false;}if (flag)count++;}return count;}// 輔函數 - 計算 patternint getPattern(int diff){if (diff == 0)return 0;return diff > 0 ? 1 : -1;}
};
// @lc code=end

復雜度分析

時間復雜度：O((m-n)*n)，其中 m 為數組 nums 的長度，n 為數組 pattern 的長度。

空間復雜度：O(1)。

題目3：3035. 回文字符串的最大數量

思路

由于可以隨意交換字母，先把所有字母都取出來，然后考慮如何填入各個字符串。

如果一個奇數長度字符串最終是回文串，那么它正中間的那個字母填什么都可以。

既然如此，不妨先把左右的字母填了，最后在往正中間填入字母。

字符串越短，需要的字母越少。

所以按照字符串的長度從小到大填。

統計所有字符串的長度之和，減去出現次數為奇數的字母，即為可以往左右填入的字母個數 total。

把字符串按照長度從小到大排序，然后遍歷。注意長為奇數的字符串，由于不考慮正中間的字母，其長度要減一。

代碼

/** @lc app=leetcode.cn id=3035 lang=cpp** [3035] 回文字符串的最大數量*/// @lc code=start
class Solution
{
public:int maxPalindromesAfterOperations(vector<string> &words){// 特判if (words.empty())return 0;int n = words.size();int total = 0; // 出現次數為偶數的字母總數unordered_map<char, int> mp;for (string &word : words){total += word.length();for (char &c : word)mp[c]++;}// 減去出現次數為奇數的字母for (auto &[ch, cnt] : mp)total -= cnt % 2;sort(words.begin(), words.end(), [](const string &s1, const string &s2){ return s1.length() < s2.length(); });int ans = 0;for (string &word : words){int len = word.length();// 長為奇數的字符串，長度要減一total -= len % 2 == 1 ? len - 1 : len;if (total < 0)break;ans++;}return ans;}
};
// @lc code=end

哈希表可以用位運算優化，詳見：【靈茶山艾府】兩種方法：正向思維 / 逆向思維（Python/Java/C++/Go）

復雜度分析

時間復雜度：O(L+nlogn)，其中 n 是數組 words 的長度，L 是數組 words 中字符串的總長度。

空間復雜度：O(|∑|)，其中 ∑ 是字符集，|∑| 為字符集的大小，因為 words[i] 僅由小寫英文字母組成，所以 |∑|=26。

題目4：3036. 匹配模式數組的子數組數目 II

思路

設數組 nums 的長度為 m，數組 pattern 的長度為 n。

遍歷數組 nums 的每個長度是 n+1 的子數組并計算子數組的模式，然后與數組 pattern 比較，如果相等則找到一個匹配模式數組的子數組。遍歷結束之后即可得到匹配模式數組的子數組數目。

我們發現這其實就是 KMP。

將匹配模式轉換成字符串：1 對應 ‘a’，0 對應 ‘b’，-1 對應 ‘c’。

代碼

/** @lc app=leetcode.cn id=3036 lang=cpp** [3036] 匹配模式數組的子數組數目 II*/// @lc code=start// KMPclass Solution
{
private:// KMP 算法vector<int> getNxt(string &pattern){vector<int> nxt;// next[0] 必然是 0nxt.push_back(0);// 從 next[1] 開始求int x = 1, now = 0;while (x < pattern.length()){if (pattern[now] == pattern[x]){// 如果 pattern[now] == pattern[x]，向右拓展一位now++;x++;nxt.push_back(now);}else if (now != 0){// 縮小 now，改成 nxt[now - 1]now = nxt[now - 1];}else{// now 已經為 0，無法再縮小，故 next[x] = 0nxt.push_back(0);x++;}}return nxt;}vector<int> kmp(string &s, string &pattern){int m = pattern.length();vector<int> nxt = getNxt(pattern);vector<int> res;int tar = 0; // 主串中將要匹配的位置int pos = 0; // 模式串中將要匹配的位置while (tar < s.length()){if (s[tar] == pattern[pos]){// 若兩個字符相等，則 tar、pos 各進一步tar++;pos++;}else if (pos != 0){// 失配，如果 pos != 0，則依據 nxt 移動標尺pos = nxt[pos - 1];}else{// pos[0] 失配，標尺右移一位tar++;}if (pos == pattern.length()){res.push_back(tar - pos);pos = nxt[pos - 1];}}return res;}public:int countMatchingSubarrays(vector<int> &nums, vector<int> &pattern){// 特判if (nums.empty() || pattern.empty())return 0;if (nums.size() <= pattern.size())return 0;int count = 0;int m = nums.size(), n = pattern.size();// 1 對應 'a'，0 對應 'b'，-1 對應 'c'string s;for (int i = 0; i < m - 1; i++){int diff = nums[i + 1] - nums[i];int p = getPattern(diff);if (p == 1)s += "a";else if (p == 0)s += "b";elses += "c";}string p;for (int &pa : pattern){if (pa == 1)p += "a";else if (pa == 0)p += "b";elsep += "c";}return kmp(s, p).size();}// 輔函數 - 計算 patternint getPattern(int diff){if (diff == 0)return 0;return diff > 0 ? 1 : -1;}
};
// @lc code=end

復雜度分析

時間復雜度：O(m)，其中 m 是數組 nums 的長度。

空間復雜度：O(n)，其中 n 是數組 pattern 的長度。