推 ILoveErr: 大師 07/15 01:03
推 Che31128: 晚上的時候停掉 07/15 01:18
※ 編輯: Rushia (122.100.75.86 臺灣), 07/15/2023 01:22:43
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
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1689353997.A.E0B.html