###### Agenda: ###### 10/26 10:00(UTC+8) 10/25 19:00(UTC-7) ###### 公布這次live session題目 ###### 10/26 10:45(UTC+8) 10/25 19:45(UTC-7) ###### 開始逐步給hint ###### 10/26 11:30(UTC+8) 10/25 20:30(UTC-7) ###### 題解 + Q&A ###### 還沒有加入DC伺服器的請記得加入，並去查看#學員驗證頻道進行驗證才可以看到live session的討論區https://discord.gg/WUE3XutPK3 --- ### 本周題目 ### LeetCode biweekly contest 100 ### https://leetcode.com/contest/biweekly-contest-100/ ### 中文題目 ### https://leetcode.cn/contest/biweekly-contest-100/ --- ### Hint - Q1 : - ##### hint 1: 如何強制滿足每個小孩都至少有一元 ---- ### Hint - Q1 - ##### hint 1: 如何強制滿足每個小孩都至少有一元 - ##### hint 2: 若有兩個小孩拿到4元 有沒有辦法調整至符合題目條件 ---- ### Hint - Q1 - ##### hint 1: 如何強制滿足每個小孩都至少有一元 - ##### hint 2: 若有兩個小孩拿到4元 有沒有辦法調整至符合題目條件 - ##### hint 3: 若有一個小孩拿到4元一個小孩拿到1元 有沒有辦法調整至符合題目條件 --- ### Hint - Q2: - ##### hint 1: 轉換一下就變成讓盡量多的數字配對到自己大的數字 ---- ### Hint - Q2: - ##### hint 1: 轉換一下就變成讓盡量多的數字配對到自己大的數字 - ##### hint 2: 一個數字如果要配，配到比自己大的數字中最小的那個會比較好 ---- ### Hint - Q2: - ##### hint 1: 轉換一下就變成讓盡量多的數字配對到自己大的數字 - ##### hint 2: 一個數字如果要配，配到比自己大的數字中最小的那個會比較好 - ##### hint 3: 如何快速找到比自己大的數字，並且支援刪除 --- ### 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: 一個數字有可能被mark兩次 --- ### Hint - Q4 - ##### hint 1: 雖然說題目說是同時修的，但也可以當成一台一台修的 ---- ### Hint - Q4 - ##### hint 1: 雖然說題目說是同時修的，但也可以當成一台一台修的 - ##### hint 2: 修k台車的最佳安排，會從k-1台車的最佳安排來 ---- ### Hint - Q4 - ##### hint 1: 雖然說題目說是同時修的，但也可以當成一台一台修的 - ##### hint 2: 修k台車的最佳安排，會從k-1台車的最佳安排來 - ##### hint 3: 會希望找一個使得答案增加最少的方法 ---- ### Hint - Q4 - ##### hint 1: 雖然說題目說是同時修的，但也可以當成一台一台修的 - ##### hint 2: 修k台車的最佳安排，會從k-1台車的最佳安排來 - ##### hint 3: 會希望找一個使得答案增加最少的方法 - ##### hint 4: 可以預先算每一台機器多處裡一台車總共會花多少時間 --- ### 題解 ---- ### Q1 題目 - 有一些錢要分給小朋友，要滿足以下條件 - 每個小朋友至少有一元 - 不能有小朋友拿到四元 - 希望讓拿到8元的小朋友越多越好 ---- ### Q1 題目 - 合法分配 - money = 20, children = 3 - [6,7,7] - [8,9,3] - 不合法分配 - money = 20, children = 3 - [0,10,10] ,有人只有0元 - [4,8,8] 有人拿到4元 - [1,8,8] 錢沒發完 - [5,8,8] 錢發超過 ---- ### Q1 - money < children - return -1 - moeny == children * 8 - return children - 先把每個人發1元，之後題目變成讓拿到7元小朋友越多越好，不能有小朋友拿到3元 - 窮舉1~children個小朋友拿7元之後，錢是不是足夠 ---- ### Q1 - 如果剩一個小朋友且剩下的錢為3，則不存在一個合法的分配方式當我們發7元給這個數量的小孩子 - 其他都可以換一種分配方式 - [3,0] ->[2,1] - [3,1] ->[2,2] - [3,2] ->[4,1] - [3,3] ->[4,2] ---- ### Q1 c++ code ```c++ int distMoney(int money, int children) { int ans = 0; if (money < children) { return -1; } money -= children; if (children * 7 == money) { return children; } for (int i = 1; i < children; i++) { money -= 7; if (money >= 0) { if (money == 3 && i == children - 1) { break; } ans = i; } else { break; } } return ans; } ``` ---- ### Test case - 錢不夠 - money = 3, children = 4 - 錢剛好夠 - money = 4, children = 4 - 錢可以讓所有小朋友拿到8元 - money = 32, children = 4 - 錢讓所有小朋友拿到8元後還有剩 - money = 33, children = 4 - 錢會讓除了一個的小朋友拿到8元，剩下一個小朋友會拿到4元 - money = 28 ---- ### Q2 題目 - 給一個array nums，假設他的長度為n，接下來開一個新的array perm，長度也為 n，兩個array sort後會長一樣。 - 讓perm[i] > nums[i]的數量越多越好 ---- ### Q2 題目 - [2,3,5,1] - [1,2,3,5] -> 1 - [3,5,1,2] -> 3 ---- ### Q2 - ordered set可以找出比自己大的最小的那個數字，也可以支援刪除 - 將所有數字塞入ordered set後去，接著對每個數字去找有沒有比自己大的數字，從中找最小的 - [1,2,2,4] - [2, _ , _ , _] {1,2,4} - [2,4, _ , _ ] {1,2} ---- ```c++ int maximizeGreatness(vector<int>& nums) { multiset<int> s; for(int num : nums){ s.insert(num); } int ans=0; for(int num : nums){ if(s.upper_bound(num)!=s.end()) { ans++; s.erase(s.upper_bound(num)); } } return ans; } ``` ---- ### Test case - 沒有重複數字 - [1,2,3] - 重複數字超過一半 - [1,2,2,2,3] - 全部都是重複數字 - [2,2,2,2] ---- ### Q3 題目 - 有一個array接下來重複以下操作 - 選一個沒有被標記過最小的數字，如果有很多個選最前面(index 最小)那個 - 把分數加上這個數字 - 將這個數字及他前後兩個數字標記起來 - 重複直每個數字都被標記過 ---- ### Q3 題目 - [2,1,3,4,5,1] - [ _ , _ , _ ,4,5,1] - 選第一個1 score =1 - [ _ , _ , _ ,4, _ , _ ] - 選最後一個1 score = 2 - [ _ , _ , _ , _ , _ , _ ] - 選4 score = 6 ---- ### Q3 - 支援快速找到最小，快速移除數字 -> ordered set - 記得同時記錄一下座標 - [2,1,3,4,5,1] -> {(2,0),(1,1),(3,2),(4,3),(5,4),(1,6)} - [ _ , _ , _ ,4,5,1] remove (2,0) (1,1) (3,2) -> {(4,3),(5,4),(1,6)} - [ _ , _ , _ ,4, _ , _ ] remove(5,4)(1,6) -> {(4,3)} - [ _ , _ , _ , _ , _ , _ ] remove (4,3) -> {} - (3,2),(5,4)不存在set裡面就不用移除了 ---- ```c++ long long findScore(vector<int>& nums) { set<pair<int, int>> s; for (int i = 0; i < nums.size(); i++) { s.insert(make_pair(nums[i], i)); } long long ans = 0; while (s.size()) { auto p = *s.begin(); ans += p.first; s.erase(s.begin()); if (p.second + 1 != nums.size() && s.find(make_pair(nums[p.second + 1], p.second + 1)) != s.end()) { s.erase(s.find(make_pair(nums[p.second + 1], p.second + 1))); } if (p.second != 0 && s.find(make_pair(nums[p.second - 1], p.second - 1)) != s.end()) { s.erase(s.find(make_pair(nums[p.second - 1], p.second - 1))); } } return ans; } ``` ---- ### Test case - 會移除到重複元素的 - [3,1,2,1,4] - 單一一個 - [1] - 兩個元素 - [2,1] - 會移除頭或尾 - [1,2,2,1] ---- ### Q4 題目 - 有 cars台車要修理，有幾個機器可以修理，每個機器有一個rank $r$，一個機器可以同時修理很多台車，當他修理$n$台車時所花的時間為$r*n^2$ - 所有機器同時運作，求最佳安排下最快把所有車修好 ---- ### Q4 題目 - ranks = [4,2,3,1] cars = 10 - 車子分配為[3,2,3,2] - 所需時間[36,8,27,4]，因此這個安排下需要的時間為 36 ---- ### Q4 - 假設現在有k台車在一個rank為r的機器修理，那增加一台車會導致時間從$r*k*k$變成 $r*(k+1)*(k+1)$ - 每次都找一台機器，使得他多修理一台車後需要的時間是所有人增加一台車後需要的時間最少的那個 - 預先算出買台機器多增加一台車後所需要的時間，並取最小那個 - 需要增加值，取最小，移除最小 -> min heap ---- ### Q4 data structure ``` c++ class Machine { public: int id; long long nextTime; Machine(int id, long long nextTime) { this->id = id; this->nextTime = nextTime; } bool operator>(const Machine& machine) const { return nextTime > machine.nextTime; } }; ``` ---- ### Q4 code ```c++ long long repairCars(vector<int>& ranks, int cars) { priority_queue<Machine, vector<Machine>, greater<Machine>> pq; vector<long long> nowCar(ranks.size()); for (int i = 0; i < ranks.size(); i++) { pq.push(Machine(i, ranks[i])); } long long ans = 0; for (int i = 0; i < cars; i++) { Machine machine = pq.top(); pq.pop(); ans = max(ans, machine.nextTime); nowCar[machine.id]++; machine.nextTime = ranks[machine.id] * (nowCar[machine.id] + 1) * (nowCar[machine.id] + 1); pq.push(machine); } return ans; } ``` ---- ### Test case - 有機器不用修 - [100,1,1] cars = 3 - 有幾台機器修的時間一樣 - [1,1,1] cars = 5 --- ### 幫我們填寫一下回饋表單讓我們變得更好 - https://forms.gle/XPtHNLBaNvBXW6B69 -