最长数对链
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();
}
}