###### Agenda: ###### 11/09 10:00(UTC+8) 11/08 19:00(UTC-7) ###### 公布這次live session題目 ###### 11/09 10:45(UTC+8) 11/08 19:45(UTC-7) ###### 開始逐步給hint ###### 11/09 11:30(UTC+8) 11/08 20:30(UTC-7) ###### 題解 + Q&A ###### 還沒有加入DC伺服器的請記得加入，並去查看#學員驗證頻道進行驗證才可以看到live session的討論區https://discord.gg/WUE3XutPK3 --- ### 本周題目 ### LeetCode biweekly contest 345 ### https://leetcode.com/contest/weekly-contest-345/ ### 中文題目 ### https://leetcode.cn/contest/weekly-contest-345/ --- ### Hint - Q1 : - ##### hint 1: 需要一些資料結構去記錄每個人拿過球的狀況。 ---- ### Hint - Q1 - ##### hint 1: 需要一些資料結構去記錄每個人拿過球的狀況。 - ##### hint 2: 可以從該資料結構去判斷遊戲需不需要停止 ---- ### Hint - Q1 - ##### hint 1: 需要一些資料結構去記錄每個人拿過球的狀況。 - ##### hint 2: 可以從該資料結構去判斷遊戲需不需要停止 - ##### hint 3: 想一下如何快速判斷若要將球往後傳 i 個人，這個人會是誰。 --- ### Hint - Q2: - ##### hint 1: xor 在大部分程式語言中，可以用\^操作，不確定相關規則的同學可以自行搜尋。 ---- ### Hint - Q2: - ##### hint 1: xor 在大部分程式語言中，可以用\^操作，不確定相關規則的同學可以自行搜尋。 - ##### hint 2: 第一個數只有兩種可能 ---- ### Hint - Q2: - ##### hint 1: xor 在大部分程式語言中，可以用\^操作，不確定相關規則的同學可以自行搜尋。 - ##### hint 2: 第一個數只有兩種可能 - ##### hint 3: 兩數xor當其中一數為一確定值，另一數也同時會確定 --- ### Hint - Q3 - ##### hint 1: 考慮只有兩個 column ---- ### Hint - Q3 - ##### hint 1: 考慮只有兩個 column - ##### hint 2: 想像三個 column 時如何簡化成兩個column ---- ### Hint - Q3 - ##### hint 1: 考慮只有兩個 column - ##### hint 2: 想像三個 column 時如何簡化成兩個column - ##### hint 3: 在考慮strictly bigger時，其實只需要考慮當下兩個格子即可 ---- ### Hint - Q3 - ##### hint 1: 考慮只有兩個 column - ##### hint 2: 想像三個 column 時如何簡化成兩個column - ##### hint 3: 在考慮strictly bigger時，其實只需要考慮當下兩個格子即可 - ##### hint 4: 可以改成考慮每個格子是否能被到達 --- ### Hint - Q4 - ##### hint 1: 題目要求的subgraph不可以跟該subgraph以外的點有邊。 ---- ### Hint - Q4 - ##### hint 1: 題目要求的subgraph不可以跟該subgraph以外的點有邊。 - ##### hint 2: 考慮先將每個connect component分開來 ---- ### Hint - Q4 - ##### hint 1: 題目要求的subgraph不可以跟該subgraph以外的點有邊。 - ##### hint 2: 考慮先將每個connect component分開來 - ##### hint 3: 剩下就是要判斷每個connect component是不是complete graph。 ---- ### Hint - Q4 - ##### hint 1: 題目要求的subgraph不可以跟該subgraph以外的點有邊。 - ##### hint 2: 考慮先將每個connect component分開來 - ##### hint 3: 剩下就是要判斷每個connect component是不是complete graph。 - ##### hint 4: 題目有說沒有重邊及自環，可能可以讓判斷complete graph變簡單 --- ### 題解 ---- ### Q1 題目 - 玩一個傳球遊戲，大家圍成一個圈，順時鐘方向依序是1, 2, 3, 4...，剛開始球在1號手上。 - 在第i回合，球會傳給當下持球者順時鐘往後數第$(i*k)$個人。 - 當有人拿到第二次球時，遊戲結束，找出所有從頭到尾都沒拿過球的人。 ---- ### Q1 - 假設我們移動人的編號從 1, 2, 3... 變成 0, 1, 2...，這樣我們在找往從i後k個人的時候，可以直接計算成(i+k)%n。 - 接著就照著模擬直到有一個人摸過兩次球。 - 可以開一個 visit array 去紀錄每個人拿球的狀況 - 每個人最多摸過一次球，因次時間複雜度為$O(n)$ ---- ### Q1 c++ ```c++ vector<int> circularGameLosers(int n, int k) { int vis[55]; fill(vis, vis + n, 0); int now = 0; int round = 1; while (!vis[now]) { vis[now] = 1; now = (now + round * k) % n; round++; } vector<int> ans; for (int i = 0; i < n; i++) { if (!vis[i]) { ans.push_back(i + 1); } } return ans; } ``` ---- ### Test case - 所有人都有拿到球過 - n=2 k=1 - 只有一個人拿到球過 - n=10, k=10 - n=1 ---- ### Q2 題目 - 有一個 original array，裡面只有0跟1。 - 一個新的array derived，$derived[i] = original[i]$ ^ $original[(i+1)\%n]$ - 給定derived，求出是否存在一個original，可以產出derived ---- ### Q2 題目 - original:[1,0,1] - derived:[1,1,0] ---- ### Q2 - 根據hint 3，假設我們知道array的第i個值，就可以得到第i+1個值，而根據hint 2，array的每一個值都只有兩種可能。 - 窮舉array第一位的兩種可能，並驗算出derived是否存在即可。 ---- ```c++ bool doesValidArrayExist(vector<int>& derived) { for (int i = 0; i < 2; i++) { int now = i; for (int j = 0; j + 1 < derived.size(); j++) { now = now ^ derived[j]; } if ((now ^ i) == derived.back()) { return true; } } return false; } ``` ---- ### Test case - 答案為yes - original:[1,0,1] - derived:[1,1,0] - 答案為no - derived:[1,1,1] ---- ### some fact - 事實上答案為yes時首項為1跟0會各存在一組解，只需要將全部數字xor 1即可。 - derived:[1,1,0] - original:[1,0,1][0,1,0] ---- ### Q3 題目 - 給定一個n*m的grid，我們可以選擇第一個column的任何一格作為起點，之後假設當下格子為(row, column)，那下一步可以前往(row+1,column+1),(row,column+1),(row-1,column+1)，但前往的格子必須嚴格大於當下格子 ---- ### Q3 題目 -  ---- ### Q3 - 可以開一個跟grid一樣大的array去記錄每個格子是否可以被到達 - 若該格在column 0 則該格子可被到達 - 若該格在(row,column)，則檢查(row-1,column-1),(row,column-1),(row+1,column-1)，滿足下列**所有條件**就標成可到達 - 被檢查的格子可到達 - 被檢查的格子數字 < grid[row][column] ---- ### Q3 c++ code ```c++ int maxMoves(vector<vector<int>>& grid) { vector<vector<int>> visited(grid.size(), vector<int>(grid[0].size())); for (int i = 0; i < grid.size(); i++) { visited[i][0] = 1; } int ans = 0; for (int i = 1; i < grid[0].size(); i++) { for (int j = 0; j < grid.size(); j++) { for (int k = -1; k <= 1; k++) { int ty = i - 1, tx = j + k; if (ty >= 0 && ty < grid[0].size() && tx >= 0 && tx < grid.size() && grid[tx][ty] < grid[j][i] && visited[tx][ty]) { visited[j][i] = 1; ans = max(ans, i); } } } } return ans; } ``` ---- ### Test case - 存在一條可以到達最後一column - [1,2,3] - [4,3,2] - 若題目改成bigger or equal就可以到達最後一column - [1,2,2] - 無法往前進 - [2,1] - [3,2] ---- ### Test case - 需要上下走 - [10,9,1] - [8,1,10] - row = 1 - column = 1 ---- ### Q4 題目 - 給一張簡單圖(無自環及重邊)，問有幾個 subgraph 沒有跟其他非該 subgraph 的 node 有連邊，且該 subgraph 為完全圖。 - 完全圖定義 : 該 graph 任兩個點中間皆存在一條邊 ---- ### Q4 題目 -  ---- ### Q4 - 先用 disjoint set，去將所有 connect component 分開來。 - 接下來只要數每個 connect component 的邊數是否為 $\frac{點數*(點數-1)}2$ ---- ### Q4 ``` c++ int countCompleteComponents(int n, vector<vector<int>>& edges) { parent.resize(n); edgeCount.resize(n, 0); nodeCount.resize(n, 0); for (int i = 0; i < n; i++) { parent[i] = i; } for (auto edge : edges) { int x = Find(edge[0]), y = Find(edge[1]); parent[x] = y; } for (auto edge : edges) { edgeCount[Find(edge[0])]++; } for (int i = 0; i < n; i++) { nodeCount[Find(i)]++; } int ans = 0; for (int i = 0; i < n; i++) { if (parent[i] == i) { if (nodeCount[i] * (nodeCount[i] - 1) / 2 == edgeCount[i]) { ans++; } } } return ans; } ``` ---- ### Test case - 有單一一個點 - 兩個點一條邊 - 三個點以上的完全圖 ---- ### Test case - 少一條邊的完全圖 -  --- ### 幫我們填寫一下回饋表單讓我們變得更好 - https://forms.gle/D6LcJ34PCCA49PVZ8 -