###### Agenda: ###### 11/30 10:00(UTC+8) 11/29 19:00(UTC-7) ###### 公布這次live session題目 ###### 11/30 10:45(UTC+8) 11/29 19:45(UTC-7) ###### 開始逐步給hint ###### 11/30 11:30(UTC+8) 11/29 20:30(UTC-7) ###### 題解 + Q&A ###### 還沒有加入DC伺服器的請記得加入，並去查看#學員驗證頻道進行驗證才可以看到live session的討論區https://discord.gg/WUE3XutPK3 --- ### 本周題目 ### LeetCode weekly contest 394 ### https://leetcode.com/contest/weekly-contest-394/ ### 中文題目 ### https://leetcode.cn/contest/weekly-contest-394/ --- ### Hint - Q1 : - ##### hint 1: 想一下如何判斷當下的字母是大寫還是小寫 ---- ### Hint - Q1 - ##### hint 1: 想一下如何判斷當下的字母是大寫還是小寫 - ##### hint 2: 最多只有26個不同的字母(不管大小寫) ---- ### Hint - Q1 - ##### hint 1: 想一下如何判斷當下的字母是大寫還是小寫 - ##### hint 2: 最多只有26個不同的字母(不管大小寫) - ##### hint 3: 每個字母判斷一下有沒有出現過大小寫 --- ### Hint - Q2: - ##### hint 1: 考慮只有一個字母時，他符合答案應該要長什麼樣子 ---- ### Hint - Q2: - ##### hint 1: 考慮只有一個字母時，他符合答案應該要長什麼樣子 - ##### hint 2: 列一下不符合答案的狀態有幾種 ---- ### Hint - Q2: - ##### hint 1: 考慮只有一個字母時，他符合答案應該要長什麼樣子 - ##### hint 2: 列一下不符合答案的狀態有幾種 - ##### hint 3: 若出現小寫後又出現大寫則不符合答案 --- ### Hint - Q3 - ##### hint 1: 題目轉換後，其實是我們想讓同一個column 的數字相同，且相鄰 column 的數字不一樣 ---- ### Hint - Q3 - ##### hint 1: 題目轉換後，其實是我們想讓同一個column 的數字相同，且相鄰 column 的數字不一樣 - ##### hint 2: 其實對於一個 column 來說，我們只在意每個數字出現了幾次 ---- ### Hint - Q3 - ##### hint 1: 題目轉換後，其實是我們想讓同一個column 的數字相同，且相鄰 column 的數字不一樣 - ##### hint 2: 其實對於一個 column 來說，我們只在意每個數字出現了幾次 - ##### hint 3: 想像我們從第一個 column 開始填，對於之後每個 column ，我們只在意前一個 column 填了甚麼數字 ---- ### Hint - Q3 - ##### hint 1: 題目轉換後，其實是我們想讓同一個column 的數字相同，且相鄰 column 的數字不一樣 - ##### hint 2: 其實對於一個column來說，我們只在意每個數字出現了幾次 - ##### hint 3: 想像我們從第一個column開始填，對於之後每個column，我們只在意前一個column填了甚麼數字 - ##### hint 4: 每一個column只需要跟前後兩個column比對，因此只需要考慮前三大出現的數字 --- ### Hint - Q4 - ##### hint 1: 先算出0->n-1的最短路 ---- ### Hint - Q4 - ##### hint 1: 先算出0->n-1的最短路 - ##### hint 2: 在算出最短路時，其實0到每個點的最短路都被算出來了 ---- ### Hint - Q4 - ##### hint 1: 先算出0~n-1的最短路 - ##### hint 2: 在算出最短路時，其實0到每個點的最短路都被算出來了 - ##### hint 3: 一條路連接(x,y)有沒有在0~n-1最短路裡面其實可以嘗試硬走到這條路 ---- ### Hint - Q4 - ##### hint 1: 先算出0~n-1的最短路 - ##### hint 2: 在算出最短路時，其實0到每個點的最短路都被算出來了 - ##### hint 3: 一條路連接(x,y)有沒有在0~n-1最短路裡面其實可以嘗試硬走到這條路 - ##### hint 4: 硬走的意思其實是就從 0 走到 x 再從 x 走這條路到 y 再從 y 走到 n-1 ---- ### Hint - Q4 - ##### hint 1: 先算出0~n-1的最短路 - ##### hint 2: 在算出最短路時，其實0到每個點的最短路都被算出來了 - ##### hint 3: 一條路連接(x,y)有沒有在0~n-1最短路裡面其實可以嘗試硬走到這條路 - ##### hint 4: 硬走的意思其實是就從 0 走到 x 再從 x 走這條路到 y 再從 y 走到 n-1 - ##### hint 5: 從 y 走到 n-1 這段資料還沒有，是不是有辦法也預先處理出來 --- ### 題解 ---- ### Q1 題目 - 給一個字串，問有幾個字母的大寫及小寫都在字串裡面出現過 ---- ### Q1 - 使用一個26長度的array，去紀錄每個字母的出現情況 - 每格array可以再使用一個長度為2的array ---- ### Q1 c++ ```c++ //time complexity: O(n) //Extra space complexity: O(1) int numberOfSpecialChars(string word) { int vis[26][2]; memset(vis, 0, sizeof(vis)); for (auto it : word) { if (it >= 'a' && it <= 'z') { vis[it - 'a'][0] = 1; } else { vis[it - 'A'][1] = 1; } } int ans = 0; for (int i = 0; i < 26; i++) { if (vis[i][0] && vis[i][1]) { ans++; } } return ans; } ``` ---- ### Test case - 字母只出現大寫 - 字母只出現小寫 - 字母大小寫都出現 - "AaBc" ---- ### Q2 題目 - 給一個字串，問有幾個字母的大寫及小寫都在字串裡面出現過 - 但如果該字母的所有小寫需要出現在第一個大寫前 ---- ### Q2 - 考慮一個字母，他應該會長成這樣 - "aaaaAAAA" - 所以跟Q1一樣紀錄大小寫，但在記錄小寫的時候，額外判斷前面是否出現過大寫了 ---- ```c++ //time complexity: O(n) //Extra space complexity: O(1) int numberOfSpecialChars(string word) { int vis[26][3]; memset(vis, 0, sizeof(vis)); for (auto it : word) { if (it >= 'a' && it <= 'z') { vis[it - 'a'][0] = 1; if (vis[it - 'a'][1]) { vis[it - 'a'][2] = 1; } } else { vis[it - 'A'][1] = 1; } } int ans = 0; for (int i = 0; i < 26; i++) { if (vis[i][0] && vis[i][1] && !vis[i][2]) { ans++; } } return ans; } ``` ---- ### Test case - 跟Q1 類似 - 額外檢查在Q2會不被視為答案的測資 - "Aa" - "aAa" ---- ### Q3 題目 - 給一個grid，每一格為一個0~9的數字，每次操作可以更換一格的數字 - 求最少操作次數使得同一個column數字相同，相鄰的column數字不相同 ---- ### Q3 題目 - 合法狀態  - 不合法狀態  ---- ### Q3 - 假設我們從第一個column開始填，因為可以從前一個column的狀態得到現在的答案因此想使用dp - 定義dp狀態 dp[i][j] = 前i個column後面且第i個column使用j這個數字時，需要更改幾個數字(or 有幾個數字不用被更改) ---- ### Q3 - 因為每個column只考慮前三高頻率出現的數字的 所以我們可以轉換一下讓j變成第j高頻率出現的數字 - 轉移就是 dp[i][j] = dp[i-1][k] + 第i column第j高頻率出現數字的次數 且只有在j跟k代表數字不相同時才能轉移 ---- ### Q3 處理出前三大出現次數 ```c++ //time complexity: O(n*m) //Extra space complexity: O(m) vector<vector<int>> dp(grid[0].size(), vector<int>(3)); vector<vector<pair<int, int>>> numberCnt(grid[0].size()); for (int i = 0; i < grid[0].size(); i++) { int cnt[10]; fill(cnt, cnt + 10, 0); for (int j = 0; j < grid.size(); j++) { cnt[grid[j][i]]++; } for (int j = 0; j < 10; j++) { numberCnt[i].push_back(make_pair(cnt[j], j)); } sort(numberCnt[i].begin(), numberCnt[i].end()); reverse(numberCnt[i].begin(), numberCnt[i].end()); } ``` ---- ### Q3 更新 dp 狀態 ```c++ for (int i = 0; i < 3; i++) { dp[0][i] = numberCnt[0][i].first; } for (int i = 1; i < grid[0].size(); i++) { for (int j = 0; j < 3; j++) { for (int k = 0; k < 3; k++) { if (numberCnt[i][j].second != numberCnt[i - 1][k].second) { dp[i][j] = max(dp[i][j], dp[i - 1][k] + numberCnt[i][j].first); } } } } int ans = 0; for (int i = 0; i < 3; i++) { ans = max(ans, dp[grid[0].size() - 1][i]); } return grid.size() * grid[0].size() - ans; ``` ---- ### Test case - 要用到第三高頻率出現的數字 - [1,1,2] - [1,1,2] - [1,2,2] - [1,2,2] - [1,3,2] - 一個column - 一個row - 會有兩邊相同數字的 - [1,1,1] - [1,0,1] ---- ### Q4 題目 - 給定一個無向的 graph ，對於每一個 edge ，想確認是否有一條0->n-1的最短路徑會走經過這條edge ---- ### Q4 題目 -  ---- ### Q4 - 看到hint 4，我們把一條路徑切成 0->x x->y y->n-1，若這條路徑長度與0->n-1相同，代表x y可以作為每條最短路徑的一部分 - 0->x 可以用0走最短路徑得到所有答案 - y->n-1 其實也可以用n-1走最短路徑得到所有答案 - 用0跟n-1去做最短路徑，接下來拿每條路徑嘗試一次就可以了 ---- ### Q4 最短路徑 ``` c++ //time complexity: O((n+m) log m) //Extra space complexity: O(m) vector<int> shortestPath(int n, int start, vector<vector<pair<int, int>>> v) { priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push(make_pair(0, start)); vector<int> dis(n, -1); while (!pq.empty()) { auto p = pq.top(); pq.pop(); if (dis[p.second] != -1) { continue; } dis[p.second] = p.first; for (auto it : v[p.second]) { if (dis[it.first] == -1) { pq.push(make_pair(p.first + it.second, it.first)); } } } return dis; } ``` ---- ### Q4 main ``` c++ vector<bool> findAnswer(int n, vector<vector<int>>& edges) { vector<vector<pair<int, int>>> v(n); for (auto it : edges) { v[it[0]].push_back(make_pair(it[1], it[2])); v[it[1]].push_back(make_pair(it[0], it[2])); } auto dis1 = shortestPath(n, 0, v); auto dis2 = shortestPath(n, n - 1, v); vector<bool> res; for (auto it : edges) { if (dis1[n - 1] == -1 || dis1[it[0]] == -1 || dis1[it[1]] == -1) { res.push_back(false); } else if (dis1[it[0]] + dis2[it[1]] + it[2] == dis1[n - 1]) { res.push_back(true); } else if (dis1[it[1]] + dis2[it[0]] + it[2] == dis1[n - 1]) { res.push_back(true); } else { res.push_back(false); } } return res; } ``` ---- ### Test case - 0到不了 n - 1 - 有些路徑到不了 n - 1 -  - 所有edge都可以是最短路徑的一部分 --- ### 幫我們填寫一下回饋表單讓我們變得更好 - https://forms.gle/U995TPnVEiEziyjm9