Leetcode 1218:最长定差子序列(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1218:最长定差子序列(超详细的解法!!!)

in leetcode with 0 comment

给你一个整数数组 arr 和一个整数 difference,请你找出 arr 中所有相邻元素之间的差等于给定 difference 的等差子序列,并返回其中最长的等差子序列的长度。

示例 1:

输入:arr = [1,2,3,4], difference = 1
输出:4
解释:最长的等差子序列是 [1,2,3,4]。

示例 2:

输入:arr = [1,3,5,7], difference = 1
输出:1
解释:最长的等差子序列是任意单个元素。

示例 3:

输入:arr = [1,5,7,8,5,3,4,2,1], difference = -2
输出:4
解释:最长的等差子序列是 [7,5,3,1]。

提示:

解题思路

简单的动态规划,假设当前位置$i$的元素$arr[i]$结果的最长定差子序列是$f(arr[i])$,那么我们只需要判断$arr[i]-dif$在此之前有没有出现过即可。如果出现过

否则的话

class Solution:
    def longestSubsequence(self, arr: List[int], dif: int) -> int:
        mem, res = {}, 1
        for i in arr:
            if i - dif in mem:
                mem[i] = mem[i-dif] + 1
            else:
                mem[i] = 1
            res = max(res, mem[i])
        return res

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses