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

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2023/07/15 00:59)推噓2(2推 0噓 0→)

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

https://leetcode.com/problems/longest-arithmetic-subsequence-of-given-difference/description/ 1218. Longest Arithmetic Subsequence of Given Difference 給你一個陣列 arr 和一個差值 difference ，我們要找出一個最長的子序列滿足所有相鄰元素差都等於 difference，如果序列元素數量為一長度為 1，返回最長長度。 Example 1: Input: arr = [1,2,3,4], difference = 1 Output: 4 Explanation: The longest arithmetic subsequence is [1,2,3,4]. Example 2: Input: arr = [1,3,5,7], difference = 1 Output: 1 Explanation: The longest arithmetic subsequence is any single element. Example 3: Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2 Output: 4 Explanation: The longest arithmetic subsequence is [7,5,3,1]. 思路： 1.子序列問題基本上都是動態規劃，對於任意元素 ei ，如果他的前面存在一個元素 ej 的差為 difference ，那麼他的長度就會是 ej 的長度 + 1，對於 ej 如果他的前面也存在一個元素 ek 差為 difference 則長度不斷累加，直到沒有滿足的元素時才為0 。 2.我們可以用一個 Map 保存每個數字上一次訪問的長度，這樣只要把當前元素減去差值再去 Map 找值就可以得到最靠近當前元素的等差序列，如果不存在則把當前設為0。 Java Code： --------------------------------------------------------- class Solution { public int longestSubsequence(int[] arr, int difference) { Map<Integer, Integer> map = new HashMap<>(); int res = 1; for (int n : arr) { int target = n - difference; int count = 1 + map.getOrDefault(target, 0); map.put(n, count); res = Math.max(res, count); } return res; } } --------------------------------------------------------- LeetCode 介面又改了= = -- https://i.imgur.com/YPBHGGE.jpg