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 的最长子序列长度为前一个元素的长度加 1dp[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 数组中存储的是除第一个元素外的等差数列长度,所以需要加1return 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 <= 10000 <= 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();}
}
相关文章:
dp练习【4】
最长数对链 646. 最长数对链 给你一个由 n 个数对组成的数对数组 pairs ,其中 pairs[i] [lefti, righti] 且 lefti < righti 。 现在,我们定义一种 跟随 关系,当且仅当 b < c 时,数对 p2 [c, d] 才可以跟在 p1 [a, b…...
php 实现推荐算法
在PHP中实现推荐算法的应用场景通常包括电商、社交媒体、内容平台等。推荐算法可以帮助用户找到与其兴趣相关的内容,提高用户体验和平台黏性。以下是几种常见的推荐算法及其PHP实现方式: 1. 基于协同过滤的推荐算法 协同过滤(Collaborative…...
相机光学(三十六)——光圈
0.参考链接 (1)Hall光圈和Piris光圈的区别 (2)自动光圈及P-IRIS原理 1.光圈分类 Hall光圈和Piris光圈是两种不同的光圈技术。它们之间的区别如下: Hall光圈:Hall光圈是一种传统的光电子元件,通…...
数据结构——树和二叉树
目录 一、树的概念 二、树结点之间的关系 三、二叉树 1、满二叉树 2、完全二叉树 四、二叉树的存储 1、顺序存储 2、链式存储 一、树的概念 如果数据和数据之间满足一对多的关系,将其逻辑结构称之为树 如下图:树的根与树的分支存在一对多的关系 将上…...
142. Go操作Kafka(confluent-kafka-go库)
文章目录 Apache kafka简介开始使用Apache Kafka构建生产者构建消费者 总结 之前已经有两篇文章介绍过 Go如何操作 kafka 28.windows安装kafka,Go操作kafka示例(sarama库) 51.Go操作kafka示例(kafka-go库) Apache ka…...
spring boot(学习笔记第十九课)
spring boot(学习笔记第十九课) Spring boot的batch框架,以及Swagger3(OpenAPI)整合 学习内容: Spring boot的batch框架Spring boot的Swagger3(OpenAPI)整合 1. Spring boot batch框架 Spring Batch是什么 Spring Batch 是一个…...
docker安装 redis 并且加密开启SSL/TLS通道
拉取镜像 docker pull registry.cn-hangzhou.aliyuncs.com/qiluo-images/redis:latest docker tag registry.cn-hangzhou.aliyuncs.com/qiluo-images/redis:latest redis:latest要在 Docker 容器中启动 Redis 并开启 SSL/TLS 加密,需按照以下步骤修改启动命令和配置…...
什么是ARM架构?什么是X86架构?两者的区别是什么?
一、什么是ARM架构 (一)起源于发展 ARM 架构由英国剑桥的 Acorn 计算机公司开发。因市场无合适产品,Acorn 自行设计出第一款微处理器,命名为 ARM。此后 ARM 架构不断发展,1990 年为与苹果合作成立 ARM 公司࿰…...
【vscode】vscode paste image插件设置
本文首发于 ❄️慕雪的寒舍 vscode编辑md文件的时候,如果想插入图片,自带的粘贴只会粘贴到当前目录下,也没有文件重命名,很不友好。 在扩展商店里面有mushan的Paste Image插件,相比自带的,更加友好一点。但…...
自定义string类
#include <iostream> #include <string> int main() { std::string str "Hello, World!"; // 使用 c_str() 将 std::string 转换为 C 风格字符串,并传递给 printf printf("The string is: %s\n", str.c_str()); // 尝试修改…...
Python | Leetcode Python题解之第387题字符串中的第一个唯一字符
题目: 题解: class Solution:def firstUniqChar(self, s: str) -> int:position dict()q collections.deque()n len(s)for i, ch in enumerate(s):if ch not in position:position[ch] iq.append((s[i], i))else:position[ch] -1while q and po…...
RocketMQ 消费时序列化报错问题分析及解决
问题背景 在2024年3月7日,系统消费 RocketMQ 消息时出现了序列化报错,错误信息显示为: java.io.InvalidClassException: com.xxx.xxx.bean.mg.GoodsChangeLogMessage; local class incompatible: stream classdesc serialVersionUID... 这是…...
全能与专精:探索未来AI模型的发展趋势与市场潜力
文章目录 每日一句正能量前言AI模型的全面评估和比较AI模型的专精化和可扩展性AI模型的合理使用和道德规范后记 每日一句正能量 一个人,如果没有经受过投资失败的痛楚,又怎么会看到绝望之后的海阔天空。很多时候,经历了人生中最艰难的事&…...
Python深度学习:【开源数据集系列】ImageNet数据集
ImageNet 是一个大规模的视觉数据集,是计算机视觉领域最重要的基准数据集之一。该数据集由普林斯顿大学和斯坦福大学的研究人员发起,于 2009 年推出。ImageNet 是用于物体分类、目标检测、图像分割、姿势估计等多种任务的通用数据集,尤其在深度学习和计算机视觉的突破性研究…...
微信小程序手写签名
微信小程序手写签名组件 该组件基于signature_pad封装,signature_pad本身是web端的插件,此处将插件代码修改为小程序端可用。 signature_pad.js /*!* Signature Pad v5.0.3 | https://github.com/szimek/signature_pad* (c) 2024 Szymon Nowak | Releas…...
Javascript 使用中点查找矩形的角(Find Corners of Rectangle using mid points)
考虑一个矩形 ABCD,我们给出了边 AD 和 BC 中点(分别为 p 和 q)的坐标以及它们的长度 L(AD BC L)。现在给定参数,我们需要打印 4 个点 A、B、C 和 D 的坐标。 例子: 输入:p (1,…...
【困难】 猿人学web第一届 第18题 jsvmp 洞察先机
文章目录 数据接口分析还原加密参数插桩调试分析日志插桩补充 python 代码 数据接口分析 数据接口 https://match.yuanrenxue.cn/match/18data 请求参数 {page: 页码, t: 时间戳, v: 加密值} 请求第一页不需要携带 t, v 参数 cookie 只需要携带 sessionid 只要 还原加密字段…...
IDEA Maven 源修改为国内阿里云镜像的正确方式
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「storm…...
OpenCV 旋转矩形边界
边界矩形是用最小面积绘制的,所以它也考虑了旋转。使用的函数是**cv.minAreaRect**()。 import cv2 import numpy as npimgcv2.imread(rD:\PythonProject\thunder.jpg) img1cv2.cvtColor(img,cv2.COLOR_BGR2GRAY) print(img.dtype) ret,threshcv2.threshold(img1,1…...
人车防撞系统安全生产方案
根据《市场监管总局关于2021~2023年全国特种设备安全状况的通告》数据显示:2023年:全国共发生特种设备事故和相关事故71起,其中死亡69人。包含叉车在内的场(厂)内专用机动车辆事故29起、死亡28人,占事故总数的40.85%、死亡人数的4…...
OpenClaw 源码泄露风波:一场由 “手滑” 引发的 AI 安全大地震
🔥个人主页:北极的代码(欢迎来访) 🎬作者简介:java后端学习者 ❄️个人专栏:苍穹外卖日记,SSM框架深入,JavaWeb ✨命运的结局尽可永在,不屈的挑战却不可须臾或…...
栈序列合法性验证:从原理到代码的深度解析
栈序列合法性验证:从原理到代码的深度解析📌问题定义:到底要验证什么?🧠核心原理:抓住出栈序列,就是解题关键📝分步推演:用例子看懂整个过程步骤1:验证出栈第…...
Figma+Cursor联动实战:5分钟搞定AI设计稿生成(含最新manifest导入避坑指南)
FigmaCursor联动实战:5分钟搞定AI设计稿生成(含最新manifest导入避坑指南) 在快节奏的前端开发领域,设计稿与代码的同步效率往往成为项目瓶颈。传统工作流中,设计师产出视觉稿后,开发者需要手动还原每个像素…...
初次学C语言编程(2)
上节课内容补充在上节课中的转义字符中\ddd 表示一个三个数字的八进制的数字 例如\130 十进制的ASCII是88 表示字符X\xdd表示的是一个两个数字的十六进制的数字 例如\x30 十进制ASCII是48 表示字符0\0表示null 没有字符 ASCII码是0,用于字符串的结束符号一、C…...
MySQL 主从延迟根因诊断法
📌 解决思路:从网络、IO、SQL 到参数,系统化定位高并发下的同步瓶颈 📌 适用版本:MySQL 5.7 / 8.0 📌 适用场景:高并发写入、主从延迟告警、从库追不上主库 目录 一、先量化延迟:别…...
第十五届题目
握手问题 #include <stdio.h> #include <stdlib.h>int main(int argc, char *argv[]) {int sum0;for(int i49;i>7;i--){sumi;}printf("%d",sum);return 0; } 小球反弹 #include <stdio.h> #include <math.h>int main(int argc, char *ar…...
别再暴力搜索了!用动态规划优化旅行商问题,C++代码效率提升实战
暴力搜索 vs 动态规划:旅行商问题的C效率革命 当城市数量超过10个时,传统的暴力搜索方法在解决旅行商问题(TSP)时就像试图用算盘计算宇宙中的原子数量——理论上可行,实际上完全不切实际。作为一名长期在算法竞赛中摸爬滚打的选手,…...
深入解析Qt平台插件xcb连接失败问题及高效解决方案
1. 为什么你的Qt程序突然罢工了? 最近在远程服务器上调试Qt程序时,你是不是也遇到过这个让人抓狂的错误提示?"qt.qpa.xcb: could not connect to display"这个报错就像一堵墙,把我们的开发工作拦在了半路。作为一个在Li…...
Visual Studio 2022 版本对决:Community、Professional 与 Enterprise 全方位深度解析
Visual Studio 2022 是微软旗舰级集成开发环境(IDE)的新版本,也是该系列首个原生 64 位版本。它提供三个主要版本:Community(社区版)、Professional(专业版) 和 Enterpriseÿ…...
CameraView录制时长控制终极指南:如何实现精确的视频时长限制
CameraView录制时长控制终极指南:如何实现精确的视频时长限制 【免费下载链接】CameraView 📸 A well documented, high-level Android interface that makes capturing pictures and videos easy, addressing all of the common issues and needs. Real…...
