###### Agenda: ###### 11/02 10:00(UTC+8) 11/01 19:00(UTC-7) ###### 公布這次live session題目 ###### 11/02 10:45(UTC+8) 11/01 19:45(UTC-7) ###### 開始逐步給hint ###### 11/02 11:30(UTC+8) 11/01 20:30(UTC-7) ###### 題解 + Q&A ###### 還沒有加入DC伺服器的請記得加入，並去查看#學員驗證頻道進行驗證才可以看到live session的討論區https://discord.gg/WUE3XutPK3 --- ### 本周題目 ### LeetCode biweekly contest 102 ### https://leetcode.com/contest/biweekly-contest-102/ ### 中文題目 ### https://leetcode.cn/contest/biweekly-contest-102/ --- ### Hint - Q1 : - ##### hint 1: 負的可以轉成正的，最後出來的結果再加一就好了 ---- ### Hint - Q1 - ##### hint 1: 負的可以轉成正的，最後出來的結果再加一就好了 - ##### hint 2: $/10$ 可以讓一個數字少一位。 ---- ### Hint - Q1 - ##### hint 1: 負的可以轉成正的，最後出來的結果再加一就好了 - ##### hint 2: $/10$ 可以讓一個數字少一位。 - ##### hint 3: 思考一下只剩個位數時 $/10$ 會發生什麼事。 --- ### Hint - Q2: - ##### hint 1: $nums[0..i]$ 跟 $nums[0..i+1]$ 的 conversion array 前 i 項是一樣的 ---- ### Hint - Q2: - ##### hint 1: $nums[0..i]$ 跟 $nums[0..i+1]$ 的 conversion array 前 i 項是一樣的 - ##### hint 2: 先把 conversion array 算出來 ---- ### Hint - Q2: - ##### hint 1: $nums[0..i]$ 跟 $nums[0..i+1]$ 的 conversion array 前 i 項是一樣的 - ##### hint 2: 先把 conversion array 算出來 - ##### hint 3: 想一下 conversion array 怎麼傳換成答案 --- ### Hint - Q3 - ##### hint 1: 如何走訪一棵樹 ---- ### Hint - Q3 - ##### hint 1: 如何走訪一棵樹 - ##### hint 2: 走訪時，樹的深度很重要 ---- ### Hint - Q3 - ##### hint 1: 如何走訪一棵樹 - ##### hint 2: 走訪時，樹的深度很重要 - ##### hint 3: 可能可以不只走訪一次 ---- ### Hint - Q3 - ##### hint 1: 如何走訪一棵樹 - ##### hint 2: 走訪時，樹的深度很重要 - ##### hint 3: 可能可以不只走訪一次 - ##### hint 4: 可以考慮在parent時去更新child的答案 --- ### Hint - Q4 - ##### hint 1: 初始化的時候可以先算出兩兩之間的最短路徑，考慮使用 adjancency matrix 來儲存圖。 ---- ### Hint - Q4 - ##### hint 1: 初始化的時候可以先算出兩兩之間的最短路徑，考慮使用 adjancency matrix 來儲存圖。 - ##### hint 2: 兩兩之間最短路徑可以查詢Floyd Warshall(後續會於進階講義提供) ---- ### Hint - Q4 - ##### hint 1: 初始化的時候可以先算出兩兩之間的最短路徑，考慮使用 adjancency matrix 來儲存圖。 - ##### hint 2: 兩兩之間最短路徑可以查詢Floyd Warshall(後續會於進階講義提供) - ##### hint 3: 每次更新 $O(n^2)$ 的複雜度是OK的 ---- ### Hint - Q4 - ##### hint 1: 初始化的時候可以先算出兩兩之間的最短路徑，考慮使用 adjancency matrix 來儲存圖。 - ##### hint 2: 兩兩之間最短路徑可以查詢Floyd Warshall(後續會於進階講義提供) - ##### hint 3: 每次更新 $O(n^2)$ 的複雜度是OK的 - ##### hint 4: 更新的時候是新增一條邊，對於任兩個點的最短路徑來說，要馬有使用到這條邊，要馬不使用這條邊(保持原狀) --- ### 題解 ---- ### Q1 題目 - 定義一個數字的長度為他在10進位的時候最少要用幾個字元表示 - $15$ -> $2$ - $-15$ -> $3$ - 求每個column 最長數字的長度 ---- ### Q1 - 先考慮單獨一個數字 - $0$ 額外處理 - 負數轉正最後答案$+1$ - 一直 $/10$ 並計算次數直到數字變成 $0$ - 在access 2d array時可以直接把 row 跟 column 反過來 ---- ### Q1 c++ 計算數字長度 ```c++ int cal(int x) { int cnt = 0; if (x == 0) { return 1; } if (x < 0) { cnt++; x = -x; } while (x) { cnt++; x /= 10; } return cnt; } ``` ---- ### Q1 c++ 計算每個column答案 ``` c++ vector<int> findColumnWidth(vector<vector<int>>& grid) { vector<int> ans; for (int i = 0; i < grid[0].size(); i++) { int Max = 0; for (int j = 0; j < grid.size(); j++) { Max = max(Max, cal(grid[j][i])); } ans.push_back(Max); } return ans; } ``` ---- ### Test case - 單一個數字 - 正數 - 15 - 負數 - -15 - 0 - 整個2d array - 一個row - 一個column - 2*2 ---- ### Q2 題目 - 給一個 array 長度為 n ，定義一個 array 的 conversion array 為以下 - conversion array 總共有 n 項 - 第 i 項為原本 array 前 i 項的最大值 + 原本 array 的第 i 項。 - 求出 array 每個前綴的 conversion array 總和 ---- ### Q2 題目 - [2,3,7,5,10] - [4] - [4,6] - [4,6,14] - [4,6,14,12] - [4,6,14,12,20] ---- ### Q2 - 可以發現每個前綴的 conversion array 第 i 項都兩兩相等。 - for loop 依序走過每個 array 上的元素，同時更新最大值就可以得到整個 conversion array - [2,3,7,5,10] - [2,3,7,7,10] - conversion array 的 prefix sum 就是答案 - [4,6,14,12,20] - [4,10,24,36,56] ---- ```c++ vector<long long> findPrefixScore(vector<int>& nums) { int Max = 0; long long sum = 0; vector<long long> ans; for (int num : nums) { Max = max(Max, num); sum += Max + num; ans.push_back(sum); } return ans; } ``` ---- ### Test case - Max 會一直變動 - [2,3,5,7] - Max 不會一直變動 - [7,5,3,2] ---- ### Q3 題目 - 給定一棵樹，用link list的方式給。 - 將每個節點的值改成與該節點同一個深度的節點值的總和 扣除 與該節點parent相同的節點值的總和 ---- ### Q3 題目 -  ---- ### Q3 - 做兩次dfs - 第一次dfs 計算出每一層的總和 - 第二次dfs 在當下節點的時候去計算出子節點的答案，可以發現子節點的答案都一樣。 ---- ### 第一次dfs ```c++ void dfs(TreeNode* node, int depth) { if (node == NULL) { return; } if (sum.size() == depth) { sum.push_back(0); } sum[depth] += node->val; dfs(node->left, depth + 1); dfs(node->right, depth + 1); } ``` ---- ### 第二次dfs ```c++ void dfs2(TreeNode* node, int val, int depth) { node->val = val; int res = 0; if (sum.size() > depth + 1) { res = sum[depth + 1]; } if (node->left) { res -= node->left->val; } if (node->right) { res -= node->right->val; } if (node->left) { dfs2(node->left, res, depth + 1); } if (node->right) { dfs2(node->right, res, depth + 1); } } ``` ---- ### 本體 ```c++ TreeNode* replaceValueInTree(TreeNode* root) { dfs(root, 0); dfs2(root, 0, 0); return root; } ``` ---- ### Test case - 只有root - 有節點只有右(左)節點沒有左(右)節點 -  ---- ### Q4 題目 - 給一張圖，點從 $0$ 到 $n-1$，接著有多筆操作， - 詢問問兩兩之間的最短路。 - 增加一條邊。 ---- ### Q4 題目 -  ---- ### Q4 - 在initial的時候，可以用基礎講義內的 Dijkstra 得到兩兩之間的最短路，抑或是可以使用 Floyd Warshall 演算法 - Floyd Warshall 核心概念，假設剛開始兩兩之間的最短路徑，要馬是中間有邊，要馬是無限大 - 那接下來，假設新增了一個點，那兩兩之間的最短路徑，要馬經過這個點，要馬不經過。 - 對於圖中的每一個點都假設他是新增的點，就可以更新出兩兩之間的最短路竟 ---- ### Q4  ---- ### Q4 - 在更新邊的時候，可以想到所有的最短路要馬使用到這條邊，要馬不使用到。 - 因此只要對於任兩個點對，判斷多使用這條邊會不會讓最短距離更短，並以此來更新答案即可。 ---- ### Q4 初始化 ``` c++ Graph(int n, vector<vector<int>>& edges) { dis.resize(n, vector<long long>(n, INT_MAX)); for (int i = 0; i < n; i++) { dis[i][i] = 0; } this->n = n; for (vector<int> edge : edges) { dis[edge[0]][edge[1]] = min(dis[edge[0]][edge[1]], (long long)edge[2]); } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { dis[j][k] = min(dis[j][k], dis[j][i] + dis[i][k]); } } } } ``` ---- ### Q4 更新及回傳答案 ```c++ void addEdge(vector<int> edge) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { dis[i][j] = min(dis[i][j], dis[i][edge[0]] + dis[edge[1]][j] + edge[2]); } } } int shortestPath(int node1, int node2) { if (dis[node1][node2] == INT_MAX) { return -1; } return dis[node1][node2]; } ``` ---- ### Test case - initial - 原本給定的邊就是兩兩之間的最短路了 - [0,1,2] - [1,0,2] - [2,2,0] - 兩兩之間的邊不是最短路(甚至沒有路) - [0,1,5] - [1,0,2] - [5,2,0] - n = 1 ---- ### Test case - update - 會更新最短路徑 - 不會更新任何一對點對的最短路徑 - 詢問 - 自己到自己 - 有被update過的最短路徑 - 沒有被update過的最短路徑 --- ### 幫我們填寫一下回饋表單讓我們變得更好 - https://forms.gle/xcEu34TuDWG2nCsy9 -