Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2023/06/23 18:48)推噓4(4推 0噓 0→)

留言4則, 4人參與討論串354/719 (看更多)

https://leetcode.com/problems/longest-arithmetic-subsequence/description/ 1027. Longest Arithmetic Subsequence 給你一個整數陣列 nums，找出最長的等差子序列長度。 Example 1: Input: nums = [3,6,9,12] Output: 4 Explanation: The whole array is an arithmetic sequence with steps of length = 3. Example 2: Input: nums = [9,4,7,2,10] Output: 3 Explanation: The longest arithmetic subsequence is [4,7,10]. Example 3: Input: nums = [20,1,15,3,10,5,8] Output: 4 Explanation: The longest arithmetic subsequence is [20,15,10,5]. 思路: 1.最長子序列(選 or 不選)十之八九是dp，推一下就可以看出規律了。 2.假設 nums = [3,6,9,12] 對於 nums[1] 他可以和 nums[0] 產生一個差 [6-3=3]，長度 = [2] 對於 nums[2] 他可以和 nums[0] 和 nums[1] 產生兩個差[9-3=6, 9-6=3] 長度=[2,2] 繼續往後推導，不失一般性。 3.當我們在 nums[2] 的時候，他會產生兩個差[6, 3]，如果我們可以知道 nums[2] 之前的所有元素的所有等差 diff = [...],產生的子序列長度的話，我們就不必每次都重頭算了，我們已知： nums[1] 在等差為 6 的時候不存在任意子序列，子序列長度為 [] + [9] = 1 nums[1] 在等差為 3 的時候存在子序列 [3, 6]，子序列長度為 [3, 6] + [9] = 3 繼續往後推導，不失一般性，所以我們可以紀錄所有先前子序列的 diff 長度並複用。 4.我們維護一個二維dp[i][diff]，表示以 nums[i] 結尾且差值為 diff 的長度，遍歷並更新 dp 的表，且每次都用更新後的值去更新最大長度。 5.diff 因為 0 <= nums[i] <= 500 所以設定大小為 1000 即可，用 Map 也可以。 Java Code： ------------------------------------- class Solution { public int longestArithSeqLength(int[] nums) { int res = 2; int n = nums.length; int[][] dp = new int[n][1001]; for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { int diff = nums[i] - nums[j]; int index = diff + 500; int len = (dp[j][index] == 0 ? 1 : dp[j][index]) + 1; dp[i][index] = len; res = Math.max(res, len); } } return res; } } ------------------------------------- -- https://i.imgur.com/PIoxddO.jpg