###### Agenda: ###### 11/08 22:00(UTC+8) 11/08 07:00(UTC-7) ###### 公布這次live session題目 ###### 11/08 22:30(UTC+8) 11/08 07:30(UTC-7) ###### 開始逐步給hint ###### 11/08 23:00(UTC+8) 11/08 08:00(UTC-7) ###### 題解 + Q&A ###### 還沒有加入DC伺服器的請記得加入，並去查看#學員驗證頻道進行驗證才可以看到live session的討論區https://discord.gg/WUE3XutPK3 --- #### 本周題目 #### Leetcode 973 #### https://leetcode.com/problems/k-closest-points-to-origin/description/ #### Leetcode 948 #### https://leetcode.com/problems/bag-of-tokens/ --- ### Hint - Leetcode 973 : - hint 1: $\sqrt{x^2+y^2}$ 就是與原點的距離 ---- ### Hint - Leetcode 973 : - hint 1: $\sqrt{x^2+y^2}$ 就是與原點的距離 - hint 2: 可以查詢一下自己的語言的sort使用方法 ---- ### Hint - Leetcode 973 : - hint 1: $\sqrt{x^2+y^2}$ 就是與原點的距離 - hint 2: 可以查詢一下自己的語言的sort使用方法 - hint 3: 若a>0 && b>0 &&a>b 則$a^2$>$b^2$ --- ### Hint - Leetcode 948 : - hint 1: 因為每一個 token 分數都一樣，一定會想挑 token value 最小的優先拿 ---- ### Hint - Leetcode 948 : - hint 1: 因為每一個 token 分數都一樣，一定會想挑 token value最小的優先拿 - hint 2: 若要使用第二種操作(Face down)，因為每一個 token 失去的分數都一樣，一定會想挑 token value 最大的優先拿 ---- ### Hint - Leetcode 948 : - hint 1: 因為每一個token分數都一樣，一定會想挑token value最小的優先拿 - hint 2: 若要使用第二種操作(Face down)，因為每一個 token 失去的分數都一樣，一定會想挑 token value 最大的優先拿 - hint 3: 通常會在 strengh 不夠時才考慮使用第二種操作 ---- ### Hint - Leetcode 948 : - hint 1: 因為每一個token分數都一樣，一定會想挑token value最小的優先拿 - hint 2: 若要使用第二種操作(Face down)，因為每一個 token 失去的分數都一樣，一定會想挑 token value 最大的優先拿 - hint 3: 通常會在 strengh 不夠時才考慮使用第二種操作 - hint 4: 注意一定要有一分才能使用第二種操作 --- ### 題解 ---- ### Leetcode 973 題目 - 給一些二維平面上的點，找出離原點(0,0)前$k$近的點。 - 保證前$k$近的點集合是唯一的，也就是第$k$近的點跟第$k+1$近的點離原點的距離一定不相等 ---- ### Leetcode 973 題目  - f 為 $\sqrt{10}$ - g 為 $\sqrt{8}$ ---- ### Leetcode 973 - 大部分程式語言都可以自定 sort 的 compare function，可以查詢一下自己語言 sort 的使用方式 - 直接在compare function裡面定義比較的基準是距離就可以了 - 為了避免浮點數誤差，其實不用特別取根號 ---- ### LeetCode 973 java code ```java private static int distance(int[] v) { return v[0] * v[0] + v[1] * v[1]; } public int[][] kClosest(int[][] points, int k) { Arrays.sort(points, (a, b) -> distance(a) - distance(b)); int[][] res = new int[k][2]; for (int i = 0; i < k; i++) { res[i] = points[i]; } return res; } ``` ---- ### Test case - k=n - 要取全部的點 - k=1 - 兩個點距離取下高斯會相等 - (1,2) (2,2) ---- ### Leetcode 948 題目 - 一個背包裡有一些 tokens ，第i個 token 有一個 value token[i] ，剛開始分數為0，然後有一個 power，每次可以針對一個還沒使用過的 token 做下列其中一個操作，假設該 token 為第 i 個。 - 若 power $\ge$ 這個token的 value，則 power 減去token[i]，分數+1 - 若至少有一分，則 power加上 token[i]，分數-1 - 目標讓分數盡量大。 ---- ### Leetcode 948 題目 - power = 10 , score = 1, token[i] =6 - 執行第一個操作 - power = 10 - 6 = 4 - score = 2 - 執行第二個操作 - power = 10 + 6 = 16 - score = 0 ---- ### Leetcode 948 解法 - 每次挑選最小value 還沒使用過的token，若power>$\ge$該token，則使用第一種操作，反之則對還沒使用過的最大token使用第二種操作 - 可以將token sort過後，用兩個指標去指著頭尾並進行移動會更方便做以上的操作 - power = 3 token = [3,4,5] - 對value = 3的token執行第一種操作 - power = 3 token = [4,5,6] - 對value = 6的token執行第二種操作 ---- ### Leetcode 948 java code ```java public int bagOfTokensScore(int[] tokens, int power) { Arrays.sort(tokens); int ans = 0; int l = 0, r = tokens.length - 1; int now = 0; while (l <= r) { if (power >= tokens[l]) { now++; power -= tokens[l]; l++; } else if (now > 0) { power += tokens[r]; now--; r--; } else { break; } ans = Math.max(ans, now); } return ans; } ``` ---- ### Test case - 當全部token都使用完時答案不是最好 - power = 3 tokes = [3,4] - power < 最小的token - power = 3 tokens = [4,5] - power >= token總和 - power = 3 tokens = [1,2] - 需使用到第二種操作來得到最好的答案 - power = 1 tokens = [1,2,3,5] ---- ### 幫忙填寫個回饋問卷讓我們變得更好 - https://forms.gle/gMVxvx1ipcs4vZ4w9 -