1004 live session

###### Agenda: ###### 10/04 22:00(UTC+8) 10/04 07:00(UTC-7) ###### 公布這次live session題目 ###### 10/04 22:30(UTC+8) 10/04 07:30(UTC-7) ###### 開始逐步給hint ###### 10/04 23:00(UTC+8) 10/04 08:00(UTC-7) ###### 題解 + Q&A ###### 還沒有加入DC伺服器的請記得加入，並去查看#學員驗證頻道進行驗證才可以看到live session的討論區https://discord.gg/WUE3XutPK3 --- #### 本周題目 #### Leetcode 1952 #### https://leetcode.com/problems/three-divisors/description/ #### Leetcode 954 #### https://leetcode.com/problems/array-of-doubled-pairs/ --- ### Hint - Leetcode 1952 : - hint 1:如何判斷一個數可以被另一個數整除 ---- ### Hint - Leetcode 1952 : - hint 1:如何判斷一個數可以被另一個數整除 - hint 2:如何列出一個數所有的因數 --- ### Hint - Leetcode 954 : - hint 1:題目簡化後變成，有偶數個數字，有沒有辦法將數字兩兩一對，使得每一對數字其中一個為另一個的兩倍 ---- ### Hint - Leetcode 954 : - hint 1:題目簡化後變成，有偶數個數字，有沒有辦法將數字兩兩一對，使得每一對數字其中一個為另一個的兩倍 - hint 2: 假如只有正整數 ---- ### Hint - Leetcode 954 : - hint 1:題目簡化後變成，有偶數個數字，有沒有辦法將數字兩兩一對，使得每一對數字其中一個為另一個的兩倍 - hint 2: 假如只有正整數 - hint 3: 考慮拿到一個數字後，可以跟他配對的數字有哪幾種可能性 ---- ### Hint - Leetcode 954 : - hint 1:題目簡化後變成，有偶數個數字，有沒有辦法將數字兩兩一對，使得每一對數字其中一個為另一個的兩倍 - hint 2: 假如只有正整數 - hint 3: 考慮拿到一個數字後，可以跟他配對的數字有哪幾種可能性 - hint 4: 當拿到的為正整數，乘2之後數字會變大，有沒有一個順序，可以讓當下數字的可能性只有一種 --- ### 題解 ---- ### Leetcode 1952 - 這題要問的是給定的數字是否只有 3 個因數 - 若 a 除以 b 的餘數為 0，代表 b 為 a 的因數 - 在大部分程式語言中，可以使用 % 來得到餘數 - 3 % 2 = 1 (3 除以 2 的餘數為 1) - 7 % 4 = 3 (7 除以 2 的餘數為 3) - 用一個迴圈窮舉出所有可能的 $\leq n$ 的數字並判斷他是不是 $n$ 的因數就可以了，時間複雜度為$O(n)$ ---- ### Q1 java code ```java public boolean isThree(int n) { int cnt = 0; for(int i = 1 ; i <= n ; i++){ if(n % i == 0){ cnt++; } } return cnt == 3; } ``` ---- ### Test case - 1 - 質數 - 2 - 一個正確答案 - 4 - 奇數個因數但不是正確答案 - 16 ---- ### Follow up 能不能做的更快呢 ---- ### Leetcode 954 - 題目簡化後變成，有偶數個數字，有沒有辦法將數字兩兩一對，使得每一對數字其中一個為另一個的兩倍 - 先考慮正整數，假設當下的我取得一個數字$x$為奇數，那他唯一的配對可能只有 $x*2$ ，但偶數的時候有兩種可能 - 但若是在所有數字裡面最小的偶數，那他的配對可能就只有一種 - 將所有數字排序後，每次取最小的往後面找他的兩倍 ---- ### Leetcode 954 - 其實可以先將當下數字留起來，若發現當前數字在前面有被留下來，那優先把留下來的數字跟他做配對 - 可以用HashTable快速找到一個數字有沒有被留下來 - 正負分開處理 ---- ### Leetcode 954 ```java boolean checkValidArray(ArrayList<Integer> arr) { HashMap<Integer, Integer> hashMap = new HashMap<>(); for(int x: arr) { if(x % 2 == 0 && hashMap.containsKey(x/2)) { hashMap.put(x/2, hashMap.get(x/2) - 1); if(hashMap.get(x/2) == 0){ hashMap.remove(x/2); } } else { if( !hashMap.containsKey(x)) { hashMap.put(x, 1); } else{ hashMap.put(x, hashMap.get(x) + 1); } } } return hashMap.isEmpty(); } ``` ---- ### Leetcode 954 ```java public boolean canReorderDoubled(int[] arr) { ArrayList<Integer> positive = new ArrayList<>(); ArrayList<Integer> negative = new ArrayList<>(); for(int num: arr){ if(num >= 0) { positive.add(num); } else { // 正負分開來所以我們把負數轉換成正數這樣排序的時候比較方便 negative.add(-num); } } Collections.sort(positive); Collections.sort(negative); return checkValidArray(positive) && checkValidArray(negative); } ``` ---- ### Test case - 有0答案為true - 有0答案為fasle - 全正，答案為yes，有一個數字可以跟兩個數字mapping - [2,4,8,16] - 全負，答案為yes，有一個數字可以跟兩個數字mapping - [-2,-4,-8,-16] - 正負都有，答案為yes，有一個數字可以跟兩個數字mapping - [2,4,8,16,-2,-4,-8,-16] - 正負都有，答案為no - [2,-2] ---- ### Test case - 取絕對值後會是yes - [-2,4,-8,16] - 全正，答案為no - [2,8] - 全負，答案為no - [-2,-8] - 有一個數字需要跟兩邊的數字都match到 - [2,,4,4,8]