首页 > 其他 > 详细

动态规划-LCS-LIS-离散化-1748. 最长公共子序列III

时间:2020-04-04 12:59:55      阅读:57      评论:0      收藏:0      [点我收藏+]

2020-04-04 12:18:00

问题描述:

给出1-n的两个排列P1和P2,求它们的最长公共子序列。请将复杂度控制在O(nlogn)。

样例

样例 1:

输入:[3,2,1,4,5],[1,2,3,4,5]
输出:3
解释:最长公共子序列为[1,4,5]。

样例 2:

输入:[6,9,4,2,8,1,3,5,7],[8,1,2,4,5,3,7,9,6]
输出:4
解释:最长公共子序列为[8,1,3,7]。

问题求解:

naive的LCS是O(n ^ 2)在本题中会卡时限。可以通过离散化的方式将原问题转为LIS问题,就可以在O(nlogn)求解。

时间复杂度:O(nlogn)

    public int longestCommonSubsequenceIII(int[] A, int[] B) {
        // Write your code here
        int n = A.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) map.put(A[i], i);
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = map.get(B[i]);
        return helper(nums);
    }
    
    private int helper(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        for (int num : nums) {
            int idx = ub(dp, num);
            dp[idx] = num;
        }
        return ub(dp, Integer.MAX_VALUE);
    }
    
    private int ub(int[] nums, int num) {
        int l = -1;
        int r = nums.length;
        while (r - l > 1) {
            int mid = l + (r - l) / 2;
            if (nums[mid] >= num) r = mid;
            else l = mid;
        }
        return r;
    }

  

 

动态规划-LCS-LIS-离散化-1748. 最长公共子序列III

原文:https://www.cnblogs.com/hyserendipity/p/12631234.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!