dp练习【4】

最长数对链 

646. 最长数对链

给你一个由 n 个数对组成的数对数组 pairs ,其中 pairs[i] = [lefti, righti] 且 lefti < righti 。

现在,我们定义一种 跟随 关系,当且仅当 b < c 时,数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面。我们用这种形式来构造 数对链 。

找出并返回能够形成的 最长数对链的长度 。

你不需要用到所有的数对,你可以以任何顺序选择其中的一些数对来构造。

示例 1:

输入:pairs = [[1,2], [2,3], [3,4]]
输出:2
解释:最长的数对链是 [1,2] -> [3,4] 。

示例 2:

输入:pairs = [[1,2],[7,8],[4,5]]
输出:3
解释:最长的数对链是 [1,2] -> [4,5] -> [7,8] 。
class Solution {
    public int findLongestChain(int[][] pairs) {
        int n = pairs.length;
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (pairs[i][0] > pairs[j][1]) {
                    // 通过i位置与前面所有的比较,然后得到当前时候最多有多少对(j到i之间最大对数)
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[n - 1];
    }
}

最长定差子序列

1218. 最长定差子序列

给你一个整数数组 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]。

这个题目不能用常规dp来做,会超时,比如说这样,就超时了

class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        int n = arr.length;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, 1);
        int maxLen = 1;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] - arr[j] == difference) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen,dp[i]);
        }
        return maxLen;
    }
}

 

要用哈希表来存储之前最长的重复子数组才行

class Solution {
    // 方法用于计算数组 arr 中具有固定差值 difference 的最长子序列长度
    public int longestSubsequence(int[] arr, int difference) {
        int ans = 0; // 初始化最长子序列的长度为 0
        // 创建一个大小为 40001 的整型数组 dp,用于存储动态规划的状态
        // 数组大小的选择是为了适应输入数据的变化范围,假设输入数据范围在 [-20000, 19999] 内
        int[] dp = new int[40001];
        
        // 遍历数组 arr 的每一个元素
        for (int num : arr) {
            // 为了使数组下标非负,将当前数字 num 偏移 20000 后使用作为 dp 数组的索引
            // dp[num + 20000] 存储了以 num 结尾的具有固定差值 difference 的最长子序列长度
            // dp[num + 20000 - difference] 则是前一个元素 (num - difference) 的最长子序列长度
            // 当前元素 num 的最长子序列长度为前一个元素的长度加 1
            dp[num + 20000] = dp[num + 20000 - difference] + 1;
            
            // 更新全局最长子序列长度 ans
            // 取当前已知的最长子序列长度和 dp[num + 20000] 中较大的值
            ans = Math.max(ans, dp[num + 20000]);
        }
        
        // 返回最长子序列的长度
        return ans;
    }
}

最长等差数列

1027. 最长等差数列

给你一个整数数组 nums,返回 nums 中最长等差子序列的长度

回想一下,nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ,且 0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]0 <= i < seq.length - 1) 的值都相同,那么序列 seq 是等差的。

示例 1:

输入:nums = [3,6,9,12]
输出:4
解释: 
整个数组是公差为 3 的等差数列。

示例 2:

输入:nums = [9,4,7,2,10]
输出:3
解释:
最长的等差子序列是 [4,7,10]。

示例 3:

输入:nums = [20,1,15,3,10,5,8]
输出:4
解释:
最长的等差子序列是 [20,15,10,5]。
class Solution {
    // 方法接收一个整数数组 nums 作为参数
    public int longestArithSeqLength(int[] nums) {
        int n = nums.length; // 获取数组长度
        // 创建一个二维数组 dp,大小为 [n][1001],用于存储动态规划的结果
        int[][] dp = new int[n][1001];
        int maxLen = 0; // 初始化最长等差数列的长度为0
        
        // 从第二个元素开始遍历数组
        for (int k = 1; k < n; k++) {
            // 从第一个元素到第k-1个元素遍历
            for (int j = 0; j < k; j++) {
                // 计算两数之差,并加上500以保证下标非负
                // 这里假设差值的范围是 [-500, 500],因此差值加上500后可以作为下标
                int d = nums[k] - nums[j] + 500;
                
                // 根据差值 d 更新 dp[k][d] 的值,即以 nums[k] 结尾且差值为 d 的等差数列的长度
                // dp[j][d] 表示以 nums[j] 结尾且差值为 d 的等差数列的长度
                // 加1是因为当前元素 nums[k] 可以与前面的等差数列形成新的等差数列
                dp[k][d] = dp[j][d] + 1;
                
                // 更新最长等差数列的长度
                maxLen = Math.max(maxLen, dp[k][d]);
            }
        }
        
        // 最终返回最长等差数列的长度,由于 dp 数组中存储的是除第一个元素外的等差数列长度,所以需要加1
        return maxLen + 1;
    }
}

腾讯面试时的算法题目

牛客上看面经,看到有人写的,在面试之后,面试官出的两道dp。自己尝试了一下,发现难度还好,属于动态规划系列中【最长递增子序列】分类和【动态规划在字符串的应用】分类中类似的题型

最长重复子数组

718. 最长重复子数组

给两个整数数组 nums1 和 nums2 ,返回 两个数组中 公共的 、长度最长的子数组的长度 

示例 1:

输入:nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出:3
解释:长度最长的公共子数组是 [3,2,1] 。

示例 2:

输入:nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出:5

提示:

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 100
class Solution {
    public int longestArithSeqLength(int[] nums) {
  
        int n=nums.length;
        int[][] dp=new int[n][1001];
        int maxLen=0;//保存结果
        for(int k=1;k<n;k++){
            for(int j=0;j<k;j++){
                int d=nums[k]-nums[j]+500;//统一加偏移量,使下标非负
                dp[k][d]=dp[j][d]+1; //根据 d 去填充dp[k][d]
                maxLen=Math.max(maxLen,dp[k][d]);//维护最大值
            }
        }
        return maxLen+1;
    }
}

最长公共子序列

1143. 最长公共子序列

给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。

一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。

  • 例如,"ace" 是 "abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1:

输入:text1 = "abcde", text2 = "ace" 
输出:3  
解释:最长公共子序列是 "ace" ,它的长度为 3 。

示例 2:

输入:text1 = "abc", text2 = "abc"
输出:3
解释:最长公共子序列是 "abc" ,它的长度为 3 。

示例 3:

输入:text1 = "abc", text2 = "def"
输出:0
解释:两个字符串没有公共子序列,返回 0 
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();

        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (text1.charAt(j - 1) == text2.charAt(i - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return dp[n][m];
    }
}

 

每日一题

3174. 清除数字

给你一个字符串 s 。

你的任务是重复以下操作删除 所有 数字字符:

  • 删除 第一个数字字符 以及它左边 最近 的 非数字 字符。

请你返回删除所有数字字符以后剩下的字符串。

示例 1:

输入:s = "abc"

输出:"abc"

解释:

字符串中没有数字。

示例 2:

输入:s = "cb34"

输出:""

解释:

一开始,我们对 s[2] 执行操作,s 变为 "c4" 。

然后对 s[1] 执行操作,s 变为 "" 。

用栈的思想解题:

class Solution {
    public String clearDigits(String s) {
        StringBuilder res = new StringBuilder();
        for (char c : s.toCharArray()){
            if (Character.isDigit(c)) {
                res.deleteCharAt(res.length() - 1);
            } else {
                res.append(c);
            }
        }
        return res.toString();
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/872456.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Ubuntu环境的MySql下载安装

下载压缩包 此文章下载的mysql版本位5.7.29 sudo wget https://downloads.mysql.com/archives/get/p/23/file/mysql-server_5.7.29-1ubuntu18.04_amd64.deb-bundle.tar解压缩 sudo tar -xvf mysql-server_5.7.29-1ubuntu18.04_amd64.deb-bundle.tar命令解释 -x&#xff1a;…

鸿蒙MPChart图表自定义(四)短刻度线

对于图表中的x轴效果&#xff0c;我们有时想要实现如图所示的特定刻度线。若需绘制x轴的短刻度线&#xff0c;我们可以利用现有资源&#xff0c;将原本的网格线稍作修改&#xff0c;只需绘制一条简洁的短线即可达到目的。 具体的方法就是写一个类MyXAxisRender继承自XAxisRend…

【补-网络安全】日常运维(二)终端端口占用排查

文章目录 一、利用ipconfig、netstat 命令行统计二 、策略封禁IP 引言:检查频繁,第一步我们梳理完资产,第二步应该对资产终端进行一个排查,诊断把脉,了解清楚系统的端口占用及开放情况 一、利用ipconfig、netstat 命令行统计 1.先用ipconfig定位该终端的IP地址 2.明确IP地址后…

汇编语言在虚拟机中输出“Hello World!”

1.软件 Nasmide64.exe(李忠老师编写) Fixvhdw64.exe(李忠老师编写) VirtualBox虚拟机(免费 开源) 2.过程 01.Fixvhdw64.exe输入以下代码: mov ax,0xb800 mov ds,ax mov byte [0x00],H mov byte [0x02],e mov byte [0x04],l mov byte [0x06],l mov byte [0x08],o mov byte…

x-cmd pkg | tig - 基于 nucurses 的 git 文本模式界面

目录 简介首次用户快速实验指南功能特点类似工具与竞品进一步探索 简介 tig 由 Jonas Fonseca 于 2006 年使用 C 语言创建的 git 交互式文本命令行工具。旨在开启交互模式快速浏览 git 存储库的信息以及 git 命令的运行。 首次用户快速实验指南 本文的 demo 展现了如何通过 …

2024年高教杯国赛(D题)数学建模竞赛解题思路|完整代码论文集合

我是Tina表姐&#xff0c;毕业于中国人民大学&#xff0c;对数学建模的热爱让我在这一领域深耕多年。我的建模思路已经帮助了百余位学习者和参赛者在数学建模的道路上取得了显著的进步和成就。现在&#xff0c;我将这份宝贵的经验和知识凝练成一份全面的解题思路与代码论文集合…

2024国赛数学建模ABC题思路模型

完整的思路模型请查看文末名片 完整的思路模型请查看文末名片 完整的思路模型请查看文末名片

精通Transformer,从零开始构建最先进的NLP模型(附PDF)

国内第1本Transformer——变形金刚红书 如果一定要说未来谁能引领人工智能世界&#xff0c;是Transformer而非chatGPT&#xff01; 编辑推荐★★★★★ ChatGPT红得发紫&#xff0c;强得让人类心悸。 但在它的背后&#xff0c;还隐藏着一位真正的大佬。 它的名字叫做——T…

科研绘图系列:R语言PCoA图(PCoA plot)

文章目录 介绍PCoA图的作用:说明的问题:加载R包导入数据数据预处理画图参考介绍 PCoA(主坐标分析,Principal Coordinate Analysis)是一种多维数据的降维技术,它用于探索高维空间中样本之间的关系。PCoA通常用于生态学、遗传学和其他领域的数据分析,以揭示样本或个体之间…

基于.NET6的WPF基础总结(上)

目录 一.常用属性介绍 二、 程序退出方式 三、布局样式 3.1 Panel的附加属性ZIndex 3.2 Grid(网格)布局 3.3 UniformGrid&#xff08;均分布局&#xff09; 3.4 StackPanel&#xff08;堆积面板&#xff09; 3.5 WrapPanel&#xff08;换行面板&#xff09; 3.6 Doc…

在模板中使用 Django 会话

在 Django 中使用会话&#xff08;session&#xff09;可以让你在用户访问网站的过程中存储和访问临时数据。我们可以利用会话在速度计算器的例子中存储和显示上次计算的结果。 1、问题背景 在 Django 中&#xff0c;可以使用会话来存储用户数据。在某些情况下&#xff0c;我们…

俄罗斯版微信遭遇大规模数据泄露,安全问题再引关注

据报道&#xff0c;俄罗斯最大的社交媒体和网络服务VK&#xff08;VKontakte&#xff09;遭遇了大规模的数据泄露事件&#xff0c;该事件对大量用户造成了影响。据非法市场BreachForums上一位名为Hikki-Chan的威胁行为者声称&#xff0c;2024年9月&#xff0c;VK的数据在论坛上…

Stream 流式编程

优质博文&#xff1a;IT-BLOG-CN 大家都知道可以将Collection类转化成流Stream进行操作&#xff08;Map并不能创建流&#xff09;&#xff0c;代码变得简约流畅。我们先看下流的几个特点&#xff1a; 1、流并不存储元素。这些元素可能存储在底层的集合中&#xff0c;或者是按需…

VMwareWorkstation安装Kali系统教程

Kali系统&#xff0c;全名为Kali Linux&#xff0c;为渗透测试和网络安全领域提供一个全面的工具集合。Kali系统预装了各种用于渗透测试和漏洞利用的工具&#xff0c;包括端口扫描、密码破解、网络嗅探、漏洞分析等。这些工具可以帮助安全专业人员评估和测试网络的安全性&#…

实例讲解Simulink应用层开发CAN报文解包及CAN信号设置方法

在VCU应用层开发中&#xff0c;在输入信号中主要包括开关信号、模拟信号、CAN信号、PWM信号等&#xff0c;其中CAN通讯由于通讯质量高&#xff0c;传输数据量大&#xff0c;采用总线通讯方式节省大量线束&#xff0c;在汽车上尤其是电动汽车上大量应用&#xff0c;当然&#xf…

数图亮相第三届中国区域零售创新峰会:共绘零售新蓝图,携手迈向新征程

8月31日&#xff0c;备受瞩目的第三届中国区域零售创新峰会在历史悠久的湖北襄阳圆满落下帷幕。在这场零售行业的盛会上&#xff0c;数图信息科技作为重要参会企业&#xff0c;积极参与其中&#xff0c;与众多行业精英共聚一堂&#xff0c;共同擘画零售业的宏伟蓝图。以下是本次…

C/C++ 中的算术运算及其陷阱(详解,举例分析)

在C/C编程中&#xff0c;算术运算是非常基础且常用的操作。然而&#xff0c;这些看似简单的运算背后却隐藏着一些潜在的陷阱&#xff0c;如果不加以注意&#xff0c;可能会导致程序出现难以预料的错误。本文将探讨C/C中常见的算术运算及其潜在的陷阱&#xff0c;并通过实例进行…

告别格式不兼容烦恼!ape转换mp3,分享3个简单方法

各位读者们&#xff0c;你们是否有过这种体验&#xff1a;满怀期待地在网上下载一首好听的歌曲&#xff0c;结果怎么点击手机都播放不了&#xff0c;定睛一看&#xff0c;弹窗显示“无法播放该音频文件”。这是为什么呢&#xff1f;原来那首歌的音频格式是ape&#xff0c;不被手…

iOS——关联对象学习补充

分类 在分类中添加属性会生成对应的成员变量&#xff0c;会生成对应的setter和getter方法的声明&#xff0c;但是不会生成setter和getter方法的实现。分类中的可以写property&#xff0c;会编译通过&#xff0c;但是引用变量会报错。分类中可以/只能访问原有类中.h中的属性。如…

如何选择合适的变压吸附制氧设备

在选择合适的变压吸附(Pressure Swing Adsorption, PSA)制氧设备时&#xff0c;需要综合考虑多个因素以确保设备能够高效、稳定地运行&#xff0c;满足特定应用场景的需求。以下是一些关键步骤和考虑因素&#xff0c;帮助您做出明智的决策。 1. 明确应用需求 明确您的制氧需求至…