###### Agenda: ###### 10/18 22:00(UTC+8) 10/18 07:00(UTC-7) ###### 公布這次live session題目 ###### 10/18 22:30(UTC+8) 10/18 07:30(UTC-7) ###### 開始逐步給hint ###### 10/18 23:00(UTC+8) 10/18 08:00(UTC-7) ###### 題解 + Q&A ###### 還沒有加入DC伺服器的請記得加入，並去查看#學員驗證頻道進行驗證才可以看到live session的討論區https://discord.gg/WUE3XutPK3 --- #### 本周題目 #### Leetcode 1390 #### https://leetcode.com/problems/four-divisors/description/ #### Leetcode 1482 #### https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/description/ --- ### Hint - Leetcode 1390 : - hint 1: 如何窮舉出一個數的所有因數 ---- ### Hint - Leetcode 1390 : - hint 1: 如何窮舉出一個數的所有因數 - hint 2: 想一想因數的性質 ---- ### Hint - Leetcode 1390 : - hint 1: 如何窮舉出一個數的所有因數 - hint 2: 想一想因數的性質 - hint 3: 因數大部分都是兩兩一對出現的 ---- ### Hint - Leetcode 1390 : - hint 1: 如何窮舉出一個數的所有因數 - hint 2: 想一想因數的性質 - hint 3: 因數大部分都是兩兩一對出現的 - hint 4: 想一想因數比較小的那個的範圍 --- ### Hint - Leetcode 1482 : - hint 1: 題目說明須要連續的花朵，若有連續x朵花朵，可以產生幾個花束呢 ---- ### Hint - Leetcode 1482 : - hint 1: 題目說明須要連續的花朵，若有連續x朵花朵，可以產生幾個花束呢 - hint 2: 假設已經知道哪幾朵花有開，能不能判斷答案呢 ---- ### Hint - Leetcode 1482 : - hint 1: 題目說明須要連續的花朵，若有連續x朵花朵，可以產生幾個花束呢 - hint 2: 假設已經知道哪幾朵花有開，能不能判斷答案呢 - hint 3: 假設現在改成問第幾天能產生多少花束，要如何做呢。 ---- ### Hint - Leetcode 1482 : - hint 1: 題目說明須要連續的花朵，若有連續x朵花朵，可以產生幾個花束呢 - hint 2: 假設已經知道哪幾朵花有開，能不能判斷答案呢 - hint 3: 假設現在改成問第幾天能產生多少花束，要如何做呢。 - hint 4: 時間越晚，則越有機會完成所有花束，若現在在第d天，則bloomDay<=d的花有開，其他的花沒有開 --- ### 題解 ---- ### Leetcode 1390 題目 - 給你一個array，找出array中的數字滿足它的因數數量剛好為4個，並計算他們的所有因數總和 ---- ### Leetcode 1390 題目 - 考慮單一一個數字，因為因數都是兩兩成對出現的，比較小的那個因數會$\leq \sqrt n$，因此只要窮舉到$\sqrt n$就可以得到所有的因數。 - 單一一個數字檢查時間為$O(\sqrt n)$，總體複雜度為$O(|nums|\sqrt n)$ - 注意兩個一樣的因數相乘 ---- ### Q1 java code ```java public int sumFourDivisors(int[] nums) { int res = 0; for (int num : nums) { int cnt = 0; int sum = 0; for (int i = 1; i * i <= num; i++) { if (num % i == 0) { cnt++; sum += i; if (num / i != i) { cnt++; sum += num / i; } } } if (cnt == 4) { res += sum; } } return res; } ``` ---- ### Test case - 只考慮一個數字 - 1 因數數量少於4 - 4 質數的平方 - 8 因數數量等於4 - 12 因數數量大於4 ---- ### Leetcode 1482 題目 - 給一個 array 裡面，每個位子為一朵花，array上的數字代表開花的日期。 - 需要準備 $m$ 個花束，每個花束為需要 $k$ 朵花，且這 $k$ 朵花在 array 上需要相鄰。 - 問最早要等到什麼時候才能準備好這 $m$ 個花束。 ---- ### Leetcode 1482 解法 - 用 binary search 去找出正確的時間。 - 搜尋一個值的時候，將開花日期早於這個時間的花當成$1$，其他當成$0$ - 找出這個 array 上所有連續的 $1$，假設有 $x$ 個連續的 $1$，則他們就可以完成 $\lfloor x/k\rfloor$ 個花束 - 因為只有有開花的日子才有意義，因此可以將有開花的日子蒐集起來排序，這樣複雜度就可以達到 $O(n\ log\ n)$ ---- ### Leetcode 1482 ```java public int minDays(int[] bloomDay, int m, int k) { int[] days= new int[bloomDay.length]; for(int i = 0 ; i < bloomDay.length ; i++){ days[i] = bloomDay[i]; } Arrays.sort(days); int min = -1, max = bloomDay.length; while(max - min > 1){ int mid = (max + min) / 2; int cnt = 0; int oneCount = 0; for(int i = 0 ; i < bloomDay.length ; i++){ if(bloomDay[i] <= days[mid]) { oneCount++; } else { oneCount = 0; } if(oneCount == k) { cnt++; oneCount = 0; } } if(cnt >= m) { max = mid; } else { min = mid; } } if (max == bloomDay.length) { return -1; } return days[max]; } ``` ---- ### Test case - $m*n > |bloomDay|$ - $m*n == |bloomDay|$ - 前 m*k早開的花就可以達成條件 - [1,1,3,3,2,2] k=2 m=2 ---- ### Test case - 前 m*k 早開的花就不能達成條件 - [1,3,1,3,2,2] k=2 m=2 - 過程中的array可能會有連續x個1但x不能被k整除 - [1,1,1,3,3] k=2 m=2 - 最佳答案卡在中間 - [3,1,1,1,3,3] k=3 m=1 - k=1 m=1 [2,1,3] ---- ### 幫忙填寫個回饋問卷讓我們變得更好 - https://forms.gle/XLqty66ZYHYUDPmUA -