文章目錄

• • 1. 比賽結果
  • 2. 題目
  • • 1. LeetCode 5408. 通過翻轉子數組使兩個數組相等 easy
    • 2. LeetCode 5409. 檢查一個字符串是否包含所有長度為 K 的二進制子串 medium
    • 3. LeetCode 5410. 課程安排 IV medium （Floyd-Warshall）
    • 4. LeetCode 5411. 摘櫻桃 II hard

1. 比賽結果

雖然只做出一題，還是記錄一下吧。第一題送分題拿下，第二題沒繞過彎，第三題超時，第四題沒看。繼續加油！

全國排名：1125 / 1966，57.2%；全球排名：4236 / 7924，53.5%

2. 題目

1. LeetCode 5408. 通過翻轉子數組使兩個數組相等 easy

題目鏈接
給你兩個長度相同的整數數組 target 和 arr 。

每一步中，你可以選擇 arr 的任意 非空子數組 并將它翻轉。你可以執行此過程任意次。

如果你能讓 arr 變得與 target 相同，返回 True；否則，返回 False 。

示例 1： 輸入：target = [1,2,3,4], arr = [2,4,1,3] 輸出：true 解釋：你可以按照如下步驟使 arr 變成 target： 1- 翻轉子數組 [2,4,1] ，arr 變成 [1,4,2,3] 2- 翻轉子數組 [4,2] ，arr 變成 [1,2,4,3] 3- 翻轉子數組 [4,3] ，arr 變成 [1,2,3,4] 上述方法并不是唯一的，還存在多種將 arr 變成 target 的方法。示例 2： 輸入：target = [7], arr = [7] 輸出：true 解釋：arr 不需要做任何翻轉已經與 target 相等。示例 3： 輸入：target = [1,12], arr = [12,1] 輸出：true示例 4： 輸入：target = [3,7,9], arr = [3,7,11] 輸出：false 解釋：arr 沒有數字 9 ，所以無論如何也無法變成 target 。示例 5： 輸入：target = [1,1,1,1,1], arr = [1,1,1,1,1] 輸出：true提示： target.length == arr.length 1 <= target.length <= 1000 1 <= target[i] <= 1000 1 <= arr[i] <= 1000

---

解答：

• 翻轉任意次，那就排序后，相等即可

class Solution { public:bool canBeEqual(vector<int>& target, vector<int>& arr) {sort(target.begin(), target.end());sort(arr.begin(),arr.end());return target == arr;} };

2. LeetCode 5409. 檢查一個字符串是否包含所有長度為 K 的二進制子串 medium

題目鏈接
給你一個二進制字符串 s 和一個整數 k 。

如果所有長度為 k 的二進制字符串都是 s 的子串，請返回 True ，否則請返回 False 。

示例 1： 輸入：s = "00110110", k = 2 輸出：true 解釋：長度為 2 的二進制串包括 "00"，"01"，"10" 和 "11"。 它們分別是 s 中下標為 0，1，3，2 開始的長度為 2 的子串。示例 2： 輸入：s = "00110", k = 2 輸出：true示例 3： 輸入：s = "0110", k = 1 輸出：true 解釋：長度為 1 的二進制串包括 "0" 和 "1"，顯然它們都是 s 的子串。示例 4： 輸入：s = "0110", k = 2 輸出：false 解釋：長度為 2 的二進制串 "00" 沒有出現在 s 中。示例 5： 輸入：s = "0000000001011100", k = 4 輸出：false提示： 1 <= s.length <= 5 * 10^5 s 中只含 0 和 1 。 1 <= k <= 20

---

解題：

• 大小為k的滑動窗口，把字符串取出來，轉成int放入集合，看集合中數的種類是不是 2^k 個

class Solution { public:bool hasAllCodes(string s, int k) {if(s.size() <= k)return false;int i, l = 0, r = 0, num;set<int> st;for( ; r < s.size(); ++r){if(r-l+1 == k)//長度為 k {num = 0;for(i = l; i <= r; ++i)//轉成數字num = s[i]-'0' + (num<<1);st.insert(num);l++;}}return st.size()== (1<<k);} };

968 ms 38.9 MB

• stoi函數簡化代碼 http://www.cplusplus.com/reference/string/stoi/

將字符串從給定下標開始的字符子串，從base進制 轉成 10 進制int int stoi (const string& str, size_t* idx = 0, int base = 10); int stoi (const wstring& str, size_t* idx = 0, int base = 10); class Solution { public:bool hasAllCodes(string s, int k) {if(s.size() <= k)return false;int i, l = 0, r = 0;set<int> st;string str;for( ; r < s.size(); ++r){if(r-l+1 == k){str = s.substr(l,k);st.insert(stoi(str,0,2));l++;}}return st.size()== (1<<k);} };

1392 ms 50.2 MB

3. LeetCode 5410. 課程安排 IV medium （Floyd-Warshall）

題目鏈接
你總共需要上 n 門課，課程編號依次為 0 到 n-1 。

有的課會有直接的先修課程，比如如果想上課程 0 ，你必須先上課程 1 ，那么會以 [1,0] 數對的形式給出先修課程數對。

給你課程總數 n 和一個直接先修課程數對列表 prerequisite 和一個查詢對列表 queries 。

對于每個查詢對 queries[i] ，請判斷 queries[i][0] 是否是 queries[i][1] 的先修課程。

請返回一個布爾值列表，列表中每個元素依次分別對應 queries 每個查詢對的判斷結果。

注意：如果課程 a 是課程 b 的先修課程且課程 b 是課程 c 的先修課程，那么課程 a 也是課程 c 的先修課程。

示例 1：

輸入：n = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]] 輸出：[false,true] 解釋：課程 0 不是課程 1 的先修課程，但課程 1 是課程 0 的先修課程。 示例 2： 輸入：n = 2, prerequisites = [], queries = [[1,0],[0,1]] 輸出：[false,false] 解釋：沒有先修課程對，所以每門課程之間是獨立的。

示例 3：

輸入：n = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]] 輸出：[true,true]示例 4： 輸入：n = 3, prerequisites = [[1,0],[2,0]], queries = [[0,1],[2,0]] 輸出：[false,true]示例 5： 輸入：n = 5, prerequisites = [[0,1],[1,2],[2,3],[3,4]], queries = [[0,4],[4,0],[1,3],[3,0]] 輸出：[true,false,true,false]提示： 2 <= n <= 100 0 <= prerequisite.length <= (n * (n - 1) / 2) 0 <= prerequisite[i][0], prerequisite[i][1] < n prerequisite[i][0] != prerequisite[i][1] 先修課程圖中沒有環。 先修課程圖中沒有重復的邊。 1 <= queries.length <= 10^4 queries[i][0] != queries[i][1]

---

解答：

• 參考 弗洛伊德算法，多點源之間的最短路徑，時間復雜度 $O(V^3)$
• 注意 i,j,k 的順序

For each cell (i, j) in M:if i == j:M[i][j] = 0if (i, j) is an edge in E:M[i][j] = weight(i, j)else:M[i][j] = infinity for k from 1 to |V|:for i from 1 to |V|:for j from 1 to |V|:if M[i][j] > M[i][k] + M[k][j]:M[i][j] = M[i][k] + M[k][j] class Solution { public:vector<bool> checkIfPrerequisite(int n, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {vector<vector<bool>> m(n, vector<bool>(n,false));for(auto& pre : prerequisites)m[pre[0]][pre[1]] = true;int i, j, k;for(i = 0; i < n; ++i){for(j = 0; j < n; ++j){for(k = 0; k < n; ++k){if(m[j][i] && m[i][k])//連通判斷m[j][k] = true;}}}vector<bool> ans(queries.size());i = 0;for(auto& q : queries)ans[i++] = m[q[0]][q[1]];return ans;} };

1068 ms 59.5 MB

4. LeetCode 5411. 摘櫻桃 II hard

題目鏈接
給你一個 rows x cols 的矩陣 grid 來表示一塊櫻桃地。 grid 中每個格子的數字表示你能獲得的櫻桃數目。

你有兩個機器人幫你收集櫻桃，機器人 1 從左上角格子 (0,0) 出發，機器人 2 從右上角格子 (0, cols-1) 出發。

請你按照如下規則，返回兩個機器人能收集的最多櫻桃數目：

• 從格子 (i,j) 出發，機器人可以移動到格子 (i+1, j-1)，(i+1, j) 或者 (i+1, j+1) 。
• 當一個機器人經過某個格子時，它會把該格子內所有的櫻桃都摘走，然后這個位置會變成空格子，即沒有櫻桃的格子。
• 當兩個機器人同時到達同一個格子時，它們中只有一個可以摘到櫻桃。
• 兩個機器人在任意時刻都不能移動到 grid 外面。
• 兩個機器人最后都要到達 grid 最底下一行。

示例 1：

輸入：grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]] 輸出：24 解釋：機器人 1 和機器人 2 的路徑在上圖中分別用綠色和藍色表示。 機器人 1 摘的櫻桃數目為 (3 + 2 + 5 + 2) = 12 。 機器人 2 摘的櫻桃數目為 (1 + 5 + 5 + 1) = 12 。 櫻桃總數為： 12 + 12 = 24 。

示例 2：

輸入：grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]] 輸出：28 解釋：機器人 1 和機器人 2 的路徑在上圖中分別用綠色和藍色表示。 機器人 1 摘的櫻桃數目為 (1 + 9 + 5 + 2) = 17 。 機器人 2 摘的櫻桃數目為 (1 + 3 + 4 + 3) = 11 。 櫻桃總數為： 17 + 11 = 28 。示例 3： 輸入：grid = [[1,0,0,3],[0,0,0,3],[0,0,3,3],[9,0,3,3]] 輸出：22示例 4： 輸入：grid = [[1,1],[1,1]] 輸出：4提示： rows == grid.length cols == grid[i].length 2 <= rows, cols <= 70 0 <= grid[i][j] <= 100

---

解題：

• 狀態定義很難，參考的大佬們的思路
• dp[i][j1][j2],表示第 i 層，兩機器人位置為 j1 , j2 的最大值

class Solution { public:int cherryPickup(vector<vector<int>>& grid) {int i, j1, j2, nj1, nj2,k1,k2, m = grid.size(), n = grid[0].size();vector<vector<vector<int>>> dp(m,vector<vector<int>>(n, vector<int>(n,-1)));//dp[i][j1][j2],表示第i層，兩機器人位置為 j1, j2 的最大值dp[0][0][n-1] = grid[0][0]+grid[0][n-1];vector<int> dir = {-1,0,1};int maxPick = 0;for(i = 1; i < m; ++i){for(j1 = 0; j1 < n; ++j1){for(j2 = 0; j2 < n; ++j2){if(dp[i-1][j1][j2] != -1){for(k1 = 0; k1 < 3; ++k1){nj1 = j1 + dir[k1];for(k2 = 0; k2 < 3; ++k2){nj2 = j2 + dir[k2];if(nj1 >= 0 && nj1 < n && nj2 >= 0 && nj2 < n){if(nj1 == nj2)dp[i][nj1][nj2] = max(dp[i][nj1][nj2], dp[i-1][j1][j2]+grid[i][nj1]);elsedp[i][nj1][nj2] = max(dp[i][nj1][nj2], dp[i-1][j1][j2]+grid[i][nj1]+grid[i][nj2]); }}}}} }}for(j1 = 0; j1 < n; ++j1)for(j2 = 0; j2 < n; ++j2)maxPick = max(maxPick, dp[m-1][j1][j2]);return maxPick;} };

140 ms 14.5 MB

總結

以上是生活随笔為你收集整理的LeetCode 第 27 场双周赛（1125/1966，前57.2%）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。