###### Agenda: ###### 12/06 22:00(UTC+8) 12/06 07:00(UTC-7) ###### 公布這次live session題目 ###### 12/06 22:30(UTC+8) 12/06 07:30(UTC-7) ###### 開始逐步給hint ###### 12/06 23:00(UTC+8) 12/06 08:00(UTC-7) ###### 題解 + Q&A ###### 還沒有加入DC伺服器的請記得加入，並去查看#學員驗證頻道進行驗證才可以看到live session的討論區https://discord.gg/WUE3XutPK3 --- #### 本周題目 #### Leetcode 2451 #### https://leetcode.com/problems/odd-string-difference/description/ #### Leetcode 2875 #### https://leetcode.com/problems/minimum-size-subarray-in-infinite-array/description/ --- ### Hint - Leetcode 2451 : - hint 1: 大部分程式語言的字元(char)都可以直接相減，python要用ord()，其他語言不確定的話就再去查 ---- ### Hint - Leetcode 2451 : - hint 1: 大部分程式語言的字元(char)都可以直接相減，python要用ord()，其他語言不確定的話就再去查 - hint 2: 嘗試做出每一個words的difference array ---- ### Hint - Leetcode 2451 : - hint 1: 大部分程式語言的字元(char)都可以直接相減，python要用ord()，其他語言不確定的話就再去查 - hint 2: 嘗試做出每一個words的difference array - hint 3: 挑一個出來做當作標準，看有誰跟他不一樣 ---- ### Hint - Leetcode 2451 : - hint 1: 大部分程式語言的字元(char)都可以直接相減，python要用ord()，其他語言不確定的話就再去查 - hint 2: 嘗試做出每一個words的difference array - hint 3: 挑一個出來做當作標準，看有誰跟他不一樣 - hint 4: 要考慮一下挑出來的那個就是答案的情況 --- ### Hint - Leetcode 2875 : - hint 1: 想像這個無線長的array，我們把它分成一段一段，每一段都是原本的array ---- ### Hint - Leetcode 2875 : - hint 1: 想像這個無線長的array，我們把它分成一段一段，每一段都是原本的array - hint 2: 思考答案可能會在這個array得哪裡，有可能就是一段原本的array 跨過原本array的邊界 ---- ### Hint - Leetcode 2875 : - hint 1: 想像這個無線長的array，我們把它分成一段一段，每一段都是原本的array - hint 2: 思考答案可能會在這個array得哪裡，有可能就是一段原本的array 跨過原本array的邊界 - hint 3: 若跨過很多次array，每跨過一次整個array，總和就會加原本的array數字總和，這操作可以做很多次 ---- ### Hint - Leetcode 2875 : - ###### hint 1: 想像這個無線長的array，我們把它分成一段一段，每一段都是原本的array - ###### hint 2: 思考答案可能會在這個array得哪裡，有可能就是一段原本的array 跨過原本array的邊界 - ###### hint 3: 若跨過很多次array，每跨過一次整個array，總和就會加原本的array數字總和，這操作可以做很多次 - ###### hint 4: 接著思考頭尾，因為中間可以無限加整個array，那可能就可以把target mod array's sum ---- ### Hint - Leetcode 2875 : - ###### hint 1: 想像這個無線長的array，我們把它分成一段一段，每一段都是原本的array - ###### hint 2: 思考答案可能會在這個array得哪裡，有可能就是一段原本的array 跨過原本array的邊界 - ###### hint 3: 若跨過很多次array，每跨過一次整個array，總和就會加原本的array數字總和，這操作可以做很多次 - ###### hint 4: 接著思考頭尾，因為中間可以無限加整個array，那可能就可以把target mod array's sum - ###### hint 5: 頭尾的那兩段相加有可能超過sum --- ### 題解 ---- ### Leetcode 2451 題目 - 給一些 string，保證每個string都一樣長。 - 對每一個 string，假設他的長度為 $n$，轉換成一個長度為 $n-1$ 的整數陣列difference，其中第 $i$ 項為string[i+1] - string[i]，兩個字元相減的意思是他們在a-z中位子的相減。 - 這些string中，只有一個string的difference array跟其他人不同，請找出該string ---- ### Leetcode 2451 題目 - "acbd" - a->1, c->3, b->2, d->4 - difference = [2,-1,2] ---- ### Leetcode 2451 - 每一個string的difference array都拿去跟第一個string比較。 - 如果超過兩個string的difference array跟第一個不一樣那第一個就是答案。 - 其實也不用真的把difference array做出來，要比較兩個difference array是否一樣，會想一個一個數字比較，還原到原本string就是拿string[i+1] - string[i]去互相做比較即可。 ---- ### LeetCode 2451 java code ```java //time complexity: O(所有字元的長度總和) //Extra space complexity: O(1) public String oddString(String[] words) { String res = words[0]; int cnt = 0; for(int i = 1 ; i < words.length ; i++){ boolean different = false; for(int j = 0; j+1<words[i].length();j++){ if(words[i].charAt(j+1) - words[i].charAt(j) != words[0].charAt(j+1)-words[0].charAt(j)){ different = true; break; } } if(different){ res = words[i]; cnt++; } } if(cnt == 1) { return res; } else{ return words[0]; } } ``` ---- ### Test case - 不一樣的words在第一個 - 不一樣的words在第二個 - 有兩個string 相同 ---- ### Leetcode 2875 題目 - 給定一個整數array，接著有一個無限長的array，是藉由一直重複複製這個給定的array所形成的 - 在這個無限長的array上找到一個最短的subarray總和是target ---- ### Leetcode 2875 題目 - array = [1,2,3] - infinite array = [1,2,3,1,2,3,1,2,3,1,2,3] - target = 10 -> [1,2,**3,1,2,3,1**,2,3,1,2,3] ---- ### Leetcode 2875 解法 - 分成三個case -  - 剩下的只是在case 2跟case 3中間加自己的總和 ---- ### Leetcode 2875 解法 - 把array 複製一份 然後將target % sum 就可以將所有case 一起handle - 但case2的情況頭尾加在一起會超過sum 所以需要判斷 target>= sum時，額外找一次target % sum + sum ---- ### Leetcode 2875 java code ```java //time complexity: O(n) //Extra space complexity: O(n) public int minSizeSubarray(int[] nums, int target) { long sum = 0; for (int x : nums) { sum += x; } List<Integer> nums2 = new ArrayList<>(); for (int x : nums) nums2.add(x); for (int x : nums) nums2.add(x); int ans = -1; Map<Long, Integer> m = new HashMap<>(); m.put(0L, -1); long prefix = 0; for (int i = 0; i < nums2.size(); i++) { prefix += nums2.get(i); m.put(prefix, i); long r = target % sum; long k = target / sum; if (m.containsKey(prefix - r)) { int len = i - m.get(prefix - r) + (int) (k * nums.length); if (ans == -1) ans = len; else ans = Math.min(ans, len); } if (target > sum) { if (m.containsKey(prefix - (r + sum))) { int len = i - m.get(prefix - (r + sum)) + (int) ((k - 1) * nums.length); if (ans == -1) ans = len; else ans = Math.min(ans, len); } } } return ans; } ``` ---- ### Test case - 答案在原本array 內 - [3,4,5,6,7] target = 9 - 答案跨過原本array，但頭尾相加小於總和 - [3,4,5,6,7] target = 20 - 答案跨過原本array，但頭尾相加大於總和 - [3,4,5,6,7] target = 30 - 有使用到整個array - [3,4,5,6,7] target = 55 ---- ### 幫忙填寫個回饋問卷讓我們變得更好 - https://forms.gle/RyJ35CZzj9atQiaW6 -