###### Agenda: ###### 11/23 10:00(UTC+8) 11/22 19:00(UTC-7) ###### 公布這次live session題目 ###### 11/23 10:45(UTC+8) 11/22 19:45(UTC-7) ###### 開始逐步給hint ###### 11/23 11:30(UTC+8) 11/22 20:30(UTC-7) ###### 題解 + Q&A ###### 還沒有加入DC伺服器的請記得加入，並去查看#學員驗證頻道進行驗證才可以看到live session的討論區https://discord.gg/WUE3XutPK3 --- ### 本周題目 ### LeetCode weekly contest 375 ### https://leetcode.com/contest/weekly-contest-375/ ### 中文題目 ### https://leetcode.cn/contest/weekly-contest-375/ --- ### Hint - Q1 : - ##### hint 1: 第$i$部手機是第$i$次被測試的 ---- ### Hint - Q1 - ##### hint 1: 第$i$部手機是第$i$次被測試的 - ##### hint 2: 想像成每過一秒就測試一台手機，且所有手機電量掉一格 ---- ### Hint - Q1 - ##### hint 1: 第$i$部手機是第$i$次被測試的 - ##### hint 2: 想像成每過一秒就測試一台手機，且所有手機電量掉一格 - ##### hint 3: 可以紀露一下現在已經測試過幾台手機。 --- ### Hint - Q2: - ##### hint 1: 每個variables可以當成單純一個問題 ---- ### Hint - Q2: - ##### hint 1: 每個variables可以當成單純一個問題 - ##### hint 2: java跟c++不要使用內建函式 pow ---- ### Hint - Q2: - ##### hint 1: 每個variables可以當成單純一個問題 - ##### hint 2: java跟c++不要使用內建函式 pow - ##### hint 3: 注意一下算式的順序 ---- ### Hint - Q2: - ##### hint 1: 每個variables可以當成單純一個問題 - ##### hint 2: java跟c++不要使用內建函式 pow - ##### hint 3: 注意一下算式的順序 - ##### hint 4: a\*b%mod = ((a%mod)\*b)%mod --- ### Hint - Q3 - ##### hint 1: 先找出最大值是誰 ---- ### Hint - Q3 - ##### hint 1: 先找出最大值是誰 - ##### hint 2: 可以將題目反過來，所有subarray扣除不符合答案的 ---- ### Hint - Q3 - ##### hint 1: 先找出最大值是誰 - ##### hint 2: 可以將題目反過來，所有subarray扣除不符合答案的 - ##### hint 3: subarray越長越容易符合答案 ---- ### Hint - Q3 - ##### hint 1: 先找出最大值是誰 - ##### hint 2: 可以將題目反過來，所有subarray扣除不符合答案的 - ##### hint 3: subarray越長越容易符合答案 - ##### hint 4: 想像每個結尾，要符合答案至少要多長 --- ### Hint - Q4 - ##### hint 1: 在array的中間切一刀，會使的左右兩邊的東西永遠不能分在同一個partition ---- ### Hint - Q4 - ##### hint 1: 在array的中間切一刀，會使的左右兩邊的東西永遠不能分在同一個partition - ##### hint 2: 題目需要把相同數字分在同一個partition ---- ### Hint - Q4 - ##### hint 1: 在array的中間切一刀，會使的左右兩邊的東西永遠不能分在同一個partition - ##### hint 2: 題目需要把相同數字分在同一個partition - ##### hint 3: 換句話就是，所一個數字出現在i跟j，則不能再i跟j中間切一刀 ---- ### Hint - Q4 - ##### hint 1: 在array的中間切一刀，會使的左右兩邊的東西永遠不能分在同一個partition - ##### hint 2: 題目需要把相同數字分在同一個partition - ##### hint 3: 換句話就是，所一個數字出現在i跟j，則不能再i跟j中間切一刀 - ##### hint 4: 剩下每一刀切或不切都不影響答案 --- ### 題解 ---- ### Q1 題目 - 每個手機有一個電量，接著要開始測試手機，只有手機電量非0的時候才可以測試。 - 從第一台手機依序開始測試，每測試完一台手機，後面的手機電量就會-1。 - 問有幾台手機可以完成測試 ---- ### Q1 - 紀錄一下現在已經測試完幾台手機 - 若手機電量>已經測試完的手機數量，則這個手機可以測試。 ---- ### Q1 c++ ```c++ //time complexity: O(n) //Extra space complexity: O(1) int countTestedDevices(vector<int>& batteryPercentages) { int ans=0; for(int i = 0;i<batteryPercentages.size();i++){ if(batteryPercentages[i]>ans) { ans++; } } return ans; } ``` ---- ### Test case - 所有手機都可以測試 - [1,2,3,4] - 只能測試第一台手機 - [1,1,1,1] - 有手機剛好不能測試 - [1,2,2] - 前面有比較高的電量 - [1,3,2] ---- ### Q2 題目 - 有n組variable(a,b,c,m)。 - 判斷每組variable是否滿足 $(a^b\ mod\ 10)^c\ mod\ m = target$ ---- ### Q2 題目 - [2,3,3,10] - $(2^3\ \%10)^3\ \%10 = 2$ ---- ### Q2 - 每個variable直接算答案就可以了，記得每次做完乘法都要直接取mod。 - 大部分語言內建的pow都換算出浮點數，所以當次方數字變大時就一定會出錯 ---- ```c++ //time complexity: O(n) //Extra space complexity: O(1) vector<int> getGoodIndices(vector<vector<int>>& variables, int target) { vector<int> ans; for(int i = 0;i<variables.size();i++){ int a=variables[i][0],b=variables[i][1],c=variables[i][2],m=variables[i][3]; long long temp = 1,res = 1; for(int j=0;j<b;j++) { temp = temp * a % 10; } for(int j=0;j<c;j++){ res = res * temp % m; } if(res == target){ ans.push_back(i); } } return ans; } ``` ---- ### Q2 - 其實次方可以用更快的算法 - binary lifting - 也就是假設要算$a^b$ 我們可以算出 $a^1\ a^2\ a^4\ a^8 ...$，之後看b的二進位組成決定把哪幾個a乘起來。 - $a^i$可以用$(a^{i/2})^2$算出來 ---- ### Q2 binary lifting ```c++ //time complexity: O(log b) //Extra space complexity: O(1) long long f_pow(int a,int b,int mod){ long long res = 1, temp = a; while(b){ if(b&1){ res = res * temp % mod; } temp = temp * temp %mod; b>>=1; } return res; } ``` ---- ### Test case - 答案為yes - [2,3,3,10], target = 2 - 答案為no - [3,3,3,1], target = 2 ---- ### Q3 題目 - 給定一個array，假設這個array的最大值為max，問有幾個subarray裡面的max出現超過k次 ---- ### Q3 題目 - [1,3,2,3,3] ---- ### Q3 - 可以考慮反過來數不符合答案的subarray，再用subarray的數量$(n*(n+1)/2)$扣掉 - 對於每個右界，找出最遠的左界使得最大值的數量$<k$ - 可以使用sliding window，每次右界往後移，當最大值數量$\ge k$時移動左界 ---- ### Q3 c++ code ```c++ //time complexity: O(n) //Extra space complexity: O(1) long long countSubarrays(vector<int>& nums, int k) { int Max = 0; long long n = nums.size(); for (auto it : nums) { Max = max(Max, it); } long long ans = 0; int l = 0, cnt = 0; for (int i = 0; i < nums.size(); i++) { if (nums[i] == Max) { cnt++; } while (cnt >= k) { if (nums[l] == Max) { cnt--; } l++; } ans += (i - l + 1); } return n * (n + 1) / 2 - ans; } ``` ---- ### Test case - array所有數字相同 - k = 1 - array最大值數量$<k$ ---- ### Q4 題目 - 給定一個array，現在要將array切塊，每一塊包含一個subarray，任兩個subarray不重疊，且每一個元素都要屬於一個subarray - 要求被分在不同subarray的數字必須不相同 ---- ### Q4 題目 - [1,1,2,2] - [1,1][2,2] - [1,1,2][2] ---- ### Q4 - 分塊相當於在array上切幾刀 - 看一下hint 3 可以想到若一個數字出現在i跟j則中間都不能被切刀 - 計算出每個數字最左邊及最右邊，他們中間就不能被切開 ---- ### Q4 - 剩下的地方都可以被切開，假設有k個地方，每個地方切或不切答案為$2^k$ - 我們想要將i~j都標示成不能且可以使用前綴的方式pre[i] +1,pre[j] - 1，最後取前綴和就可以知道每個位子可不可以切 - i=1,j=3 - [0,1,0,-1,0] - prefix sum:[0,1,1,0,0] ---- ### Q4 ``` c++ //time complexity: O(n) //Extra space complexity: O(n) const int mod=1e9+7; int numberOfGoodPartitions(vector<int>& nums) { unordered_map<int,int> Max,Min; for(int i = 0;i<nums.size();i++){ Max[nums[i]]=max(Max[nums[i]],i); if(Min.find(nums[i])==Min.end()){ Min[nums[i]]=i; } } vector<int> vis(nums.size()); for(auto num:Max){ vis[Min[num.first]]++; vis[num.second]--; } long long ans= 1; int sum=0; for(int i = 0;i+1<nums.size();i++){ sum+=vis[i]; if(sum == 0){ ans=ans*2%mod; } } return ans; } ``` ---- ### Test case - 有些數字只出現過一次 - 整個array都不能切 - array長度為1 --- ### 幫我們填寫一下回饋表單讓我們變得更好 - https://forms.gle/zWx5X3oyNJunm7Kt6