###### Agenda: ###### 11/15 22:00(UTC+8) 11/15 07:00(UTC-7) ###### 公布這次live session題目 ###### 11/15 22:30(UTC+8) 11/15 07:30(UTC-7) ###### 開始逐步給hint ###### 11/15 23:00(UTC+8) 11/15 08:00(UTC-7) ###### 題解 + Q&A ###### 還沒有加入DC伺服器的請記得加入，並去查看#學員驗證頻道進行驗證才可以看到live session的討論區https://discord.gg/WUE3XutPK3 --- #### 本周題目 #### Leetcode 976 #### https://leetcode.com/problems/largest-perimeter-triangle/ #### Leetcode 3557 #### https://leetcode.com/problems/find-maximum-number-of-non-intersecting-substrings/description/ --- ### Hint - Leetcode 976 : - hint 1: 三個邊要組成一個三角形，前兩個小的邊相加必須大於第三條邊 ---- ### Hint - Leetcode 976 : - hint 1: 三個邊要組成一個三角形，前兩個小的邊相加必須大於第三條邊 - hint 2: 窮舉最長的那條邊 ---- ### Hint - Leetcode 976 : - hint 1: 三個邊要組成一個三角形，前兩個小的邊相加必須大於第三條邊 - hint 2: 窮舉最長的那條邊 - hint 3: 當我們決定最長那條邊後，第二三條邊會想要選所有比最長的那條邊短的中最長的那兩條 --- ### Hint - Leetcode 3557 : - hint 1: 想像已經得到一組答案了，他的結構會長什麼樣 ---- ### Hint - Leetcode 3557 : - hint 1: 想像已經得到一組答案了，他的結構會長什麼樣 - hint 2: 想像第一組答案，如果前面經過一些字母但他們沒辦法組成題目要求的子字串，但現在經過一個他可以做到，會想使用他們 ---- ### Hint - Leetcode 3557 : - hint 1: 想像已經得到一組答案了，他的結構會長什麼樣 - hint 2: 想像第一組答案，如果前面經過一些字母但他們沒辦法組成題目要求的子字串，但現在經過一個他可以做到，會想使用他們 - hint 3: 可以記錄前一組答案的最後位的位子讓後面的答案不要跟他們重疊 ---- ### Hint - Leetcode 3557 : - hint 1: 想像已經得到一組答案了，他的結構會長什麼樣 - hint 2: 想像第一組答案，如果前面經過一些字母但他們沒辦法組成題目要求的子字串，但現在經過一個他可以做到，會想使用他們 - hint 3: 可以記錄前一組答案的最後位的位子讓後面的答案不要跟他們重疊 - hint 4: 紀錄每個字母上一次出現，但要注意離現在至少有3格距離 --- ### 題解 ---- ### Leetcode 976 題目 - 給一些數字，請找出三個數字，使他們可作為三角形的三個邊，且加起來最大 ---- ### Leetcode 976 題目 - [2,1,2,10] ---- ### Leetcode 976 - 三角形的構成條件為最長的那條邊<第二長的邊 + 第三長的邊 - 窮舉最長的邊後，需要找出比這條邊短的邊裡最長的兩條，因為他們更容易符合三角形條件，且也會是更好的答案。 ---- ### LeetCode 976 java code ```java //time complexity: O(n log n) //Extra space complexity: O(1) public int largestPerimeter(int[] nums) { Arrays.sort(nums); for(int i = nums.length - 1 ; i >= 2 ; i--){ if(nums[i] < nums[i - 1] + nums[i - 2]) { return nums[i] + nums[i - 1] + nums[i - 2]; } } return 0; } ``` ---- ### Test case - 沒有三角形 - [1,2,3,5] - 三角形為最小的三個數字 - [1,2,2,10] ---- ### Leetcode 3557 題目 - 給定一個字串，我們需要找出盡量多的子字串滿足以下條件 - 每個子字串頭尾相同 - 該子字串至少四個字元 - 任兩個子字串在原字串內不重疊 ---- ### Leetcode 3557 題目 - "abcaabcac" - [abca][abca]c - a[bcaab]cac ---- ### Leetcode 3557 解法 - 考慮出答案的第一組，可以發現若第一組答案的最後一個位子再越前面越好 - 每次掃到一個位子可以跟前面組成答案後就直接讓他們組成答案 - 當依序掃過時，紀錄一下每個字母最後出現的位子，但只紀錄當前位子往前三個位子以前的 - 也就是當你在i時，只會紀錄到i-3的 - 最後判斷當前字母上一次出現是不是在前一次答案後面 ---- ### Leetcode 3557 java code ```java //time complexity: O(n) //Extra space complexity: O(1) public int maxSubstrings(String word) { int ans = 0; int[] vis = new int[26]; for(int i = 0 ; i < 26 ; i++){ vis[i] = -1; } int lastAns = -1; for(int i = 3 ; i < word.length() ; i++){ if(i - 3>lastAns){ vis[word.charAt(i - 3) - 'a'] = i - 3; } if(vis[word.charAt(i) - 'a'] > lastAns){ ans++; lastAns = i; } } return ans; } ``` ---- ### Test case - 沒有重複字元 - "abc" - 有重複字元但沒有合法的字串 - "aabbcc" - 會讓答案重疊的 - "abcab" - 兩組答案相鄰的 - "abcaabca" ---- ### 幫忙填寫個回饋問卷讓我們變得更好 - https://forms.gle/9VytW23bWVmdDDuE6 -