首页 > 其他分享 >1218.最长定差子序列

1218.最长定差子序列

时间:2023-06-13 16:59:31浏览次数:54  
标签:arr ump 1218 序列 num 差子 difference

问题描述

1218. 最长定差子序列 (Medium)

给你一个整数数组 arr 和一个整数 difference,请你找出并返回 arr 中最长等差子序列的长度,该子序列中相邻元素之间的差等于 difference子序列 是指在不改变其余元素顺序的情况下,通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。 示例 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]。

提示:

  • 1 <= arr.length <= 10⁵
  • -10⁴ <= arr[i], difference <= 10⁴

解题思路

利用哈希表,记录数组中每个元素,作为子序列末尾元素时,该元素对应的最长子序列的长度,有

if (ump.find(num - difference) != ump.end()) {
    ump[num] = ump[num - difference] + 1;
} else {
    ump[num] = 1;
}

代码

class Solution {
  public:
    int longestSubsequence(vector<int> &arr, int difference) {
        unordered_map<int, int> ump;
        for (auto &num : arr) {
            if (ump.find(num - difference) != ump.end()) {
                ump[num] = ump[num - difference] + 1;
            } else {
                ump[num] = 1;
            }
        }
        int res = 0;
        for (auto &num : ump) {
            res = res < num.second ? num.second : res;
        }
        return res;
    }
};

标签:arr,ump,1218,序列,num,差子,difference
From: https://www.cnblogs.com/zwyyy456/p/17478090.html

相关文章

  • 300.最长递增子序列
    问题描述300.最长递增子序列本题简写为LIS问题,与LCS问题(最长公共子序列)相对。解题思路动态规划关键在于,dp[i]表示什么含义便于解这道题,子序列不一定连续,所以为了便于求解,dp[i]应该表示为以nums[i-1]结尾的最长严格递增子序列的长度;递推关系为:if(nums[i-1]>nums[j-......
  • 序列化和反序列化_demo
    参考:一文搞懂序列化与反序列化-知乎(zhihu.com)一、jdk序列化和反序列化module结构: FactInfo.javapackagecom.hmb;importjava.io.Serial;importjava.io.Serializable;publicclassFactInfoimplementsSerializable{@Serialprivatestaticfinall......
  • python基础day23 os模块和序列化模块
    os模块(重要,多)os模块是与操作系统交互的一个接口('a/aa/aaa/aaaa/aaaaa')#递归创建文件夹os.removedirs('a/aa/aaa')#上推删除空文件夹os.mkdir('aaa')#当前文件所在位置创建一个新的文件夹或文件os.mkdir('a.txt')os.rmdir('aaa')#删除当前文件所在位置平级......
  • Python利用jsonpickle库把对象序列化为json
    python中经常要保存一些数据,json是一种理想的存储格式,纯文本的,也方便阅读,但有时使用起来不太方便,比如下面的例子:a=jsonData['A']b=jsonData['B']只能按字典方式引用,还不支持自动完成,不如python对象使用方便.如果定义python类,使用方便,但是保存为文件时......
  • os模块、序列化模块、pickle和json的区别
    os模块#os模块是与操作系统交互的一个接口1.文件相关的os.makedirs('dirname1/dirname2')#可生成多层递归目录os.removedirs('dirname1')#若目录为空,则删除,并递归到上一级目录,如若也为空,则删除,依此类推os.mkdir('dirname')#生成单级目录;相当于shell中mkd......
  • python 序列化模块
    一、jsonJson模块提供了四个功能:dumps、dump、loads、load1、前景什么叫序列化——将原本的字典、列表等内容转换成一个字符串的过程就叫做序列化。序列化的目的以某种存储形式使自定义对象持久化;将对象从一个地方传递到另一个地方。使程序更具维护性2、loads和dumps......
  • django views 序列化
      RESTframework中的序列化类与Django的Form和ModelForm类非常相似。我们提供了一个Serializer类,它提供了一种强大的通用方法来控制响应的输出,以及一个ModelSerializer类,它为创建处理模型实例和查询集的序列化提供了有效的快捷方式。Serializers 序列化器允许把像查询......
  • Java反序列化之Commons-Collection篇04-CC4链
    <1>环境分析因为CommonsCollections4除4.0的其他版本去掉了InvokerTransformer不再继承Serializable,导致无法序列化。同时CommonsCollections4的版本TransformingComparator继承了Serializable接口,而CommonsCollections3里是没有的。这个就提供了一个攻击的路径jd......
  • 对数据进行模糊匹配搜索(动态规划、最长公共子串、最长公共子序列)
    在搜索时常常在输入一半或者输入错误时,搜索引擎就给出智能提示。已知的搜索推荐主要包括以下几个方面:包含:“清华”和“清华大学”相似:“聊天软件”和“通讯软件”相关:“明星”和“刘亦菲”纠错:“好奇害死毛”和“好奇害死猫”其中包含模糊匹配可以使用动态规划算......
  • 对数据进行模糊匹配搜索(动态规划、最长公共子串、最长公共子序列)
    在搜索时常常在输入一半或者输入错误时,搜索引擎就给出智能提示。已知的搜索推荐主要包括以下几个方面:包含:“清华”和“清华大学”相似:“聊天软件”和“通讯软件”相关:“明星”和“刘亦菲”纠错:“好奇害死毛”和“好奇害死猫”其中包含模糊匹配可以使用动态规划算......