|
2021.7.26 每日一题非常好，所以单独发一个，前两个题是前置问题
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 。
提示：
1 <= text1.length, text2.length <= 1000
text1 和 text2 仅由小写英文字符组成。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-common-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
动态规划，f[i][j]表示两个字符串分别以i和j结尾的最长公共子序列长度
如果text1[i]和text[j]相同，那么长度就是f[i - 1][j - 1]+1
如果不相同，那么长度就是max(f[i-1][j], f[i][j-1])
我这里相同的情况写的更加严谨了一点，其实不这样写也是正确的，之前也简单分析过
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int l1 = text1.length();
int l2 = text2.length();
int[][] dp = new int[l1+ 1][l2 + 1];
for(int i = 1; i <= l1; i++){
for(int j = 1; j <= l2; j++){
if(text1.charAt(i - 1) == text2.charAt(j - 1)){
dp[i][j] = Math.max(dp[i - 1][j - 1] + 1,Math.max(dp[i][j - 1], dp[i - 1][j]));
}
else{
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
return dp[l1][l2];
}
}
300. 最长递增子序列
题目描述
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
提示：
1 <= nums.length <= 2500
-104 <= nums[i] <= 104
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
常规思路动规：
class Solution {
public int lengthOfLIS(int[] nums) {
int l = nums.length;
if(l == 0)
return 0;
int maxlen = 1;
int[] dp = new int[l];
dp[0] = 1;
for(int i = 1; i < l; i++){
int maxpart = 0;
for(int j = 0; j < i; j++){
if(nums[j] < nums[i])
maxpart = Math.max(dp[j], maxpart);
}
dp[i] = 1 + maxpart;
maxlen = Math.max(maxlen, dp[i]);
}
return maxlen;
}
}
要求复杂度为O(nlogn)，所以优化
考虑改变状态的定义：dp[i]定义为长度为 i 的最小的末尾元素
这样，dp这个数组就变的有序起来了，而思路就是尽可能的使递增的元素变小
那么，如何去维护这个数组呢，遍历原数组，如果大于末尾元素，说明能使递增序列继续加1
如果比末尾元素小，那么这个元素必然不可能使有序序列长度增加了，但是能使长度为 i 的序列末尾元素变小，
用二分法找到这个元素进行替换
这样，长度为 i 的最小末尾元素就确定下来了，而dp的长度就是最长递增序列的长度
class Solution {
public int lengthOfLIS(int[] nums) {
int l = nums.length;
int[] d = new int[l + 1];
int len = 1;
d[1] = nums[0];
for(int i = 1; i < l; i++){
if(nums[i] > d[len]){
d[++len] = nums[i];
}else{
int left = 1;
int right = len;
while(left < right){
int mid = (right - left) / 2 + left;
if(d[mid] < nums[i]){
left = mid + 1;
}else{
right = mid;
}
}
d[left] = nums[i];
}
}
return len;
}
}
1713. 得到子序列的最少操作次数
2021.7.26 每日一题
题目描述
给你一个数组 target ，包含若干 互不相同 的整数，以及另一个整数数组 arr ，arr 可能 包含重复元素。
每一次操作中，你可以在 arr 的任意位置插入任一整数。比方说，如果 arr = [1,4,1,2] ，那么你可以在中间添加 3 得到 [1,4,3,1,2] 。你可以在数组最开始或最后面添加整数。
请你返回 最少 操作次数，使得 target 成为 arr 的一个子序列。
一个数组的 子序列 指的是删除原数组的某些元素（可能一个元素都不删除），同时不改变其余元素的相对顺序得到的数组。比方说，[2,7,4] 是 [4,2,3,7,2,1,4] 的子序列（加粗元素），但 [2,4,2] 不是子序列。
示例 1：
输入：target = [5,1,3], arr = [9,4,2,3,4]
输出：2
解释：你可以添加 5 和 1 ，使得 arr 变为 [5,9,4,1,2,3,4] ，target 为 arr 的子序列。
示例 2：
输入：target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]
输出：3
提示：
1 <= target.length, arr.length <= 105
1 <= target[i], arr[i] <= 109
target 不包含任何重复元素。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-operations-to-make-a-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
第一反应，求最长公共子序列，动态规划，然后长度减去最长的公共子序列长度就是答案。然后去复习最长公共子序列，见上一题
但是这样写的话很明显超时了，那么怎么做呢
那么，根据提示target是互不相同的整数，可以将target中的整数存储在一个哈希表中
这样可以快速查找arr中是否有没有这个元素
然后如果这个元素在arr中存在的话，就把这个元素替换成它target中出现的下标，不存在的元素就去掉
因为需要按顺序出现，所以求替换后arr数组的最长上升子序列就可以了
然后再去复习最长上升子序列，因为我第一时间想到的求最长上升子序列的方法是动规，状态转移方程，就是dp[i] = 1 + dp[比i小的所有数字]中的最大值
但是动规的复杂度是n方，所以还是不行
那么继续优化，怎么操作才能使复杂度降下来
看到对数复杂度，首先想到二分，然后想到二分需要的条件，是排序的
那么怎么定义状态才能使其排序呢，看上面的题300. 最长递增子序列
定义d[i]为长度为 i 的递增子序列末尾元素的最小值
class Solution {
public int minOperations(int[] target, int[] arr) {
Map<Integer, Integer> map = new HashMap<>();
int m = target.length;
for(int i = 0; i < m; i++){
map.put(target[i], i);
}
List<Integer> list = new ArrayList<>();
int n = arr.length;
for(int i = 0; i < n; i++){
if(map.containsKey(arr[i])){
list.add(map.get(arr[i]));
}
}
int size = list.size();
if(size == 0)
return m;
int[] d = new int[size + 1];
int len = 1;
d[1] = list.get(0);
for(int i = 1; i < size; i++){
int num = list.get(i);
if(num > d[len]){
d[++len] = num;
}else{
int left = 1;
int right = len;
while(left < right){
int mid = (right - left) / 2 + left;
if(num > d[mid]){
left = mid + 1;
}else{
right = mid;
}
}
d[left] = num;
}
}
return m - len;
}
}
总结
这个题非常值得收藏，第一点，意识到这是一个求最长公共子序列的问题
第二点，看到target中互不相同四个字，想到能将arr数组中的对应元素变成下标
第三点，变成下标以后，意识到因为target中下标肯定是递增的，所以在arr中要找的就变成了了最长递增子序列
第四点，最长递增子序列常规做法动规，复杂度n方，要通过需要写nlogn的方法，然后再想到怎么构造一个可以递增的数组，用二分查找
环环相扣，层层递进，秒啊秒啊
|