注册功能网站建设,网络营销课程培训机构,百度自然排名网站的logo怎么做,做京东网站的摘要LC1713. 得到子序列的最少操作次数 题目描述LIS 动态规划 二分法代码演示 题目描述 难度 - 困难 LC1713.得到子序列的最少操作次数 给你一个数组 target #xff0c;包含若干 互不相同 的整数#xff0c;以及另一个整数数组 arr #xff0c;arr 可能 包含重复元素。 每一次… LC1713. 得到子序列的最少操作次数 题目描述LIS 动态规划 二分法代码演示 题目描述 难度 - 困难 LC1713.得到子序列的最少操作次数 给你一个数组 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 10^5 1 target[i], arr[i] 10^9 target 不包含任何重复元素。 LIS 动态规划 二分法 为了方便我们令 target 长度为 narr 长度为 mtarget 和 arr 的最长公共子序列长度为 max不难发现最终答案为 n−max。 因此从题面来说这是一道最长公共子序列问题LCS。 但朴素求解 LCS 问题复杂度为 O(n∗m)使用状态定义「f[i][j] 为考虑 a 数组的前 i 个元素和 b 数组的前 j 个元素的最长公共子序列长度为多少」进行求解。 而本题的数据范围为 10^5使用朴素求解 LCS 的做法必然超时。 一个很显眼的切入点是 target 数组元素各不相同当 LCS 问题增加某些条件限制之后会存在一些很有趣的性质。 其中一个经典的性质就是当其中一个数组元素各不相同时最长公共子序列问题LCS可以转换为最长上升子序列问题LIS进行求解。同时最长上升子序列问题LIS存在使用「维护单调序列 二分」的贪心解法复杂度为 O(nlogn)。 因此本题可以通过「抽象成 LCS 问题」-「利用 target数组元素各不相同转换为 LIS 问题」-「使用 LIS 的贪心解法」做到 O(nlogn) 的复杂度。 朴素的 LIS 问题求解我们需要定义一个 f[i] 数组代表以 nums[i] 为结尾的最长上升子序列的长度为多少。 对于某个 f[i] 而言我们需要往回检查 [0,i−1] 区间内所有可以将 nums[i] 接到后面的位置 jjj在所有的 f[j]1中取最大值更新 f[i]。因此朴素的 LIS 问题复杂度是 O(n^2) 的。 LIS 的贪心解法则是维护一个额外 ggg 数组g[len]x 代表上升子序列长度为 lenlenlen 的上升子序列的「最小结尾元素」为 x。 整理一下我们总共有两个数组 f 动规数组与朴素 LIS 解法的动规数组含义一致。f[i]f[i]f[i] 代表以 nums[i] 为结尾的上升子序列的最大长度g 贪心数组g[len]x代表上升子序列长度为 len 的上升子序列的「最小结尾元素」为 x。 由于我们计算 f[i] 时需要找到满足 nums[j]nums[i]同时取得最大 f[j] 的位置 j。 我们期望通过 g 数组代替线性遍历。 显然如果 g 数组具有「单调递增」特性的话我们可以通过「二分」找到符合 g[idx]nums[i] 分割点 idxi下标最大即利用 O(logn) 复杂度找到最佳转移位置。 代码演示
class Solution {public int minOperations(int[] target , int[] arr) {MapInteger, Integer map new HashMap();int Tlen target.length, Alen arr.length;//1target的元素和对应下标 装入mapfor(int i 0; i Tlen; i) map.put(target[i], i);//2在arr中寻找相等的值的下标装入下标数组int[] index new int[Alen];int p 0;for(int i 0; i Alen; i){if(map.containsKey(arr[i])) index[p] map.get(arr[i]);}//3直接调用处理最长递增公共子串代码之前做过这里赋值过来偷懒int uplen lengthOfLIS(index,p);return Tlen - uplen;}public int lengthOfLIS(int[] nums,int n){if(n 0) return 0;int res 1;int[] dp new int[n];dp[0] nums[0];for(int num:nums){int i 0,j res;while(i j){int mid (i j)1;if(dp[mid] num) j mid;else i mid 1;}dp[i] num;if(j res) res;}return res;}}
